Comment by scott_s | Hacker News Reader

Comment by scott_s | Hacker News Reader

Parent Full thread

The Linux kernel uses intrusive linked lists extensively. Container based linked lists contain a copy of the data item. Intrusive linked lists force the data structures in the list to contain list pointers inside of the actual data structure, and the list operations manipulate those list-specific pointers in the data structure.

I am not sure if anyone has evaluated using alternatives, but my understanding of why has generally been memory efficiency. If you allocate a Foo, you also allocate everything you need for Foo to be on all of the lists it may appear on. I couldn't find any confirmation (with actual numbers) for this intuition, but this is what I could find:

A 2005 explanation of how intrusive lists work in the Linux kernel: "Linux Kernel Linked List Explained", https://isis.poly.edu/kulesh/stuff/src/klist/

HN submission on intrusive lists in Doom 3: https://news.ycombinator.com/item?id=8795745

And that points to technical note on the optimizations to Doom 3's BFG Edition to get it to perform well on PS3, XBox 360 and PC: http://fabiensanglard.net/doom3_documentation/DOOM-3-BFG-Tec... One of the optimizations was moving from intrusive lists.

I'm quite aware of how inappropriate linked lists are for most applications because of their poor cache locality. I thought the Linux kernel may be a case where linked lists are actually better, but I can't find any numbers or even arguments why they would be.

Linux uses linked lists because it is simple to code. That linked lists are slow doesn't matter very much because there are lots of slow parts in Linux that are a better use of attention.

Doom moved to vectors (arrays) because linked lists are slow, and because there wasn't enough other slow parts that needed attention.

You can't necessarily replace intrusive linked lists with arrays. They have more operations. You can traverse so far in one list then switch to traversing in another.

No, but you also don't have to do that.

One list is traversed when committing blocks, so a linked list was never necessary - just a commit-list (vector of pointers).

Another list is traversed when dequeueing the next lock, so again: a linked list isn't necessary, just a dequeue (which might not have to be serialised).

Another list is traversed when finding the next blocked reader, but again serialisation wasn't required here.

And so on.

I don't know how the kernel is using intrusive lists, but that kind of traversing and switching is occasionally useful.

Yes. It is occasionally useful.

However when you have the right data structure, you'll find you won't need it.

Benchmarking is important because searching for the right data structure is time consuming (expensive for the programmer) and it's usually not necessary.

When you need that kind of behaviour, you can't replace it with something flat (without doing binary searches or similiar at each crossing). Sometimes intrusive lists are the right thing.

I built something once that used intrusive skiplists because it needed to expire elements using one ordering and search them by another. It would have been much less efficient if I'd have broken it up into multiple flat representations.

(Actually, it was flat, but explaining that aspect of it is quite difficult).

Is this your understanding from intuition, or are you aware of kernel developers who have made this same argument?

Not sure exactly what you're asking.

We can evaluate the Linux kernel developers' priorities by benchmarking[1] and assuming they aren't stupid, because if they are stupid, then their opinion doesn't matter, and if they're not and they're not making things faster, then it's because they have other priorities.

That being said, there are a few[2] notable[3] moves away from linked lists that were ostensibly for performance reasons.

[1]: Even crap benchmarks: http://www.phoronix.com/scan.php?page=article&item=linux-44-...

[2]: https://lkml.org/lkml/2016/8/1/164

[3]: https://lkml.org/lkml/2008/4/1/458

You provided a reason for why the kernel does a certain thing (easier to code; performance in those places doesn't matter). I was asking if this was your understanding based on inference (your understanding of the performance trade offs in general combined with the fact things are done a certain way) or from fact (claims made directly by kernel developers, or experiments).

Linked-Lists often get used in low-level code and embedded systems in situations where you might need multiple statically allocated entries to be turned into a list of unknown length. There certainly are times where this comes in useful, but it is also a memory constrained space with an emphasis on determinism, where malloc and new can be bad ideas.

There is a time and a place for them, but if you need speed I agree... there are better solutions

An OS kernel has no business maintaining, and even less business accessing in bulk, large data structures that are performance-critical enough to worry about coherent memory access. It is also an infrastructure-deprived environment in which swapping around pointers to implement a linked list with correct locking is relatively easy to get right but allocating vectors is out of the question.

> An OS kernel has no business maintaining, and even less business accessing in bulk, large data structures that are performance-critical enough to worry about coherent memory access

File systems are usually part of the kernel.

File systems tend not to have large data structures. They are relatively modest data structures which manage bulk access to large blocks of data. A subtle distinction, but important in this context.

Really? Even huge volumes with loads of tiny files? Mail and Usenet servers? Build servers? What is your definition of large and modest here?

The data structures under discussion here are those used to track individual files. Yes, there can be squillions of them, but as data structures, they are, in fact, rather modest.

> memory efficiency. If you allocate a Foo, you also allocate everything you need for Foo to be on all of the lists it may appear on.

I can't speak for the kernel developers, but for the same line of reasoning it may be more significant that there is the lack of error paths.

When you allocate an 'object', further changes of state (eg. added or removal to other lists) in its lifetime can be done without the possibility of running out of memory or address space. This can be a huge benefit to overall program structure in certain types of application.

In contrast, addition or removal to a vector or flat list can ultimately require various actions to happen.

Reply on news.ycombinator.com