code review 881050: big: Add Lsh and Value; convert pidigits to use big

big: Add Lsh and Value; convert pidigits to use big

This yields a pretty significant performance boost to pidigits and there are still some improvements to be made. Here are my numbers:

amd64 w/ bignum:
pidigits 10000
        gcc -O2 pidigits.c -lgmp        2.10u 0.00s 2.10r
        gc pidigits     22.92u 0.02s 22.97r
        gc_B pidigits   22.62u 0.00s 22.65r

amd64 w/ big:
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

386 w/ bignum:
pidigits 10000
        gcc -O2 pidigits.c -lgmp        2.09u 0.00s 2.09r
        gc pidigits     44.30u 0.01s 44.35r
        gc_B pidigits   44.29u 0.03s 44.35r

386 w/ big:
pidigits 10000
        gcc -O2 pidigits.c -lgmp        2.10u 0.00s 2.10r
        gc pidigits     22.70u 0.06s 22.79r
        gc_B pidigits   22.80u 0.09s 22.91r

[eds, 2010-04-18 23:32:06]

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

I'd like you to review this change.

[rsc1, 2010-04-19 03:04:12]

+gri

This looks pretty good.  Thanks for picking up the ball on this.
Robert wrote the package, so I'm adding him to the review.

http://codereview.appspot.com/881050/diff/2001/3001
File src/pkg/big/int.go (right):

http://codereview.appspot.com/881050/diff/2001/3001#newcode172
src/pkg/big/int.go:172: // Value returns the value of z if it fits into an int64
Complete sentences, with periods, please.

// Int64 returns the int64 representation of z.
// If z cannot be represented in an int64, the result is undefined.

http://codereview.appspot.com/881050/diff/2001/3001#newcode174
src/pkg/big/int.go:174: func (z *Int) Value() (v int64) {
Should be called Int64 not Value.
Let's avoid the named return value unless it's helping the
documentation, which it isn't here.

http://codereview.appspot.com/881050/diff/2001/3001#newcode179
src/pkg/big/int.go:179: // This can only happen if _W == 32
If _W==64 and there is more than one word,
instead of returning the bottom 64 bits this would
return a mix of the bottom 96 bits, which is kind of odd.
I know it's undefined, but still.  Better would be

if len(z.abs) == 0 {
    return 0
}
v := int64(z.abs[0])
if _W == 32 && len(z.abs) > 0 {
    ...
}
...

http://codereview.appspot.com/881050/diff/2001/3001#newcode383
src/pkg/big/int.go:383: // z cannot refer to the same Int as x.
Please make this work and test it.
It's very common to want z to refer to the same Int as x,
and it's not too hard to implement (just do the shift loop
in the right order, which you've already done).

http://codereview.appspot.com/881050/diff/2001/3001#newcode394
src/pkg/big/int.go:394: // z cannot refer to the same Int as x.
Again, please make this work and test it. 
(I think it already did.)

http://codereview.appspot.com/881050/diff/2001/3002
File src/pkg/big/int_test.go (right):

http://codereview.appspot.com/881050/diff/2001/3002#newcode522
src/pkg/big/int_test.go:522: type iShiftTest struct {
How about shiftTest?
Not sure what the i is.

http://codereview.appspot.com/881050/diff/2001/3002#newcode588
src/pkg/big/int_test.go:588: func TestLsh(t *testing.T) {
Please add a TestLshRsh that tests that for every
case in the lshTests and rshTests tables:

    in << shift >> shift == in
    ((in << shift) | (1<<shift - 1)) >> shift == in

Please also add TestLshSelf TestRshSelf TestLshRshSelf
variants of TestLsh TestRsh TestLshRshSelf that test that
it is okay to do a shift with z == x.

http://codereview.appspot.com/881050/diff/2001/3002#newcode600
src/pkg/big/int_test.go:600: var valueTests = []int64{
int64 etc

http://codereview.appspot.com/881050/diff/2001/3003
File src/pkg/big/nat.go (right):

http://codereview.appspot.com/881050/diff/2001/3003#newcode535
src/pkg/big/nat.go:535: func shiftLeft(dst, src []Word, n int) {
should probably be uint

http://codereview.appspot.com/881050/diff/2001/3003#newcode541
src/pkg/big/nat.go:541: dst[len(dst)-1] |= src[len(src)-1] >> ñ
This is making an assumption about len(dst) that the caller
may or may not need to make.  Perhaps handle this case more
gracefully:

if len(dst) > len(src) {
    dst[len(src)] = src[len(src)-1] >> ñ
}

http://codereview.appspot.com/881050/diff/2001/3003#newcode543
src/pkg/big/nat.go:543: dst[i] = src[i] << uint(n)
Might as well combine this line and the next into one.

http://codereview.appspot.com/881050/diff/2001/3003#newcode550
src/pkg/big/nat.go:550: func shiftRight(dst, src []Word, n int) {
should probably be uint here too
(I know it's not your code.)

http://codereview.appspot.com/881050/diff/2001/3003#newcode557
src/pkg/big/nat.go:557: dst[i] = src[i] >> uint(n)
Might as well combine this line and the next into one.
(I know it's not your code.)

http://codereview.appspot.com/881050/diff/2001/3004
File test/bench/pidigits.go (right):

http://codereview.appspot.com/881050/diff/2001/3004#newcode64
test/bench/pidigits.go:64: tmp1 = new(big.Int).Lsh(numer, 1)
The trick to being competitive with gmp is going to be eliminating
all the allocations here.  If you allocate tmp1 above (tmp1 = big.NewInt(0)),
this line can be

tmp1.Lsh(numer, 1)

And similarly all the new(big.Int) below can be eliminated too.

You can use the New method (which should be renamed to SetInt64)
on a persistent *big.Int for things like y2 and bigk.

The final allocation to remove will be the ones in Div: the interface
should probably be:

// Div calculates q = (x-r)/y where 0 <= r < y and sets z = q.
func (z *Int) Div(x, y *Int) (q, r *Int) {

// Mod calculates q = (x-r)/y and sets z = r.
func (z *Int) Mod(x, y *Int) (r *Int)

// DivMod calculates q = (x-r)/y and sets z = q.  (It returns z, r.)
func (z *Int) DivMod(x, y, r *Int) (q, r *Int)

DivMod is the obvious wrapper around div.
The other two can internally pass a new(Int) to div for now
but longer term we should try to arrange to make them
not allocate.

[eds, 2010-04-19 05:10:03]

I'll address most of these, but have comments/questions on a few points.

On Sun, Apr 18, 2010 at 10:04 PM,  <rsc@google.com> wrote:
> http://codereview.appspot.com/881050/diff/2001/3001#newcode172
> src/pkg/big/int.go:172: // Value returns the value of z if it fits into
> an int64
> Complete sentences, with periods, please.
Done.

> // Int64 returns the int64 representation of z.
> // If z cannot be represented in an int64, the result is undefined.
>
> http://codereview.appspot.com/881050/diff/2001/3001#newcode174
> src/pkg/big/int.go:174: func (z *Int) Value() (v int64) {
> Should be called Int64 not Value.
> Let's avoid the named return value unless it's helping the
> documentation, which it isn't here.
Done.

> http://codereview.appspot.com/881050/diff/2001/3001#newcode179
> src/pkg/big/int.go:179: // This can only happen if _W == 32
> If _W==64 and there is more than one word,
> instead of returning the bottom 64 bits this would
> return a mix of the bottom 96 bits, which is kind of odd.
> I know it's undefined, but still.  Better would be
>
> if len(z.abs) == 0 {
>    return 0
> }
> v := int64(z.abs[0])
> if _W == 32 && len(z.abs) > 0 {
>    ...
> }
> ...
Done.

> http://codereview.appspot.com/881050/diff/2001/3001#newcode383
> src/pkg/big/int.go:383: // z cannot refer to the same Int as x.
> Please make this work and test it.
> It's very common to want z to refer to the same Int as x,
> and it's not too hard to implement (just do the shift loop
> in the right order, which you've already done).
The problem here isn't a bug in the shifting code, but a bug in makeN.
makeN is allocating more often than it should because it's calling
len() where it should be calling cap(). Fixing this exposes bugs in
other important functions. It's really a separate issue, but I'll
include it in this CL if you want.

> http://codereview.appspot.com/881050/diff/2001/3001#newcode394
> src/pkg/big/int.go:394: // z cannot refer to the same Int as x.
> Again, please make this work and test it.
> (I think it already did.)
See above.

> http://codereview.appspot.com/881050/diff/2001/3002
> File src/pkg/big/int_test.go (right):
>
> http://codereview.appspot.com/881050/diff/2001/3002#newcode522
> src/pkg/big/int_test.go:522: type iShiftTest struct {
> How about shiftTest?
> Not sure what the i is.
shiftTest was already taken by nat_test.go. So i is for Int. It's not
the best name, I admit. Maybe intShiftTest would be better?

> http://codereview.appspot.com/881050/diff/2001/3002#newcode588
> src/pkg/big/int_test.go:588: func TestLsh(t *testing.T) {
> Please add a TestLshRsh that tests that for every
> case in the lshTests and rshTests tables:
>
>    in << shift >> shift == in
>    ((in << shift) | (1<<shift - 1)) >> shift == in
>
> Please also add TestLshSelf TestRshSelf TestLshRshSelf
> variants of TestLsh TestRsh TestLshRshSelf that test that
> it is okay to do a shift with z == x.
Will do.

> http://codereview.appspot.com/881050/diff/2001/3002#newcode600
> src/pkg/big/int_test.go:600: var valueTests = []int64{
> int64 etc
>
> http://codereview.appspot.com/881050/diff/2001/3003
> File src/pkg/big/nat.go (right):
>
> http://codereview.appspot.com/881050/diff/2001/3003#newcode535
> src/pkg/big/nat.go:535: func shiftLeft(dst, src []Word, n int) {
> should probably be uint
Done.

> http://codereview.appspot.com/881050/diff/2001/3003#newcode541
> src/pkg/big/nat.go:541: dst[len(dst)-1] |= src[len(src)-1] >> ñ
> This is making an assumption about len(dst) that the caller
> may or may not need to make.  Perhaps handle this case more
> gracefully:
>
> if len(dst) > len(src) {
>    dst[len(src)] = src[len(src)-1] >> ñ
> }
Done.

> http://codereview.appspot.com/881050/diff/2001/3003#newcode543
> src/pkg/big/nat.go:543: dst[i] = src[i] << uint(n)
> Might as well combine this line and the next into one.
Done.

> http://codereview.appspot.com/881050/diff/2001/3003#newcode550
> src/pkg/big/nat.go:550: func shiftRight(dst, src []Word, n int) {
> should probably be uint here too
> (I know it's not your code.)
Done.

> http://codereview.appspot.com/881050/diff/2001/3003#newcode557
> src/pkg/big/nat.go:557: dst[i] = src[i] >> uint(n)
> Might as well combine this line and the next into one.
> (I know it's not your code.)
Done.

> http://codereview.appspot.com/881050/diff/2001/3004
> File test/bench/pidigits.go (right):
>
> http://codereview.appspot.com/881050/diff/2001/3004#newcode64
> test/bench/pidigits.go:64: tmp1 = new(big.Int).Lsh(numer, 1)
> The trick to being competitive with gmp is going to be eliminating
> all the allocations here.  If you allocate tmp1 above (tmp1 =
> big.NewInt(0)),
> this line can be
>
> tmp1.Lsh(numer, 1)
>
> And similarly all the new(big.Int) below can be eliminated too.
>
> You can use the New method (which should be renamed to SetInt64)
> on a persistent *big.Int for things like y2 and bigk.
WIll do.

> The final allocation to remove will be the ones in Div: the interface
> should probably be:
>
> // Div calculates q = (x-r)/y where 0 <= r < y and sets z = q.
> func (z *Int) Div(x, y *Int) (q, r *Int) {
>
> // Mod calculates q = (x-r)/y and sets z = r.
> func (z *Int) Mod(x, y *Int) (r *Int)
>
> // DivMod calculates q = (x-r)/y and sets z = q.  (It returns z, r.)
> func (z *Int) DivMod(x, y, r *Int) (q, r *Int)
>
> DivMod is the obvious wrapper around div.
> The other two can internally pass a new(Int) to div for now
> but longer term we should try to arrange to make them
> not allocate.
Just to be clear: are you talking long term, or do you want all this in this CL?

- Evan

[eds, 2010-04-19 12:30:31]

On Mon, Apr 19, 2010 at 12:10 AM, Evan Shaw <chickencha@gmail.com> wrote:
>> http://codereview.appspot.com/881050/diff/2001/3001#newcode383
>> src/pkg/big/int.go:383: // z cannot refer to the same Int as x.
>> Please make this work and test it.
>> It's very common to want z to refer to the same Int as x,
>> and it's not too hard to implement (just do the shift loop
>> in the right order, which you've already done).
> The problem here isn't a bug in the shifting code, but a bug in makeN.
> makeN is allocating more often than it should because it's calling
> len() where it should be calling cap(). Fixing this exposes bugs in
> other important functions. It's really a separate issue, but I'll
> include it in this CL if you want.

After sleeping on it, I realized that this isn't quite the case. I
still believe there's a bug in makeN, but the bit shifting code will
still fail in some cases even if that bug's fixed. I'll fix the bit
shifting code and then fix the makeN bug separately.

- Evan

[rsc, 2010-04-19 14:24:32]

On Mon, Apr 19, 2010 at 05:30, Evan Shaw <chickencha@gmail.com> wrote:
> On Mon, Apr 19, 2010 at 12:10 AM, Evan Shaw <chickencha@gmail.com> wrote:
>>> http://codereview.appspot.com/881050/diff/2001/3001#newcode383
>>> src/pkg/big/int.go:383: // z cannot refer to the same Int as x.
>>> Please make this work and test it.
>>> It's very common to want z to refer to the same Int as x,
>>> and it's not too hard to implement (just do the shift loop
>>> in the right order, which you've already done).
>> The problem here isn't a bug in the shifting code, but a bug in makeN.
>> makeN is allocating more often than it should because it's calling
>> len() where it should be calling cap(). Fixing this exposes bugs in
>> other important functions. It's really a separate issue, but I'll
>> include it in this CL if you want.
>
> After sleeping on it, I realized that this isn't quite the case. I
> still believe there's a bug in makeN, but the bit shifting code will
> still fail in some cases even if that bug's fixed. I'll fix the bit
> shifting code and then fix the makeN bug separately.

If it's a small change, this CL is fine.

Same with DivMod (which I think is a tiny change).

Russ

[eds, 2010-04-19 17:50:35]

One more question

http://codereview.appspot.com/881050/diff/2001/3002
File src/pkg/big/int_test.go (right):

http://codereview.appspot.com/881050/diff/2001/3002#newcode600
src/pkg/big/int_test.go:600: var valueTests = []int64{
On 2010/04/19 03:04:12, rsc1 wrote:
> int64 etc
> 

Sorry, I missed this comment before. What do you mean?

[eds, 2010-04-20 00:02:51]

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

Please take another look.

[rsc, 2010-04-20 01:44:43]

> src/pkg/big/int_test.go:600: var valueTests = []int64{
> On 2010/04/19 03:04:12, rsc1 wrote:
>>
>> int64 etc
>
>
> Sorry, I missed this comment before. What do you mean?

Since the method is Int64 not Value, this should be
int64Tests, TestInt64, not valueTests, TestValue.

Russ

[rsc1, 2010-04-21 00:56:16]

Looks pretty good.

I'd like to change the Div, Mod signatures now even if the
implementations don't get better (less allocation), because
we can always fix up the implementations later behind the
scenes as long as we get the signatures right.

Did you update the timings?

http://codereview.appspot.com/881050/diff/23001/24001
File src/pkg/big/int.go (right):

http://codereview.appspot.com/881050/diff/23001/24001#newcode103
src/pkg/big/int.go:103: // Div calculates q = (x-r)/y where 0 <= r < y. The
receiver is set to q.
// Div calculates q = (x-r)/y and sets z = q.
func (z *Int) Div(x, y *Int) *Int {

http://codereview.appspot.com/881050/diff/23001/24001#newcode112
src/pkg/big/int.go:112: // Mod calculates q = (x-r)/y and returns r.
// Mod calculates q = (x-r)/y and sets z = r.
func (z *Int) Mod(x, y *Int) *Int {

http://codereview.appspot.com/881050/diff/23001/24001#newcode389
src/pkg/big/int.go:389: // If we don't make a temp and makeN needs to allocate,
z will be cleared.
I'd call it znew instead of tmp, and shorten the comment:

// Don't assign z.abs yet, in case z == x.
znew := makeN(z.abs, len(x.abs)+addedWords+1, false)
...
z.abs = normN(znew)

http://codereview.appspot.com/881050/diff/23001/24001#newcode405
src/pkg/big/int.go:405: // If we don't make a temp and makeN needs to allocate,
z will be cleared.
Same.

http://codereview.appspot.com/881050/diff/23001/24002
File src/pkg/big/int_test.go (right):

http://codereview.appspot.com/881050/diff/23001/24002#newcode539
src/pkg/big/int_test.go:539: //intShiftTest{"-87", 1, "-44"},
If this test is correct, uncomment.
If not, delete.

http://codereview.appspot.com/881050/diff/23001/24002#newcode588
src/pkg/big/int_test.go:588: //intShiftTest{"-87", 1, "-174"},
Same

http://codereview.appspot.com/881050/diff/23001/24003
File src/pkg/big/nat.go (right):

http://codereview.appspot.com/881050/diff/23001/24003#newcode542
src/pkg/big/nat.go:542: dst[len(dst)-1] |= src[len(src)-1] >> ñ
This should be dst[len(src)] in case len(dst) is much bigger.

[eds, 2010-04-21 01:07:00]

The timings are updated, yes. I've got another CL coming after this one that
will almost cut those times in half again. (There's still at least one issue to
iron out, though.)

http://codereview.appspot.com/881050/diff/23001/24001
File src/pkg/big/int.go (right):

http://codereview.appspot.com/881050/diff/23001/24001#newcode103
src/pkg/big/int.go:103: // Div calculates q = (x-r)/y where 0 <= r < y. The
receiver is set to q.
On 2010/04/21 00:56:16, rsc1 wrote:
> // Div calculates q = (x-r)/y and sets z = q.
> func (z *Int) Div(x, y *Int) *Int {
> 
> 

Done.

http://codereview.appspot.com/881050/diff/23001/24001#newcode112
src/pkg/big/int.go:112: // Mod calculates q = (x-r)/y and returns r.
On 2010/04/21 00:56:16, rsc1 wrote:
> // Mod calculates q = (x-r)/y and sets z = r.
> func (z *Int) Mod(x, y *Int) *Int {
> 

Done.

http://codereview.appspot.com/881050/diff/23001/24001#newcode389
src/pkg/big/int.go:389: // If we don't make a temp and makeN needs to allocate,
z will be cleared.
On 2010/04/21 00:56:16, rsc1 wrote:
> I'd call it znew instead of tmp, and shorten the comment:
> 
> // Don't assign z.abs yet, in case z == x.
> znew := makeN(z.abs, len(x.abs)+addedWords+1, false)
> ...
> z.abs = normN(znew)
> 

Done.

http://codereview.appspot.com/881050/diff/23001/24001#newcode405
src/pkg/big/int.go:405: // If we don't make a temp and makeN needs to allocate,
z will be cleared.
On 2010/04/21 00:56:16, rsc1 wrote:
> Same.
> 

Done.

http://codereview.appspot.com/881050/diff/23001/24002
File src/pkg/big/int_test.go (right):

http://codereview.appspot.com/881050/diff/23001/24002#newcode539
src/pkg/big/int_test.go:539: //intShiftTest{"-87", 1, "-44"},
On 2010/04/21 00:56:16, rsc1 wrote:
> If this test is correct, uncomment.
> If not, delete.
> 

Done.

http://codereview.appspot.com/881050/diff/23001/24002#newcode588
src/pkg/big/int_test.go:588: //intShiftTest{"-87", 1, "-174"},
On 2010/04/21 00:56:16, rsc1 wrote:
> Same
> 

Done.

http://codereview.appspot.com/881050/diff/23001/24003
File src/pkg/big/nat.go (right):

http://codereview.appspot.com/881050/diff/23001/24003#newcode542
src/pkg/big/nat.go:542: dst[len(dst)-1] |= src[len(src)-1] >> ñ
On 2010/04/21 00:56:16, rsc1 wrote:
> This should be dst[len(src)] in case len(dst) is much bigger.
> 

Done.

[eds, 2010-04-21 01:08:13]

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

Please take another look.

[rsc1, 2010-04-21 02:07:37]

Looks good but please update the signatures.

http://codereview.appspot.com/881050/diff/29001/30001
File src/pkg/big/int.go (right):

http://codereview.appspot.com/881050/diff/29001/30001#newcode104
src/pkg/big/int.go:104: func (z *Int) Div(x, y *Int) (q, r *Int) {
You didn't change the function signatures I suggested in the last note.
Both this and Mod should return *Int (no named values).

[eds, 2010-04-21 02:17:37]

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

Please take another look.

[rsc1, 2010-04-21 03:18:44]

LGTM

I think Robert is out for a day or two.
I'll submit this so that you can work on the
next step that you mentioned before, and
we can incorporate Robert's feedback
as part of that CL.

[rsc, 2010-04-21 03:39:43]

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

big: Add Lsh and Value; convert pidigits to use big

This yields a pretty significant performance boost to pidigits and there are
still some improvements to be made. Here are my numbers:

amd64 w/ bignum:
pidigits 10000
        gcc -O2 pidigits.c -lgmp        2.10u 0.00s 2.10r
        gc pidigits     22.92u 0.02s 22.97r
        gc_B pidigits   22.62u 0.00s 22.65r

amd64 w/ big:
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

386 w/ bignum:
pidigits 10000
        gcc -O2 pidigits.c -lgmp        2.09u 0.00s 2.09r
        gc pidigits     44.30u 0.01s 44.35r
        gc_B pidigits   44.29u 0.03s 44.35r

386 w/ big:
pidigits 10000
        gcc -O2 pidigits.c -lgmp        2.10u 0.00s 2.10r
        gc pidigits     22.70u 0.06s 22.79r
        gc_B pidigits   22.80u 0.09s 22.91r

R=rsc, gri
CC=golang-dev
http://codereview.appspot.com/881050

Committer: Russ Cox <rsc@golang.org>