8 ms·
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
by geocar 10y ago
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.
- DanWaterworth 10y agoYou 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.
- geocar 10y agoNo, 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.
- DanWaterworth 10y agoI don't know how the kernel is using intrusive lists, but that kind of traversing and switching is occasionally useful.
- geocar 10y agoYes. 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.
- DanWaterworth 10y agoWhen 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).
- scott_s 10y agoIs this your understanding from intuition, or are you aware of kernel developers who have made this same argument?
- geocar 10y agoNot 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-19way&num=1 http://www.phoronix.com/scan.php?page=article&item=linux-44-... [2]: https://lkml.org/lkml/2016/8/1/164 https://lkml.org/lkml/2016/8/1/164 [3]: https://lkml.org/lkml/2008/4/1/458 https://lkml.org/lkml/2008/4/1/458
- scott_s 10y agoYou 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).
- cjwoodall 10y agoLinked-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
- HelloNurse 10y agoAn 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.
- dom0 10y ago> 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.
- scott_s 10y agoFile 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.
- IgorPartola 10y agoReally? Even huge volumes with loads of tiny files? Mail and Usenet servers? Build servers? What is your definition of large and modest here?
- 10y ago