Hacker News Reader

Comment by damienkatz | Hacker News Reader

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

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!

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.

I would like to read more about what you described here. Know of any good articles or open source projects where this is done?

If you like Go I have written a ringbuffer library here

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-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

If you are near Ireland I highly recommend Martin Thomson's concurrency course

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/

Nitsan contributes to a very focused java library here

https://github.com/JCTools/JCTools

Why: https://github.com/LMAX-Exchange/disruptor/wiki/Blogs-And-Ar...

Java: https://lmax-exchange.github.io/disruptor/

.NET: https://github.com/disruptor-net/Disruptor-net

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-...

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-... (uses per-producer counters instead, and relaxes some ordering guarantees; see comments)

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.

Reply on news.ycombinator.com