Hacker News Reader

Comment by jbandela1 | Hacker News Reader

In my experience, the linked lists that are useful are intrusive linked lists where the data you care about has a next/previous embedded pointer as opposed to an just storing an arbitrary object inside a linked list.

One example would be if your thread structure has these embedded pointers, you can easily add/remove a thread to a linked list of threads waiting for some resource without any allocation just by pointer manipulation.

View on HN

This is a very useful pattern when you have small collections of large objects, where the vector/array implementation starts to fall flat on its face. Kernels and high-performance servers use these a lot for state tracking.

If you combine intrusive linking with a pool allocator, you can have decent locality too.

That's absolutely right, but it's not just large objects. Any situation where you follow links rarely compared to your other memory accesses then the cache performance of links becomes negligible and the benefit of simplicity and O(1) operations can shine. Vectors for scrubbing through things without changing their structure, lists and trees the opposite.

Scrubbing through things quickly is empirically more common, hence the standard advice to use vectors by default.

Or how about an object that can't easily be relocated like, you know, a stack for a kernel thread which also contains the task struct and needs to be moved around between different scheduler queues.

But yeah, I understand they took the task struct out of the kernel stack now.

Edit: difficult being an understatement, you'd need to solve the halting problem to be able to rewrite any self-referential pointers to stack objects wherever they may be.

The other benefit of this kind of data structure is the ability for one object to participate in multiple collections. Otherwise you would have to do some kind of hash map structure to point to them.

Isn't that the opposite, though? If you store the next/prev pointers in the data structure itself, you can't use the same object in multiple collections.

If you have a standalone linked list data structure, then you can, as long as you have a good means of tracking the lifetime of the data itself.

Typically you keep a list entry in the struct: https://man7.org/linux/man-pages/man3/stailq.3.html#EXAMPLES

The same list entry can be moved between several lists using the same type.

If the struct need to be in multiple lists in the same time you can keep multiple list entries in the same struct: https://github.com/freebsd/freebsd-src/blob/69413598d2660054...

This is a very popolar use case inside kernels implementations.

FWIW, I recently implemented a safe Rust crate around the Windows variant of intrusive linked lists [1] and spoke about it at EuroRust [2].

I did it only for compatibility and would still prefer vectors whenever I can use them. Nevertheless, I put some efforts into coming up with a useful and high-performing implementation. To give an example: My `append` function is O(1) and not a poor O(N) version that you rightfully criticized in your tweet.

[1] https://colinfinck.de/posts/nt-list-windows-linked-lists-in-... [2] https://www.youtube.com/watch?v=IxhZIyXOIw8

I know it’s splitting hairs but doesn’t that mean the structure is, indeed, a linked list? A structure can be two things at once.

Reply on news.ycombinator.com