The Pros of Conds

Ah, sync.Cond, the black sheep of the sync package. In the entire Go corpus, sync.Cond is only used in 42 packages—less than sync.Once, less than sync.Pool, less than even atomic.CompareAndSwap! Well, what the heck is a sync.Cond? How do you use it? And why would you use it, when we already have channels and mutexes?

If I had to summarize sync.Cond in one sentence: A channel says “here’s a specific event that occurred;” a sync.Cond says "something happened, idk, you go figure it out." Thus, sync.Cond is more vague—which means it’s also more flexible. It’s kind of like a chan struct{} paired with a sync.Mutex: after you receive from the channel, you lock the mutex, then go investigate what happened.

Another way to look at sync.Cond is as a “smart busy-wait.” Imagine you have a goroutine that needs to wait until at least 100 users are logged in, and then give a prize to the first 10. The dumbest way to do that would be something like:

for {
    mu.Lock()
    if len(users) >= 100 {
        givePrizes(users[:10])
        mu.Unlock()
        return
    }
    mu.Unlock()
}

This is terrible because the loop is constantly burning CPU time to lock and unlock the mutex over and over and over. More precisely, it’s terrible because the condition is checked far more frequently than it actually changes. In a loop like this, the value of len(users) might be checked millions of times before changing once!

It would be much better if we could somehow sleep until len(users) changed, and then wake up and check our condition. Well, we can accomplish that with a chan struct{} and a bit of “cooperative multitasking:” after unlocking the mutex, our loop can block on <-ch, and whenever a goroutine modifies users, it can perform a non-blocking send, e.g.:

mu.Lock()
users = append(users, newUser)
mu.Unlock()
select {
case ch <- struct{}{}:
default:
}

So a bit more ceremony is required, but now our loop is far more efficient: it will only check len(users) when it changes, i.e. 100 times instead of millions–great!

sync.Cond encapsulates this pattern. With sync.Cond, we would write our example like so:

cond.L.Lock()
for len(users) < 100 {
    cond.Wait()
}
givePrizes(users[:10])
cond.L.Unlock()

// in some other goroutine:
cond.L.Lock()
users = append(users, newUser)
cond.L.Unlock()
cond.Signal()

Internally, cond.Wait unlocks the mutex (L), sleeps until awoken by a call to Signal, then re-locks the mutex before returning.

Now, this is an improvement, but it’s still far from ideal, right? Wouldn’t it be more efficient if we could sleep until our condition was exactly true? Well, firstly, bear in mind that the cost of a wakeup is on the order of a few dozen nanoseconds—not something to be overly concerned with. But more importantly, in order to wakeup at precisely the right time, we’d have to move the conditional logic to the sender: “if condition is true, then wake up sleeping goroutine.” Oftentimes this is fine, but in some cases it can conflict with the proper separation of concerns. In such situations, you may find yourself thinking: “But foo shouldn’t have to know what condition bar is waiting on.” That’s a sign that a sync.Cond may be warranted.

Another unique strength of sync.Cond is its Broadcast method. Imagine we have multiple goroutines, all waiting on different conditions. Rather than call Signal once per goroutine (which would be racy anyway), we can call Broadcast to simultaneously wake all sleeping goroutines. This is analogous to calling close on a channel—except that Broadcast can be called multiple times, whereas calling close twice will result in a panic. So perhaps that’s another rule of thumb: if you find yourself thinking “gee, I wish I could close this channel more than once,” consider using a sync.Cond.

A good example of where Broadcast is handy is to signal cancellation or shutdown. When the user hits Ctrl-C, we need all our goroutines to exit; thus, our code needs to “select” on two conditions:

cond.L.Lock()
for len(users) < 100 && !shutdown {
    cond.Wait()
}
if shutdown {
    cond.L.Unlock()
    return
}
givePrizes(users[:10])
cond.L.Unlock()

Now, when it’s time to clean up, we can set shutdown = true and call cond.Broadcast(). All of the sleeping goroutines will wakeup, observe the condition, and exit.

It hopefully goes without saying that sync.Cond, like any other concurrency primitive, is prone to deadlocks. If you forget to unlock the mutex—deadlock. If you don’t call Signal or Broadcast after changing the condition variable—deadlock. If you use Signal where you should have used Broadcast—believe it or not, deadlock. I don’t have a ton of experience debugging these deadlocks, so the only tip I can offer is to try spawning a goroutine that just calls cond.Broadcast() in an infinite loop. If that fixes the deadlock, it means you’re failing to call cond.Signal() or cond.Broadcast() somewhere. If it doesn’t, it means that your conditions are never being satisfied.

By the way, sync.Cond is not novel to Go; it’s simply Go’s implementation of a monitor. In fact, if you read up on monitors, you’ll see that the method names xof sync.Cond, as well as the names of internal runtime functions that it calls, are all lifted straight from the original source. (That original source, by the way, is Tony Hoare—the same guy who came up with CSP, which is what Go’s entire concurrency model is based on.)

Lastly: What is sync.Cond used for in the real world? Well, I looked at those 42 packages in the Go corpus, and I’ll be honest, most of them aren’t great. Their usage of sync.Cond isn’t incorrect, per se, but a channel would probably work just as well or better. I did find at least two good examples, though: an in-memory pipe, and a connection multiplexer. If you squint a bit, these are both solving roughly the same problem: simulating a connection with byte buffers. There’s no underlying syscall to block on, so we need to “artificially” block until data is available. And since we’re simulating a connection, we also need to support I/O deadlines and closing. I don’t doubt that it’s possible to implement this using channels, but in my experience, sync.Cond is a better fit. (For comparison, io.Pipe is implemented with three channels, three mutexes, and a sync.Once—and even with all that, it doesn’t support deadlines!)

Okay, that’s all I’ve got for you. Hopefully sync.Cond is a bit less mysterious now, but please don’t rush off and find a way to shoehorn it into whatever project you’re currently working on; it’s probably not the best tool for the job! Just keep it in your toolbox, so it’ll be at your disposal when you truly need it.

Appendix A: Implementing sync.Cond with channels

Most Go programmers are comfortable with channels, so this may make sync.Cond easier to grasp. We implement Wait with a receive, Signal with a non-blocking send, and Broadcast with a close, using a mutex to “refresh” the channel after each close:

type Cond struct {
    L  sync.Mutex // used by caller
    mu sync.Mutex // guards ch
    ch chan struct{}
}

func (c *Cond) Wait() {
    c.mu.Lock()
    ch := c.ch
    c.mu.Unlock()
    c.L.Unlock()
    <-ch
    c.L.Lock()
}

func (c *Cond) Signal() {
    c.mu.Lock()
    defer c.mu.Unlock()
    select {
    case c.ch <- struct{}{}:
    default:
    }
}

func (c *Cond) Broadcast() {
    c.mu.Lock()
    defer c.mu.Unlock()
    close(c.ch)
    c.ch = make(chan struct{})
}

In my microbenchmarks, this performs 2-5x worse than the real sync.Cond, which is actually better than I expected! Performance-wise, its main failing is that each Broadcast call incurs an allocation. To be honest, I’m kind of surprised that the runtime has such deep support for sync.Cond, given that the performance delta isn’t huge and sync.Cond is very rarely used.

Appendix B: Implementing a fancy channel with sync.Cond

Channels are pretty great, but there are two features that would be nice to have: dynamic capacity, and a “peek” function. We can use sync.Cond to implement a channel-ish…thing…with these features, although of course it won’t be compatible with select, which makes it kinda useless.

type IntChan struct {
    queue  []int
    closed bool
    cond   sync.Cond
}

func (ch *IntChan) Send(x int) {
    ch.cond.L.Lock()
    defer ch.cond.L.Unlock()
    ch.queue = append(ch.queue, x)
    ch.cond.Broadcast()
}

func (ch *IntChan) Close() {
    ch.cond.L.Lock()
    defer ch.cond.L.Unlock()
    ch.closed = true
    ch.cond.Broadcast()
}

func (ch *IntChan) Receive() (int, bool) {
    ch.cond.L.Lock()
    defer ch.cond.L.Unlock()
    for len(ch.queue) == 0 && !ch.closed {
        ch.cond.Wait()
    }
    if len(ch.queue) > 0 {
        x := ch.queue[0]
        ch.queue = ch.queue[1:]
        return x, true
    }
    return 0, false
}

func (ch *IntChan) Peek() (int, bool) {
    ch.cond.L.Lock()
    defer ch.cond.L.Unlock()
    if len(ch.queue) > 0 {
        return ch.queue[0], true
    }
    return 0, false
}

By the way, sync.Cond has a constructor (sync.NewCond), but I almost never use it; sync.Cond{L: new(sync.Mutex)} is more direct, and gives you a value rather than a pointer.

Appendix C: Runtime implementation of sync.Cond

Like much of the sync package, the implementation sync.Cond is tightly coupled to the runtime. Consequently, the actual source is extremely short (comments and copy-checking omitted):

type Cond struct {
    L      Locker
    notify notifyList
}

func (c *Cond) Wait() {
    t := runtime_notifyListAdd(&c.notify)
    c.L.Unlock()
    runtime_notifyListWait(&c.notify, t)
    c.L.Lock()
}

func (c *Cond) Signal()    { runtime_notifyListNotifyOne(&c.notify) }
func (c *Cond) Broadcast() { runtime_notifyListNotifyAll(&c.notify) }

The real meat is in the notifyList type and its accompanying functions, which can be found in runtime/sema.go. A notifyList is basically just two integers (wait and notify) and a linked list of goroutines. notifyListAdd increments wait and returns it; that’s t, our “ticket.” Then, notifyListWait sets the current goroutine’s ticket to t, adds it to the linked list, and sleeps. On the other side of the equation, we have notifyListNotifyOne (i.e. Signal) and notifyListNotifyAll (i.e. Broadcast). Starting with the latter—because it’s simpler—notifyListNotifyAll sets notify equal to wait, then walks the linked list, waking up all of the goroutines. notifyListNotifyOne, by contrast, increments notify by one, and searches the linked list for a goroutine whose ticket matches the previous value of notify. If it finds such a goroutine, it wakes it and removes it from the list; otherwise, it no-ops (much like a non-blocking channel send). Thus, the “ticket system” of wait and notify ensures that goroutines are awoken fairly, i.e. on a first-come, first-serve basis, while also allowing all goroutines to be awoken simultaneously. It also allows a goroutine to skip the sleep-wake sequence entirely if “it’s number has already been called.”

Appendix D: Concurrency primitives in the Go corpus

There are 7406 packages in the Go corpus. I grepped for various functions and types from the sync and atomic packages to determine their relative frequency in “real-world” code. Note that sync.Map does not appear here; the Go corpus predates it. Similarly, the low usage of atomic.Value might be due to its relatively late introduction—it was added to the standard library just two years before the corpus was compiled.

Type Packages
sync.Mutex 812
sync.WaitGroup 446
sync.RWMutex 413
atomic.Add 230
sync.Once 212
atomic.Load 178
atomic.Store 118
sync.Pool 84
atomic.CompareAndSwap 50
sync.Cond 42
atomic.Value 11
atomic.Swap 11