One thing that I've always wondered was why it seems like most cache line mappings seem to collide at powers of two -- since so much software uses power of two sized buffers, it seems like it would be a big win to bucket by some non power of two size.
The point of having less-than-fully-associative cache is that it is both cheaper and faster than fully-associative one. Using some kind of complex mapping would require significant additional circuitry, which would certainly introduce significant additional delay (or even additional clock cycle).
I'm not saying that the cache should be fully associative, I'm saying that instead of each bucket being a power of two, make it a prime number -- eg, 67 byte cache lines instead of 64, for example, seem to me like they would prevent quite a bit of aliasing with common data sizes.
There would be more circuitry to divide the addresses. I haven't done too much with hardware (only some light FPGA experience), so I don't know how much extra, but it doesn't feel like it would be prohibitive. I could be wrong.
(If you're aware of someone doing analysis on that, I'd be curious to see it -- I haven't seen any.)
Computer architecture researchers have been working at this for a long time. Here's a recent paper on a technique to do the division and modulus operations for arbitrary numbers of cache banks and set sizes.
What I meant is that making the cache fully-associative would result in faster implementation than N-way associative with non-power-of-2 cache line size or bucket count because of the additional circuitry involved in selecting right bucket (integer modulus and so on).
Interesting trick is using different values for cache index and tag (logical address for index and physical address as tag is common, but that's mostly about doing cache lookup concurrently with TLB lookup). In theory one could use result of some hash function as index, which would certainly change the aliasing behavior (although it is not exactly certain that such change would be for the better) and again, there is the additional cost of calculating said hash function (in combinatorial logic and with reasonably small delay).
Correction: Division by arbitrary integer valued variables are the slowest integer operations.
You can accomplish division by a constant / modulus by a constant without a full division, however. For example, (x == x % 256 - x * 256), mod 257. That sort of thing.
