3 ms·
If you have a pointer to an element of a doubly liked list, you can always remove it in a few processor cycles. You can also always add or remove from the end o
by colonwqbang 4y ago
If you have a pointer to an element of a doubly liked list, you can always remove it in a few processor cycles. You can also always add or remove from the end of front of the list in a few cycles.
This means that you can do those things under a spin lock or with interrupts masked. You cannot really resize a dynamic array under a tight spinlock, or modify a tree that should be kept balanced.
Another use case is free lists, a list of preallocated structures where you can grab one or put one back quickly under spinlock.
These are some examples of how lists are used in kernel land.
- pornel 4y agoI'm not saying there are no uses. Concurrent lock-free algorithms are an especially useful case, and a e.g. linked list of on-stack mutex waiters is a very clever approach that I don't think has a better replacement. But I doubt that lists are as common as they are because every place really needs them. Vecdeque can cheaply pop/push front and end too. Arrays have swap-remove. You may not need to grow if you preallocated a capacity. Freelists can be a stack, or you can choose a data structure that doesn't allocate objects individually so you don't need the freelist in the first place. Another thing that is C-specific is that most objects are treated as unmovable and their address is their permanent identity. Without language features for prevention of dangling pointers, moves are asking for trouble. This favors linked lists and pointery data structures over contiguous containers and inlined data.