code review 6248049: cmd/6g, cmd/8g: move panicindex calls out of line

cmd/6g, cmd/8g: move panicindex calls out of line

The old code generated for a bounds check was
                CMP
                JLT ok
                CALL panicindex
        ok:
                ...

The new code is (once the linker finishes with it):
                CMP
                JGE panic
                ...
        panic:
                CALL panicindex

which moves the calls out of line, putting more useful
code in each cache line.  This matters especially in tight
loops, such as in Fannkuch.  The benefit is more modest
elsewhere, but real.

From test/bench/go1, amd64:

benchmark                old ns/op    new ns/op    delta
BenchmarkBinaryTree17   6096092000   6088808000   -0.12%
BenchmarkFannkuch11     6151404000   4020463000  -34.64%
BenchmarkGobDecode        28990050     28894630   -0.33%
BenchmarkGobEncode        12406310     12136730   -2.17%
BenchmarkGzip               179923       179903   -0.01%
BenchmarkGunzip              11219        11130   -0.79%
BenchmarkJSONEncode       86429350     86515900   +0.10%
BenchmarkJSONDecode      334593800    315728400   -5.64%
BenchmarkRevcomp25M     1219763000   1180767000   -3.20%
BenchmarkTemplate        492947600    483646800   -1.89%

And 386:

benchmark                old ns/op    new ns/op    delta
BenchmarkBinaryTree17   6354902000   6243000000   -1.76%
BenchmarkFannkuch11     8043769000   7326965000   -8.91%
BenchmarkGobDecode        19010800     18941230   -0.37%
BenchmarkGobEncode        14077500     13792460   -2.02%
BenchmarkGzip               194087       193619   -0.24%
BenchmarkGunzip              12495        12457   -0.30%
BenchmarkJSONEncode      125636400    125451400   -0.15%
BenchmarkJSONDecode      696648600    685032800   -1.67%
BenchmarkRevcomp25M     2058088000   2052545000   -0.27%
BenchmarkTemplate        602140000    589876800   -2.04%

To implement this, two new instruction forms:

        JLT target      // same as always
        JLT $0, target  // branch expected not taken
        JLT $1, target  // branch expected taken

The linker could also emit the prediction prefixes, but it
does not: expected taken branches are reversed so that the
expected case is not taken (as in example above), and
the default expectaton for such a jump is not taken
already.

[rsc, 2012-05-25 06:44:59]

Hello golang-dev@googlegroups.com,

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

[gri, 2012-05-25 17:37:11]

This is great.

I've done this in the code gens of V8 and the JVM in the past - always
moved every code branch that was unlikely to be executed the end. The
IR had a special mechanism just for that (and often those stubs - of
which there were many - could be shared as well, thus reducing the
overall code size).

Results look good. Don't know what happened to Mandelbrot. It doesn't
use complex numbers (the one in shootout).

- gri



On Thu, May 24, 2012 at 11:44 PM,  <rsc@golang.org> wrote:
> Reviewers: golang-dev_googlegroups.com,
>
> Message:
> Hello golang-dev@googlegroups.com,
>
> I'd like you to review this change to
> https://go.googlecode.com/hg/
>
>
> Description:
> cmd/6g, cmd/8g: move panicindex calls out of line
>
> The old code generated for a bounds check was
>                CMP
>                JLT ok
>                CALL panicindex
>        ok:
>                ...
>
> The new code is (once the linker finishes with it):
>                CMP
>                JGE panic
>                ...
>        panic:
>                CALL panicindex
>
> which moves the calls out of line, putting more useful
> code in each cache line.  This matters especially in tight
> loops, such as in Fannkuch.  The benefit is more modest
> elsewhere, but real.
>
> From test/bench/go1, amd64:
>
> benchmark                old ns/op    new ns/op    delta
> BenchmarkBinaryTree17   6096092000   6088808000   -0.12%
> BenchmarkFannkuch11     6151404000   4020463000  -34.64%
> BenchmarkGobDecode        28990050     28894630   -0.33%
> BenchmarkGobEncode        12406310     12136730   -2.17%
> BenchmarkGzip               179923       179903   -0.01%
> BenchmarkGunzip              11219        11130   -0.79%
> BenchmarkJSONEncode       86429350     86515900   +0.10%
> BenchmarkJSONDecode      334593800    315728400   -5.64%
> BenchmarkRevcomp25M     1219763000   1180767000   -3.20%
> BenchmarkTemplate        492947600    483646800   -1.89%
>
> And 386:
>
> benchmark                old ns/op    new ns/op    delta
> BenchmarkBinaryTree17   6354902000   6243000000   -1.76%
> BenchmarkFannkuch11     8043769000   7326965000   -8.91%
> BenchmarkGobDecode        19010800     18941230   -0.37%
> BenchmarkGobEncode        14077500     13792460   -2.02%
> BenchmarkGzip               194087       193619   -0.24%
> BenchmarkGunzip              12495        12457   -0.30%
> BenchmarkJSONEncode      125636400    125451400   -0.15%
> BenchmarkJSONDecode      696648600    685032800   -1.67%
> BenchmarkRevcomp25M     2058088000   2052545000   -0.27%
> BenchmarkTemplate        602140000    589876800   -2.04%
>
> To implement this, two new instruction forms:
>
>        JLT target      // same as always
>        JLT $0, target  // branch expected not taken
>        JLT $1, target  // branch expected taken
>
> The linker could also emit the prediction prefixes, but it
> does not: expected taken branches are reversed so that the
> expected case is not taken (as in example above), and
> the default expectaton for such a jump is not taken
> already.
>
> Please review this at http://codereview.appspot.com/6248049/
>
> Affected files:
>  M src/cmd/6a/a.y
>  M src/cmd/6a/y.tab.c
>  M src/cmd/6a/y.tab.h
>  M src/cmd/6g/cgen.c
>  M src/cmd/6g/gg.h
>  M src/cmd/6g/ggen.c
>  M src/cmd/6g/gsubr.c
>  M src/cmd/6l/optab.c
>  M src/cmd/6l/pass.c
>  M src/cmd/8a/a.y
>  M src/cmd/8a/y.tab.c
>  M src/cmd/8g/cgen.c
>  M src/cmd/8g/gg.h
>  M src/cmd/8g/ggen.c
>  M src/cmd/8g/gsubr.c
>  M src/cmd/8l/optab.c
>  M src/cmd/8l/pass.c
>
>

[r, 2012-05-26 17:27:34]

why not 5g?

[rsc, 2012-05-28 23:28:43]

On Sat, May 26, 2012 at 1:27 PM,  <r@golang.org> wrote:
> why not 5g?

only because i don't know what the right answer is there.
it seems likely that we should be using a conditional suffix
instead of a jump anyway: the optimization might be entirely
different.

russ

[dave_cheney.net, 2012-05-29 01:23:25]

> only because i don't know what the right answer is there.
> it seems likely that we should be using a conditional suffix
> instead of a jump anyway: the optimization might be entirely
> different.
> 
> russ

The current bound check looks like this 

CMP R3, R1
BLO good
BL runtime.panic
:good 

Ideally the condition should be inverted so the BL is conditional on the result
of the comparison. 

CMP R3, R1
BL.HI runtime.panic
:good

If nothing else, you save a word for each bounds check.

Cheers

Dave

[rsc, 2012-05-29 16:09:36]

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

cmd/6g, cmd/8g: move panicindex calls out of line

The old code generated for a bounds check was
                CMP
                JLT ok
                CALL panicindex
        ok:
                ...

The new code is (once the linker finishes with it):
                CMP
                JGE panic
                ...
        panic:
                CALL panicindex

which moves the calls out of line, putting more useful
code in each cache line.  This matters especially in tight
loops, such as in Fannkuch.  The benefit is more modest
elsewhere, but real.

From test/bench/go1, amd64:

benchmark                old ns/op    new ns/op    delta
BenchmarkBinaryTree17   6096092000   6088808000   -0.12%
BenchmarkFannkuch11     6151404000   4020463000  -34.64%
BenchmarkGobDecode        28990050     28894630   -0.33%
BenchmarkGobEncode        12406310     12136730   -2.17%
BenchmarkGzip               179923       179903   -0.01%
BenchmarkGunzip              11219        11130   -0.79%
BenchmarkJSONEncode       86429350     86515900   +0.10%
BenchmarkJSONDecode      334593800    315728400   -5.64%
BenchmarkRevcomp25M     1219763000   1180767000   -3.20%
BenchmarkTemplate        492947600    483646800   -1.89%

And 386:

benchmark                old ns/op    new ns/op    delta
BenchmarkBinaryTree17   6354902000   6243000000   -1.76%
BenchmarkFannkuch11     8043769000   7326965000   -8.91%
BenchmarkGobDecode        19010800     18941230   -0.37%
BenchmarkGobEncode        14077500     13792460   -2.02%
BenchmarkGzip               194087       193619   -0.24%
BenchmarkGunzip              12495        12457   -0.30%
BenchmarkJSONEncode      125636400    125451400   -0.15%
BenchmarkJSONDecode      696648600    685032800   -1.67%
BenchmarkRevcomp25M     2058088000   2052545000   -0.27%
BenchmarkTemplate        602140000    589876800   -2.04%

To implement this, two new instruction forms:

        JLT target      // same as always
        JLT $0, target  // branch expected not taken
        JLT $1, target  // branch expected taken

The linker could also emit the prediction prefixes, but it
does not: expected taken branches are reversed so that the
expected case is not taken (as in example above), and
the default expectaton for such a jump is not taken
already.

R=golang-dev, gri, r, dave
CC=golang-dev
http://codereview.appspot.com/6248049

[rsc, 2012-05-30 13:32:19]

This CL also ended up containing an experiment that disables stack
splitting in leaf functions. The definition of leaf is very strict: if
the function evaluates x[i], then it might need to call panicindex, so
it's not a leaf.

[mtj1, 2012-05-30 13:43:13]

Russ, speaking of x[i] and possible panics, I have a question about
bounds checking. In this post:

http://dave.cheney.net/?tag=golang

Dave suggests that "Each access the ith element of e requires the
compiler to insert an array bounds checks." I believe this to be an
overstatement. Does the compiler now know enough to realize that only
one check is needed in this body?

If not, this seems low-hanging fruit on performance...

Michael

On Wed, May 30, 2012 at 3:31 PM, Russ Cox <rsc@golang.org> wrote:
> This CL also ended up containing an experiment that disables stack
> splitting in leaf functions. The definition of leaf is very strict: if
> the function evaluates x[i], then it might need to call panicindex, so
> it's not a leaf.



-- 
Michael T. Jones | Chief Technology Advocate  | mtj@google.com |  +1
650-335-5765

[dave_cheney.net, 2012-05-30 13:44:18]

Did 5g get this side effect?

Sent from my iPad

On 30/05/2012, at 23:31, Russ Cox <rsc@golang.org> wrote:

> This CL also ended up containing an experiment that disables stack
> splitting in leaf functions. The definition of leaf is very strict: if
> the function evaluates x[i], then it might need to call panicindex, so
> it's not a leaf.

[rsc, 2012-05-30 14:11:56]

On Wed, May 30, 2012 at 9:44 AM, Dave Cheney <dave@cheney.net> wrote:
> Did 5g get this side effect?

No. It was an experiment that I did not intend to submit. Because of
x[i] making something a non-leaf I expect the effect to be minimal. I
do want to do this in general later, but until more bounds checks are
gone it's not too useful.

Russ

[rsc, 2012-05-30 14:12:57]

On Wed, May 30, 2012 at 9:42 AM, Michael Jones <mtj@google.com> wrote:
> Dave suggests that "Each access the ith element of e requires the
> compiler to insert an array bounds checks." I believe this to be an
> overstatement. Does the compiler now know enough to realize that only
> one check is needed in this body?
>
> If not, this seems low-hanging fruit on performance...

It's not exactly low-hanging but it is definitely the most important.
Once I finish fighting floating point performance step functions I do
plan to address that.

Russ

[mtj1, 2012-05-30 23:48:59]

Metaphorical fruit seems lower the further one is from picking it. ;-)

Another question about Go -- why is range not useful to get addresses?
Maybe a mark (*) added to the value argument would seem sufficient.

On Wed, May 30, 2012 at 4:12 PM, Russ Cox <rsc@golang.org> wrote:
> On Wed, May 30, 2012 at 9:42 AM, Michael Jones <mtj@google.com> wrote:
>> Dave suggests that "Each access the ith element of e requires the
>> compiler to insert an array bounds checks." I believe this to be an
>> overstatement. Does the compiler now know enough to realize that only
>> one check is needed in this body?
>>
>> If not, this seems low-hanging fruit on performance...
>
> It's not exactly low-hanging but it is definitely the most important.
> Once I finish fighting floating point performance step functions I do
> plan to address that.
>
> Russ



-- 
Michael T. Jones | Chief Technology Advocate  | mtj@google.com |  +1
650-335-5765

[rsc, 2012-05-30 23:57:09]

On Wed, May 30, 2012 at 7:48 PM, Michael Jones <mtj@google.com> wrote:
> Metaphorical fruit seems lower the further one is from picking it. ;-)
>
> Another question about Go -- why is range not useful to get addresses?
> Maybe a mark (*) added to the value argument would seem sufficient.

There are definitely times when I would have used that syntax, but
they've never seemed often enough to invent something.

Russ

[mtj1, 2012-05-31 00:00:43]

for i := range z.cols {
                z.cols[i].L = &z.cols[(i+g4-1)%g4]
                z.cols[i].R = &z.cols[(i+1)%g4]
                z.cols[i].u = &z.cols[i].node
                z.cols[i].d = &z.cols[i].node
                z.cols[i].size = 0
                z.cols[i].covered = false
        }

vs

for i,*c := range z.cols {
                c.L = &z.cols[(i+g4-1)%g4]
                c.R = &z.cols[(i+1)%g4]
                c.u = &c.node
                c.d = &c.node
                c.size = 0
                c.covered = false
        }

On Thu, May 31, 2012 at 1:56 AM, Russ Cox <rsc@golang.org> wrote:
> On Wed, May 30, 2012 at 7:48 PM, Michael Jones <mtj@google.com> wrote:
>> Metaphorical fruit seems lower the further one is from picking it. ;-)
>>
>> Another question about Go -- why is range not useful to get addresses?
>> Maybe a mark (*) added to the value argument would seem sufficient.
>
> There are definitely times when I would have used that syntax, but
> they've never seemed often enough to invent something.
>
> Russ



-- 
Michael T. Jones | Chief Technology Advocate  | mtj@google.com |  +1
650-335-5765

[gri, 2012-05-31 00:10:32]

this is not too bad:

for i := range z.cols {
    c := &z.cols[i]
    ...
}

(that said, sometimes I wished I could get the reference directly, but
then again, it's not really making a big difference and probably not
worth the complication)

- gri




On Wed, May 30, 2012 at 5:00 PM, Michael Jones <mtj@google.com> wrote:
> for i := range z.cols {
>                z.cols[i].L = &z.cols[(i+g4-1)%g4]
>                z.cols[i].R = &z.cols[(i+1)%g4]
>                z.cols[i].u = &z.cols[i].node
>                z.cols[i].d = &z.cols[i].node
>                z.cols[i].size = 0
>                z.cols[i].covered = false
>        }
>
> vs
>
> for i,*c := range z.cols {
>                c.L = &z.cols[(i+g4-1)%g4]
>                c.R = &z.cols[(i+1)%g4]
>                c.u = &c.node
>                c.d = &c.node
>                c.size = 0
>                c.covered = false
>        }
>
> On Thu, May 31, 2012 at 1:56 AM, Russ Cox <rsc@golang.org> wrote:
>> On Wed, May 30, 2012 at 7:48 PM, Michael Jones <mtj@google.com> wrote:
>>> Metaphorical fruit seems lower the further one is from picking it. ;-)
>>>
>>> Another question about Go -- why is range not useful to get addresses?
>>> Maybe a mark (*) added to the value argument would seem sufficient.
>>
>> There are definitely times when I would have used that syntax, but
>> they've never seemed often enough to invent something.
>>
>> Russ
>
>
>
> --
> Michael T. Jones | Chief Technology Advocate  | mtj@google.com |  +1
> 650-335-5765

[mtj1, 2012-05-31 01:17:59]

I'll try that and see if it sits well with me.

Just debugged a subtle problem porting a Sudoku solver from C++ to Go.
Undoing the subclassing using embedding was not hard at all; undoing a
subtle error flowing from the lack of chained assignments (a = b = c)
in Go took two half-days (nights) in the hotel room. ;-)

On Thu, May 31, 2012 at 2:10 AM, Robert Griesemer <gri@golang.org> wrote:
> this is not too bad:
>
> for i := range z.cols {
>    c := &z.cols[i]
>    ...
> }
>
> (that said, sometimes I wished I could get the reference directly, but
> then again, it's not really making a big difference and probably not
> worth the complication)
>
> - gri
>
>
>
>
> On Wed, May 30, 2012 at 5:00 PM, Michael Jones <mtj@google.com> wrote:
>> for i := range z.cols {
>>                z.cols[i].L = &z.cols[(i+g4-1)%g4]
>>                z.cols[i].R = &z.cols[(i+1)%g4]
>>                z.cols[i].u = &z.cols[i].node
>>                z.cols[i].d = &z.cols[i].node
>>                z.cols[i].size = 0
>>                z.cols[i].covered = false
>>        }
>>
>> vs
>>
>> for i,*c := range z.cols {
>>                c.L = &z.cols[(i+g4-1)%g4]
>>                c.R = &z.cols[(i+1)%g4]
>>                c.u = &c.node
>>                c.d = &c.node
>>                c.size = 0
>>                c.covered = false
>>        }
>>
>> On Thu, May 31, 2012 at 1:56 AM, Russ Cox <rsc@golang.org> wrote:
>>> On Wed, May 30, 2012 at 7:48 PM, Michael Jones <mtj@google.com> wrote:
>>>> Metaphorical fruit seems lower the further one is from picking it. ;-)
>>>>
>>>> Another question about Go -- why is range not useful to get addresses?
>>>> Maybe a mark (*) added to the value argument would seem sufficient.
>>>
>>> There are definitely times when I would have used that syntax, but
>>> they've never seemed often enough to invent something.
>>>
>>> Russ
>>
>>
>>
>> --
>> Michael T. Jones | Chief Technology Advocate  | mtj@google.com |  +1
>> 650-335-5765



-- 
Michael T. Jones | Chief Technology Advocate  | mtj@google.com |  +1
650-335-5765