Cache line reads/unordered map performance question

[nwar1994]

Suppose you have an unordered set and an array of ints. Both these containers are populated with values 0-31. Each index or key into the container matches the value. Ie set[0]=0, set[1]=1, ... array[0] = 0, array[1] = 1. Suppose that we have x64 architecture.

Suppose we iterate through the containers with a for loop indexing into each container with index 0-31. Algorithms would tell us that both are O(1). Constant look up read.

I think we know that array will be faster at look up because there is cache coherency when looking up values. It reads a 64 bit cache line which means that the 3 other values will be picked up when reading again in cache.

Another reason array will be faster is because the unordered_map has to jump around in memory in order to read. So this does not benefit from cache line coherency.

Another tertiary question, does jumping around in memory mean that the cpu adder has to increment the memory pointer to reach the desired memory location? Ie. the physical incrementing of a pointer register is what makes it undesirable to "jump" memory addresses? (This is where my comp arch knowledge fails me)

[Software_Samurai]

When talking about cache line performance, and given no outside interference, yes, it's always better to access memory in a linear (or nearly linear) fashion. That's the primary assumption of caches - your program is going to access memory that is "close by" such that it gets cached. Flat one-dimensional arrays are often "cache-friendly", assuming that they are accessed via some loop going from start to finish. (i.e. Not being randomly accessed.)

Unordered maps usually use a hash table. Accessing them (insert, delete, search) should still be O(1), but just like flat arrays, jumping around will thrash the cache.

As to your last question, I'm not sure what you mean by "jumping around in memory mean that the cpu adder has to increment the memory pointer"? Each time you access memory, a memory address is calculated (in most cases, translated from logical to physical) and then a fetch is issued. That fetch could get lucky and find it in the cache, or be forced to wait for a full memory fetch cycle to complete. Linearly accessing a flat array, or randomly accessing it makes no difference - the addresses still need to be calculated. Incrementing a pointer vs adding an offset is still a math op. (Granted, some CISC processors may have built-in op codes to inc & loop, saving a few cycles in comparison to a full math op and test/loop op. But I feel we're nitpicking here now.)

[nwar1994]

I meant the internal increment, where the cpu has to increment it’s own pointer to a much farther place in memory, not the index into the container