3 ms·

Rust prevents races but not deadlocks, which is one of the bigger problems in multithreaded GUI code.

sillysaurus3 11y ago
Locks turn out to be unnecessary for multithreaded code. A ringbuffer of messages is only slightly more complex, yet the gains are massive. Both in performance and simplicity. It's possible to manage a ringbuffer without any locks. The trick is to have a counter for the producer thread, and a counter for each consumer thread. Whenever the producer wants to know "Is it safe to add a message?" it takes the minimum of all consumer counters, modulo the size of the ringbuffer. The result is the smallest index that the producer must not write beyond. In other words, you always know when you're producing messages too quickly and need to wait on the consumers. And the consumers know when there's a message waiting -- they just look at the producer's counter. Blazingly fast, and no locks. Cool trick!
- jpgvm 11y ago
  One can probably argue it's not even more complex at all. Locks just look simple because it's "just chuck a mutex around it", in reality though it's all a mirage. Locks are comfortable, not simple - is how I like to put it at least.
- 885895 11y ago
  I would like to read more about what you described here. Know of any good articles or open source projects where this is done?
  - fmstephe 11y ago
    If you like Go I have written a ringbuffer library here https://github.com/fmstephe/flib https://github.com/fmstephe/flib have a look in queues/spscq. spsc here stands for single producer, single consumer. I gave a talk in London about these queues here https://skillsmatter.com/skillscasts/6163-high-performance-single-producer-single-consumer-in-memory-queue https://skillsmatter.com/skillscasts/6163-high-performance-s... ------------------- But all of this work is based on the work, and teaching, of Martin Thomson. Martin Thomson has published a large collection of data structures (which probably include these ringbuffers (I haven't checked specifically)) https://github.com/real-logic/Agrona https://github.com/real-logic/Agrona If you are near Ireland I highly recommend Martin Thomson's concurrency course http://instil.co/courses/writing-concurrent-code-with-lock-free-algorithms/ http://instil.co/courses/writing-concurrent-code-with-lock-f... ---------- I highly recommend Nitsan Wakart's blog. He covers a lot of interesting ground, all in Java. Probably best to start at the early blog posts and work your way forward. http://psy-lob-saw.blogspot.co.uk/ http://psy-lob-saw.blogspot.co.uk/ Nitsan contributes to a very focused java library here https://github.com/JCTools/JCTools https://github.com/JCTools/JCTools
  - ryanjshaw 11y ago
    Why: https://github.com/LMAX-Exchange/disruptor/wiki/Blogs-And-Articles https://github.com/LMAX-Exchange/disruptor/wiki/Blogs-And-Ar... Java: https://lmax-exchange.github.io/disruptor/ https://lmax-exchange.github.io/disruptor/ .NET: https://github.com/disruptor-net/Disruptor-net https://github.com/disruptor-net/Disruptor-net
  - btown 11y ago
    There are multiple ways to make a lock-free ringbuffer; most use some sort of similar trick with per-consumer atomic counters, though I hadn't heard of something as simple as the minimum-modulo trick described in the gp! Some implementations: http://mechanitis.blogspot.com/2011/07/dissecting-disruptor-writing-to-ring.html http://mechanitis.blogspot.com/2011/07/dissecting-disruptor-... http://www.boost.org/doc/libs/1_59_0/doc/html/boost/lockfree/queue.html http://www.boost.org/doc/libs/1_59_0/doc/html/boost/lockfree... - hard to find implementation details though http://moodycamel.com/blog/2014/a-fast-general-purpose-lock-free-queue-for-c++ http://moodycamel.com/blog/2014/a-fast-general-purpose-lock-... (uses per-producer counters instead, and relaxes some ordering guarantees; see comments)
- pron 11y ago
  Ringbuffers (or any queue, actually) don't solve the problems associated with locks. Often when people talk about locks when discussing concurrent algorithms, they don't necessarily mean the particular construct called a lock but any synchronization mechanism that might end up suspending some computation when waiting for another to happen, so a queue may well be a lock in this kind of discussion. To see the duality between locks and queues note that any queue can be implemented with any list/array and a lock, and a lock itself is nothing more than some atomic operation, plus a queue plus a mechanism to suspend computation. Whether that suspension involves an actual parking of the kernel thread or spinning, is an implementation detail from the perspective of the algorithm. You can use queues without deadlocks, but then you won't have the same advantages locks can give you (transactions), or you can have the same advantages, but then get the same problems.

Locks turn out to be unnecessary for multithreaded code. A ringbuffer of messages is only slightly more complex, yet the gains are massive. Both in performance and simplicity. It's possible to manage a ringbuffer without any locks. The trick is to have a counter for the producer thread, and a counter for each consumer thread. Whenever the producer wants to know "Is it safe to add a message?" it takes the minimum of all consumer counters, modulo the size of the ringbuffer. The result is the smallest index that the producer must not write beyond. In other words, you always know when you're producing messages too quickly and need to wait on the consumers. And the consumers know when there's a message waiting -- they just look at the producer's counter. Blazingly fast, and no locks. Cool trick!

jpgvm 11y ago
One can probably argue it's not even more complex at all. Locks just look simple because it's "just chuck a mutex around it", in reality though it's all a mirage. Locks are comfortable, not simple - is how I like to put it at least.
885895 11y ago
I would like to read more about what you described here. Know of any good articles or open source projects where this is done?
- fmstephe 11y ago
  If you like Go I have written a ringbuffer library here https://github.com/fmstephe/flib https://github.com/fmstephe/flib have a look in queues/spscq. spsc here stands for single producer, single consumer. I gave a talk in London about these queues here https://skillsmatter.com/skillscasts/6163-high-performance-single-producer-single-consumer-in-memory-queue https://skillsmatter.com/skillscasts/6163-high-performance-s... ------------------- But all of this work is based on the work, and teaching, of Martin Thomson. Martin Thomson has published a large collection of data structures (which probably include these ringbuffers (I haven't checked specifically)) https://github.com/real-logic/Agrona https://github.com/real-logic/Agrona If you are near Ireland I highly recommend Martin Thomson's concurrency course http://instil.co/courses/writing-concurrent-code-with-lock-free-algorithms/ http://instil.co/courses/writing-concurrent-code-with-lock-f... ---------- I highly recommend Nitsan Wakart's blog. He covers a lot of interesting ground, all in Java. Probably best to start at the early blog posts and work your way forward. http://psy-lob-saw.blogspot.co.uk/ http://psy-lob-saw.blogspot.co.uk/ Nitsan contributes to a very focused java library here https://github.com/JCTools/JCTools https://github.com/JCTools/JCTools
- ryanjshaw 11y ago
  Why: https://github.com/LMAX-Exchange/disruptor/wiki/Blogs-And-Articles https://github.com/LMAX-Exchange/disruptor/wiki/Blogs-And-Ar... Java: https://lmax-exchange.github.io/disruptor/ https://lmax-exchange.github.io/disruptor/ .NET: https://github.com/disruptor-net/Disruptor-net https://github.com/disruptor-net/Disruptor-net
- btown 11y ago
  There are multiple ways to make a lock-free ringbuffer; most use some sort of similar trick with per-consumer atomic counters, though I hadn't heard of something as simple as the minimum-modulo trick described in the gp! Some implementations: http://mechanitis.blogspot.com/2011/07/dissecting-disruptor-writing-to-ring.html http://mechanitis.blogspot.com/2011/07/dissecting-disruptor-... http://www.boost.org/doc/libs/1_59_0/doc/html/boost/lockfree/queue.html http://www.boost.org/doc/libs/1_59_0/doc/html/boost/lockfree... - hard to find implementation details though http://moodycamel.com/blog/2014/a-fast-general-purpose-lock-free-queue-for-c++ http://moodycamel.com/blog/2014/a-fast-general-purpose-lock-... (uses per-producer counters instead, and relaxes some ordering guarantees; see comments)
pron 11y ago
Ringbuffers (or any queue, actually) don't solve the problems associated with locks. Often when people talk about locks when discussing concurrent algorithms, they don't necessarily mean the particular construct called a lock but any synchronization mechanism that might end up suspending some computation when waiting for another to happen, so a queue may well be a lock in this kind of discussion. To see the duality between locks and queues note that any queue can be implemented with any list/array and a lock, and a lock itself is nothing more than some atomic operation, plus a queue plus a mechanism to suspend computation. Whether that suspension involves an actual parking of the kernel thread or spinning, is an implementation detail from the perspective of the algorithm. You can use queues without deadlocks, but then you won't have the same advantages locks can give you (transactions), or you can have the same advantages, but then get the same problems.