sync: faster Cond

sync: faster Cond
The new version does not require any memory allocations and is 30-50% faster.
Also detect and painc if Cond is copied after first.

benchmark            old ns/op    new ns/op    delta
BenchmarkCond1             317          195  -38.49%
BenchmarkCond1-2           875          607  -30.63%
BenchmarkCond1-4          1116          548  -50.90%
BenchmarkCond1-8          1013          613  -39.49%
BenchmarkCond1-16          983          450  -54.22%
BenchmarkCond2             559          352  -37.03%
BenchmarkCond2-2          1916         1378  -28.08%
BenchmarkCond2-4          1518         1322  -12.91%
BenchmarkCond2-8          2313         1291  -44.19%
BenchmarkCond2-16         1885         1078  -42.81%
BenchmarkCond4            1070          614  -42.62%
BenchmarkCond4-2          4899         3047  -37.80%
BenchmarkCond4-4          3813         3006  -21.16%
BenchmarkCond4-8          3605         3045  -15.53%
BenchmarkCond4-16         4148         2637  -36.43%
BenchmarkCond8            2086         1264  -39.41%
BenchmarkCond8-2          9961         6736  -32.38%
BenchmarkCond8-4          8135         7689   -5.48%
BenchmarkCond8-8          9623         7517  -21.89%
BenchmarkCond8-16        11661         8093  -30.60%

[sougou, 2013-07-19 15:54:34]

Don't know enough about runtime to comment there, but the Cond side looks
peachy.

[rsc, 2013-08-09 14:44:51]

Okay, now I understand why this works.

I want to avoid putting runtime Locks into user data structures.
Users could corrupt the Lock by copying one Cond onto another and cause all
manner of interesting problems in the runtime, especially since on some
platforms the Lock holds an M pointer.

Can you use an address-indexed table like the SemaRoot table?

[rsc, 2013-08-09 15:15:10]

If you don't want to use an address-indexed table it is also fine to make
the Cond pass in an opaque uintptr that you use as a pointer to a SyncSema
allocated on first use.

Please reuse the Sema struct instead of defining the basically identical
SyncSemaWaiter.
We can rename Sema to Waiter if you want.

[dvyukov, 2013-08-09 15:19:49]

On Fri, Aug 9, 2013 at 7:15 PM, Russ Cox <rsc@golang.org> wrote:
> If you don't want to use an address-indexed table it is also fine to make
> the Cond pass in an opaque uintptr that you use as a pointer to a SyncSema
> allocated on first use.

Allocations is the thing that this CL tries to avoid.
I will see how to do it w/o allocations and w/o exposing M.

> Please reuse the Sema struct instead of defining the basically identical
> SyncSemaWaiter.
> We can rename Sema to Waiter if you want.
>

[dvyukov, 2013-08-09 16:52:09]

On Fri, Aug 9, 2013 at 6:44 PM,  <rsc@golang.org> wrote:
> Okay, now I understand why this works.
>
> I want to avoid putting runtime Locks into user data structures.
> Users could corrupt the Lock by copying one Cond onto another and cause
> all manner of interesting problems in the runtime, especially since on
> some platforms the Lock holds an M pointer.
>
> Can you use an address-indexed table like the SemaRoot table?


Is copying the only concern?
If so, then I can add a back pointer to itself to SyncSema. Initialize
it lazily in acquire/release. If already initialized check that it's
correct. If incorrect - panic.
The same trick can be used in async semaphores to avoid the hashtable.

[dvyukov, 2013-08-09 16:58:48]

On Fri, Aug 9, 2013 at 6:44 PM,  <rsc@golang.org> wrote:
> Okay, now I understand why this works.
>
> I want to avoid putting runtime Locks into user data structures.
> Users could corrupt the Lock by copying one Cond onto another and cause
> all manner of interesting problems in the runtime, especially since on
> some platforms the Lock holds an M pointer.
>
> Can you use an address-indexed table like the SemaRoot table?


Is copying the only concern?
If so, then I can add a back pointer to itself to SyncSema. Initialize
it lazily in acquire/release. If already initialized check that it's
correct. If incorrect - panic.
The same trick can be used in async semaphores to avoid the hashtable.

[rsc, 2013-08-09 18:02:31]

On Fri, Aug 9, 2013 at 12:50 PM, Dmitry Vyukov <dvyukov@google.com> wrote:

> On Fri, Aug 9, 2013 at 6:44 PM,  <rsc@golang.org> wrote:
> > Okay, now I understand why this works.
> >
> > I want to avoid putting runtime Locks into user data structures.
> > Users could corrupt the Lock by copying one Cond onto another and cause
> > all manner of interesting problems in the runtime, especially since on
> > some platforms the Lock holds an M pointer.
> >
> > Can you use an address-indexed table like the SemaRoot table?
>
> Is copying the only concern?
>

It's the only problem I can think of.


> If so, then I can add a back pointer to itself to SyncSema. Initialize
> it lazily in acquire/release. If already initialized check that it's
> correct. If incorrect - panic.
> The same trick can be used in async semaphores to avoid the hashtable.
>

Okay, let's try that.

Russ

[dvyukov, 2013-08-09 18:07:48]

On 2013/08/09 18:02:31, rsc wrote:
> On Fri, Aug 9, 2013 at 12:50 PM, Dmitry Vyukov <mailto:dvyukov@google.com>
wrote:
> 
> > On Fri, Aug 9, 2013 at 6:44 PM,  <mailto:rsc@golang.org> wrote:
> > > Okay, now I understand why this works.
> > >
> > > I want to avoid putting runtime Locks into user data structures.
> > > Users could corrupt the Lock by copying one Cond onto another and cause
> > > all manner of interesting problems in the runtime, especially since on
> > > some platforms the Lock holds an M pointer.
> > >
> > > Can you use an address-indexed table like the SemaRoot table?
> >
> > Is copying the only concern?
> >
> 
> It's the only problem I can think of.
> 
> 
> > If so, then I can add a back pointer to itself to SyncSema. Initialize
> > it lazily in acquire/release. If already initialized check that it's
> > correct. If incorrect - panic.
> > The same trick can be used in async semaphores to avoid the hashtable.
> >
> 
> Okay, let's try that.


I've just refactored the following:

var mu sync.Mutex
mu.Lock
go func() {
  mu.Unlock()
}()

into the following:

var mu sync.Mutex
mu.Lock
go foo(mu)

func foo(mu sync.Mutex) {
  mu.Unlock()
}()

and it hanged (the mutex was copied).

As a side effect of the back pointer trick, we will be able to detect and panic
with a proper message in such cases -- copy a mutex that was already locked, and
then use the copy.

[rsc, 2013-08-09 18:13:43]

>
> As a side effect of the back pointer trick, we will be able to detect
> and panic with a proper message in such cases -- copy a mutex that was
> already locked, and then use the copy.
>

Great!

Russ

[dvyukov, 2013-08-12 13:49:31]

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

I'd like you to review this change to
https://dvyukov%40google.com@code.google.com/p/go/

[dvyukov, 2013-08-12 13:55:36]

On 2013/08/09 18:13:43, rsc wrote:
> >
> > As a side effect of the back pointer trick, we will be able to detect
> > and panic with a proper message in such cases -- copy a mutex that was
> > already locked, and then use the copy.
> >
> 
> Great!
> 
> Russ


If we decide that we can panic on sync.Mutex copying, then we can change async
semaphores to use the same scheme and then remove the sem table, hashing, list
traversals, etc.

[bradfitz, 2013-08-12 14:55:34]

https://codereview.appspot.com/11573043/diff/29001/src/pkg/sync/runtime.go
File src/pkg/sync/runtime.go (right):

https://codereview.appspot.com/11573043/diff/29001/src/pkg/sync/runtime.go#ne...
src/pkg/sync/runtime.go:22: type syncSema [3]uintptr
add a comment referencing where/what this is in the runtime code, so something
can explain the [3]?

// same size as struct SyncSema in sema.goc.

https://codereview.appspot.com/11573043/diff/29001/src/pkg/sync/runtime.go#ne...
src/pkg/sync/runtime.go:25: // Returns false if the semaphore is corrupted.
how does it return false? it has no return value.

https://codereview.appspot.com/11573043/diff/29001/src/pkg/sync/runtime.go#ne...
src/pkg/sync/runtime.go:29: // Returns false if the semaphore is corrupted.
likewise

[dvyukov, 2013-08-12 17:23:12]

PTAL

https://codereview.appspot.com/11573043/diff/29001/src/pkg/sync/runtime.go
File src/pkg/sync/runtime.go (right):

https://codereview.appspot.com/11573043/diff/29001/src/pkg/sync/runtime.go#ne...
src/pkg/sync/runtime.go:22: type syncSema [3]uintptr
On 2013/08/12 14:55:35, bradfitz wrote:
> add a comment referencing where/what this is in the runtime code, so something
> can explain the [3]?
> 
> // same size as struct SyncSema in sema.goc.

Done.

https://codereview.appspot.com/11573043/diff/29001/src/pkg/sync/runtime.go#ne...
src/pkg/sync/runtime.go:25: // Returns false if the semaphore is corrupted.
On 2013/08/12 14:55:35, bradfitz wrote:
> how does it return false? it has no return value.

Done.

https://codereview.appspot.com/11573043/diff/29001/src/pkg/sync/runtime.go#ne...
src/pkg/sync/runtime.go:29: // Returns false if the semaphore is corrupted.
On 2013/08/12 14:55:35, bradfitz wrote:
> likewise

Done.

[bradfitz, 2013-08-12 17:52:53]

https://codereview.appspot.com/11573043/diff/36001/src/pkg/runtime/sema.goc
File src/pkg/runtime/sema.goc (right):

https://codereview.appspot.com/11573043/diff/36001/src/pkg/runtime/sema.goc#n...
src/pkg/runtime/sema.goc:221: // Returns false if the semaphore is corrupted.
also doesn't return

https://codereview.appspot.com/11573043/diff/36001/src/pkg/runtime/sema.goc#n...
src/pkg/runtime/sema.goc:264: // Returns false if the semaphore is corrupted.
also doesn't return

[dvyukov, 2013-08-12 18:05:57]

PTAL

https://codereview.appspot.com/11573043/diff/36001/src/pkg/runtime/sema.goc
File src/pkg/runtime/sema.goc (right):

https://codereview.appspot.com/11573043/diff/36001/src/pkg/runtime/sema.goc#n...
src/pkg/runtime/sema.goc:221: // Returns false if the semaphore is corrupted.
On 2013/08/12 17:52:53, bradfitz wrote:
> also doesn't return

Well, if memory is corrupted, I can imagine that void function still returns
something :)

Done

[r, 2013-08-13 03:50:09]

https://codereview.appspot.com/11573043/diff/43001/src/pkg/sync/runtime.go
File src/pkg/sync/runtime.go (right):

https://codereview.appspot.com/11573043/diff/43001/src/pkg/sync/runtime.go#ne...
src/pkg/sync/runtime.go:28: // Syncsemrelease waits for n pairing Syncsemacquire
on the same semaphore s.
should these be CamelCaSed?

[rsc, 2013-08-13 04:05:50]

LGTM

https://codereview.appspot.com/11573043/diff/43001/src/pkg/sync/runtime.go
File src/pkg/sync/runtime.go (right):

https://codereview.appspot.com/11573043/diff/43001/src/pkg/sync/runtime.go#ne...
src/pkg/sync/runtime.go:28: // Syncsemrelease waits for n pairing Syncsemacquire
on the same semaphore s.
On 2013/08/13 03:50:09, r wrote:
> should these be CamelCaSed?

perhaps, but the existing code set the pattern. this is all a weird mix of C and
Go so it's unclear.
let's leave it as is. it's not user-visible.

[dvyukov, 2013-08-13 10:45:41]

*** Submitted as https://code.google.com/p/go/source/detail?r=0b7a3fb56379 ***

sync: faster Cond
The new version does not require any memory allocations and is 30-50% faster.
Also detect and painc if Cond is copied after first.

benchmark            old ns/op    new ns/op    delta
BenchmarkCond1             317          195  -38.49%
BenchmarkCond1-2           875          607  -30.63%
BenchmarkCond1-4          1116          548  -50.90%
BenchmarkCond1-8          1013          613  -39.49%
BenchmarkCond1-16          983          450  -54.22%
BenchmarkCond2             559          352  -37.03%
BenchmarkCond2-2          1916         1378  -28.08%
BenchmarkCond2-4          1518         1322  -12.91%
BenchmarkCond2-8          2313         1291  -44.19%
BenchmarkCond2-16         1885         1078  -42.81%
BenchmarkCond4            1070          614  -42.62%
BenchmarkCond4-2          4899         3047  -37.80%
BenchmarkCond4-4          3813         3006  -21.16%
BenchmarkCond4-8          3605         3045  -15.53%
BenchmarkCond4-16         4148         2637  -36.43%
BenchmarkCond8            2086         1264  -39.41%
BenchmarkCond8-2          9961         6736  -32.38%
BenchmarkCond8-4          8135         7689   -5.48%
BenchmarkCond8-8          9623         7517  -21.89%
BenchmarkCond8-16        11661         8093  -30.60%

R=sougou, rsc, bradfitz, r
CC=golang-dev
https://codereview.appspot.com/11573043