2

If you have a linked-list, where the items are not necessarily close to each other in memory, wondering if it is (in general) better/worse/no difference to do the following.

Say you want to iterate through the items 2 or 3 times. One solution is to just iterate through them each time, finding the pointers one at a time with right or next. Another solution is to create a local temporary array filled with pointers to the items, and iterate through that the second/third times. The values are still in their normal spot. A third solution is like the second but you also copy the values (say they are numbers not arbitrary strings). Perhaps there are other better alternatives. The thinking is that you would somehow take advantage of memory locality for caching. The lists can be as small as 1 item to as large as a few thousand. I am new to the memory stuff.

  • 1
    Have you proven that you have a locality-related bottleneck? What will happen to the cache after you've traversed the list once? – Blrfl Apr 29 '18 at 10:52
4

Caching effects are difficult to predict. In general, contiguous memory data structures like arrays of values are more cache friendly, but does this matter? Not for most code.

For the purpose of iteration over the pointed-to values, an array of pointers is very similar to a linked list which you traverse by pointer chasing. Note that arrays of objects in most OOP programming languages are arrays of pointers (e.g. Java, C#, Python, …), and their performance is generally fine.

While a linked list does not require that the list nodes are adjacent in memory, this can still often be the case. E.g. when using an arena allocator and/or when the list nodes were allocated in their iteration order at roughly the same time, they might have array-like cache behaviour. Any clever optimizations would then have all the overhead of many small copies, without noticeable gains.

So whether any clever optimization would make a noticeable difference can only be answered reliably by running a realistic benchmark. I once encountered a case where simplifying a collection for repeated iteration did make a big measurable difference, but that was in the absolute hot spot of a very computationally expensive program. Most programs do not have such hot spots where nanosecond-scale savings are multiplied into noticeable speedups.

Do prefer cache friendly data structures where easily possible, but quite often that is not possible. E.g. in C++, vector<T> is often “better” than a list<T>, but adding a new element to a vector can invalidate any pointers to elements. So if I need stable pointers, then memory locality be damned – I need a vector<unique_ptr<T>>or a list<T>. Also, lists can do many things that vectors cannot, e.g. O(1) removal or O(1) insertion at the front.

Correctness trumps performance. At scale, algorithmic complexity trumps cache effects.

0

In response to genuine hotspots, it can be a useful optimization at times to especially apply the third solution you proposed which creates a contiguous array of elements that are stored by value (ex: numbers, not variable-sized sub-sequences like strings), and more so if the resulting array doesn't need to store all the data of the original list (some fields might be irrelevant to subsequent usage).

For variable-sized subsequences it can be helpful sometimes too to transfer to a flat container, like std::vector<char>, with null terminators to terminate one string from the next if the subsequent and repetitive access patterns are sequential. That might not be as helpful these days now that strings use SBOs, but there was a time long ago at least where that was enormously helpful in my cases that involved repetitive UTF8 string processing to just flatten it all out to one giant array of characters.

That said, the cases where I benefitted from such optimizations did not traverse the linked structure (tree in our case) 2 or 3 times. It was more like 100+ times a second with the original data in the linked structure not changing very frequently at all (not invalidating the data cached into a contiguous array), and on top of that it enabled us to do things like SIMD processing with the resulting array as we repeatedly looped through it.

One the biggest examples I can recall where that sort of optimization was useful was a motion hierarchy evaluation. To compute the resulting matrices of child matrices down a hierarchy, we had to traverse the motion hierarchy (tree) in breadth/level-first order to transfer motions from parent to child. There, it was very helpful to frame rates to just grab an array of elements out of that level-first traversal and use that array sequentially instead of traversing the tree over and over every single frame. In that case the motion of the items was dynamic and frequently changing, but not the structure of the tree (very infrequently changed). And we did only do that after seeing hotspots and cache misses there in VTune.

Also as pointed out linked structures don't necessarily have to result in a loss of spatial locality. You can even write linked lists using arrays where the array elements just store like a next 32-bit index to skip to the next part of the array storing the next element, and use like -1 in place of a nullptr. Of course the next index for element 40 might might skip to the 35,000th position in the array if you start inserting and removing all over the place in the middle of the list, but then you can restore the spatial locality with a simple copying pass which traverses the original list using those links and then inserts to the new list in order (in which case all neighboring nodes would be right next to each other in memory/array in the new copy). I often use that rep these days as I find it far less cumbersome than having to deal with separate allocators like free lists; in general I don't like to deal with memory allocator and data structure as two separate things to deal with in usage if I can help it.

Finally I could imagine even a case where traversing the list one time to copy to array only to traverse the array one time might be beneficial if the work done per iteration is hefty and capable of being done in parallel. The array, with its random access, allows that loop to be parallelized, whereas the linked list traversal is serial in nature.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.