3 ms·
This is not good advice if you need your list to have unbounded size and want it to be lock-free. Growing an array and copying all the elements over is very exp
by pcwalton 14y ago
This is not good advice if you need your list to have unbounded size and want it to be lock-free. Growing an array and copying all the elements over is very expensive in a thread-safe scenario. If you use a linked list, however, you can implement all the operations without using any locks at all.
(Linked lists are what we use for our channels in Rust, and as a result they're extremely fast: in the new scheduler they're totally lock-free except if the task is sleeping, which we can optimize to be lock-free later. They have unlimited size, which helps prevent deadlocks.)
- gosu 14y agoVery cool. What kind of lockfree linked lists? Did you work from one of the papers on the subject? (Searching "rust lockfree" reveals a feature request for a lockfree malloc. I happen to have one of those, but the reality is that synchronization will probably not be your bottleneck.)