3 ms·
Lock-Free Data Structures: Yet Another Treatise
- fmstephe 12y agoA fun article. But, it seems odd to me that almost all of the focus in lock free queues are unbounded linked-list based implementations. Unbounded size is usually undesirable in production systems. It's a fine property to have sometimes, but I would always default to a bounded queue. When a consumer is overwhelmed the producer must experience push-back. Linked lists produce prodigious garbage. If you really are pushing the performance shown here, 10 million per second, that is a lot of garbage to collect, even if it all dies in Eden space. Linked list based implementations are extremely complex. My first lock-free queue implementation was based on Java's ConcurrentLinkedQueue. It was a monumental headache, and I didn't quite complete it. Compare that to a (admittedly single-consumer,single-producer) array based queue and the explanation is fairly straightforward, by comparison. You can extend the single-consumer, single-producer to multi/multi fairly easily and still be able to explain how it works to most programmers. (all written in Go) I am sort of confused by the amount of attention these complex linked-list based queues get in the write-ups. If the intention is to introduce lock-free techniques and concepts then I think the array based queues are much better. If you want the best performance with low garbage and predictable latency I would expect arrays to win almost always. Very happy to be proved wrong here. The best collection of write-ups on lock-free array backed queues is here http://psy-lob-saw.blogspot.co.uk/p/lock-free-queues.html http://psy-lob-saw.blogspot.co.uk/p/lock-free-queues.html My code to back it up :) The queues I have built are based on work by Martin Thomson (of disruptor fame) https://github.com/fmstephe/flib/tree/master/queues/spscq https://github.com/fmstephe/flib/tree/master/queues/spscq
- fmstephe 12y agoNitsan Wakart gave two presentations about lock free queues. https://skillsmatter.com/legacy_profile/nitsan-wakart#skillscasts https://skillsmatter.com/legacy_profile/nitsan-wakart#skills... I gave a talk on simple versions of those queues in London. https://skillsmatter.com/skillscasts/6163-high-performance-single-producer-single-consumer-in-memory-queue https://skillsmatter.com/skillscasts/6163-high-performance-s...
- amelius 12y agoThese type of data structures seem to me as the perfect case for formal proof systems. They are (almost) too complicated to understand for a human, yet sufficiently simple (I guess) for formal tools to deal with. I'm still waiting for a tutorial that will teach me to use both :)