Hacker News Reader

Comment by Matthias247 | Hacker News Reader

Not only avoiding the cache miss. It's also avoiding an allocation. The non-intrusive list that the parent described means the list node requires one allocation, and the content another. Intrusive lists mean there's just one allocation required for the actual element - and hooking it into a list comes for free.

If the struct we want to insert is on the stack we don't even need a single allocation. That is for example be useful on wait nodes, where we put some waiter object on the stack, register it in a shared wait queue, and then wait until the object gets signalled => No allocation is required for any waiter.

View on HN

Yes. I would caution on inserting stack objects into shared lists, though, because it's such an easy footgun if the reference outlives the stack frame.

It's not really worse than heap allocated objects. For them you also need to make sure the pointer in the list does not outlive the actual object.

The only safe structures are heap allocated plus reference counted ones, where inserting something into a list also increments the refcount.

I think you're completely correct, in a pedantic sense. However, heap object lifetimes aren't bound to control flow in quite the same way.

You could allocate a single novel struct containing the structure of interest and any number of list elements that will contain it in a single malloc().

If the lists don’t need to know about each other, each novel struct could be different.

This would work, but it’s a bit exotic, so I’m not recommending it. But it addresses the locality and multiple allocation issues.

isn't that exactly equivalent to an intrusive linked list in memory except harder to implement?

Not quite. With traditional intrusive linked lists, you'll have to modify the payload struct whenever you want to add it to another or different lists; with OP's approach, maybe not (but it depends on the implementation details).

Reply on news.ycombinator.com