Linux内核使用TCP的链表和RB树进行进程调度.
就算法效率而言,这些都是有意义的.你将一次收到一堆数据包,所以在列表末尾的O(1)插入很好.
通过进程调度,Completely Fair Scheduler使用红黑树,有O(1)时间来选择任务.
据我所知,这些都不是以"平面"方式实现的 - 链表是一堆节点,指向其他节点,就像树一样.这意味着,据我所知,这些结构的位置应该很差.
从我所看到的缓存局部性往往超过算法效率.
是否有关于Linux编程的数据集的某些内容使得这些结构的算法效率超过了其他结构的缓存效率？
我误会了什么吗？有人描述过吗？