Waiting on an indeterminate number of goroutines

Question

I have code where a single goroutine will fire off an indeterminate number of child goroutines, which in turn will fire off more goroutines, etc. My goal is to wait for all of the child goroutines to finish.

I do not know the total number of goroutines I will be firing off in advance, so I cannot use a sync.WaitGroup, and ideally I wouldn't have to artificially limit the total number of goroutines running via the channel-as-semaphore pattern.

Briefly I thought of having a local channel or waitgroup in each goroutine that serves as a semaphore to wait for all its children, but that results in each goroutine hanging around consuming stack space while all of its decendants finish.

Right now my idea is to increment an atomic counter when a goroutine is fired off (in the parent, to avoid spuriously hitting zero if the child starts running after the parent finishes), decrement it when a goroutine finishes, and periodically check whether it's equal to zero.

Am I basically on the right track, or is there a more elegant solution?

Answer 1

I wrote the first implementation of sync.WaitGroup, and this and other edge cases were well supported. Since then the implementation has been improved by Dmitry, and given his track record I bet he's only made it safer.

In particular, you can trust that if there is currently one or more blocked Wait calls, and you then call Add with a positive delta before you call Done, you won't unblock any of the previously existent Wait calls.

So you can definitely do this, for example:

var wg sync.WaitGroup
wg.Add(1)
go func() {
    wg.Add(1)
    go func() {
        wg.Done()
    }()
    wg.Done()
}()
wg.Wait()

I'm actually using equivalent logic in production since the code was first integrated.

As a reference, this internal comment was put in place in the first implementation, and is still there:

// WaitGroup creates a new semaphore each time the old semaphore
// is released. This is to avoid the following race:
//
// G1: Add(1)
// G1: go G2()
// G1: Wait() // Context switch after Unlock() and before Semacquire().
// G2: Done() // Release semaphore: sema == 1, waiters == 0. G1 doesn't run yet.
// G3: Wait() // Finds counter == 0, waiters == 0, doesn't block.
// G3: Add(1) // Makes counter == 1, waiters == 0.
// G3: go G4()
// G3: Wait() // G1 still hasn't run, G3 finds sema == 1, unblocked! Bug.

This is describing a different race condition to keep in mind while touching the implementation, but note that even there G1 is doing the Add(1) + go f() pattern while racing with G3.

I understand your question, though, as there is indeed a confusing statement in the documentation that has been put there recently, but let's look at the history of the comment to see what it is actually addressing.

The comment was put there by Russ, in revision 15683:

(...)
+// Note that calls with positive delta must happen before the call to Wait,
+// or else Wait may wait for too small a group. Typically this means the calls
+// to Add should execute before the statement creating the goroutine or
+// other event to be waited for. See the WaitGroup example.
func (wg *WaitGroup) Add(delta int) {

The log comment from Russ states:

sync: add caution about where to call (*WaitGroup).Add

Fixes issue 4762.

If we read issue 4762, we find:

It may be worth adding an explicit comment in the documentation for sync.WaitGroup that the call to Add should be done before launching the go routine containing the call to Done.

So the documentation is in fact warning against code like this:

var wg sync.WaitGroup
wg.Add(1)
go func() {
    go func() {
        wg.Add(1)
        wg.Done()
    }()
    wg.Done()
}()
wg.Wait()

This is indeed broken. The comment should just be improved to be more specific and avoid the plausible but misleading understanding you've had while reading it.