code review 229049: math: faster hypot

math: faster hypot

Use hardware sqrt for faster hypot; preserve software-only
hypot as hypotGo (like sqrtGo); enable benchmarking of
hypotGo.

[Charlie Dorian, 2010-03-04 03:29:34]

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

I'd like you to review this change.

[rsc, 2010-03-04 17:32:24]

Thanks.  You said cbrt is 10% faster.
Why?  What changes in the generated code?

http://codereview.appspot.com/229049/diff/14/17
File src/pkg/math/cbrt.go (right):

http://codereview.appspot.com/229049/diff/14/17#newcode71
src/pkg/math/cbrt.go:71: y = y * (t + x) / (s + t)
Why does this matter?
If this generates better code than using *=, then there's
a compiler bug that I'd rather fix instead.

http://codereview.appspot.com/229049/diff/14/17#newcode74
src/pkg/math/cbrt.go:74: y = y - y*(((14.0/81.0)*s-(2.0/9.0))*s+(1.0/3.0))*s
Same here for -=.

http://codereview.appspot.com/229049/diff/14/19
File src/pkg/math/hypot_port.go (right):

http://codereview.appspot.com/229049/diff/14/19#newcode22
src/pkg/math/hypot_port.go:22: func hypotGo(p, q float64) float64 {
What's faster on amd64?  Hypot or hypotGo?
If the answer is Hypot, then you can delete this file.

[Charlie Dorian, 2010-03-04 18:10:01]

I'll answer your other comments later, but for now, just FYI:
math_test.BenchmarkHypot    100000000            16 ns/op
math_test.BenchmarkHypotGo    20000000           108 ns/op
(darwin, amd64)

On Thu, Mar 4, 2010 at 12:32 PM, <rsc@golang.org> wrote:
http://codereview.appspot.com/229049/diff/14/19

>
> http://codereview.appspot.com/229049/diff/14/19#newcode22
> src/pkg/math/hypot_port.go:22: func hypotGo(p, q float64) float64 {
> What's faster on amd64?  Hypot or hypotGo?
> If the answer is Hypot, then you can delete this file.
>
>
> http://codereview.appspot.com/229049/show
>

[rsc, 2010-03-04 18:12:24]

On Thu, Mar 4, 2010 at 10:10, Charles Dorian <cldorian@gmail.com> wrote:
> I'll answer your other comments later, but for now, just FYI:
> math_test.BenchmarkHypot    100000000            16 ns/op
> math_test.BenchmarkHypotGo    20000000           108 ns/op

Right, I forgot that amd64 had hardware sqrt.
My actual question was whether HypotGo was
faster than Hypot using the software sqrt (sqrtGo).

If HypotGo is slower than Hypot+sqrtGo, then
it can be deleted entirely.

Russ

[Charlie Dorian, 2010-03-04 23:53:24]

Yes, HypotGo is faster than Hypot+sqrtGo :
math_test.BenchmarkHypot    10000000           282 ns/op
math_test.BenchmarkHypotGo    20000000           108 ns/op

So, HypotGo remains a part of this CL.

On Thu, Mar 4, 2010 at 1:12 PM, Russ Cox <rsc@golang.org> wrote:

> On Thu, Mar 4, 2010 at 10:10, Charles Dorian <cldorian@gmail.com> wrote:
> > I'll answer your other comments later, but for now, just FYI:
> > math_test.BenchmarkHypot    100000000            16 ns/op
> > math_test.BenchmarkHypotGo    20000000           108 ns/op
>
> Right, I forgot that amd64 had hardware sqrt.
> My actual question was whether HypotGo was
> faster than Hypot using the software sqrt (sqrtGo).
>
> If HypotGo is slower than Hypot+sqrtGo, then
> it can be deleted entirely.
>
> Russ
>

[Charlie Dorian, 2010-03-05 01:03:59]

Thanks for the review.

On Thu, Mar 4, 2010 at 12:32 PM, <rsc@golang.org> wrote:

> Thanks.  You said cbrt is 10% faster.
> Why?  What changes in the generated code?
>

In each case, for both 8g and 6g, better code is generated
if I don't use opEquals.  Better use of registers, no indirect
stores, no wasted instructions (for example line 0152, just below;
AX is never used again).  The code for comparison is below.

>
> http://codereview.appspot.com/229049/diff/14/17#newcode71
> src/pkg/math/cbrt.go:71: y = y * (t + x) / (s + t)
> Why does this matter?
> If this generates better code than using *=, then there's
> a compiler bug that I'd rather fix instead.
>

8g code; slower version first

y *= (t + x) / (s + t)
0145 (cbrt.go:74) FMOVD   t+-48(SP),F0
0146 (cbrt.go:74) FADDD   x+0(FP),F0
0147 (cbrt.go:74) FMOVD   s+-40(SP),F0
0148 (cbrt.go:74) FADDD   t+-48(SP),F0
0149 (cbrt.go:74) FDIVDP  F0,F1
0150 (cbrt.go:74) FMOVDP  F0,autotmp_0012+-100(SP)
0151 (cbrt.go:74) LEAL    y+-32(SP),BX
0152 (cbrt.go:74) MOVL    BX,AX
0153 (cbrt.go:74) FMOVD   (BX),F0
0154 (cbrt.go:74) FMULD   autotmp_0012+-100(SP),F0
0155 (cbrt.go:74) FMOVDP  F0,autotmp_0014+-112(SP)
0156 (cbrt.go:74) FMOVD   autotmp_0014+-112(SP),F0
0157 (cbrt.go:74) FMOVDP  F0,(BX)

y = y * (t + x) / (s + t)
0145 (cbrt_test.go:74) FMOVD   t+-48(SP),F0
0146 (cbrt_test.go:74) FADDD   x+0(FP),F0
0147 (cbrt_test.go:74) FMULD   y+-32(SP),F0
0148 (cbrt_test.go:74) FMOVD   s+-40(SP),F0
0149 (cbrt_test.go:74) FADDD   t+-48(SP),F0
0150 (cbrt_test.go:74) FDIVDP  F0,F1
0151 (cbrt_test.go:74) FMOVDP  F0,y+-32(SP)

6g code; slower code first

y *= (t + x) / (s + t)
0145 (cbrt.go:71) ADDSD   X7,X0
0146 (cbrt.go:71) MOVSD   X6,X1
0147 (cbrt.go:71) ADDSD   X5,X1
0148 (cbrt.go:71) DIVSD   X1,X0
0149 (cbrt.go:71) LEAQ    y+-32(SP),BX
0150 (cbrt.go:71) MOVSD   (BX),X1
0151 (cbrt.go:71) MULSD   X0,X1
0152 (cbrt.go:71) MOVSD   X1,(BX)

y = y * (t + x) / (s + t)
0142 (cbrt_test.go:72) ADDSD   X8,X0
0143 (cbrt_test.go:72) MULSD   X5,X0
0144 (cbrt_test.go:72) MOVSD   X7,X1
0145 (cbrt_test.go:72) ADDSD   X6,X1
0146 (cbrt_test.go:72) DIVSD   X1,X0
0147 (cbrt_test.go:72) MOVSD   X0,X5


>
> http://codereview.appspot.com/229049/diff/14/17#newcode74
> src/pkg/math/cbrt.go:74: y = y -
> y*(((14.0/81.0)*s-(2.0/9.0))*s+(1.0/3.0))*s
> Same here for -=.
>

8g code; slower version first

y -= y * (((14.0/81.0)*s-(2.0/9.0))*s + (1.0 / 3.0)) * s
0164 (cbrt.go:77) FMOVD   $(1.72839506172839500e-01),F0
0165 (cbrt.go:77) FMULD   s+-40(SP),F0
0166 (cbrt.go:77) FSUBD   $(2.22222222222222200e-01),F0
0167 (cbrt.go:77) FMULD   s+-40(SP),F0
0168 (cbrt.go:77) FADDD   $(3.33333333333333300e-01),F0
0169 (cbrt.go:77) FMULD   y+-32(SP),F0
0170 (cbrt.go:77) FMULD   s+-40(SP),F0
0171 (cbrt.go:77) FMOVDP  F0,autotmp_0015+-120(SP)
0172 (cbrt.go:77) LEAL    y+-32(SP),BX
0173 (cbrt.go:77) MOVL    BX,AX
0174 (cbrt.go:77) FMOVD   (BX),F0
0175 (cbrt.go:77) FSUBD   autotmp_0015+-120(SP),F0
0176 (cbrt.go:77) FMOVDP  F0,autotmp_0017+-132(SP)
0177 (cbrt.go:77) FMOVD   autotmp_0017+-132(SP),F0
0178 (cbrt.go:77) FMOVDP  F0,(BX)

y = y - y * (((14.0/81.0)*s-(2.0/9.0))*s + (1.0 / 3.0)) * s
0158 (cbrt_test.go:77) FMOVD   $(1.72839506172839500e-01),F0
0159 (cbrt_test.go:77) FMULD   s+-40(SP),F0
0160 (cbrt_test.go:77) FSUBD   $(2.22222222222222200e-01),F0
0161 (cbrt_test.go:77) FMULD   s+-40(SP),F0
0162 (cbrt_test.go:77) FADDD   $(3.33333333333333300e-01),F0
0163 (cbrt_test.go:77) FMULD   y+-32(SP),F0
0164 (cbrt_test.go:77) FMULD   s+-40(SP),F0
0165 (cbrt_test.go:77) FSUBRD  y+-32(SP),F0
0166 (cbrt_test.go:77) FMOVDP  F0,y+-32(SP)

6g code; slower code first

y -= y*(((14.0/81.0)*s-(2.0/9.0))*s+(1.0/3.0))*s
0161 (cbrt.go:74) MOVSD   $(1.72839506172839500e-01),X0
0162 (cbrt.go:74) MULSD   X5,X0
0163 (cbrt.go:74) MOVSD   $(2.22222222222222200e-01),X1
0164 (cbrt.go:74) SUBSD   X1,X0
0165 (cbrt.go:74) MULSD   X5,X0
0166 (cbrt.go:74) MOVSD   $(3.33333333333333300e-01),X1
0167 (cbrt.go:74) ADDSD   X1,X0
0168 (cbrt.go:74) MOVSD   y+-32(SP),X1
0169 (cbrt.go:74) MULSD   X1,X0
0170 (cbrt.go:74) MULSD   X5,X0
0171 (cbrt.go:74) MOVSD   (BX),X1
0172 (cbrt.go:74) SUBSD   X0,X1
0173 (cbrt.go:74) MOVSD   X1,(BX)

y = y - y*(((14.0/81.0)*s-(2.0/9.0))*s+(1.0/3.0))*s
0153 (cbrt_test.go:75) MOVSD   $(1.72839506172839500e-01),X0
0154 (cbrt_test.go:75) MULSD   X6,X0
0155 (cbrt_test.go:75) MOVSD   $(2.22222222222222200e-01),X1
0156 (cbrt_test.go:75) SUBSD   X1,X0
0157 (cbrt_test.go:75) MULSD   X6,X0
0158 (cbrt_test.go:75) MOVSD   $(3.33333333333333300e-01),X1
0159 (cbrt_test.go:75) ADDSD   X1,X0
0160 (cbrt_test.go:75) MULSD   X5,X0
0161 (cbrt_test.go:75) MULSD   X6,X0
0162 (cbrt_test.go:75) MOVSD   X5,X1
0163 (cbrt_test.go:75) SUBSD   X0,X1
0164 (cbrt_test.go:75) MOVSD   X1,X5


>
> http://codereview.appspot.com/229049/show
>

[rsc, 2010-03-05 04:19:32]

Thanks.  I'll get rid of the temporaries and the LEAQs.

[rsc, 2010-03-05 23:35:45]

If you update, you'll find that the compilers generate
the same code with and without -= or *= as long as
the expressions are the same.  The code generated
for *= is still slightly different from what you saw for
    y = y * (t + x) / (s + t)
but that's because in the *= version the division must
happen first and in the version above the multiply must
happen first - they're different programs.  Cbrt should
get faster now on its own; we'll have to watch the
benchmark pages.

Russ

[rsc, 2010-03-05 23:36:55]

Re this CL:

Please remove cbrt.go.
Please fix the copyright year in hypot.go (20010).
Otherwise looks good.

Russ

[Charlie Dorian, 2010-03-06 00:28:33]

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

Please take another look.

[Charlie Dorian, 2010-03-06 00:33:57]

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

Please take another look.

[Charlie Dorian, 2010-03-06 00:35:11]

Thanks.

On Fri, Mar 5, 2010 at 6:36 PM, Russ Cox <rsc@golang.org> wrote:

> Re this CL:
>
> Please remove cbrt.go.
>
Done.

> Please fix the copyright year in hypot.go (20010).
>
Done.

> Otherwise looks good.
>
> Russ
>

[Charlie Dorian, 2010-03-06 00:36:25]

Biggest change noticed so far was sqrtGo, from 459 to 393 ns

On Fri, Mar 5, 2010 at 6:35 PM, Russ Cox <rsc@golang.org> wrote:

> If you update, you'll find that the compilers generate
> the same code with and without -= or *= as long as
> the expressions are the same.  The code generated
> for *= is still slightly different from what you saw for
>     y = y * (t + x) / (s + t)
> but that's because in the *= version the division must
> happen first and in the version above the multiply must
> happen first - they're different programs.  Cbrt should
> get faster now on its own; we'll have to watch the
> benchmark pages.
>
> Russ
>

[rsc, 2010-03-06 00:44:56]

LGTM

[rsc, 2010-03-06 00:45:47]

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

math: faster hypot

Use hardware sqrt for faster hypot; preserve software-only
hypot as hypotGo (like sqrtGo); enable benchmarking of
hypotGo.

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

Committer: Russ Cox <rsc@golang.org>