Linux Kernel 对 TCP 使用链表，对进程调度使用 RB 树。
就算法效率而言，这些是有道理的。您将一次获得一堆数据包，因此在列表末尾插入 O(1) 很好。
对于进程调度，完全公平调度器使用红黑树，用 O(1) 的时间来选择任务。
据我所知，这些都不是以“平面”方式实现的——链表是一堆节点，带有指向其他节点的指针，就像树一样。这意味着据我所知，这些结构的局部性应该很差。
据我所知，缓存局部性通常比算法效率更重要。
Linux 所针对的数据集是否存在某些问题，使得这些结构的算法效率超过其他结构的缓存效率？
我是不是误会了什么？有人介绍过吗？
最佳答案
关于链表的使用，我有部分答案，相信你会在this page about the CFS scheduler中找到一些有趣的信息。 ，特别是它提到了红黑树如何为插入、搜索和删除等操作提供良好的最坏情况时间，这对于调度程序来说确实是一个非常理想的属性。
我敢打赌，是的，内核已经进行了大量分析，而且这些数据结构似乎在现实世界中表现良好。
This blog post有一些关于内核链表使用的很好的数据。这些数据显然是在 3 天的正常使用中通过保持每次操作完成的计数器而收集的。
+--------------------+-----------+
| Operation | Frequency |
+--------------------+-----------+
| Empty Test | 45% |
| Delete | 25% |
| Add | 23% |
| Iterate Start | 3.5% |
| Iterate Next | 2.5% |
| Replace | 0.76% |
| Other Manipulation | 0.0072% |
+--------------------+-----------+
如您所见，实际访问元素的操作只占总数的 6%，而插入和删除加起来几乎占一半。这是一个链表开始变得更有意义的用例。请注意，数据是在整个内核中收集的，而不是专门针对 TCP 代码，因此每次使用链表的理由可能并不相同，但汇总数据确实表明这些选择总体上是明智的。
我认为同样重要的是要记住，内核的设计必须能够从最小的嵌入式设备扩展到处理大量数据的 super 计算机，此时算法效率可能开始严重超过缓存问题。
关于c - 为什么 Linux 内核使用它所使用的数据结构？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28818557/