Is Go's buffered channel lockless?

Question

Go's buffered channel is essentially a thread-safe FIFO queue. (See Is it possible to use Go's buffered channel as a thread-safe queue?)

I am wondering how it's implemented. Is it lock-free like described in Is there such a thing as a lockless queue for multiple read or write threads??

greping in Go's src directory (grep -r Lock .|grep chan) gives following output:

./pkg/runtime/chan.c:   Lock;
./pkg/runtime/chan_test.go: m.Lock()
./pkg/runtime/chan_test.go: m.Lock() // wait
./pkg/sync/cond.go: L Locker // held while observing or changing the condition

Doesn't to be locking on my machine (MacOS, intel x86_64) though. Is there any official resource to validate this?

Milklivered

Answer 1

If you read the runtime·chansend function in chan.c, you will see that runtime·lock is called before the check to see if the channel is buffered if(c->dataqsiz > 0).

In other words, buffered channels (and all channels in general) use locks.

The reason your search did not find it was you were looking for "Lock" with a capital L. The lock function used for channels is a non-exported C function in the runtime.

Bangs

Thanks! Any ideas about why it isn't implemented as lock-free? – Milklivered

"Lockfree" does not imply better performance. It is also easier to reason about locks. The Lock method is probably faster when there is high contention. – Bangs

Thanks, @stephen-weinberg . That makes more sense now. – Milklivered

Answer 2

You can write lock-free (and even wait-free!) implementations for everything you like. Modern hardware primitives like CMPXCHG are enough to be universally usable. But writing and verifying such algorithms isn't one of the easiest tasks. In addition to that, much faster algorithms might exists: lock free algorithms are just a very small subset of algorithms in general.

As far as I remember, Dmitry Vyukov has written a lock-free MPMC (mutli-producer/multi-consumer) channel implementation for Go in the past, but the patch was abandoned, because of some problems with Go's select statement. Supporting this statement efficiently seems to be really hard.

The main goal of Go's channel type is however, to provide a high-level concurrency primitive that is easily usable for a broad range of problems. Even developers who aren't experts at concurrent programming should be able to write correct programs that can be easily reviewed and maintained in larger software projects. If you are interested in squeezing out every last bit of performance, you would have to write a specialized queue implementation that suits your needs.

Camarata