code review 4631075: sync: improve Mutex to allow successive acquisitions

sync: improve Mutex to allow successive acquisitions
This implementation allows a goroutine to do successive acquisitions
of a mutex even if there are blocked goroutines.
Moreover, it allows a newcomer goroutine to acquire a mutex ahead of
blocked goroutines (that is, it does not enforce FIFO).
On implementation level it's achieved by separating waiter count and
locked flag.
Benchmark results on HP Z600 (2 x Xeon E5620, 8 HT cores, 2.40GHz)
are as follows (with 4631059 "replace Semacquire/Semrelease implementation"
patch applied):
benchmark                                        old ns/op    new ns/op    delta
sync_test.BenchmarkMutexUncontended                  24.10        25.40   +5.39%
sync_test.BenchmarkMutexUncontended-2                12.00        13.00   +8.33%
sync_test.BenchmarkMutexUncontended-4                 6.06         6.83  +12.71%
sync_test.BenchmarkMutexUncontended-8                 3.63         3.60   -0.83%
sync_test.BenchmarkMutexUncontended-16                2.38         2.49   +4.62%

sync_test.BenchmarkMutex                             25.00        26.40   +5.60%
sync_test.BenchmarkMutex-2                          231.00        49.00  -78.79%
sync_test.BenchmarkMutex-4                          259.00       114.00  -55.98%
sync_test.BenchmarkMutex-8                          641.00       110.00  -82.84%
sync_test.BenchmarkMutex-16                        1380.00        96.30  -93.02%

sync_test.BenchmarkMutexSlack                        24.80        26.20   +5.65%
sync_test.BenchmarkMutexSlack-2                     210.00       106.00  -49.52%
sync_test.BenchmarkMutexSlack-4                     453.00       119.00  -73.73%
sync_test.BenchmarkMutexSlack-8                    1024.00       105.00  -89.75%
sync_test.BenchmarkMutexSlack-16                   1291.00        91.90  -92.88%

sync_test.BenchmarkMutexWork                        796.00       796.00   +0.00%
sync_test.BenchmarkMutexWork-2                      399.00       401.00   +0.50%
sync_test.BenchmarkMutexWork-4                      216.00       212.00   -1.85%
sync_test.BenchmarkMutexWork-8                     1547.00       196.00  -87.33%
sync_test.BenchmarkMutexWork-16                    2754.00       287.00  -89.58%

sync_test.BenchmarkMutexWorkSlack                   792.00       800.00   +1.01%
sync_test.BenchmarkMutexWorkSlack-2                 430.00       420.00   -2.33%
sync_test.BenchmarkMutexWorkSlack-4                 467.00       230.00  -50.75%
sync_test.BenchmarkMutexWorkSlack-8                1860.00       273.00  -85.32%
sync_test.BenchmarkMutexWorkSlack-16               3029.00       294.00  -90.29%

[dvyukov, 2011-06-28 19:05:28]

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

I'd like you to review this change to
https://go.googlecode.com/hg/

[rsc, 2011-06-28 19:33:51]

Nice speedup.

http://codereview.appspot.com/4631075/diff/5001/src/pkg/sync/mutex.go
File src/pkg/sync/mutex.go (right):

http://codereview.appspot.com/4631075/diff/5001/src/pkg/sync/mutex.go#newcode20
src/pkg/sync/mutex.go:20: state uint32
I think using int32 will make things easier.

http://codereview.appspot.com/4631075/diff/5001/src/pkg/sync/mutex.go#newcode32
src/pkg/sync/mutex.go:32: MUTEX_LOCKED = uint32(1 << 0)
Case determines whether a name is exported by the package.
Also the preference in Go is for mixedCaps or MixedCaps,
not under_scores.  

The types are not typically necessary either.

const (
    mutexLocked = 1<<0  // mutex is locked
    mutexWoken = 1<<1  // goroutine woken to acquire mutex
    mutexWaiter = 1<<2  // waiter count multiplier
    mutexWaiterMask = ^uint32(mutexWaiter-1)
)

It's not clear you need Waiter and WaiterMask anyway.
I'd be inclined to do

const (
    mutexLocked = 1<<iota  // mutex is locked
    mutexWoken
    mutexWaiterShift = iota
)

http://codereview.appspot.com/4631075/diff/5001/src/pkg/sync/mutex.go#newcode46
src/pkg/sync/mutex.go:46: // Fast-path: assume that the mutex is unlocked
// Fast path: grab unlocked mutex.

http://codereview.appspot.com/4631075/diff/5001/src/pkg/sync/mutex.go#newcode51
src/pkg/sync/mutex.go:51: // Slow-path: try to either acquire the mutex if it's
not locked,
// Slow path: grab mutex or sleep.

blank line before here please

can also just drop the comment.
the fact that there is a fast path 
implies that the rest of the function
is the slow path.  either way.

http://codereview.appspot.com/4631075/diff/5001/src/pkg/sync/mutex.go#newcode53
src/pkg/sync/mutex.go:53: retry := false
s/retry/awoke/

(The flag tracks whether the goroutine has been woken up,
as the comment below says.)

http://codereview.appspot.com/4631075/diff/5001/src/pkg/sync/mutex.go#newcode54
src/pkg/sync/mutex.go:54: for true {
In Go, we write "for true {" as "for {".

http://codereview.appspot.com/4631075/diff/5001/src/pkg/sync/mutex.go#newcode55
src/pkg/sync/mutex.go:55: cmp := m.state
cmp and xchg are cute names but not super helpful
for understanding the algorithm.  I think calling them
old and new would help more.

http://codereview.appspot.com/4631075/diff/5001/src/pkg/sync/mutex.go#newcode58
src/pkg/sync/mutex.go:58: xchg = cmp + MUTEX_WAITER
new = old + 1<<mutexWaiterShift

http://codereview.appspot.com/4631075/diff/5001/src/pkg/sync/mutex.go#newcode63
src/pkg/sync/mutex.go:63: xchg = xchg &^ MUTEX_WOKEN
new &^= mutexWoken

http://codereview.appspot.com/4631075/diff/5001/src/pkg/sync/mutex.go#newcode83
src/pkg/sync/mutex.go:83: cmp := atomic.AddUint32(&m.state, ^MUTEX_LOCKED+1)
Using int32 means you can use -mutexLocked here.

// Fast path: drop lock bit.
new := atomic.AddUint32(&m.state, -mutexLocked)

http://codereview.appspot.com/4631075/diff/5001/src/pkg/sync/mutex.go#newcode87
src/pkg/sync/mutex.go:87: if cmp&MUTEX_WAITER_MASK == 0 || cmp&MUTEX_WOKEN != 0
{
Seems easy and free to merge this with the loop:

old := new
for {
    // If there are no waiters or a goroutine has already
    // been woken or grabbed the lock, no need to wake anyone.
    if old>>mutexWaiterShift == 0 || old&(mutexLocked|mutexWoken) != 0 {
        return
    }

    // Grab the right to wake someone.
    new := (old - 1<<mutexWaiterShift) | mutexWoken
    if ... {
        ...
    }

    old = m.state
}

[dvyukov, 2011-06-29 09:16:31]

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

Please take another look.

[dvyukov, 2011-06-29 18:55:11]

On 2011/06/29 09:16:31, dvyukov wrote:
> Hello mailto:rsc@golang.org (cc: mailto:golang-dev@googlegroups.com),
> 
> Please take another look.

ping

[rsc, 2011-06-30 14:44:02]

LGTM

[rsc, 2011-06-30 15:13:38]

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

sync: improve Mutex to allow successive acquisitions
This implementation allows a goroutine to do successive acquisitions
of a mutex even if there are blocked goroutines.
Moreover, it allows a newcomer goroutine to acquire a mutex ahead of
blocked goroutines (that is, it does not enforce FIFO).
On implementation level it's achieved by separating waiter count and
locked flag.
Benchmark results on HP Z600 (2 x Xeon E5620, 8 HT cores, 2.40GHz)
are as follows (with 4631059 "replace Semacquire/Semrelease implementation"
patch applied):
benchmark                                        old ns/op    new ns/op    delta
sync_test.BenchmarkMutexUncontended                  24.10        25.40   +5.39%
sync_test.BenchmarkMutexUncontended-2                12.00        13.00   +8.33%
sync_test.BenchmarkMutexUncontended-4                 6.06         6.83  +12.71%
sync_test.BenchmarkMutexUncontended-8                 3.63         3.60   -0.83%
sync_test.BenchmarkMutexUncontended-16                2.38         2.49   +4.62%

sync_test.BenchmarkMutex                             25.00        26.40   +5.60%
sync_test.BenchmarkMutex-2                          231.00        49.00  -78.79%
sync_test.BenchmarkMutex-4                          259.00       114.00  -55.98%
sync_test.BenchmarkMutex-8                          641.00       110.00  -82.84%
sync_test.BenchmarkMutex-16                        1380.00        96.30  -93.02%

sync_test.BenchmarkMutexSlack                        24.80        26.20   +5.65%
sync_test.BenchmarkMutexSlack-2                     210.00       106.00  -49.52%
sync_test.BenchmarkMutexSlack-4                     453.00       119.00  -73.73%
sync_test.BenchmarkMutexSlack-8                    1024.00       105.00  -89.75%
sync_test.BenchmarkMutexSlack-16                   1291.00        91.90  -92.88%

sync_test.BenchmarkMutexWork                        796.00       796.00   +0.00%
sync_test.BenchmarkMutexWork-2                      399.00       401.00   +0.50%
sync_test.BenchmarkMutexWork-4                      216.00       212.00   -1.85%
sync_test.BenchmarkMutexWork-8                     1547.00       196.00  -87.33%
sync_test.BenchmarkMutexWork-16                    2754.00       287.00  -89.58%

sync_test.BenchmarkMutexWorkSlack                   792.00       800.00   +1.01%
sync_test.BenchmarkMutexWorkSlack-2                 430.00       420.00   -2.33%
sync_test.BenchmarkMutexWorkSlack-4                 467.00       230.00  -50.75%
sync_test.BenchmarkMutexWorkSlack-8                1860.00       273.00  -85.32%
sync_test.BenchmarkMutexWorkSlack-16               3029.00       294.00  -90.29%

R=rsc
CC=golang-dev
http://codereview.appspot.com/4631075

Committer: Russ Cox <rsc@golang.org>