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
http://codereview.appspot.com/953042

Committer: Russ Cox <rsc@golang.org>

1 files changed, 10 insertions, 4 deletions

diff --git a/src/pkg/big/nat.go b/src/pkg/big/nat.go
index f8d4a2d43..456952aa8 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)