From 4f445d2744337bd0565c8e8eb1523f512a180d4e Mon Sep 17 00:00:00 2001 From: Evan Shaw Date: Tue, 20 Apr 2010 21:24:07 -0700 Subject: [PATCH] big: reduce the number of allocations There was a bug in makeN that caused lots of unnecessary allocations. Fixing this exposed a few bugs in other functions which worked when makeN allocated a new slice, but failed when it simply resized an existing slice. The result is a pretty big performance improvement. When running pidigits, here were the numbers I got on amd64: Before this change: pidigits 10000 gcc -O2 pidigits.c -lgmp 2.09u 0.02s 2.11r gc pidigits 12.68u 0.04s 12.72r gc_B pidigits 12.71u 0.03s 12.75r After: pidigits 10000 gcc -O2 pidigits.c -lgmp 2.09u 0.00s 2.10r gc pidigits 6.82u 0.00s 6.85r gc_B pidigits 6.55u 0.01s 6.59r R=rsc, gri CC=golang-dev https://golang.org/cl/953042 --- src/pkg/big/nat.go | 14 ++++++++++---- 1 file changed, 10 insertions(+), 4 deletions(-) diff --git a/src/pkg/big/nat.go b/src/pkg/big/nat.go index f8d4a2d434..456952aa88 100644 --- a/src/pkg/big/nat.go +++ b/src/pkg/big/nat.go @@ -48,7 +48,7 @@ func normN(z []Word) []Word { func makeN(z []Word, m int, clear bool) []Word { - if len(z) > m { + if cap(z) > m { z = z[0:m] // reuse z - has at least one extra word for a carry, if any if clear { for i := range z { @@ -224,9 +224,10 @@ func mulNN(z, x, y []Word) []Word { } // m >= n && m > 1 && n > 1 - z = makeN(z, m+n, true) - if &z[0] == &x[0] || &z[0] == &y[0] { + if z == nil || &z[0] == &x[0] || &z[0] == &y[0] { z = makeN(nil, m+n, true) // z is an alias for x or y - cannot reuse + } else { + z = makeN(z, m+n, true) } for i := 0; i < n; i++ { if f := y[i]; f != 0 { @@ -297,7 +298,12 @@ func divLargeNN(z, z2, uIn, v []Word) (q, r []Word) { n := len(v) m := len(uIn) - len(v) - u := makeN(z2, len(uIn)+1, false) + var u []Word + if z2 == nil || &z2[0] == &uIn[0] { + u = makeN(nil, len(uIn)+1, true) // uIn is an alias for z2 + } else { + u = makeN(z2, len(uIn)+1, true) + } qhatv := make([]Word, len(v)+1) q = makeN(z, m+1, false) -- 2.50.0