7 ms·
Doubly-linked lists -all data structures that have back pointers- are really difficult to mutate thread-safely.
by cryptonector 14d ago
Doubly-linked lists -all data structures that have back pointers- are really difficult to mutate thread-safely.
- max_k 13d agoDifficult compared to what? Mutating a std::vector is much more difficult because you need a coarse lock and serialize every access with it - there's no other option. Linked lists, on the other hand, can be made thread-safe with a single coarse lock, or many finer-grained locks, or atomics, or fancier tricks like RCU. All of that is difficult, sure, but what is less difficult than thread-safe linked lists?
- cryptonector 8d agoDifficult to do thread-safely and lock-less-ly. An atomic compare-and-swap operation can be used to build lock-less, thread-safe singly-linked list. Doing that for doubly-linked lists is harder.