3 ms·

Both Redis and Linux are C projects, and in C it's customary to roll your own containers. Without generics, and with a culture of avoiding small dependencies, i

by pornel 4y ago

Both Redis and Linux are C projects, and in C it's customary to roll your own containers. Without generics, and with a culture of avoiding small dependencies, it's preferred to roll your own simple list than to reach for more advanced reusable data structures. So I don't think it's a particularly enlightened decision by these projects to use so many lists on their merit, but rather a programming pattern especially common in the C language they use.

scottlamb 4y ago
Meh, that's true of some C projects, but AFAIK Linux/Redis have good reasons here, and if I were to criticize Linux for something, it wouldn't be unwillingness to write more code. I still prefer to evaluate each decision on its merits. Linux has made some great decisions. Also some terrible ones—e.g. fsync semantics [1], attitude to fuzzing. Redis probably has too. They can agree on something and be wrong. [1] https://wiki.postgresql.org/wiki/Fsync_Errors https://wiki.postgresql.org/wiki/Fsync_Errors
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 ago
  I'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.

by pornel 4y ago

scottlamb 4y ago

Meh, that's true of some C projects, but AFAIK Linux/Redis have good reasons here, and if I were to criticize Linux for something, it wouldn't be unwillingness to write more code. I still prefer to evaluate each decision on its merits. Linux has made some great decisions. Also some terrible ones—e.g. fsync semantics [1], attitude to fuzzing. Redis probably has too. They can agree on something and be wrong. [1] https://wiki.postgresql.org/wiki/Fsync_Errors https://wiki.postgresql.org/wiki/Fsync_Errors

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 ago
I'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.