2 ms·
This article offers a list of the very few occasions when a linked list is actually the correct data structure including: > You're doing some awesome lock-free
by tialaramex 5y ago
This article offers a list of the very few occasions when a linked list is actually the correct data structure including:
> You're doing some awesome lock-free concurrent thing.
Here's an actual example of an "awesome lock-free concurrent thing" that indeed needs linked lists, Jon Gjengset re-implementing (most of) Folly's Hazard Pointers but in Rust and he eventually checks they work correctly and have decent performance:
https://www.youtube.com/playlist?list=PLqbS7AVVErFgO7RUIC6lhd0UekFMbjJzb https://www.youtube.com/playlist?list=PLqbS7AVVErFgO7RUIC6lh...
Unlike the "too many linked list" stuff this is not a Rust tutorial and you should not try to learn Rust by following how this is done. But if you know Rust pretty well it's a pretty interesting watch. This is definitely past the point where safe Rust is enough to get work done. Rust has no idea why hazard pointers could be OK, so Jon will be responsible for delivering Rust's fabled safety in his implementation any time he needs to write "unsafe" - or else everything catches fire. I think it might also be interesting for C++ programmers who know how Folly's Hazard Pointers work and would like to just see what Rust looks like when used on real problems rather than starting with Hello World and the Fibonacci numbers.