code review 6337058: cmd/gc: cache itab lookup in convT2I.

cmd/gc: cache itab lookup in convT2I.

There may be further savings if convT2I can avoid the function call
if the cache is good and T is uintptr-shaped, a la convT2E, but that
will be a follow-up CL.

src/pkg/runtime:
benchmark                  old ns/op    new ns/op    delta
BenchmarkConvT2ISmall             43           15  -64.01%
BenchmarkConvT2IUintptr           45           14  -67.48%
BenchmarkConvT2ILarge            130          101  -22.31%

test/bench/go1:
benchmark                 old ns/op    new ns/op    delta
BenchmarkBinaryTree17    8588997000   8499058000   -1.05%
BenchmarkFannkuch11      5300392000   5358093000   +1.09%
BenchmarkGobDecode         30295580     31040190   +2.46%
BenchmarkGobEncode         18102070     17675650   -2.36%
BenchmarkGzip             774191400    771591400   -0.34%
BenchmarkGunzip           245915100    247464100   +0.63%
BenchmarkJSONEncode       123577000    121423050   -1.74%
BenchmarkJSONDecode       451969800    596256200  +31.92%
BenchmarkMandelbrot200     10060050     10072880   +0.13%
BenchmarkParse             10989840     11037710   +0.44%
BenchmarkRevcomp         1782666000   1716864000   -3.69%
BenchmarkTemplate         798286600    723234400   -9.40%

[nigeltao, 2012-06-26 17:58:38]

Hello rsc@golang.org (cc: daniel.morsing@gmail.com, dave@cheney.net,
golang-dev@googlegroups.com),

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

[nigeltao, 2012-06-26 18:01:35]

On 26 June 2012 10:58,  <nigeltao@golang.org> wrote:
> BenchmarkJSONDecode       451969800    596256200  +31.92%

I'm not sure why JSONDecode regressed so much on linux/amd64. I'm
still poking at it, but I would be curious to know if it's
reproducible for other people. I'm also curious what effect it has on
ARM.

[bradfitz, 2012-06-26 18:01:53]

I assume BenchmarkJSONDecode isn't actually 32% slower, and this is just
because code (stacks?) moved around and we got unlucky.

But makes me question the value of that/these benchmarks.

Is BenchmarkTemplate actually faster or did we just get lucky there?


On Tue, Jun 26, 2012 at 10:58 AM, <nigeltao@golang.org> wrote:

> Reviewers: rsc,
>
> Message:
> Hello rsc@golang.org (cc: daniel.morsing@gmail.com, dave@cheney.net,
> golang-dev@googlegroups.com),
>
> I'd like you to review this change to
> https://go.googlecode.com/hg/
>
>
> Description:
> cmd/gc: cache itab lookup in convT2I.
>
> There may be further savings if convT2I can avoid the function call
> if the cache is good and T is uintptr-shaped, a la convT2E, but that
> will be a follow-up CL.
>
> src/pkg/runtime:
> benchmark                  old ns/op    new ns/op    delta
> BenchmarkConvT2ISmall             43           15  -64.01%
> BenchmarkConvT2IUintptr           45           14  -67.48%
> BenchmarkConvT2ILarge            130          101  -22.31%
>
> test/bench/go1:
> benchmark                 old ns/op    new ns/op    delta
> BenchmarkBinaryTree17    8588997000   8499058000   -1.05%
> BenchmarkFannkuch11      5300392000   5358093000   +1.09%
> BenchmarkGobDecode         30295580     31040190   +2.46%
> BenchmarkGobEncode         18102070     17675650   -2.36%
> BenchmarkGzip             774191400    771591400   -0.34%
> BenchmarkGunzip           245915100    247464100   +0.63%
> BenchmarkJSONEncode       123577000    121423050   -1.74%
> BenchmarkJSONDecode       451969800    596256200  +31.92%
> BenchmarkMandelbrot200     10060050     10072880   +0.13%
> BenchmarkParse             10989840     11037710   +0.44%
> BenchmarkRevcomp         1782666000   1716864000   -3.69%
> BenchmarkTemplate         798286600    723234400   -9.40%
>
> Please review this at
http://codereview.appspot.com/**6337058/<http://codereview.appspot.com/6337058/>
>
> Affected files:
>  M src/cmd/5g/gsubr.c
>  M src/cmd/6g/gsubr.c
>  M src/cmd/8g/gsubr.c
>  M src/cmd/gc/builtin.c
>  M src/cmd/gc/go.h
>  M src/cmd/gc/lex.c
>  M src/cmd/gc/obj.c
>  M src/cmd/gc/reflect.c
>  M src/cmd/gc/walk.c
>  M src/pkg/runtime/iface.c
>  M src/pkg/runtime/iface_test.go
>  M test/convT2X.go
>
>
>

[nigeltao, 2012-06-26 18:25:36]

On 26 June 2012 11:01, Brad Fitzpatrick <bradfitz@golang.org> wrote:
> Is BenchmarkTemplate actually faster or did we just get lucky there?

I'm willing to believe so. For example, Mr. Cheney's hammer suggests
that "go test -test.bench=Template" does a million more convT2Is (out
of 6 or 7 million for -test.bench=.) than "go test
-test.bench=Fannkuch". But that's a pretty crude metric: it doesn't
separate BenchmarkTemplate's conversions from package testing's
conversions, and the raw number depends on the number of iterations,
which depends on timings.

Still poking at JSONDecode...

[DMorsing, 2012-06-26 19:39:59]

On Tue, 2012-06-26 at 11:01 -0700, Nigel Tao wrote:
> On 26 June 2012 10:58,  <nigeltao@golang.org> wrote:
> > BenchmarkJSONDecode       451969800    596256200  +31.92%
> 
> I'm not sure why JSONDecode regressed so much on linux/amd64. I'm
> still poking at it, but I would be curious to know if it's
> reproducible for other people. I'm also curious what effect it has on
> ARM.

The benchmark hit on JSONDecode pops up on my machine as well

benchmark                 old ns/op    new ns/op    delta
BenchmarkJSONDecode       304121200    414444200  +36.28%

It might be better to put the cache pointer loading inside itab(). If we
decide to inline parts of the interface generation for T2I conversions
(like OEFACE), itab() will called separately, and we would have to
construct the cache pointer loading branch at every call site.

As an aside, I think you could generate these interfaces at link time,
but that would be a much bigger task and it would complicate things so
much that I don't know if it's worth it.

Regards,
Daniel Morsing

[peterGo, 2012-06-26 19:50:19]

On 2012/06/26 18:01:35, nigeltao wrote:
> On 26 June 2012 10:58,  <mailto:nigeltao@golang.org> wrote:
> > BenchmarkJSONDecode &nbsp; &nbsp; &nbsp; 451969800 &nbsp; &nbsp;596256200
&nbsp;+31.92%
> 
> I'm not sure why JSONDecode regressed so much on linux/amd64. I'm
> still poking at it, but I would be curious to know if it's
> reproducible for other people.

Yes.

$ uname -a
Linux M13 3.2.0-23-generic #36-Ubuntu SMP Tue Apr 10 20:39:51 UTC 2012 x86_64
x86_64 x86_64 GNU/Linux

Intel Core i5-2390T CPU @ 2.70GHz × 4 

$ hg id
d8bd45866999+ tip

benchmark                old ns/op      new ns/op      delta
BenchmarkJSONEncode     70,209,625     71,818,925     +2.24%
BenchmarkJSONDecode    243,272,600    336,194,600    +27.64%

Peter

[nigeltao, 2012-06-26 20:00:32]

On 26 June 2012 11:01, Brad Fitzpatrick <bradfitz@golang.org> wrote:
> I assume BenchmarkJSONDecode isn't actually 32% slower, and this is just
> because code (stacks?) moved around and we got unlucky.

The CPU profile of BenchmarkJSONDecode, after this patch, starts with:

Total: 363 samples
      36   9.9%   9.9%       36   9.9% runtime.memmove
      32   8.8%  18.7%       59  16.3% runtime.newstack
      27   7.4%  26.2%       59  16.3% runtime.oldstack
      23   6.3%  32.5%       48  13.2% reflect.StructTag.Get
      16   4.4%  36.9%      214  59.0% encoding/json.(*decodeState).object
      13   3.6%  40.5%       36   9.9% encoding/json.(*decodeState).indirect
      13   3.6%  44.1%       21   5.8% encoding/json.(*decodeState).scanWhile
      12   3.3%  47.4%       12   3.3% strconv.contains

Hmm...

[nigeltao, 2012-06-26 20:19:58]

On 26 June 2012 12:38, Daniel Morsing <daniel.morsing@gmail.com> wrote:
> It might be better to put the cache pointer loading inside itab(). If we
> decide to inline parts of the interface generation for T2I conversions
> (like OEFACE), itab() will called separately, and we would have to
> construct the cache pointer loading branch at every call site.

Possibly. The branch may or may not be cheaper than a call, though.

Note also that itab is used by convI2I, not just convT2I. If package a
declares a type T and returns it as I1, and package b takes an I1 and
converts it to an I2, then static analysis can't easily determine that
it needs to reserve a word to cache the T-to-I2 conversion. I suppose
that you could just pass a NULL **Itab in that case, but it's not a
clear win.


> As an aside, I think you could generate these interfaces at link time,
> but that would be a much bigger task and it would complicate things so
> much that I don't know if it's worth it.

Yeah, I think you could, but it's out of scope for this change. One
thing is that you want the linker to eliminate the code for type T if
it's unreachable from main.main, but adding init code to populate the
itab cache creates a reference to T, so (riffing off the top of my
head) you have to teach the toolchain about weak inits.

[DMorsing, 2012-06-26 20:32:59]

Had a closer look.

http://codereview.appspot.com/6337058/diff/3/src/cmd/gc/builtin.c
File src/cmd/gc/builtin.c (right):

http://codereview.appspot.com/6337058/diff/3/src/cmd/gc/builtin.c#newcode44
src/cmd/gc/builtin.c:44: "func @\"\".convT2I(@\"\".typ *byte, @\"\".typ2 *byte,
@\"\".cache *uintptr, @\"\".elem any) (@\"\".ret any)\n"
This needs to have been generated from cmd/gc/runtime.go instead of being edited
in manually.

http://codereview.appspot.com/6337058/diff/3/src/pkg/runtime/iface.c
File src/pkg/runtime/iface.c (right):

http://codereview.appspot.com/6337058/diff/3/src/pkg/runtime/iface.c#newcode198
src/pkg/runtime/iface.c:198: if(!*cache)
Doesn't this need some sort of synchronization? Multiple goroutines may try to
modify *cache at once.

[DMorsing, 2012-06-26 20:45:42]

On Tue, 2012-06-26 at 13:19 -0700, Nigel Tao wrote:
> On 26 June 2012 12:38, Daniel Morsing <daniel.morsing@gmail.com> wrote:
> > It might be better to put the cache pointer loading inside itab(). If we
> > decide to inline parts of the interface generation for T2I conversions
> > (like OEFACE), itab() will called separately, and we would have to
> > construct the cache pointer loading branch at every call site.
> 
> Possibly. The branch may or may not be cheaper than a call, though.
> 
> Note also that itab is used by convI2I, not just convT2I. If package a
> declares a type T and returns it as I1, and package b takes an I1 and
> converts it to an I2, then static analysis can't easily determine that
> it needs to reserve a word to cache the T-to-I2 conversion. I suppose
> that you could just pass a NULL **Itab in that case, but it's not a
> clear win.
> 

I think we can disregard my earlier comment. itab() has to be exposed to
the compiler somehow if we go down the inlining route, so we could just
put the cache loading inside the wrapper function that exposes itab().

[nigeltao, 2012-06-26 21:43:13]

http://codereview.appspot.com/6337058/diff/3/src/cmd/gc/builtin.c
File src/cmd/gc/builtin.c (right):

http://codereview.appspot.com/6337058/diff/3/src/cmd/gc/builtin.c#newcode44
src/cmd/gc/builtin.c:44: "func @\"\".convT2I(@\"\".typ *byte, @\"\".typ2 *byte,
@\"\".cache *uintptr, @\"\".elem any) (@\"\".ret any)\n"
On 2012/06/26 20:32:59, DMorsing wrote:
> This needs to have been generated from cmd/gc/runtime.go instead of being
edited
> in manually.

Done.

http://codereview.appspot.com/6337058/diff/3/src/pkg/runtime/iface.c
File src/pkg/runtime/iface.c (right):

http://codereview.appspot.com/6337058/diff/3/src/pkg/runtime/iface.c#newcode198
src/pkg/runtime/iface.c:198: if(!*cache)
On 2012/06/26 20:32:59, DMorsing wrote:
> Doesn't this need some sort of synchronization? Multiple goroutines may try to
> modify *cache at once.

The itab function should be idempotent, and I'm assuming that writing a uintptr
is atomic. I'll let rsc have the definitive say in this.

[dave_cheney.net, 2012-06-26 23:37:03]

linux/arm:

benchmark                 old ns/op    new ns/op    delta
BenchmarkBinaryTree17   37654663000  36924836000   -1.94%
BenchmarkFannkuch11     34433411000  34773925000   +0.99%
BenchmarkGobDecode        115759300    113108800   -2.29%
BenchmarkGobEncode         61251820     60582880   -1.09%
BenchmarkGzip            5657135000   5548889000   -1.91%
BenchmarkGunzip          1191772000   1189667000   -0.18%
BenchmarkJSONEncode       805096400    733081200   -8.94%
BenchmarkJSONDecode      2685211000   2287323000  -14.82%
BenchmarkMandelbrot200     45551140     45515140   -0.08%
BenchmarkParse             60627440     55930780   -7.75%
BenchmarkRevcomp          143875100    145361300   +1.03%
BenchmarkTemplate        5809356000   5175629000  -10.91%

benchmark                  old MB/s     new MB/s  speedup
BenchmarkGobDecode             6.63         6.79    1.02x
BenchmarkGobEncode            12.53        12.67    1.01x
BenchmarkGzip                  3.43         3.50    1.02x
BenchmarkGunzip               16.28        16.31    1.00x
BenchmarkJSONEncode            2.41         2.65    1.10x
BenchmarkJSONDecode            0.72         0.85    1.18x
BenchmarkParse                 0.96         1.04    1.08x
BenchmarkRevcomp              17.67        17.49    0.99x
BenchmarkTemplate              0.33         0.37    1.12x

[DMorsing, 2012-06-29 13:56:57]

I'd really like to know what's up with the JSON performance regression. Dave's
numbers seem to suggest it's some weird alignment/size issue. What does a 386
version of the test do?

In the meantime, Have another review comment.

http://codereview.appspot.com/6337058/diff/11003/src/pkg/runtime/iface.c
File src/pkg/runtime/iface.c (right):

http://codereview.appspot.com/6337058/diff/11003/src/pkg/runtime/iface.c#newc...
src/pkg/runtime/iface.c:198: if(!*cache)
The runtime package has code for atomically storing a pointer that isn't just a
plain assignment. I guess there isn't a guarantee for it being atomic.

Since itab() is already synchronized, the change should just be:

Itab *tmp;
tmp = runtime.atomicloadp(cache);
if(!tmp) {
    tmp = itab(inter, t, 0);
    runtime.atomicstorep(cache, tmp);
}
ret->tab = tmp;

[rsc, 2012-06-29 14:07:17]

LGTM

http://codereview.appspot.com/6337058/diff/11003/src/pkg/runtime/iface.c
File src/pkg/runtime/iface.c (right):

http://codereview.appspot.com/6337058/diff/11003/src/pkg/runtime/iface.c#newc...
src/pkg/runtime/iface.c:198: if(!*cache)
On 2012/06/29 13:56:57, DMorsing wrote:
> The runtime package has code for atomically storing a pointer that isn't just
a
> plain assignment. I guess there isn't a guarantee for it being atomic.
> 
> Since itab() is already synchronized, the change should just be:
> 
> Itab *tmp;
> tmp = runtime.atomicloadp(cache);
> if(!tmp) {
>     tmp = itab(inter, t, 0);
>     runtime.atomicstorep(cache, tmp);
> }
> ret->tab = tmp;

I agree, although s/tmp/tab/

[luriel, 2012-06-29 21:53:02]

On Fri, Jun 29, 2012 at 3:56 PM,  <daniel.morsing@gmail.com> wrote:
> I'd really like to know what's up with the JSON performance regression.
> Dave's numbers seem to suggest it's some weird alignment/size issue.

I think Russ has mentioned in the past that the JSON benchmarks
numbers jump around if you look at them funny, seems to be some
alignment thing, there was some discussion about it some weeks ago in
the list, IIRC the conclusion was "dark magic", ie., the JSON numbers
are best taken with a huge grain of salt.

Uriel


>
> In the meantime, Have another review comment.
>
>
> http://codereview.appspot.com/6337058/diff/11003/src/pkg/runtime/iface.c
> File src/pkg/runtime/iface.c (right):
>
>
http://codereview.appspot.com/6337058/diff/11003/src/pkg/runtime/iface.c#newc...
> src/pkg/runtime/iface.c:198: if(!*cache)
> The runtime package has code for atomically storing a pointer that isn't
> just a plain assignment. I guess there isn't a guarantee for it being
> atomic.
>
> Since itab() is already synchronized, the change should just be:
>
> Itab *tmp;
> tmp = runtime.atomicloadp(cache);
> if(!tmp) {
>     tmp = itab(inter, t, 0);
>     runtime.atomicstorep(cache, tmp);
> }
> ret->tab = tmp;
>
> http://codereview.appspot.com/6337058/

[rsc, 2012-06-29 22:07:08]

The JSON numbers are troubling but not a reason to hold up this CL.
Since we advise users to work from the official release points, it is
okay if tip gets a little slower. I do intend to investigate before
this CL becomes part of a release (in Go 1.1) but it's okay not to
worry about it for now. I filed issue 3787 so we don't forget.

Russ

[nigeltao, 2012-07-02 23:08:37]

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

cmd/gc: cache itab lookup in convT2I.

There may be further savings if convT2I can avoid the function call
if the cache is good and T is uintptr-shaped, a la convT2E, but that
will be a follow-up CL.

src/pkg/runtime:
benchmark                  old ns/op    new ns/op    delta
BenchmarkConvT2ISmall             43           15  -64.01%
BenchmarkConvT2IUintptr           45           14  -67.48%
BenchmarkConvT2ILarge            130          101  -22.31%

test/bench/go1:
benchmark                 old ns/op    new ns/op    delta
BenchmarkBinaryTree17    8588997000   8499058000   -1.05%
BenchmarkFannkuch11      5300392000   5358093000   +1.09%
BenchmarkGobDecode         30295580     31040190   +2.46%
BenchmarkGobEncode         18102070     17675650   -2.36%
BenchmarkGzip             774191400    771591400   -0.34%
BenchmarkGunzip           245915100    247464100   +0.63%
BenchmarkJSONEncode       123577000    121423050   -1.74%
BenchmarkJSONDecode       451969800    596256200  +31.92%
BenchmarkMandelbrot200     10060050     10072880   +0.13%
BenchmarkParse             10989840     11037710   +0.44%
BenchmarkRevcomp         1782666000   1716864000   -3.69%
BenchmarkTemplate         798286600    723234400   -9.40%

R=rsc, bradfitz, go.peter.90, daniel.morsing, dave, uriel
CC=golang-dev
http://codereview.appspot.com/6337058

[cw, 2012-07-03 05:07:04]

> BenchmarkJSONDecode       451969800    596256200  +31.92%

Any idea why this got so much slower?

[bradfitz, 2012-07-03 05:10:10]

On Mon, Jul 2, 2012 at 10:07 PM, Chris Wedgwood <cw@f00f.org> wrote:

> > BenchmarkJSONDecode       451969800    596256200  +31.92%
>
> Any idea why this got so much slower?
>

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