code::dive conference 2014 - Scott Meyers: Cpu Caches and Why You Care

> If your primary operation is inserting at a random location in the list, linked lists are faster than arrays at large sizes. You avoid having to move all the memory after the index you are modifying (to make space for the inserted element). This is false. Big O notation says it should be true, you'll get marked wrong if you say arrays are faster in your algorithms & data structures final, but when you're running on actual hardware the array is faster at all sizes of n and as n becomes larger so does the gap in performance. Here is a talk[0] by Bjarne Stroustrop (Creator of C++) that even includes imaginary graphs demonstrating this phenomenon. If you want a visual for what the missing graph was supposed to look like, here's a similar one.[1] Here's another video[2] by Scott Meyers (Author of Effective C++) that goes into more detail about why this happens. [0]: [link] [1]: [link] [2]: [this video]

I don't buy this. [this video] Prefetching in CPUs predates this talk. [link] That talk is 2018. Cache prefetching works best for linear accesses like with a vector, not for random pointer lookups. Prefetchers are also going to have an extra harder time with double indirection since they're unable to see which value is going to be fed to the lea. Prefetching is also expensive in and of itself, the CPU doesn't do it unless you're already incurring cache hits. This makes cache misses even worse . There are also multiple prefetchers in the CPU and the L1 prefetcher is very basic and is only going to help with contiguous accesses. Your allocator might be doing some nice things for you that let the one of the L2 prefetchers help, I would expect that you'll see better L2 performance due to prefetching. If you have an example of a linked list being as fast as a vector for iteration, please do show it.