code review 5574054: math/big: assembly versions of bitLen for x86-64, 386,...

math/big:  assembly versions of bitLen for x86-64, 386, and ARM.

Roughly 2x speedup for the internal bitLen function in arith.go.  Added TestWordBitLen test.

Performance differences against the new version of
bitLen generic:

x86-64 Macbook pro (current tip):

benchmark                old ns/op    new ns/op    delta
big.BenchmarkBitLen0             6            4  -37.40%
big.BenchmarkBitLen1             6            2  -51.79%
big.BenchmarkBitLen2             6            2  -65.04%
big.BenchmarkBitLen3             6            2  -66.10%
big.BenchmarkBitLen4             6            2  -60.96%
big.BenchmarkBitLen5             6            2  -55.80%
big.BenchmarkBitLen8             6            2  -56.19%
big.BenchmarkBitLen9             6            2  -64.73%
big.BenchmarkBitLen16            7            2  -68.84%
big.BenchmarkBitLen17            6            2  -67.11%
big.BenchmarkBitLen31            7            2  -61.57%


386 Intel Atom (current tip):
benchmark                old ns/op    new ns/op    delta
big.BenchmarkBitLen0            23           20  -13.04%
big.BenchmarkBitLen1            23           20  -14.77%
big.BenchmarkBitLen2            24           20  -19.28%
big.BenchmarkBitLen3            25           20  -21.57%
big.BenchmarkBitLen4            24           20  -16.94%
big.BenchmarkBitLen5            25           20  -20.78%
big.BenchmarkBitLen8            24           20  -19.28%
big.BenchmarkBitLen9            25           20  -20.47%
big.BenchmarkBitLen16           26           20  -23.37%
big.BenchmarkBitLen17           26           20  -25.09%
big.BenchmarkBitLen31           32           20  -35.51%


ARM v5 SheevaPlug, previous weekly patched with bitLen:
benchmark                old ns/op    new ns/op    delta
big.BenchmarkBitLen0            50           29  -41.73%
big.BenchmarkBitLen1            51           29  -42.75%
big.BenchmarkBitLen2            59           29  -50.08%
big.BenchmarkBitLen3            60           29  -50.75%
big.BenchmarkBitLen4            59           29  -50.08%
big.BenchmarkBitLen5            60           29  -50.75%
big.BenchmarkBitLen8            59           29  -50.08%
big.BenchmarkBitLen9            60           29  -50.75%
big.BenchmarkBitLen16           69           29  -57.35%
big.BenchmarkBitLen17           70           29  -57.89%
big.BenchmarkBitLen31           95           29  -69.07%

[dga, 2012-01-24 02:33:50]

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

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

[minux1, 2012-01-24 02:39:16]

http://codereview.appspot.com/5574054/diff/1001/src/pkg/math/big/arith_arm.s
File src/pkg/math/big/arith_arm.s (right):

http://codereview.appspot.com/5574054/diff/1001/src/pkg/math/big/arith_arm.s#...
src/pkg/math/big/arith_arm.s:317: WORD	$0xe16f0f10
I think this line needs a comment about the assembly instruction.

[dga, 2012-01-24 02:42:20]

Hello golang-dev@googlegroups.com, minux.ma@gmail.com (cc:
golang-dev@googlegroups.com),

Please take another look.

[dga, 2012-01-24 02:43:00]

On 2012/01/24 02:39:16, minux wrote:
http://codereview.appspot.com/5574054/diff/1001/src/pkg/math/big/arith_arm.s#...
> src/pkg/math/big/arith_arm.s:317: WORD	$0xe16f0f10
> I think this line needs a comment about the assembly instruction.

It certainly did.  Thanks!

[gri, 2012-01-25 17:44:31]

http://codereview.appspot.com/5574054/diff/6001/src/pkg/math/big/arith_386.s
File src/pkg/math/big/arith_386.s (right):

http://codereview.appspot.com/5574054/diff/6001/src/pkg/math/big/arith_386.s#...
src/pkg/math/big/arith_386.s:248: // divWVW(z* Word, xn Word, x []Word, y Word)
(r Word)
for concistency, this should be:

// func divWVW....

http://codereview.appspot.com/5574054/diff/6001/src/pkg/math/big/arith_386.s#...
src/pkg/math/big/arith_386.s:267: // func bitLen(x Word) (n int)
see the 64bit version for a simpler implementation

http://codereview.appspot.com/5574054/diff/6001/src/pkg/math/big/arith_amd64.s
File src/pkg/math/big/arith_amd64.s (right):

http://codereview.appspot.com/5574054/diff/6001/src/pkg/math/big/arith_amd64....
src/pkg/math/big/arith_amd64.s:246: // divWVW(z []Word, xn Word, x []Word, y
Word) (r Word)
// func divWVW ...

http://codereview.appspot.com/5574054/diff/6001/src/pkg/math/big/arith_amd64....
src/pkg/math/big/arith_amd64.s:265: // func bitLen(x Word) (n int)
This can be done with half the amount of code:

// func bitLen(x Word) (n int)
TEXT ·bitLen(SB),7,$0
	BSRQ x+0(FP), AX
	JZ Z1
	INCQ AX

Z1:	MOVQ AX, n+8(FP)
	RET

[gri, 2012-01-25 17:52:06]

Also: There should be a Test function in arith_test.go for bitLen
(probably TestbitLen since TestBitLen is already taken for the Int
version).
- gri

On Wed, Jan 25, 2012 at 9:44 AM,  <gri@golang.org> wrote:
>
> http://codereview.appspot.com/5574054/diff/6001/src/pkg/math/big/arith_386.s
> File src/pkg/math/big/arith_386.s (right):
>
>
http://codereview.appspot.com/5574054/diff/6001/src/pkg/math/big/arith_386.s#...
> src/pkg/math/big/arith_386.s:248: // divWVW(z* Word, xn Word, x []Word,
> y Word) (r Word)
> for concistency, this should be:
>
> // func divWVW....
>
>
http://codereview.appspot.com/5574054/diff/6001/src/pkg/math/big/arith_386.s#...
> src/pkg/math/big/arith_386.s:267: // func bitLen(x Word) (n int)
> see the 64bit version for a simpler implementation
>
> http://codereview.appspot.com/5574054/diff/6001/src/pkg/math/big/arith_amd64.s
> File src/pkg/math/big/arith_amd64.s (right):
>
>
http://codereview.appspot.com/5574054/diff/6001/src/pkg/math/big/arith_amd64....
> src/pkg/math/big/arith_amd64.s:246: // divWVW(z []Word, xn Word, x
>
> []Word, y Word) (r Word)
> // func divWVW ...
>
>
http://codereview.appspot.com/5574054/diff/6001/src/pkg/math/big/arith_amd64....
> src/pkg/math/big/arith_amd64.s:265: // func bitLen(x Word) (n int)
> This can be done with half the amount of code:
>
>
> // func bitLen(x Word) (n int)
> TEXT ·bitLen(SB),7,$0
>        BSRQ x+0(FP), AX
>        JZ Z1
>        INCQ AX
>
> Z1:     MOVQ AX, n+8(FP)
>        RET
>
> http://codereview.appspot.com/5574054/

[dga, 2012-01-25 18:53:04]

On 2012/01/25 17:44:31, gri wrote:
> TEXT ·bitLen(SB),7,$0
> 	BSRQ x+0(FP), AX
> 	JZ Z1
> 	INCQ AX
> 
> Z1:	MOVQ AX, n+8(FP)
> 	RET

This produces the wrong result for bitLen(0)
(BSR only updates the dest register if the value was non-zero); needs
  MOVQ $0, AX
at the start.  But with that, it's good.  Updating and addressing testing and
commenting requirements now.

I'm naming the test function TestWordBitLen instead - the word following Test
can't start with [a-z].  I assume that's preferable to TestArithBitLen?

[dga, 2012-01-25 19:42:41]

> (BSR only updates the dest register if the value was non-zero); needs
>   MOVQ $0, AX

Which, now that I read what I just wrote, suggests that the code can be even
shorter and eliminate the branch (negligible performance change, but it's
nicer):

TEXT ·bitLen(SB),7,$0
        MOVQ $-1, AX
        BSRQ x+0(FP), AX
        INCQ AX
        MOVQ AX, n+8(FP)
        RET

[dga, 2012-01-25 19:51:02]

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

Please take another look.

[dga, 2012-01-25 19:52:43]

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

Please take another look.

[gri, 2012-01-25 21:55:08]

Please add the test function. TestWordBitLen is fine.

http://codereview.appspot.com/5574054/diff/2019/src/pkg/math/big/arith_386.s
File src/pkg/math/big/arith_386.s (right):

http://codereview.appspot.com/5574054/diff/2019/src/pkg/math/big/arith_386.s#...
src/pkg/math/big/arith_386.s:269: MOVL $-1, AX
I believe this is not correct in general because the result (AX) of bsr is not
defined (may not be -1 anymore) if the argument is 0 (but bsr sets the Z flag).
You probably need the branch.

http://codereview.appspot.com/5574054/diff/2019/src/pkg/math/big/arith_amd64.s
File src/pkg/math/big/arith_amd64.s (right):

http://codereview.appspot.com/5574054/diff/2019/src/pkg/math/big/arith_amd64....
src/pkg/math/big/arith_amd64.s:267: MOVQ $-1, AX
see other comment

[dga, 2012-01-25 21:59:49]

Agreed - was just about to say the same thing about the branch.  I'd looked at a
non-official instruction reference, but the Intel reference is clear that it's
undefined.  Thanks for catching that.

Test function added already.

On 2012/01/25 21:55:08, gri wrote:
> Please add the test function. TestWordBitLen is fine.
> 
> http://codereview.appspot.com/5574054/diff/2019/src/pkg/math/big/arith_386.s
> File src/pkg/math/big/arith_386.s (right):
> 
>
http://codereview.appspot.com/5574054/diff/2019/src/pkg/math/big/arith_386.s#...
> src/pkg/math/big/arith_386.s:269: MOVL $-1, AX
> I believe this is not correct in general because the result (AX) of bsr is not
> defined (may not be -1 anymore) if the argument is 0 (but bsr sets the Z
flag).
> You probably need the branch.
> 
> http://codereview.appspot.com/5574054/diff/2019/src/pkg/math/big/arith_amd64.s
> File src/pkg/math/big/arith_amd64.s (right):
> 
>
http://codereview.appspot.com/5574054/diff/2019/src/pkg/math/big/arith_amd64....
> src/pkg/math/big/arith_amd64.s:267: MOVQ $-1, AX
> see other comment

[dga, 2012-01-25 22:08:41]

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

Please take another look.

[gri, 2012-01-25 22:23:19]

Close, but there's a bug in your comments (or your code). Please use my simple
test.

I assume you have updated the performance numbers to match this last version?
- gri

http://codereview.appspot.com/5574054/diff/9002/src/pkg/math/big/arith_test.go
File src/pkg/math/big/arith_test.go (right):

http://codereview.appspot.com/5574054/diff/9002/src/pkg/math/big/arith_test.g...
src/pkg/math/big/arith_test.go:356: y = (y << 1) | 0x1
this is 1000...001 and not 1111...111

http://codereview.appspot.com/5574054/diff/9002/src/pkg/math/big/arith_test.g...
src/pkg/math/big/arith_test.go:358: }
Too complicated. How about:

func TestWordBitLen(t *testing.T) {
	for i := 0; i <= _W; i++ {
		x := Word(1)<<uint(i-1) // i == 0 => x == 0
		n := bitLen(x)
		if n != i {
			t.Errorf("got %d; want %d for bitLen(%x)", n, i, x)
		}
	}
}

[gri, 2012-01-25 23:03:09]

LGTM

http://codereview.appspot.com/5574054/diff/9002/src/pkg/math/big/arith_test.go
File src/pkg/math/big/arith_test.go (right):

http://codereview.appspot.com/5574054/diff/9002/src/pkg/math/big/arith_test.g...
src/pkg/math/big/arith_test.go:356: y = (y << 1) | 0x1
On 2012/01/25 22:23:19, gri wrote:
> this is 1000...001 and not 1111...111

Never mind - I read this a bit too quickly.

[gri, 2012-01-25 23:04:19]

*** Submitted as 77457a85f621 ***

math/big:  assembly versions of bitLen for x86-64, 386, and ARM.

Roughly 2x speedup for the internal bitLen function in arith.go.  Added
TestWordBitLen test.

Performance differences against the new version of
bitLen generic:

x86-64 Macbook pro (current tip):

benchmark                old ns/op    new ns/op    delta
big.BenchmarkBitLen0             6            4  -37.40%
big.BenchmarkBitLen1             6            2  -51.79%
big.BenchmarkBitLen2             6            2  -65.04%
big.BenchmarkBitLen3             6            2  -66.10%
big.BenchmarkBitLen4             6            2  -60.96%
big.BenchmarkBitLen5             6            2  -55.80%
big.BenchmarkBitLen8             6            2  -56.19%
big.BenchmarkBitLen9             6            2  -64.73%
big.BenchmarkBitLen16            7            2  -68.84%
big.BenchmarkBitLen17            6            2  -67.11%
big.BenchmarkBitLen31            7            2  -61.57%


386 Intel Atom (current tip):
benchmark                old ns/op    new ns/op    delta
big.BenchmarkBitLen0            23           20  -13.04%
big.BenchmarkBitLen1            23           20  -14.77%
big.BenchmarkBitLen2            24           20  -19.28%
big.BenchmarkBitLen3            25           20  -21.57%
big.BenchmarkBitLen4            24           20  -16.94%
big.BenchmarkBitLen5            25           20  -20.78%
big.BenchmarkBitLen8            24           20  -19.28%
big.BenchmarkBitLen9            25           20  -20.47%
big.BenchmarkBitLen16           26           20  -23.37%
big.BenchmarkBitLen17           26           20  -25.09%
big.BenchmarkBitLen31           32           20  -35.51%


ARM v5 SheevaPlug, previous weekly patched with bitLen:
benchmark                old ns/op    new ns/op    delta
big.BenchmarkBitLen0            50           29  -41.73%
big.BenchmarkBitLen1            51           29  -42.75%
big.BenchmarkBitLen2            59           29  -50.08%
big.BenchmarkBitLen3            60           29  -50.75%
big.BenchmarkBitLen4            59           29  -50.08%
big.BenchmarkBitLen5            60           29  -50.75%
big.BenchmarkBitLen8            59           29  -50.08%
big.BenchmarkBitLen9            60           29  -50.75%
big.BenchmarkBitLen16           69           29  -57.35%
big.BenchmarkBitLen17           70           29  -57.89%
big.BenchmarkBitLen31           95           29  -69.07%

R=golang-dev, minux.ma, gri
CC=golang-dev
http://codereview.appspot.com/5574054

Committer: Robert Griesemer <gri@golang.org>

[dga, 2012-01-25 23:09:39]

On 2012/01/25 22:23:19, gri wrote:
> 
> I assume you have updated the performance numbers to match this last version?

Yup.  The change is that on amd64, bitLen(0) got a bit slower (~4 ns/op) because
of the jump, but it's still quite a bit faster than the non-asm version.  The
other numbers and platforms were unchanged.  I figure that a caller who thinks
they're going to be feeding a lot of zeros in to bitLen can do the test
themselves.