code review 6716048: math/big: add 4-bit, fixed window exponentiation.

math/big: add 4-bit, fixed window exponentiation.

A 4-bit window is convenient because 4 divides both 32 and 64,
therefore we never have a window spanning words of the exponent.
Additionaly, the benefit of a 5-bit window is only 2.6% at 1024-bits
and 3.3% at 2048-bits.

This code is still not constant time, however.

benchmark                        old ns/op    new ns/op    delta
BenchmarkRSA2048Decrypt           17108590     11180370  -34.65%
Benchmark3PrimeRSA2048Decrypt     13003720      7680390  -40.94%

[agl1, 2012-10-16 20:34:35]

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

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

[gri, 2012-10-16 21:24:30]

Some suggestions.

https://codereview.appspot.com/6716048/diff/7001/src/pkg/math/big/nat.go
File src/pkg/math/big/nat.go (right):

https://codereview.appspot.com/6716048/diff/7001/src/pkg/math/big/nat.go#newc...
src/pkg/math/big/nat.go:1251: // If the exponent is large and the base is
non-trivial, we use a
s/we use a/we use/

https://codereview.appspot.com/6716048/diff/7001/src/pkg/math/big/nat.go#newc...
src/pkg/math/big/nat.go:1256: if len(y) > 1 && len(x) > 1 && len(m) > 0 {
perhaps check the values in the order they appear in the signature:

if len(x) > 1 && len(y) > 1 && len(m) > 0 ...

and adjust the comment accordingly:

If the base is non-trivial and the exponent large, we use

https://codereview.appspot.com/6716048/diff/7001/src/pkg/math/big/nat.go#newc...
src/pkg/math/big/nat.go:1321: 
Can we make 4 a constant?

const n = 4

https://codereview.appspot.com/6716048/diff/7001/src/pkg/math/big/nat.go#newc...
src/pkg/math/big/nat.go:1323: var powers [16]nat
s/16/1<<n/

https://codereview.appspot.com/6716048/diff/7001/src/pkg/math/big/nat.go#newc...
src/pkg/math/big/nat.go:1324: powers[0] = powers[0].make(1)
powers[0] = natOne

https://codereview.appspot.com/6716048/diff/7001/src/pkg/math/big/nat.go#newc...
src/pkg/math/big/nat.go:1325: powers[0][0] = 1
get rid of this line

https://codereview.appspot.com/6716048/diff/7001/src/pkg/math/big/nat.go#newc...
src/pkg/math/big/nat.go:1327: for i := 2; i < 16; i += 2 {
s/16/1<<n/

https://codereview.appspot.com/6716048/diff/7001/src/pkg/math/big/nat.go#newc...
src/pkg/math/big/nat.go:1328: powers[i] = powers[i].mul(powers[i/2],
powers[i/2])
	for i := 2; i < 1<<n; i += 2 {
		p2, p, p1 := &powers[i/2], &powers[i], &powers[i+1]
		*p = p.mul(*p2, *p2)
		zz, r = zz.div(r, *p, m)
		*p, r = r, *p
		*p1 = p1.mul(*p, x)
		zz, r = zz.div(r, *p1, m)
		*p1, r = r, *p1
	}

https://codereview.appspot.com/6716048/diff/7001/src/pkg/math/big/nat.go#newc...
src/pkg/math/big/nat.go:1336: z = z.make(1)
z = z.setWord(1)

https://codereview.appspot.com/6716048/diff/7001/src/pkg/math/big/nat.go#newc...
src/pkg/math/big/nat.go:1337: z[0] = 1
get rid of this line

https://codereview.appspot.com/6716048/diff/7001/src/pkg/math/big/nat.go#newc...
src/pkg/math/big/nat.go:1340: word := y[i]
s/word/yi/

word is almost Word and yi is saying more and shorter

https://codereview.appspot.com/6716048/diff/7001/src/pkg/math/big/nat.go#newc...
src/pkg/math/big/nat.go:1341: for j := 0; j < _W; j += 4 {
s/4/n/

https://codereview.appspot.com/6716048/diff/7001/src/pkg/math/big/nat.go#newc...
src/pkg/math/big/nat.go:1343: // Manually unrolling this speeds the code up by
~15%.
Really?

for k := 0; k < n; k++ {
	zz = zz.mul(z, z)
	zz, z = z, zz
	zz, r = zz.div(r, z, m)
	z, r = r, z
}

The loop overhead should be neglible compared to the mul/div stuff

https://codereview.appspot.com/6716048/diff/7001/src/pkg/math/big/nat.go#newc...
src/pkg/math/big/nat.go:1365: zz = zz.mul(z, powers[word>>(_W-4)])
s/4/n/

https://codereview.appspot.com/6716048/diff/7001/src/pkg/math/big/nat.go#newc...
src/pkg/math/big/nat.go:1370: word <<= 4
s/4/n/

[agl1, 2012-10-16 22:22:56]

https://codereview.appspot.com/6716048/diff/7001/src/pkg/math/big/nat.go
File src/pkg/math/big/nat.go (right):

https://codereview.appspot.com/6716048/diff/7001/src/pkg/math/big/nat.go#newc...
src/pkg/math/big/nat.go:1251: // If the exponent is large and the base is
non-trivial, we use a
On 2012/10/16 21:24:30, gri wrote:
> s/we use a/we use/

Done.

https://codereview.appspot.com/6716048/diff/7001/src/pkg/math/big/nat.go#newc...
src/pkg/math/big/nat.go:1256: if len(y) > 1 && len(x) > 1 && len(m) > 0 {
On 2012/10/16 21:24:30, gri wrote:
> perhaps check the values in the order they appear in the signature:
> 
> if len(x) > 1 && len(y) > 1 && len(m) > 0 ...
> 
> and adjust the comment accordingly:
> 
> If the base is non-trivial and the exponent large, we use

Done.

https://codereview.appspot.com/6716048/diff/7001/src/pkg/math/big/nat.go#newc...
src/pkg/math/big/nat.go:1321: 
On 2012/10/16 21:24:30, gri wrote:
> Can we make 4 a constant?
> 
> const n = 4

Done.

https://codereview.appspot.com/6716048/diff/7001/src/pkg/math/big/nat.go#newc...
src/pkg/math/big/nat.go:1323: var powers [16]nat
On 2012/10/16 21:24:30, gri wrote:
> s/16/1<<n/

Done.

https://codereview.appspot.com/6716048/diff/7001/src/pkg/math/big/nat.go#newc...
src/pkg/math/big/nat.go:1324: powers[0] = powers[0].make(1)
On 2012/10/16 21:24:30, gri wrote:
> powers[0] = natOne

Done.

https://codereview.appspot.com/6716048/diff/7001/src/pkg/math/big/nat.go#newc...
src/pkg/math/big/nat.go:1325: powers[0][0] = 1
On 2012/10/16 21:24:30, gri wrote:
> get rid of this line

Done.

https://codereview.appspot.com/6716048/diff/7001/src/pkg/math/big/nat.go#newc...
src/pkg/math/big/nat.go:1327: for i := 2; i < 16; i += 2 {
On 2012/10/16 21:24:30, gri wrote:
> s/16/1<<n/

Done.

https://codereview.appspot.com/6716048/diff/7001/src/pkg/math/big/nat.go#newc...
src/pkg/math/big/nat.go:1328: powers[i] = powers[i].mul(powers[i/2],
powers[i/2])
On 2012/10/16 21:24:30, gri wrote:
> 	for i := 2; i < 1<<n; i += 2 {
> 		p2, p, p1 := &powers[i/2], &powers[i], &powers[i+1]
> 		*p = p.mul(*p2, *p2)
> 		zz, r = zz.div(r, *p, m)
> 		*p, r = r, *p
> 		*p1 = p1.mul(*p, x)
> 		zz, r = zz.div(r, *p1, m)
> 		*p1, r = r, *p1
> 	}

Done.

https://codereview.appspot.com/6716048/diff/7001/src/pkg/math/big/nat.go#newc...
src/pkg/math/big/nat.go:1336: z = z.make(1)
On 2012/10/16 21:24:30, gri wrote:
> z = z.setWord(1)

Done.

https://codereview.appspot.com/6716048/diff/7001/src/pkg/math/big/nat.go#newc...
src/pkg/math/big/nat.go:1337: z[0] = 1
On 2012/10/16 21:24:30, gri wrote:
> get rid of this line

Done.

https://codereview.appspot.com/6716048/diff/7001/src/pkg/math/big/nat.go#newc...
src/pkg/math/big/nat.go:1340: word := y[i]
On 2012/10/16 21:24:30, gri wrote:
> s/word/yi/
> 
> word is almost Word and yi is saying more and shorter

Done.

https://codereview.appspot.com/6716048/diff/7001/src/pkg/math/big/nat.go#newc...
src/pkg/math/big/nat.go:1343: // Manually unrolling this speeds the code up by
~15%.
On 2012/10/16 21:24:30, gri wrote:
> Really?
> 
> for k := 0; k < n; k++ {
> 	zz = zz.mul(z, z)
> 	zz, z = z, zz
> 	zz, r = zz.div(r, z, m)
> 	z, r = r, z
> }
> 
> The loop overhead should be neglible compared to the mul/div stuff

Yea, I know. And yet, when I put it in a loop as you've written:

benchmark                        old ns/op    new ns/op    delta
BenchmarkRSA2048Decrypt           11243420     13158090  +17.03%
Benchmark3PrimeRSA2048Decrypt      7870770     10122080  +28.60%

Maybe inlining is kicking in and doing more than we expect?

[gri, 2012-10-16 23:56:06]

LGTM

https://codereview.appspot.com/6716048/diff/10001/src/pkg/math/big/nat.go
File src/pkg/math/big/nat.go (right):

https://codereview.appspot.com/6716048/diff/10001/src/pkg/math/big/nat.go#new...
src/pkg/math/big/nat.go:1343: zz = zz.mul(z, z)
I'd leave a comment here, something along the lines:

// Unrolled loop for significant performance gain.
// Use go test -bench=XXX to check performance before making changes.

(fill in XXX)

[agl1, 2012-10-17 15:19:36]

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

math/big: add 4-bit, fixed window exponentiation.

A 4-bit window is convenient because 4 divides both 32 and 64,
therefore we never have a window spanning words of the exponent.
Additionaly, the benefit of a 5-bit window is only 2.6% at 1024-bits
and 3.3% at 2048-bits.

This code is still not constant time, however.

benchmark                        old ns/op    new ns/op    delta
BenchmarkRSA2048Decrypt           17108590     11180370  -34.65%
Benchmark3PrimeRSA2048Decrypt     13003720      7680390  -40.94%

R=gri
CC=golang-dev
http://codereview.appspot.com/6716048

http://codereview.appspot.com/6716048/diff/10001/src/pkg/math/big/nat.go
File src/pkg/math/big/nat.go (right):

http://codereview.appspot.com/6716048/diff/10001/src/pkg/math/big/nat.go#newc...
src/pkg/math/big/nat.go:1343: zz = zz.mul(z, z)
On 2012/10/16 23:56:06, gri wrote:
> I'd leave a comment here, something along the lines:
> 
> // Unrolled loop for significant performance gain.
> // Use go test -bench=XXX to check performance before making changes.
> 
> (fill in XXX)

Done.