Re:In Defense of Linked Lists
by CalChris on Saturday November 05, 2022 @12:08AM
(#33477848)
If your list is short then you won't have a problem. But if your list is long then traversing it can be a major problem.
For example, if your list item is page aligned like the task_struct in the Linux kernel, rescheduling the next process could traverse the process list. The process list links will be at the same page offset and associate with a restricted set of the L1/L2/L3 caches lines and thrash from memory. Worse, the TLB will thrash as well. This was actually the case for Linux until about 2000.
For example, if your list item is page aligned like the task_struct in the Linux kernel, rescheduling the next process could traverse the process list. The process list links will be at the same page offset and associate with a restricted set of the L1/L2/L3 caches lines and thrash from memory. Worse, the TLB will thrash as well. This was actually the case for Linux until about 2000.
https://www.usenix.org/legacy/publications/library/proceedin...