Comment by philsnow
5 years ago
You can also force-align (with padding if necessary) your structures to be along whatever boundaries make sense for your processor's cache lines.
Ensuring an oft-loaded structure always fits inside a single cache line (instead of splaying across ~1.9 cache lines on average) is good not only for fitting lots of those structures into your L1 but for not blowing out cache bandwidth (read _and_ write, if you're modifying them).
It's much more difficult to prefetch them, though - if you're traversing a large list it misses the cache every time, rather than just the first element.
(someone please correct me if I'm wrong)
That's right. The reason why you see linked lists so much in old C stuff is (IMO) similar to the reason you see null terminated strings (and the associated bugs if you truncate incorrectly). And that's because of one of C's original sin: the failure to include size information in array objects.
There is also the claim that linked lists are better in certain types of performance sensitive code because you can sometimes avoid allocating. I don't fully understand the logic there myself but I trust that there are cases where this is true.
The actual reason why you see linked lists (and similar pointer-chasing data structures) so much in old code is because the entire problem of slow-vs-fast memory accesses didn't exist back then. Memory access always happened in a fixed and very low number of CPU cycles (the entire RAM essentially had L1 cache performance). The cpu-memory-gap only slowly started to widen during the 90's when CPU frequencies started to skyrocket and caches had to be added to CPUs. Unfortunately this problem still isn't as widely recognized as it should be in high-level programming circles even today.
1 reply →
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).
A linked list also avoids copying the entire array when you need to insert more elements than you have allocated space for.
15 replies →