Intrusive Linked List Learning

[joydo]

• https://www.data-structures-in-practice.com/intrusive-linked-lists/

• https://llvm.org/doxygen/ilist_8h_source.html

• https://www.reddit.com/r/C_Programming/comments/d88ikx/intrusive_linked_lists_in_linux/

• https://news.ycombinator.com/item?id=13263038

• http://deepsea.inria.fr/chunkedseq/ This is for chunked sequences

[joydo]

Source from hacknews discussion :

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: 1） 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/ 2） HN submission on intrusive lists in Doom 3: https://news.ycombinator.com/item?id=8795745 3） 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-Technical-Note.pdf One of the optimizations was moving from intrusive lists. Conclusion: 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.