Hacker News Reader

Comment by exDM69 | Hacker News Reader

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.

View on HN

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.

Reply on news.ycombinator.com