code review 4811041: runtime: tweak select performance

runtime: tweak select performance
Make selectsend() accept pointer to the element,
it makes it possible to make Scase fixed-size
and allocate/free Select, all Scase's and all SudoG at once.
As a consequence SudoG freelist die out.

benchmark                       old,ns/op  new,ns/op
BenchmarkSelectUncontended	     1080        558
BenchmarkSelectUncontended-2	      675        264
BenchmarkSelectUncontended-4	      459        205
BenchmarkSelectContended	     1086        560
BenchmarkSelectContended-2	     1775       1672
BenchmarkSelectContended-4	     2668       2149
(on Intel Q6600, 4 cores, 2.4GHz)

benchmark                       old ns/op    new ns/op    delta
BenchmarkSelectUncontended         517.00       326.00  -36.94%
BenchmarkSelectUncontended-2       281.00       166.00  -40.93%
BenchmarkSelectUncontended-4       250.00        83.10  -66.76%
BenchmarkSelectUncontended-8       107.00        47.40  -55.70%
BenchmarkSelectUncontended-16       67.80        41.30  -39.09%
BenchmarkSelectContended           513.00       325.00  -36.65%
BenchmarkSelectContended-2         699.00       628.00  -10.16%
BenchmarkSelectContended-4        1085.00      1092.00   +0.65%
BenchmarkSelectContended-8        3253.00      2477.00  -23.85%
BenchmarkSelectContended-16       5313.00      5116.00   -3.71%
(on Intel E5620, 8 HT cores, 2.4 GHz)

[dvyukov, 2011-07-20 17:32:48]

Hello rsc@golang.org, ken@golang.org, 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-07-20 18:05:32]

http://codereview.appspot.com/4811041/diff/3005/src/cmd/gc/select.c
File src/cmd/gc/select.c (right):

http://codereview.appspot.com/4811041/diff/3005/src/cmd/gc/select.c#newcode316
src/cmd/gc/select.c:316: if(n->right->op != ONAME ||
This test is wrong.  You always need the copy,
except when you know for sure that the variable
is not shared with other goroutines. 

The value used will be the value 
at the time the select branch was chosen, not
the value at the time the select blocked.  
If those two can be different, you must make
a copy to make sure they are the same.

Please add a test demonstrating this bug
and then fix.  Only class=PAUTO and PPARAM
are safe to leave this way.

It would be nice to put this in a separate function:
n->right = localexpr(n->right, &init);
(see safeexpr, cheapexpr).

http://codereview.appspot.com/4811041/diff/3005/src/cmd/gc/select.c#newcode318
src/cmd/gc/select.c:318: // If the channel is a function call then we must
invoke it
ch = safeexpr(ch, &init);

http://codereview.appspot.com/4811041/diff/3005/src/pkg/runtime/chan.c
File src/pkg/runtime/chan.c (right):

http://codereview.appspot.com/4811041/diff/3005/src/pkg/runtime/chan.c#newcode73
src/pkg/runtime/chan.c:73: Scase*	scase[1];		// one per case
If you change this to Scase scase[1]; the code would get even simpler, no?

http://codereview.appspot.com/4811041/diff/3005/src/pkg/runtime/chan.c#newcod...
src/pkg/runtime/chan.c:636: runtime·selectsend(Select *sel, Hchan *c, ...)
Since you changed this to a pointer, you can drop the #pragma textflag 7 
and the comment at 630 and recombine with the static selectsend below.

runtime.selectsend(Select *sel, Hchan *c, void *elem)

[dvyukov, 2011-07-20 18:57:52]

>
http://codereview.appspot.com/4811041/diff/3005/src/pkg/runtime/chan.c#newcode73
> src/pkg/runtime/chan.c:73: Scase*	scase[1];		// one per case
> If you change this to Scase scase[1]; the code would get even simpler, no?

It's what I've done first. However, then I realized that we need 3 orders of
cases: (1) lexical - to fill in during selectrecv/selectsend, (2) randomized
poll order and (3) sorted locking order.
I can make it "Scase scase[1]" and then introduce "uint16 *lockorder" (similar
to current Select::order). But it's much more work to do.

[rsc, 2011-07-20 19:01:13]

> It's what I've done first. However, then I realized that we need 3
> orders of cases: (1) lexical - to fill in during selectrecv/selectsend,
> (2) randomized poll order and (3) sorted locking order.
> I can make it "Scase scase[1]" and then introduce "uint16 *lockorder"
> (similar to current Select::order). But it's much more work to do.

I see.  How about introducing Hchan **lockorder; instead of the
scase pointer array?  It will take the same amount of space
and should be clearer why there is an extra indirect.

[dvyukov, 2011-07-20 19:09:02]

>
http://codereview.appspot.com/4811041/diff/3005/src/pkg/runtime/chan.c#newcod...
> src/pkg/runtime/chan.c:636: runtime·selectsend(Select *sel, Hchan *c, ...)
> Since you changed this to a pointer, you can drop the #pragma textflag 7 
> and the comment at 630 and recombine with the static selectsend below.
> 
> runtime.selectsend(Select *sel, Hchan *c, void *elem)

Humm... selectsend become exactly as selectrecv, but selectrecv has textflag
7... Do I need to do the same with selectrecv?

[rsc, 2011-07-20 19:13:00]

>> runtime.selectsend(Select *sel, Hchan *c, void *elem)
>
> Humm... selectsend become exactly as selectrecv, but selectrecv has
> textflag 7... Do I need to do the same with selectrecv?

No, I forgot about the pc argument.
So you do want to leave them separate,
but you can still drop the "..." and replace it with
just a void *elem argument.  Then there is less
math to do in the static selectsend.

[dvyukov, 2011-07-20 19:31:19]

On 2011/07/20 18:05:32, rsc wrote:
> http://codereview.appspot.com/4811041/diff/3005/src/cmd/gc/select.c
> File src/cmd/gc/select.c (right):
> 
> http://codereview.appspot.com/4811041/diff/3005/src/cmd/gc/select.c#newcode316
> src/cmd/gc/select.c:316: if(n->right->op != ONAME ||
> This test is wrong.  You always need the copy,
> except when you know for sure that the variable
> is not shared with other goroutines. 
> 
> The value used will be the value 
> at the time the select branch was chosen, not
> the value at the time the select blocked.  
> If those two can be different, you must make
> a copy to make sure they are the same.
> 
> Please add a test demonstrating this bug
> and then fix.  Only class=PAUTO and PPARAM
> are safe to leave this way.

I've seen a similar logic when temps for RECV are introduced
(n->left->class&PHEAP), but I can't quite understand it. If user's code is
race-free (which we should assume), then it does not make any difference when
the copy is done - the result must be the same. If there is a race on the
element, then it does not make any difference when the copy is done again - a
concurrent goroutine can mutate the element during the case evaluation...

Hummm... wait. Do you mean something along the lines of:

case ch1 <- X:
case <-publish_ptr_to_X_and_return_chan():

Damn! OK, I see... Is it really allowed by the specification?..

OK, "For all the cases in the "select" statement, the channel expressions are
evaluated in top-to-bottom order, along with any expressions that appear on the
right hand side of send statements".

As far as I see, it does not quite say that *copies* of sent values are done
during case evaluation. But I agree to do it.

[dvyukov, 2011-07-21 14:50:26]

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

Please take another look.

[rsc, 2011-07-21 15:42:48]

very nice

http://codereview.appspot.com/4811041/diff/22001/src/cmd/gc/select.c
File src/cmd/gc/select.c (right):

http://codereview.appspot.com/4811041/diff/22001/src/cmd/gc/select.c#newcode313
src/cmd/gc/select.c:313: n->left = localexpr(n->left, &r->ninit);
you don't need a local copy here.
n->left = safeexpr(n->left, &r->ninit)

http://codereview.appspot.com/4811041/diff/22001/src/cmd/gc/subr.c
File src/cmd/gc/subr.c (right):

http://codereview.appspot.com/4811041/diff/22001/src/cmd/gc/subr.c#newcode2784
src/cmd/gc/subr.c:2784: * return side-effect free and cheap n, appending side
effects to init.
return n in a local variable if it is not already.

http://codereview.appspot.com/4811041/diff/22001/src/cmd/gc/subr.c#newcode2792
src/cmd/gc/subr.c:2792: (n->class == PAUTO || n->class == PPARAM || n->class ==
PPARAMOUT) &&
If n->class == one of these 3,
then PHEAP is not set.  So the next line can go away.

http://codereview.appspot.com/4811041/diff/22001/src/pkg/runtime/chan.c
File src/pkg/runtime/chan.c (right):

http://codereview.appspot.com/4811041/diff/22001/src/pkg/runtime/chan.c#newco...
src/pkg/runtime/chan.c:771: for(i=sel->ncase; i>0; i--) {
I know you just preserved the old code, but isn't the old code 
unnecessarily complicated?

for(i=sel->ncase; i-->0; ) {
    if(sel->lockorder[i] != c) {
        c = sel->lockorder[i];
        runtime.lock(c);
    }
}

same as in sellock (almost)

[dvyukov, 2011-07-21 16:35:49]

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

Please take another look.

[dvyukov, 2011-07-21 16:36:10]

On 2011/07/21 15:42:48, rsc wrote:
> very nice
> 
> http://codereview.appspot.com/4811041/diff/22001/src/cmd/gc/select.c
> File src/cmd/gc/select.c (right):
> 
>
http://codereview.appspot.com/4811041/diff/22001/src/cmd/gc/select.c#newcode313
> src/cmd/gc/select.c:313: n->left = localexpr(n->left, &r->ninit);
> you don't need a local copy here.
> n->left = safeexpr(n->left, &r->ninit)

Your right. I just need to produce side effects before evaluation of n->right.


> http://codereview.appspot.com/4811041/diff/22001/src/cmd/gc/subr.c
> File src/cmd/gc/subr.c (right):
> 
> http://codereview.appspot.com/4811041/diff/22001/src/cmd/gc/subr.c#newcode2784
> src/cmd/gc/subr.c:2784: * return side-effect free and cheap n, appending side
> effects to init.
> return n in a local variable if it is not already.

Done.


> http://codereview.appspot.com/4811041/diff/22001/src/cmd/gc/subr.c#newcode2792
> src/cmd/gc/subr.c:2792: (n->class == PAUTO || n->class == PPARAM || n->class
==
> PPARAMOUT) &&
> If n->class == one of these 3,
> then PHEAP is not set.  So the next line can go away.

OK. I was thinking of a param which address is taken. It's not represented as a
PPARAM, right?


> http://codereview.appspot.com/4811041/diff/22001/src/pkg/runtime/chan.c
> File src/pkg/runtime/chan.c (right):
> 
>
http://codereview.appspot.com/4811041/diff/22001/src/pkg/runtime/chan.c#newco...
> src/pkg/runtime/chan.c:771: for(i=sel->ncase; i>0; i--) {
> I know you just preserved the old code, but isn't the old code 
> unnecessarily complicated?
> 
> for(i=sel->ncase; i-->0; ) {
>     if(sel->lockorder[i] != c) {
>         c = sel->lockorder[i];
>         runtime.lock(c);
>     }
> }

Hummm.... I think your code can sigsegv on nil channel...

[rsc, 2011-07-21 16:58:15]

> Hummm.... I think your code can sigsegv on nil channel...

my code is identical to sellock except for the loop order.
if it's wrong then sellock is wrong.
i think it's okay: there are no nils in the array itself,
just at the start of the loop (because we start with c == nil).

my rewrite just makes the loop identical to sellock
except for the order.

[dvyukov, 2011-07-21 17:13:35]

On 2011/07/21 16:58:15, rsc wrote:
> > Hummm.... I think your code can sigsegv on nil channel...
> 
> my code is identical to sellock except for the loop order.
> if it's wrong then sellock is wrong.
> i think it's okay: there are no nils in the array itself,
> just at the start of the loop (because we start with c == nil).
> 
> my rewrite just makes the loop identical to sellock
> except for the order.

There may be a nil channel from default case.
In sellock() we start with potentially nil channel, and so it's skipped by !=c
check.
In selunlock() we end with potentially nil channel, and so it's not necessary
skipped by !=c check, because c may be not nil already.

It's quite tricky and implicit. Perhaps it's better to add explicit check for
nil channels to sellock(), so code in both functions will be consistent.

[rsc, 2011-07-21 17:22:16]

> It's quite tricky and implicit. Perhaps it's better to add explicit
> check for nil channels to sellock(), so code in both functions will be
> consistent.

ok

[dvyukov, 2011-07-21 17:31:48]

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

Please take another look.

[rsc, 2011-07-21 17:49:54]

LGTM

[rsc, 2011-07-21 17:57:18]

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

runtime: faster select

Make selectsend() accept pointer to the element,
it makes it possible to make Scase fixed-size
and allocate/free Select, all Scase's and all SudoG at once.
As a consequence SudoG freelist die out.

benchmark                       old,ns/op  new,ns/op
BenchmarkSelectUncontended	     1080        558
BenchmarkSelectUncontended-2	      675        264
BenchmarkSelectUncontended-4	      459        205
BenchmarkSelectContended	     1086        560
BenchmarkSelectContended-2	     1775       1672
BenchmarkSelectContended-4	     2668       2149
(on Intel Q6600, 4 cores, 2.4GHz)

benchmark                       old ns/op    new ns/op    delta
BenchmarkSelectUncontended         517.00       326.00  -36.94%
BenchmarkSelectUncontended-2       281.00       166.00  -40.93%
BenchmarkSelectUncontended-4       250.00        83.10  -66.76%
BenchmarkSelectUncontended-8       107.00        47.40  -55.70%
BenchmarkSelectUncontended-16       67.80        41.30  -39.09%
BenchmarkSelectContended           513.00       325.00  -36.65%
BenchmarkSelectContended-2         699.00       628.00  -10.16%
BenchmarkSelectContended-4        1085.00      1092.00   +0.65%
BenchmarkSelectContended-8        3253.00      2477.00  -23.85%
BenchmarkSelectContended-16       5313.00      5116.00   -3.71%
(on Intel E5620, 8 HT cores, 2.4 GHz)

R=rsc, ken
CC=golang-dev
http://codereview.appspot.com/4811041

Committer: Russ Cox <rsc@golang.org>

[albert.strasheim, 2011-07-25 15:11:54]

Hello all

On 2011/07/21 17:57:18, rsc wrote:
> *** Submitted as http://code.google.com/p/go/source/detail?r=2ccdb29d715c ***
> runtime: faster select
> Make selectsend() accept pointer to the element,
> it makes it possible to make Scase fixed-size
> and allocate/free Select, all Scase's and all SudoG at once.
> As a consequence SudoG freelist die out.

This change seems to have broken some of our internal code.

Bug report here:

http://code.google.com/p/go/issues/detail?id=2102

Regards

Albert

[rsc, 2011-07-25 15:25:24]

will fix

[dvyukov, 2011-07-25 15:43:10]

On 2011/07/25 15:11:54, albert.strasheim wrote:
> Hello all
> 
> On 2011/07/21 17:57:18, rsc wrote:
> > *** Submitted as http://code.google.com/p/go/source/detail?r=2ccdb29d715c
***
> > runtime: faster select
> > Make selectsend() accept pointer to the element,
> > it makes it possible to make Scase fixed-size
> > and allocate/free Select, all Scase's and all SudoG at once.
> > As a consequence SudoG freelist die out.
> 
> This change seems to have broken some of our internal code.
> 
> Bug report here:
> 
> http://code.google.com/p/go/issues/detail?id=2102
> 
> Regards
> 
> Albert

Hi Albert,

Sorry for this. Please, try this patch:
hg clpatch 4825043

http://codereview.appspot.com/4825043/