Comment by exDM69 | Hacker News Reader

Comment by exDM69 | Hacker News Reader

Parent Full thread

Yes, linked lists have terrible cache behavior and usually the performance of any packed structure with less pointer chasing should beat it. ArrayList, Vector, whatever you call it usually is faster.

But computers aren't fast in allocating memory. In particular, they're not predictably fast in allocating memory, as most allocators will have complex internal data structures and may end up having to call the operating system to give fresh pages of unused memory. The best case may be smoking fast, the amortized cost may be decent but the worst case is pretty bad.

So when reliable and predictable performance is needed, memory allocations are to be avoided. This is relevant if you're working on (soft) real time applications, say audio, games or so.

And linked lists are still mighty fast in addition and removal, joining and splitting. Intrusive linked lists drop one extra pointer chase.

In kernel space, there are tons of use cases for linked lists that are never traversed, or at least not traversed in the fast path. Traversal is the slow part, but that's not necessary for a lot of cases where you add something to a list or a set, and remove items one by one.

There's no other data structure that beats linked lists when there's only addition, removal, joins and splits, but no traversals. Linked lists are almost always the wrong data structure for the job, but in special niche cases (which are not that rare, at least in kernel space) it's the simplest and most effective.

> Intrusive linked lists drop one extra pointer chase.

Template-based lists (in the style of C++ STL) let you have your cake and eat it too in that you still keep the list structure out of your data, but you still get the cache locality of an intrusive list.

I think your typical template-based list is actually a bad example :P Maybe there's something about C++ I don't know, but typically those implementations only allow for adding one list node (via the template wrapping), and also they can't usually take an element from one list and then attach it to another one. Where-as intrusive implementations like the Linux Kernel's allow for any number of list nodes or other data structures to be placed alongside the data, and the elements can be moved onto any list you want without any allocations necessary.

std::list has splice to move nodes between lists.

boost.intrusive does, among other things, provide true intrusive lists and, for example, can insert the same node on multiple containers (not just lists) at the same time.

But really, no need for boost.intrusive, writing a templated intrusive list is not hard.

Once you do that though (use a "true" intrusive implementation), you typically lose the "keep the list structure out of your data" aspect. std::list allows you to avoid that, but carries its own limitations that embedding the list structures into the data does not.

Don't get me wrong, I'm not saying one is better or worse, just that containers like std::list aren't better for every use-case you might have compared to an intrusive implementation. Perhaps I just misunderstood your "have your cake in eat it too" remark though.

> So when reliable and predictable performance is needed, memory allocations are to be avoided. This is relevant if you're working on (soft) real time applications, say audio, games or so.

Surely LLs are a poor example of this because _every_ newly created element becomes an allocation? The PR in the GP only managed to significantly reduce allocations because it was a particularly niche case and the PR was accidentally cheating.

My understanding from friends in the worlds where allocation matters is they use a lot of statically sized arrays.

You don't need to couple the linked list nodes with your allocations. Either you make an array of link structs or embed your links in the stored struct (intrusive linked list).

The linux kernel uses intrusive linked lists (and intrusive rbtrees) a lot. They are the perfect data structure for a lot of uses where performance matters and allocations are a no go.

You still need to allocate a node for each addition to the LL for the stored struct, unless you pre-allocate a set of them, and at that point you very likely are better off using a static array.

The linux kernel LL implementation uses kmalloc (i.e. it performs allocations) - although they get to dodge some of the problems of userspace allocators by using their own.

You can easily see by searching for 'kmalloc' (or 'malloc') at https://github.com/torvalds/linux/blob/master/include/linux/... that it does no such thing.

Here's the logic for adding a list node:

    /*
     * Insert a new entry between two known consecutive entries.
     *
     * This is only for internal list manipulation where we know
     * the prev/next entries already!
     */
    static inline void __list_add(struct list_head *new,
                                  struct list_head *prev,
                                  struct list_head *next)
    {
            if (!__list_add_valid(new, prev, next))
                    return;

            next->prev = new;
            new->next = next;
            new->prev = prev;
            WRITE_ONCE(prev->next, new);
    }

No allocation, just mutating some fields in preexisting list_head structures. Those are by convention stored as a field in whatever struct needs to be kept in the list, which is what 'intrusive' means.

And where do you think that "new" comes from? I guess my phrasing is poor so I should have been clearer: elements in kernel LLs generally came from a kmalloc, even though the LL functions don't use a malloc themselves.

Yes, preallocation was what I was referring to. The other strategy is what Linux does, embedding the links to the stored struct.

Static arrays are poor at joining, splitting, removal and merging.

> Static arrays are poor at joining, splitting, removal and merging.

True, but these are relatively rare requirements for a data container. My point isn't that LLs are totally useless but it seems like they'll see relatively little use if the goal is "no allocations at all".

Intrusive linked lists don't need any allocations.

Merging (in the sense of retaining some order property) is probably just as fast in static arrays as in lists. For large element sizes, you'd use an array of pointers (requiring only one pointer per element in the data, doubling during the merge) and the pointer fiddling during the merge is about the same for either. For small elements, the list overhead alone is probably enough to make arrays faster.

O(1) joining, splitting and removal are of course not beatable by contiguous data structures.

LLs are often used to manage fixed sized object pools. So yes, statically sized arrays, but with pointers between the elements acting as linked lists.

Reply on news.ycombinator.com