Re:Stop Using Linked Lists
by rayiner on Wednesday May 22, 2013 @05:37PM
(#5753921)
As I've said elsewhere, there are linked lists buried in key operations of the kernel. E.g. the O(1) scheduler's core data structure was an array of linked lists (www.cis.ksu.edu/~gud/docs/ppt/scheduler.pdf). There was one list per priority level, and tasks were queued/removed from the lists at each scheduler tick. The current scheduler (CFS) uses an RB-tree. Virtual memory areas are tracked using vm_area_struct structures organized in a sorted linked list (http://lxr.free-electrons.com/source/include/linux/mm_types....). They're used in the futex implementation (http://lxr.free-electrons.com/source/kernel/futex.c#L467, the kernel's internal memory allocators (http://lxr.free-electrons.com/source/mm/slab.c), and extensively in the network stack.
[ Parent
| on HN ]
Those links are of little value to the current discussion. If you took the performance profile, you'd find that the primary reason linked lists are used in those scenarios is because the performance worst case for linked lists occurs rarely. Which means the choice of datastructure is irrelavant w.r.t performance in those cases.