Linux 为何偏爱 Intrusive Linked Lists？
Intrusive Linked Lists 将链表节点直接嵌入对象内部，省去了额外的内存分配开销。这种设计在 Linux 内核中无处不在，从内存管理到进程调度，都依赖它来减少缓存抖动并提升效率。文章深入解析了 Linux 如何利用 Circular Doubly Linked Lists 管理 task_struct，展示了如何通过指针运算从节点反推父对象地址。对于追求极致性能的系统开发者而言，理解这种数据结构是掌握 Linux 内核运作机制的关键一步。
使用 Intrusive Linked Lists 意味着内存分配次数减少了一半，从而降低了内存分配失败的风险。
HN 评论区
61- el_pollo_diablo
这篇文章在侵入式数据结构的优势上比原文走得更远，以链表为例：
正如文章所述，侵入式数据结构自然地减少了一次间接寻址。若要在传统链表（链表节点拥有载荷）中实现同样的效果，每种载荷类型都需要一个不同的节点类型。在拥有完善的单态化泛型支持时，这很容易实现，参见 C++ 的 std::list。但在 C 语言中这很别扭，因为实现必须通过宏生成。C 语言天然倾向于通过 void *进行间接寻址，这使得侵入式链表更具吸引力。
侵入式数据结构的另一个优势是能够将一个载荷链接到多个并行集合中，而无需间接寻址（传统集合则要求例如一个集合拥有载荷，而其他集合仅持有非拥有权的指针）。
最后但同样重要的是，侵入式数据结构的定义性特征是它将元素分配的责任留给了用户。元素可以分配在堆上、栈上、全局数组中（如文章中的 "initholes"）、特殊区域（arena）等。甚至使用非统一的分配策略也是合理的；例如，对于循环链表，可以将锚节点分配在栈上，而其他节点（嵌入在载荷中的节点）分配在堆上。
- pclmulqdq
我很惊讶，侵入式链接的主要优势竟然只是作为附带一提：即在不复制的情况下，在列表之间（以及列表内部）移动数据的能力。此外，假设你在其他地方持有对象的指针，你还可以实现 O(1) 复杂度的中间节点移除。因此，当你拥有大型状态结构体且不进行大量列表扫描时，侵入式链接比使用像 vector 这样的紧凑结构快得多。
- flohofwoe
嗯，挺有意思，这里展示的双向链表似乎缺少了 AmigaOS 中那个优雅的“重叠列表头”技巧（至少我是第一次在那里见到）：
例如，AmigaOS 的列表节点看起来很常规，它有两个指针，一个指向下一个节点（succ），一个指向上一个节点（pred）：
struct Node {
struct Node* ln_Succ;
struct Node* ln_Pred;
};
大多数 AmigaOS 结构体在开头嵌入了这样一个 Node 结构体。
……但列表头有三个指针，它们基本上构成了两个重叠的 Node 结构体：
struct List {
struct Node* lh_Head;
struct Node* lh_Tail;
struct Node* lh_TailPred;
};
在空列表中，lh_Head 指向 &lh_Tail，而 lh_TailPred 指向 &lh_Head。lh_Tail 指针始终为 null（这是“结束标记”）。
在已填充的列表中，lh_Head 指向第一个列表节点中嵌入的 Node 结构体，而 lh_TailPred 指向最后一个列表节点中嵌入的 Node 结构体。最后一个节点的 ln_Succ 指针指向列表头的 lh_Tail 指针的地址（……该地址始终为 null）。
这样，你只需要一个现有的节点指针就可以向前或向后遍历，或者插入/移除节点。当你顺着 succ 或 pred 指针遍历列表时，遇到 null 指针就知道到达末尾了。
显然，文章中提到的 Linux 风格链表需要知道列表头的地址来检测是否到达末尾，而 Amiga 风格的列表则不需要（代价是 […]
- cryptonector
双向链表——所有带有反向指针的数据结构——真的很难做到线程安全地修改。
- eventualcomp
服务员，服务员！再来点没有基准测试的优化文章，谢谢！