Hacker News Reader

Comment by ernst_klim | Hacker News Reader

It's pretty useful, just not as a "sequential container" as people are usually taught. And definitely now with an interface C++ provides. There are two main cases for linked lists:

  1. When you need a persistent version of sequential data structure. I.e. you need addition not to change the previous version of list. Very useful in traversals which can fail and/or have multiple routes. C++ list obviously fails here because it's a mutable data structure and each addition is mutation. The proper interface is cons(head, old_list) -> new_list, where old_list exists after new_list is constructed.

  2. When you need the values be never moved in memory. Aka intrusive lists. Can be optimized for more cache friendliness by having lists of big chunks of values instead of just lists in some cases. Useful in operating systems and many low level apps. Alternative is usually a vector of pointers which still gives you indirection.

View on HN

I'm not sure I follow the second point. Array-based solutions are able to guarantee that an element is never relocated, it's just that std::vector doesn't offer this guarantee. The Boost libraries offer this though, they call it stable_vector.

https://www.boost.org/doc/libs/1_92_0/doc/html/container/non...

> Array-based solutions are able to guarantee that an element is never relocated

This is an array of pointers, I mentioned it in the post you're replying to. It completely obliterates the "cache-friendliness" argument, making it worse than linked list (now you have same indirection overhead plus overhead of copying minus benefits of being able to CAS your value atomically into a list making it lock-free)

Yes you're right. Here's an alternative that behaves the way I had in mind but doesn't support deletions, as handling deletions the way std::vector does would naturally mean relocating elements. [0]

I figure it would be possible to add support for deletions, but it would cost us: we would lose guaranteed contiguous placement of elements with neighbouring indices, and (unless no deletions are made) we'd need a private data structure to correspond vector indices to addresses, and to determine where to locate new elements. This would of course bring us back to continually paying the price of indirection overhead, and simple lock-free modifications would not be possible.

My completely unsupported guess is the cache behaviour wouldn't be too bad unless deletions (of elements that aren't at the end of the vector) are common. I imagine the cache behaviour of a linked list must depend greatly on what the allocator gives you. Presumably using a pool, specific to that particular list, could help there.

[0] https://github.com/david-grs/stable_vector

Arrays of pointers are more cache-friendly than linked lists because the pointers can all be traversed in parallel.

Vector of pointers almost always wins for immovable elements. Copying the whole vector is usually better than making a persistent linked list too.

> Vector of pointers almost always wins

In what way? It's the same thing with additional overhead on copying the vector when adding/removing elements.

Not to mention you can have a lock-free intrusive list, and with vector well, you just can't.

> Copying the whole vector is usually better

With linked list you don't need to copy anything when you add/remove.

I suspect that the performance advantage of allowing the CPU to cache-prefetch many pointers at once (vs. having to follow a pointer to get the next pointer, in the case of the linked list) still makes a vector of pointers better than a linked list for sequential traversal.

Reply on news.ycombinator.com