[vvanders]

Solid stuff, glad to see someone testing my assumptions :).

If there's one thing I could teach new CS-grads it's how much your memory access patterns(and cache) really-effing-matter. Everything else is almost noise in comparison.

[sanderjd]

I'm pretty curious about this: have memory access patterns and cache awareness become more of a big deal in the past decade or so, or has it only recently reached my awareness? I studied CS in the early 2000s and while I was aware of various trade-offs between contiguous and linked data structures, it's only in the last few years that the importance of cache (and non-"system" languages' widespread flouting of its importance) has really bubbled up in my consciousness.

It's certainly likely that I just didn't take the right kinds of classes, or that I did but just missed or failed to really internalize this, but I'm curious if something else is going on. Has the bottleneck increasingly become memory rather than CPU? Have we more thoroughly exhausted other areas of optimization?

I was thinking about this while watching a talk[0] given by someone from Google about data structures in the STL, which decried that the standardized specification for `std::unordered_map` more or less forces an implementation to use buckets instead of the more cache-friendly technique of probing. I'm sure that the people who standardized it were very competent, which makes me think that, at least at the time, buckets were thought to be the better implementation.

[0]: https://www.youtube.com/watch?v=fHNmRkzxHWs

Edit: Added video link.

[blt]

> Has the bottleneck increasingly become memory rather than CPU?

Yes.

Besides the basic memory latency vs. CPU clock speed issue, there's also:

- CPU caches have gotten bigger, so the payoff of making an program cache-friendly is larger

- CPUs have gained SIMD vector ALUs and increased superscalar behavior, so the CPU is capable of processing more data in per clock cycle

- A cultural shift happened after the freewheeling Moore's Law era ended in the mid-2000s, and people started examining performance more closely

http://gec.di.uminho.pt/discip/minf/ac0102/1000gap_proc-mem_...

[sanderjd]

Thanks, this is what I had suspected, but it seems to be left unstated in everything I've read.