code review 3770045: sync: Proposal for barrier implementation

sync: Proposal for barrier implementation

As discussed in the mailing list, this adds a simple barrier
implementation to the sync package which enables one or more
goroutines to wait for a counter to go down to zero.

[niemeyer, 2011-01-05 12:11:52]

Hello rsc (cc: golang-dev@googlegroups.com),

I'd like you to review this change.

[niemeyer, 2011-01-05 12:52:25]

Added Done() and DoneWait() to the API, using the same primitives. The former is
just Add(-1), but it's much nicer as a name (and was suggested in the ticket). 
The latter is useful on computations which have to wait for all goroutines to
reach the same point, and is error prone to do without (Done() + Wait() is not
correct due to lack of atomicity).

[niemeyer, 2011-01-05 22:14:01]

I've reduced the proposal to reduce the API to the part that is
not being disputed in issue 1382, and included some proper testing.

I will post these further enhancements in a separate CL once the
agreed bits go in.

[rog, 2011-01-06 15:22:53]

http://codereview.appspot.com/3770045/diff/17001/src/pkg/sync/barrier_test.go
File src/pkg/sync/barrier_test.go (right):

http://codereview.appspot.com/3770045/diff/17001/src/pkg/sync/barrier_test.go...
src/pkg/sync/barrier_test.go:16: max = i
what's this trying to test? it's concurrently assigning to max, so there's no
guarantee of any particular final value for max.

[niemeyer, 2011-01-06 16:38:43]

- Now based on semaphores (faster, reduced memory use).
- Renamed to WaitGroup as requested.
- Improved testing.

PTAL

[niemeyer, 2011-01-06 16:39:43]

Problem fixed in the latest version, and other improvements.

http://codereview.appspot.com/3770045/diff/17001/src/pkg/sync/barrier_test.go
File src/pkg/sync/barrier_test.go (right):

http://codereview.appspot.com/3770045/diff/17001/src/pkg/sync/barrier_test.go...
src/pkg/sync/barrier_test.go:16: max = i
True.. I was attempting to guarantee that the the Wait() wasn't unblocked until
the last Done(), but got blinded by the rest of the problem.  Will fix that up.

[rog, 2011-01-06 20:38:43]

http://codereview.appspot.com/3770045/diff/39001/src/pkg/sync/waitgroup.go
File src/pkg/sync/waitgroup.go (right):

http://codereview.appspot.com/3770045/diff/39001/src/pkg/sync/waitgroup.go#ne...
src/pkg/sync/waitgroup.go:9: // to wait for a task which is being performed in
parallel to finish.
something more like Russ's original proposal text here?

http://codereview.appspot.com/3770045/diff/39001/src/pkg/sync/waitgroup.go#ne...
src/pkg/sync/waitgroup.go:16: //   for i := 0; i != n; i++ {
for i := 0; i < n; i++ {

is more idiomatic.

http://codereview.appspot.com/3770045/diff/39001/src/pkg/sync/waitgroup.go#ne...
src/pkg/sync/waitgroup.go:29: sema    *uint32
perhaps better to name the semaphore value after the thing it's guarding?
e.g. done or await

http://codereview.appspot.com/3770045/diff/39001/src/pkg/sync/waitgroup.go#ne...
src/pkg/sync/waitgroup.go:33: // wait round, to avoid this race:
// The WaitGroup creates a new semaphore each time the old semaphore
// is released. This is to avoid the following race:

http://codereview.appspot.com/3770045/diff/39001/src/pkg/sync/waitgroup.go#ne...
src/pkg/sync/waitgroup.go:42: // becomes zero, all goroutines blocked on Wait()
are released.
is there a good use case for allowing negative deltas?
i think the code is marginally clearer if it doesn't, the error message can be
clearer, and the documentation simpler IMHO.

http://codereview.appspot.com/3770045/diff/39001/src/pkg/sync/waitgroup.go#ne...
src/pkg/sync/waitgroup.go:50: if wg.counter == 0 && wg.waiters > 0 {
if wg.counter == 0 {

http://codereview.appspot.com/3770045/diff/39001/src/pkg/sync/waitgroup.go#ne...
src/pkg/sync/waitgroup.go:51: for i := 0; i != wg.waiters; i++ {
for i := 0; i < wg.waiters; i++ {

http://codereview.appspot.com/3770045/diff/39001/src/pkg/sync/waitgroup.go#ne...
src/pkg/sync/waitgroup.go:66: // In case the WaitGroup counter is greater than
zero, block the
// Wait blocks until the WaitGroup counter is zero.

[niemeyer, 2011-01-06 21:31:39]

Comments addressed. Thanks.

http://codereview.appspot.com/3770045/diff/39001/src/pkg/sync/waitgroup.go
File src/pkg/sync/waitgroup.go (right):

http://codereview.appspot.com/3770045/diff/39001/src/pkg/sync/waitgroup.go#ne...
src/pkg/sync/waitgroup.go:9: // to wait for a task which is being performed in
parallel to finish.
> something more like Russ's original proposal text here?

Looks good, changed.

http://codereview.appspot.com/3770045/diff/39001/src/pkg/sync/waitgroup.go#ne...
src/pkg/sync/waitgroup.go:16: //   for i := 0; i != n; i++ {
> for i := 0; i < n; i++ { is more idiomatic.

Changed. :-)

http://codereview.appspot.com/3770045/diff/39001/src/pkg/sync/waitgroup.go#ne...
src/pkg/sync/waitgroup.go:29: sema    *uint32
> perhaps better to name the semaphore value after the thing it's guarding?

I'm following the convention used elsewhere.

http://codereview.appspot.com/3770045/diff/39001/src/pkg/sync/waitgroup.go#ne...
src/pkg/sync/waitgroup.go:33: // wait round, to avoid this race:
> // The WaitGroup creates a new semaphore each time the old semaphore

Changed, thanks.

http://codereview.appspot.com/3770045/diff/39001/src/pkg/sync/waitgroup.go#ne...
src/pkg/sync/waitgroup.go:42: // becomes zero, all goroutines blocked on Wait()
are released.
> is there a good use case for allowing negative deltas?

Yes, Done() is Add(-1) which looks clearer and more concise.

http://codereview.appspot.com/3770045/diff/39001/src/pkg/sync/waitgroup.go#ne...
src/pkg/sync/waitgroup.go:50: if wg.counter == 0 && wg.waiters > 0 {
> if wg.counter == 0 {

No reason to execute the block if waiters is 0.

http://codereview.appspot.com/3770045/diff/39001/src/pkg/sync/waitgroup.go#ne...
src/pkg/sync/waitgroup.go:51: for i := 0; i != wg.waiters; i++ {
> for i := 0; i < wg.waiters; i++ {

Changed. :-)

http://codereview.appspot.com/3770045/diff/39001/src/pkg/sync/waitgroup.go#ne...
src/pkg/sync/waitgroup.go:66: // In case the WaitGroup counter is greater than
zero, block the
> // Wait blocks until the WaitGroup counter is zero.

The original text looks better in this case.

[rsc, 2011-01-06 22:19:32]

Please read golang.org/doc/effective_go.html#commentary

The doc comments should begin with nouns.

Russ

[rog, 2011-01-06 22:44:03]

http://codereview.appspot.com/3770045/diff/39001/src/pkg/sync/waitgroup.go
File src/pkg/sync/waitgroup.go (right):

http://codereview.appspot.com/3770045/diff/39001/src/pkg/sync/waitgroup.go#ne...
src/pkg/sync/waitgroup.go:42: // becomes zero, all goroutines blocked on Wait()
are released.
On 2011/01/06 21:31:39, niemeyer wrote:
> > is there a good use case for allowing negative deltas?
> 
> Yes, Done() is Add(-1) which looks clearer and more concise.

that's an implementation decision. i was asking from an API point of view.

http://codereview.appspot.com/3770045/diff/39001/src/pkg/sync/waitgroup.go#ne...
src/pkg/sync/waitgroup.go:50: if wg.counter == 0 && wg.waiters > 0 {
On 2011/01/06 21:31:39, niemeyer wrote:
> > if wg.counter == 0 {
> 
> No reason to execute the block if waiters is 0.

no need to check the condition since the code inside the block deals with
waiters==0 fine. premature optimisation IMHO - it's easier to read the code
without the check.

http://codereview.appspot.com/3770045/diff/39001/src/pkg/sync/waitgroup.go#ne...
src/pkg/sync/waitgroup.go:66: // In case the WaitGroup counter is greater than
zero, block the
On 2011/01/06 21:31:39, niemeyer wrote:
> > // Wait blocks until the WaitGroup counter is zero.
> 
> The original text looks better in this case.

see russ's comment.

[niemeyer, 2011-01-06 23:00:46]

> Please read golang.org/doc/effective_go.html#commentary
> 
> The doc comments should begin with nouns.

Missed that, sorry. Documentation updated.

[rog, 2011-01-07 10:49:01]

http://codereview.appspot.com/3770045/diff/47001/src/pkg/sync/waitgroup.go
File src/pkg/sync/waitgroup.go (right):

http://codereview.appspot.com/3770045/diff/47001/src/pkg/sync/waitgroup.go#ne...
src/pkg/sync/waitgroup.go:12: // given number of goroutines have finished.
Although this is Russ's original text, it's a perhaps little too specific for
this implementation, which is more general (for instance Add need not be called
by the main goroutine, and Wait can be called several times).

how about this:

// A WaitGroup waits for a collection of goroutines to finish.
// Add is called to add goroutines to the collection.
// Then each of the goroutines runs and calls Done when finished.
// At the same time, Wait can be used to block until all the goroutines finish.

http://codereview.appspot.com/3770045/diff/47001/src/pkg/sync/waitgroup.go#ne...
src/pkg/sync/waitgroup.go:63: // Done decrements the WaitGroup counter by one. 
When the counter
// Done decrements the WaitGroup goroutine count. If it becomes zero,
// any calls to Wait are unblocked.

(The main description doesn't mention a counter)

http://codereview.appspot.com/3770045/diff/47001/src/pkg/sync/waitgroup.go#ne...
src/pkg/sync/waitgroup.go:69: // Wait blocks the calling goroutine while the
WaitGroup counter is
// Wait blocks until the WaitGroup goroutine count is zero.

(matching the language in Mutex.Lock)

[niemeyer, 2011-02-01 10:06:06]

Updated tests to reflect recent changes on non-blocking channel
receiving. Also tweaked some docstrings following ideas of Roger.

[rsc, 2011-02-03 04:10:20]

looks good

http://codereview.appspot.com/3770045/diff/13001/src/pkg/sync/barrier.go
File src/pkg/sync/barrier.go (right):

http://codereview.appspot.com/3770045/diff/13001/src/pkg/sync/barrier.go#newc...
src/pkg/sync/barrier.go:4: // Synchronization primitive which enables blocking
one or more
These comments are not the right form.
See http://golang.org/doc/effective_go.html#commentary

http://codereview.appspot.com/3770045/diff/53001/src/pkg/sync/waitgroup.go
File src/pkg/sync/waitgroup.go (right):

http://codereview.appspot.com/3770045/diff/53001/src/pkg/sync/waitgroup.go#ne...
src/pkg/sync/waitgroup.go:15: //   wg.Add(n)
A more interesting example would be

for i := 0; i < n; i++ {
    if !condition(i) {
        continue
    }
    wg.Add(1)
    go func() {
        // Do something.
        wg.Done()
    }
}

http://codereview.appspot.com/3770045/diff/53001/src/pkg/sync/waitgroup.go#ne...
src/pkg/sync/waitgroup.go:33: // is released. This is to avoid the following
race:
I believe that there is a race here but the one 
below is not convincing, because G3 comes out of nowhere
and starts using the wg.  I think you need a G3: Wait()
after the G1: Wait(), and then G3 wakes up when G2 does
Done().

http://codereview.appspot.com/3770045/diff/53001/src/pkg/sync/waitgroup.go#ne...
src/pkg/sync/waitgroup.go:41: // Add sums the given delta to the WaitGroup
counter.  If the counter
s/sums/adds/
s/the given //

http://codereview.appspot.com/3770045/diff/53001/src/pkg/sync/waitgroup.go#ne...
src/pkg/sync/waitgroup.go:47: panic("Attempted to decrement barrier counter
below zero")
panic("sync: negative WaitGroup count")

http://codereview.appspot.com/3770045/diff/53001/src/pkg/sync/waitgroup.go#ne...
src/pkg/sync/waitgroup.go:60: // Done decrements the WaitGroup counter by one. 
When the counter
s/ by one//
can drop second sentence (Wait already says that)

http://codereview.appspot.com/3770045/diff/53001/src/pkg/sync/waitgroup.go#ne...
src/pkg/sync/waitgroup.go:69: if wg.counter > 0 {
if wg.counter == 0 {
    wg.m.Unlock()
    return
}
...

[niemeyer, 2011-02-03 14:28:54]

All addressed, with the following details.

PTAL

http://codereview.appspot.com/3770045/diff/13001/src/pkg/sync/barrier.go
File src/pkg/sync/barrier.go (right):

http://codereview.appspot.com/3770045/diff/13001/src/pkg/sync/barrier.go#newc...
src/pkg/sync/barrier.go:4: // Synchronization primitive which enables blocking
one or more
> These comments are not the right form.

That's a probably left over review point. This file doesn't exist anymore in the
current patch set.

http://codereview.appspot.com/3770045/diff/53001/src/pkg/sync/waitgroup.go
File src/pkg/sync/waitgroup.go (right):

http://codereview.appspot.com/3770045/diff/53001/src/pkg/sync/waitgroup.go#ne...
src/pkg/sync/waitgroup.go:33: // is released. This is to avoid the following
race:
In this case there wouldn't be a race, because Done()
would properly release the semaphore twice (waiters is
within the mutex region), and unlock both G1 and G3.

The race affects most visibly the reuse of the WaitGroup
in sequential iterations, because the conclusion of a
former batch would leak into the following one, which is
what I was trying to demonstrate in the example.

I've tweaked it slightly to show G1 firing G2.  Not sure
if it helped solve your concern.

[rsc, 2011-02-03 15:32:19]

http://codereview.appspot.com/3770045/diff/59001/src/pkg/sync/waitgroup.go
File src/pkg/sync/waitgroup.go (right):

http://codereview.appspot.com/3770045/diff/59001/src/pkg/sync/waitgroup.go#ne...
src/pkg/sync/waitgroup.go:39: // G3: Add(1)
G3 still comes out of nowhere.

There needs to be a reason that G3 would think that
the waitgroup was available for use.  That is, it has
to know that the previous round has concluded.
As it is, this is just some other goroutine coming in
and stomping on someone else's data structures.
If G3 were waiting too before this call to Add, that
could give such a reason.

[niemeyer, 2011-02-03 16:27:28]

> There needs to be a reason that G3 would think that
> the waitgroup was available for use.  That is, it has

Ah, I misunderstood your concern.

I've managed to introduce the G3 Wait() while maintaining
the bug, and also clarified the state.

PTAL

[rsc, 2011-02-03 18:24:36]

Seems fine to me.  Adding r to reviewers for his comments.

[r, 2011-02-03 20:18:07]

looks good but the package comment will need to be updated

http://codereview.appspot.com/3770045/diff/61001/src/pkg/sync/waitgroup.go
File src/pkg/sync/waitgroup.go (right):

http://codereview.appspot.com/3770045/diff/61001/src/pkg/sync/waitgroup.go#ne...
src/pkg/sync/waitgroup.go:44: // Add adds delta to the WaitGroup counter.  If
the counter
delta, which may be negative,

[niemeyer, 2011-02-03 20:31:07]

Thanks for all the reviews.  Both done, and also added the
copyright header into the new files.

[r, 2011-02-03 20:38:30]

LGTM

[r, 2011-02-03 20:39:27]

*** Submitted as http://code.google.com/p/go/source/detail?r=85f202d81c64 ***

sync: Proposal for barrier implementation

As discussed in the mailing list, this adds a simple barrier
implementation to the sync package which enables one or more
goroutines to wait for a counter to go down to zero.

R=rsc, rog, r
CC=golang-dev
http://codereview.appspot.com/3770045

Committer: Rob Pike <r@golang.org>