From cda633b39b1353d23965337fb3118a3fc532a0c1 Mon Sep 17 00:00:00 2001 From: Alberto Donizetti Date: Wed, 11 May 2016 20:55:53 +0200 Subject: [PATCH] math/big: avoid allocation in float.{Add, Sub} when there's no aliasing MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit name old time/op new time/op delta FloatAdd/10-4 116ns ± 1% 82ns ± 0% -28.74% (p=0.008 n=5+5) FloatAdd/100-4 124ns ± 0% 86ns ± 1% -30.34% (p=0.016 n=4+5) FloatAdd/1000-4 192ns ± 1% 123ns ± 0% -35.94% (p=0.008 n=5+5) FloatAdd/10000-4 826ns ± 0% 438ns ± 0% -46.99% (p=0.000 n=4+5) FloatAdd/100000-4 6.82µs ± 1% 3.36µs ± 0% -50.74% (p=0.008 n=5+5) FloatSub/10-4 108ns ± 1% 77ns ± 1% -29.06% (p=0.008 n=5+5) FloatSub/100-4 115ns ± 0% 79ns ± 0% -31.48% (p=0.029 n=4+4) FloatSub/1000-4 168ns ± 0% 99ns ± 0% -41.09% (p=0.029 n=4+4) FloatSub/10000-4 690ns ± 2% 288ns ± 1% -58.24% (p=0.008 n=5+5) FloatSub/100000-4 5.37µs ± 1% 2.10µs ± 1% -60.89% (p=0.008 n=5+5) name old alloc/op new alloc/op delta FloatAdd/10-4 48.0B ± 0% 0.0B ±NaN% -100.00% (p=0.008 n=5+5) FloatAdd/100-4 64.0B ± 0% 0.0B ±NaN% -100.00% (p=0.008 n=5+5) FloatAdd/1000-4 176B ± 0% 0B ±NaN% -100.00% (p=0.008 n=5+5) FloatAdd/10000-4 1.41kB ± 0% 0.00kB ±NaN% -100.00% (p=0.008 n=5+5) FloatAdd/100000-4 13.6kB ± 0% 0.0kB ±NaN% -100.00% (p=0.008 n=5+5) FloatSub/10-4 48.0B ± 0% 0.0B ±NaN% -100.00% (p=0.008 n=5+5) FloatSub/100-4 64.0B ± 0% 0.0B ±NaN% -100.00% (p=0.008 n=5+5) FloatSub/1000-4 176B ± 0% 0B ±NaN% -100.00% (p=0.008 n=5+5) FloatSub/10000-4 1.41kB ± 0% 0.00kB ±NaN% -100.00% (p=0.008 n=5+5) FloatSub/100000-4 13.6kB ± 0% 0.0kB ±NaN% -100.00% (p=0.008 n=5+5) Fixes #14868 Change-Id: Ia2b8b1a8ef0868288ecb25f812b17bd03ff40d1c Reviewed-on: https://go-review.googlesource.com/23568 Reviewed-by: Robert Griesemer --- src/math/big/float.go | 44 +++++++++++++++++++++++++++----------- src/math/big/float_test.go | 38 ++++++++++++++++++++++++++++++++ 2 files changed, 70 insertions(+), 12 deletions(-) diff --git a/src/math/big/float.go b/src/math/big/float.go index 7a9c2b3dfb..aabd7b4477 100644 --- a/src/math/big/float.go +++ b/src/math/big/float.go @@ -1210,20 +1210,30 @@ func (z *Float) uadd(x, y *Float) { ex := int64(x.exp) - int64(len(x.mant))*_W ey := int64(y.exp) - int64(len(y.mant))*_W + al := alias(z.mant, x.mant) || alias(z.mant, y.mant) + // TODO(gri) having a combined add-and-shift primitive // could make this code significantly faster switch { case ex < ey: - // cannot re-use z.mant w/o testing for aliasing - t := nat(nil).shl(y.mant, uint(ey-ex)) - z.mant = z.mant.add(x.mant, t) + if al { + t := nat(nil).shl(y.mant, uint(ey-ex)) + z.mant = z.mant.add(x.mant, t) + } else { + z.mant = z.mant.shl(y.mant, uint(ey-ex)) + z.mant = z.mant.add(x.mant, z.mant) + } default: // ex == ey, no shift needed z.mant = z.mant.add(x.mant, y.mant) case ex > ey: - // cannot re-use z.mant w/o testing for aliasing - t := nat(nil).shl(x.mant, uint(ex-ey)) - z.mant = z.mant.add(t, y.mant) + if al { + t := nat(nil).shl(x.mant, uint(ex-ey)) + z.mant = z.mant.add(t, y.mant) + } else { + z.mant = z.mant.shl(x.mant, uint(ex-ey)) + z.mant = z.mant.add(z.mant, y.mant) + } ex = ey } // len(z.mant) > 0 @@ -1247,18 +1257,28 @@ func (z *Float) usub(x, y *Float) { ex := int64(x.exp) - int64(len(x.mant))*_W ey := int64(y.exp) - int64(len(y.mant))*_W + al := alias(z.mant, x.mant) || alias(z.mant, y.mant) + switch { case ex < ey: - // cannot re-use z.mant w/o testing for aliasing - t := nat(nil).shl(y.mant, uint(ey-ex)) - z.mant = t.sub(x.mant, t) + if al { + t := nat(nil).shl(y.mant, uint(ey-ex)) + z.mant = t.sub(x.mant, t) + } else { + z.mant = z.mant.shl(y.mant, uint(ey-ex)) + z.mant = z.mant.sub(x.mant, z.mant) + } default: // ex == ey, no shift needed z.mant = z.mant.sub(x.mant, y.mant) case ex > ey: - // cannot re-use z.mant w/o testing for aliasing - t := nat(nil).shl(x.mant, uint(ex-ey)) - z.mant = t.sub(t, y.mant) + if al { + t := nat(nil).shl(x.mant, uint(ex-ey)) + z.mant = t.sub(t, y.mant) + } else { + z.mant = z.mant.shl(x.mant, uint(ex-ey)) + z.mant = z.mant.sub(z.mant, y.mant) + } ex = ey } diff --git a/src/math/big/float_test.go b/src/math/big/float_test.go index 464619b338..bea5ac175c 100644 --- a/src/math/big/float_test.go +++ b/src/math/big/float_test.go @@ -1762,3 +1762,41 @@ func TestFloatCmpSpecialValues(t *testing.T) { } } } + +func BenchmarkFloatAdd(b *testing.B) { + x := new(Float) + y := new(Float) + z := new(Float) + + for _, prec := range []uint{10, 1e2, 1e3, 1e4, 1e5} { + x.SetPrec(prec).SetRat(NewRat(1, 3)) + y.SetPrec(prec).SetRat(NewRat(1, 6)) + z.SetPrec(prec) + + b.Run(fmt.Sprintf("%v", prec), func(b *testing.B) { + b.ReportAllocs() + for i := 0; i < b.N; i++ { + z.Add(x, y) + } + }) + } +} + +func BenchmarkFloatSub(b *testing.B) { + x := new(Float) + y := new(Float) + z := new(Float) + + for _, prec := range []uint{10, 1e2, 1e3, 1e4, 1e5} { + x.SetPrec(prec).SetRat(NewRat(1, 3)) + y.SetPrec(prec).SetRat(NewRat(1, 6)) + z.SetPrec(prec) + + b.Run(fmt.Sprintf("%v", prec), func(b *testing.B) { + b.ReportAllocs() + for i := 0; i < b.N; i++ { + z.Sub(x, y) + } + }) + } +} -- 2.48.1