You say not very often, but the true usefulness is almost never. Extremely little. One in a trillion times. Even when you think linked lists would be faster, they usually aren't.

Naturally the mind races to think of where linked lists are used.

The Linux kernel uses them, at least some of the time they're used with their lock-free RCU pattern. I'm not sure if it's for performance reasons though, I think they're using it in contexts where correctness requires the absence of blocking operations.

I'd expect a lock-free non-linked-list solution would also be possible, but I don't know enough to state that definitively.

https://docs.kernel.org/RCU/listRCU.html

Linux is definitely a mix of "It's a linked list because multiple CPUs are simultaneously doing swap operations on the list while it is still in use, with linked lists that's an atomic operation whereas if we did something else it would need a lock" and "C does not provide a growable array type, so I used a linked list 'cos that's easy to write in C"

My guess for the 0.x releases in particular is that there's a lot of the latter and as Linux goes from "Like Minix but I made it in my bedroom" to Serious Business™ more and more of the former.

> My guess for the 0.x releases in particular is that there's a lot of the latter and as Linux goes from "Like Minix but I made it in my bedroom" to Serious Business™ more and more of the former.

In the early releases of Linux, the cache locality argument wasn't as prominent an issue on the hardware of the day. So the computer science textbook argument of O(1) inserts and [if you have the node pointer already] removals was more compelling.

Allocation and deallocation are fairly expensive with or without modern caches though, surely?

Or are pools used to avoid that?

I'm not sure I can answer that about their malloc, now and in the past.

But your question reminded me of another aspect of linked lists in the Linux kernel: unlike a lot of high level languages, there isn't an extra allocation for a node structure. The node structure is a member of the structure being linked.

Often the structure being linked might be something like a reference counted heap object, so the question of adding an extra member to store the next pointer is not a big difference.

IIRC Linux looks pretty much everything.

Well not explicitly, but it uses a version of malloc that has a pool for every rounded object size.

Linux uses linked lists because they can reserve a fixed amount of memory for the linked list cells inside the element itself (intrusive list) and they can be allocated non-continguously aka you can freely extend them as you like. This is useful if you want to reserve a chunk of memory statically. This guarantees that you can do work before your allocator is online and then when the allocator is online, you can transparently extend your memory with further allocations.

You can also take independent modules that provide their own statically allocated memory and chain them together using the reserved linked list cells. (think kernel modules)

This is a bit of a wishy washy explanation because I work on a highly adjacent project that has similar constraints but I never looked at the kernel source (strictly working with statically allocated memory during startup).

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.

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.

> One in a trillion times.

This is wildly overstating it. Yeah, I agree, they're much less often the right choice compared to a good-ol' growable array, but they have lots of uses in high-performance code and concurrent code, and they're building blocks in lots of other data structures. Like, in a bucket hash-table, the buckets are linked lists, in a LRU cache you interleave a hash table and linked list, std::hive is a linked list of chunks of elements, etc. Anything that has ever had to deal with memory pooling/allocation uses free-lists which are linked lists. And on and on and on.