code review 4538053: big: add Int methods to act on numbered bits.

big: add Int methods to act on numbered bits.
Speeds up setting individual bits by ~75%, useful
when using big.Int as a bit set.

[rog, 2011-05-12 12:40:39]

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

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

[rog, 2011-05-12 12:43:01]

i wasn't sure whether to make the bit number a uint or an int.
i can see arguments both ways (if uint, the consequences of
passing doing SetBit(x, uint(-1), true) could be severe - int allows the
value to be checked)

On 12 May 2011 13:40,  <rogpeppe@gmail.com> wrote:
> Reviewers: gri,
>
> Message:
> Hello gri (cc: golang-dev@googlegroups.com),
>
> I'd like you to review this change to
> https://go.googlecode.com/hg/
>
>
> Description:
> big: add Int methods to act on numbered bits.
> Speeds up setting individual bits by ~75%, useful
> when using big.Int as a bit set.
>
> Please review this at http://codereview.appspot.com/4538053/
>
> Affected files:
>  M src/pkg/big/int.go
>  M src/pkg/big/int_test.go
>  M src/pkg/big/nat.go
>
>
>

[gri, 2011-05-12 18:54:49]

I'll have a look at the tests in a 2nd round.

I am wondering if it would make sense to return the i'th bit as 1 or 0 instead
of true or false.

The bit() functions would be equally fast. The SetBit functions could take a <
0, 0, > 0 as bit value , with < 0 meaning xor. In the value == 0 case nothing
changes. In the value != case there would be an extra if, but that's about it.

Just a thought.

Also, as it is, I am tempted to call the functions just Test and Set (the result
is a bool). With Bit() I am more inclined to get a 0 or 1.

http://codereview.appspot.com/4538053/diff/11001/src/pkg/big/int.go
File src/pkg/big/int.go (right):

http://codereview.appspot.com/4538053/diff/11001/src/pkg/big/int.go#newcode563
src/pkg/big/int.go:563: // Bit returns the b'th bit of z, (z & (1 << b)) != 0.
// Bit returns the value of the i'th bit of z. That is, it returns (z & (1 <<
b)) != 0.
// The bit index i must be >= 0.

(matching the description of SetBit)

http://codereview.appspot.com/4538053/diff/11001/src/pkg/big/int.go#newcode564
src/pkg/big/int.go:564: func (z *Int) Bit(b int) bool {
I would probably call it i: Bit(i int); as in the bit index i.
In Go, indices are integers, I think it's ok to not use uint here.

http://codereview.appspot.com/4538053/diff/11001/src/pkg/big/int.go#newcode576
src/pkg/big/int.go:576: // SetBit sets the b'th bit to the given value.
SetBit sets the i'th bit of z to bit and returns z.
That is, if ...

http://codereview.appspot.com/4538053/diff/11001/src/pkg/big/nat.go
File src/pkg/big/nat.go (right):

http://codereview.appspot.com/4538053/diff/11001/src/pkg/big/nat.go#newcode793
src/pkg/big/nat.go:793: func (z nat) setBit(x nat, b uint, bit bool) nat {
Please move this functions above "and" - they are in the middle of section of
and, andNot, or, xor, and don't belong here (also, then it matches the order in
int.go). 

Also, I suggest the order:

bit
setBit

http://codereview.appspot.com/4538053/diff/11001/src/pkg/big/nat.go#newcode794
src/pkg/big/nat.go:794: i := int(b >> _W)
i := b/_W
m := 1 << (b%_W)
n := len(x)


I am surprised the tests worked as it's % and not << for the index i
computation.

http://codereview.appspot.com/4538053/diff/11001/src/pkg/big/nat.go#newcode796
src/pkg/big/nat.go:796: n := i + 1
instead of lines 796-799:

if i >= n {
    n = i+1
}

http://codereview.appspot.com/4538053/diff/11001/src/pkg/big/nat.go#newcode802
src/pkg/big/nat.go:802: z[i] |= 1 << (b & (_W - 1))
z[i] |= m

http://codereview.appspot.com/4538053/diff/11001/src/pkg/big/nat.go#newcode803
src/pkg/big/nat.go:803: return z // no need to normalize.
s/.//

http://codereview.appspot.com/4538053/diff/11001/src/pkg/big/nat.go#newcode805
src/pkg/big/nat.go:805: z = z.make(len(x))
s/len(x)/n/

(symmetric to the code above)

http://codereview.appspot.com/4538053/diff/11001/src/pkg/big/nat.go#newcode807
src/pkg/big/nat.go:807: if i >= len(z) {
if i >= n { ...

(symmetric to the code suggested above - in this case we don't need to grow)

http://codereview.appspot.com/4538053/diff/11001/src/pkg/big/nat.go#newcode808
src/pkg/big/nat.go:808: return z
in this case we have the mask m computed but didn't need it. However, arguably
this is not a common case (clearing bits outside the range). Computing the mask
once makes this code easier to read and less error-prone.

http://codereview.appspot.com/4538053/diff/11001/src/pkg/big/nat.go#newcode810
src/pkg/big/nat.go:810: z[i] &^= 1 << (b & (_W - 1))
z[i] &^= m

http://codereview.appspot.com/4538053/diff/11001/src/pkg/big/nat.go#newcode815
src/pkg/big/nat.go:815: i := int(b >> _W)
this should be b/_W

http://codereview.appspot.com/4538053/diff/11001/src/pkg/big/nat.go#newcode819
src/pkg/big/nat.go:819: return z[i]&(1<<(b&(_W-1))) != 0
return z[i] & (1 << (b%_W)) != 0

or perhaps, for symmetry with the code above:

m := 1 << (b%_W)
return z[i] & m != 0

much nicer to read

[rog, 2011-05-12 19:35:30]

oops. thanks for the review. will fix tomorrow.

http://codereview.appspot.com/4538053/diff/11001/src/pkg/big/nat.go
File src/pkg/big/nat.go (right):

http://codereview.appspot.com/4538053/diff/11001/src/pkg/big/nat.go#newcode794
src/pkg/big/nat.go:794: i := int(b >> _W)
On 2011/05/12 18:54:49, gri wrote:
> i := b/_W
> m := 1 << (b%_W)
> n := len(x)
> 
> 
> I am surprised the tests worked as it's % and not << for the index i
> computation.

i'm surprised too. bad tests. and i've done this before, how did i get that
wrong? can we do log2(number of bits in word) in const exprs?

[gri, 2011-05-12 19:41:48]

On Thu, May 12, 2011 at 12:35 PM,  <rogpeppe@gmail.com> wrote:
> oops. thanks for the review. will fix tomorrow.
>
>
> http://codereview.appspot.com/4538053/diff/11001/src/pkg/big/nat.go
> File src/pkg/big/nat.go (right):
>
> http://codereview.appspot.com/4538053/diff/11001/src/pkg/big/nat.go#newcode794
> src/pkg/big/nat.go:794: i := int(b >> _W)
> On 2011/05/12 18:54:49, gri wrote:
>>
>> i := b/_W
>> m := 1 << (b%_W)
>> n := len(x)
>
>
>> I am surprised the tests worked as it's % and not << for the index i
>> computation.
>
> i'm surprised too. bad tests. and i've done this before, how did i get
> that wrong? can we do log2(number of bits in word) in const exprs?

b/_W and b%_W should be strength-reduced by the compiler to a shift
and a & with mask since _W is a constant > 0 and b is unsigned.
There's no need to do this manually.

- gri

>
> http://codereview.appspot.com/4538053/
>

[rog, 2011-05-16 12:01:49]

PTAL

> I am wondering if it would make sense to return the i'th bit as 1 or 0
> instead of true or false.

i started doing this, and then realised that it was quite nice that
it was not possible to mix up the arguments in SetBit, so i left
it as bool.

Test and Set would be nice, but Set is already taken.

http://codereview.appspot.com/4538053/diff/11001/src/pkg/big/int.go
File src/pkg/big/int.go (right):

http://codereview.appspot.com/4538053/diff/11001/src/pkg/big/int.go#newcode563
src/pkg/big/int.go:563: // Bit returns the b'th bit of z, (z & (1 << b)) != 0.
On 2011/05/12 18:54:49, gri wrote:
> // Bit returns the value of the i'th bit of z. That is, it returns (z & (1 <<
> b)) != 0.
> // The bit index i must be >= 0.
> 
> (matching the description of SetBit)

Done.

http://codereview.appspot.com/4538053/diff/11001/src/pkg/big/int.go#newcode564
src/pkg/big/int.go:564: func (z *Int) Bit(b int) bool {
On 2011/05/12 18:54:49, gri wrote:
> I would probably call it i: Bit(i int); as in the bit index i.
> In Go, indices are integers, I think it's ok to not use uint here.

Done.

http://codereview.appspot.com/4538053/diff/11001/src/pkg/big/nat.go
File src/pkg/big/nat.go (right):

http://codereview.appspot.com/4538053/diff/11001/src/pkg/big/nat.go#newcode802
src/pkg/big/nat.go:802: z[i] |= 1 << (b & (_W - 1))
On 2011/05/12 18:54:49, gri wrote:
> z[i] |= m

Done.

http://codereview.appspot.com/4538053/diff/11001/src/pkg/big/nat.go#newcode803
src/pkg/big/nat.go:803: return z // no need to normalize.
On 2011/05/12 18:54:49, gri wrote:
> s/.//

Done.

http://codereview.appspot.com/4538053/diff/11001/src/pkg/big/nat.go#newcode805
src/pkg/big/nat.go:805: z = z.make(len(x))
On 2011/05/12 18:54:49, gri wrote:
> s/len(x)/n/
> 
> (symmetric to the code above)

Done.

http://codereview.appspot.com/4538053/diff/11001/src/pkg/big/nat.go#newcode807
src/pkg/big/nat.go:807: if i >= len(z) {
On 2011/05/12 18:54:49, gri wrote:
> if i >= n { ...
> 
> (symmetric to the code suggested above - in this case we don't need to grow)

Done.

http://codereview.appspot.com/4538053/diff/11001/src/pkg/big/nat.go#newcode808
src/pkg/big/nat.go:808: return z
On 2011/05/12 18:54:49, gri wrote:
> in this case we have the mask m computed but didn't need it. However, arguably
> this is not a common case (clearing bits outside the range). Computing the
mask
> once makes this code easier to read and less error-prone.

Done.

http://codereview.appspot.com/4538053/diff/11001/src/pkg/big/nat.go#newcode810
src/pkg/big/nat.go:810: z[i] &^= 1 << (b & (_W - 1))
On 2011/05/12 18:54:49, gri wrote:
> z[i] &^= m

Done.

http://codereview.appspot.com/4538053/diff/11001/src/pkg/big/nat.go#newcode815
src/pkg/big/nat.go:815: i := int(b >> _W)
On 2011/05/12 18:54:49, gri wrote:
> this should be b/_W

Done.

http://codereview.appspot.com/4538053/diff/11001/src/pkg/big/nat.go#newcode819
src/pkg/big/nat.go:819: return z[i]&(1<<(b&(_W-1))) != 0
On 2011/05/12 18:54:49, gri wrote:
> return z[i] & (1 << (b%_W)) != 0
> 
> or perhaps, for symmetry with the code above:
> 
> m := 1 << (b%_W)
> return z[i] & m != 0
> 
> much nicer to read

Done.

[rsc, 2011-05-16 12:48:20]

http://codereview.appspot.com/4538053/diff/6/src/pkg/big/int.go
File src/pkg/big/int.go (right):

http://codereview.appspot.com/4538053/diff/6/src/pkg/big/int.go#newcode564
src/pkg/big/int.go:564: func (z *Int) Bit(i int) bool {
seems like i should be uint to match shifts.

A bit is a binary digit, a 0 or 1.
A bool is one possible interpretation of a bit but not the only one.
Returning bool here conflates two related but distinct concepts.

I think these should be 

func (z *Int) Bit(i uint) int 
func (z *Int) SetBit(x *Int, i uint, b int)

http://codereview.appspot.com/4538053/diff/6/src/pkg/big/int.go#newcode577
src/pkg/big/int.go:577: // That is, if bit is true SetBit sets z = x | (1 << b),
s/b/i/

http://codereview.appspot.com/4538053/diff/6/src/pkg/big/int.go#newcode578
src/pkg/big/int.go:578: // otherwise it sets z = x &^ (1 << b).
s/b/i/

http://codereview.appspot.com/4538053/diff/6/src/pkg/big/int.go#newcode580
src/pkg/big/int.go:580: func (z *Int) SetBit(x *Int, i int, bit bool) *Int {
same

[rog, 2011-05-16 13:17:51]

On 16 May 2011 13:48,  <rsc@golang.org> wrote:
>
> http://codereview.appspot.com/4538053/diff/6/src/pkg/big/int.go
> File src/pkg/big/int.go (right):
>
> http://codereview.appspot.com/4538053/diff/6/src/pkg/big/int.go#newcode564
> src/pkg/big/int.go:564: func (z *Int) Bit(i int) bool {
> seems like i should be uint to match shifts.

i'm not sure that uint is right here.

if i accidentally do x.SetBit(x, uint(i-1), true) where i happens
to be zero then i suddenly use 1GB of memory. as
with arrays it's more useful to get a panic.

> A bit is a binary digit, a 0 or 1.
> A bool is one possible interpretation of a bit but not the only one.
> Returning bool here conflates two related but distinct concepts.
>
> I think these should be
>
> func (z *Int) Bit(i uint) int
> func (z *Int) SetBit(x *Int, i uint, b int)

if b is an int, what do we do when b is not zero or one?

that's the nice thing about using bool - you don't have to
worry about this, which saves at least one test.

[rog, 2011-05-16 13:19:57]

http://codereview.appspot.com/4538053/diff/6/src/pkg/big/int.go
File src/pkg/big/int.go (right):

http://codereview.appspot.com/4538053/diff/6/src/pkg/big/int.go#newcode577
src/pkg/big/int.go:577: // That is, if bit is true SetBit sets z = x | (1 << b),
On 2011/05/16 12:48:20, rsc wrote:
> s/b/i/

Done.

http://codereview.appspot.com/4538053/diff/6/src/pkg/big/int.go#newcode578
src/pkg/big/int.go:578: // otherwise it sets z = x &^ (1 << b).
On 2011/05/16 12:48:20, rsc wrote:
> s/b/i/

Done.

http://codereview.appspot.com/4538053/diff/6/src/pkg/big/int.go#newcode580
src/pkg/big/int.go:580: func (z *Int) SetBit(x *Int, i int, bit bool) *Int {
On 2011/05/16 12:48:20, rsc wrote:
> same
?

[gri, 2011-05-16 17:46:36]

http://codereview.appspot.com/4538053/diff/10004/src/pkg/big/int.go
File src/pkg/big/int.go (right):

http://codereview.appspot.com/4538053/diff/10004/src/pkg/big/int.go#newcode564
src/pkg/big/int.go:564: func (z *Int) Bit(i int) bool {
We had some discussions here (r, rsc, gri) and we believe that these should be:

Bit(i int) uint
SetBit(x *Int, i int, b uint) *Int

Bit returns either 0 or 1; SetBit accepts 0 or 1 for b and other values cause
panics. 

Go indices are always ints; a bit is a (unsigned) binary digit and thus a number
0 or 1. Also, by keeping those as int and uint (as opposed to int, int), there
is a smaller chance of confusion.

http://codereview.appspot.com/4538053/diff/10004/src/pkg/big/nat.go
File src/pkg/big/nat.go (right):

http://codereview.appspot.com/4538053/diff/10004/src/pkg/big/nat.go#newcode776
src/pkg/big/nat.go:776: func (z nat) setBit(x nat, b uint, bit bool) nat {
setBit(x nat, i int, b uint) nat

http://codereview.appspot.com/4538053/diff/10004/src/pkg/big/nat.go#newcode781
src/pkg/big/nat.go:781: if bit {
switch b {
case 0:
case 1:
}
panic(...)

http://codereview.appspot.com/4538053/diff/10004/src/pkg/big/nat.go#newcode789
src/pkg/big/nat.go:789: }
please put an empty line after 789 or remove the one at 780 (i'm in favor of the
former, to make the two cases visually very clear)

http://codereview.appspot.com/4538053/diff/10004/src/pkg/big/nat.go#newcode800
src/pkg/big/nat.go:800: func (z nat) bit(b uint) bool {
bit(i int) uint

http://codereview.appspot.com/4538053/diff/10004/src/pkg/big/nat.go#newcode805
src/pkg/big/nat.go:805: m := Word(1) << (b % _W)
return uint(z[i] >> (b % W) & 1)

[rog, 2011-05-16 17:59:47]

On 16 May 2011 18:46,  <gri@golang.org> wrote:
>
> http://codereview.appspot.com/4538053/diff/10004/src/pkg/big/int.go
> File src/pkg/big/int.go (right):
>
> http://codereview.appspot.com/4538053/diff/10004/src/pkg/big/int.go#newcode564
> src/pkg/big/int.go:564: func (z *Int) Bit(i int) bool {
> We had some discussions here (r, rsc, gri) and we believe that these
> should be:
>
> Bit(i int) uint
> SetBit(x *Int, i int, b uint) *Int
>
> Bit returns either 0 or 1; SetBit accepts 0 or 1 for b and other values
> cause panics.
>
> Go indices are always ints; a bit is a (unsigned) binary digit and thus
> a number 0 or 1. Also, by keeping those as int and uint (as opposed to
> int, int), there is a smaller chance of confusion.

this seems good to me.
just one thing: it could be uint8 rather than uint,
but i don't really mind.

[gri, 2011-05-16 18:10:11]

I think it should be uint; there's no added benefit of making it a byte.

- gri

On Mon, May 16, 2011 at 10:59 AM, roger peppe <rogpeppe@gmail.com> wrote:
> On 16 May 2011 18:46,  <gri@golang.org> wrote:
>>
>> http://codereview.appspot.com/4538053/diff/10004/src/pkg/big/int.go
>> File src/pkg/big/int.go (right):
>>
>>
http://codereview.appspot.com/4538053/diff/10004/src/pkg/big/int.go#newcode564
>> src/pkg/big/int.go:564: func (z *Int) Bit(i int) bool {
>> We had some discussions here (r, rsc, gri) and we believe that these
>> should be:
>>
>> Bit(i int) uint
>> SetBit(x *Int, i int, b uint) *Int
>>
>> Bit returns either 0 or 1; SetBit accepts 0 or 1 for b and other values
>> cause panics.
>>
>> Go indices are always ints; a bit is a (unsigned) binary digit and thus
>> a number 0 or 1. Also, by keeping those as int and uint (as opposed to
>> int, int), there is a smaller chance of confusion.
>
> this seems good to me.
> just one thing: it could be uint8 rather than uint,
> but i don't really mind.
>

[rog, 2011-05-16 19:03:26]

PTAL

http://codereview.appspot.com/4538053/diff/10004/src/pkg/big/nat.go
File src/pkg/big/nat.go (right):

http://codereview.appspot.com/4538053/diff/10004/src/pkg/big/nat.go#newcode776
src/pkg/big/nat.go:776: func (z nat) setBit(x nat, b uint, bit bool) nat {
On 2011/05/16 17:46:36, gri wrote:
> setBit(x nat, i int, b uint) nat

Done.

http://codereview.appspot.com/4538053/diff/10004/src/pkg/big/nat.go#newcode781
src/pkg/big/nat.go:781: if bit {
On 2011/05/16 17:46:36, gri wrote:
> switch b {
> case 0:
> case 1:
> }
> panic(...)

Done.

http://codereview.appspot.com/4538053/diff/10004/src/pkg/big/nat.go#newcode789
src/pkg/big/nat.go:789: }
On 2011/05/16 17:46:36, gri wrote:
> please put an empty line after 789 or remove the one at 780 (i'm in favor of
the
> former, to make the two cases visually very clear)

Done.

http://codereview.appspot.com/4538053/diff/10004/src/pkg/big/nat.go#newcode800
src/pkg/big/nat.go:800: func (z nat) bit(b uint) bool {
On 2011/05/16 17:46:36, gri wrote:
> bit(i int) uint

Done.

http://codereview.appspot.com/4538053/diff/10004/src/pkg/big/nat.go#newcode805
src/pkg/big/nat.go:805: m := Word(1) << (b % _W)
On 2011/05/16 17:46:36, gri wrote:
> return uint(z[i] >> (b % W) & 1)

Done.

[gri, 2011-05-16 20:27:23]

It's close.

http://codereview.appspot.com/4538053/diff/17001/src/pkg/big/nat.go
File src/pkg/big/nat.go (right):

http://codereview.appspot.com/4538053/diff/17001/src/pkg/big/nat.go#newcode776
src/pkg/big/nat.go:776: func (z nat) setBit(x nat, i int, b uint) nat {
I think the index checking should also happen in this function (and bit, below)
since you're passing in an int (and since the value of b is also checked here).
Alternatively, this function should take a uint index (it's internal).

[rog, 2011-05-16 21:02:14]

I had a uint index originally for this reason, and I changed it to int as
suggested, but I'll change it back.
On 16 May 2011 21:27, <gri@golang.org> wrote:
> It's close.
>
>
>
> http://codereview.appspot.com/4538053/diff/17001/src/pkg/big/nat.go
> File src/pkg/big/nat.go (right):
>
>
http://codereview.appspot.com/4538053/diff/17001/src/pkg/big/nat.go#newcode776
> src/pkg/big/nat.go:776: func (z nat) setBit(x nat, i int, b uint) nat {
> I think the index checking should also happen in this function (and bit,
> below) since you're passing in an int (and since the value of b is also
> checked here). Alternatively, this function should take a uint index
> (it's internal).
>
> http://codereview.appspot.com/4538053/

[rog, 2011-05-17 06:47:39]

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

Please take another look.

[rsc, 2011-05-17 14:35:44]

LGTM

Leaving for gri.

[gri, 2011-05-17 15:55:45]

It looks like it's unchanged. But when I look at patch set 13 your
changes (int -> uint) are there. Did you change it back? Please
advise.
- Robert

On Mon, May 16, 2011 at 11:47 PM,  <rogpeppe@gmail.com> wrote:
> Hello gri, rsc (cc: golang-dev@googlegroups.com),
>
> Please take another look.
>
>
> http://codereview.appspot.com/4538053/
>

[rog, 2011-05-17 17:12:50]

I'm fairly sure I didn't change it back, and the usual "View" link seems to
show what I expect (with the nat index int->uint changes). I'm away from my
computer currently, so I can't check properly until tomorrow.
On 17 May 2011 16:55, "Robert Griesemer" <gri@golang.org> wrote:
> It looks like it's unchanged. But when I look at patch set 13 your
> changes (int -> uint) are there. Did you change it back? Please
> advise.
> - Robert
>
> On Mon, May 16, 2011 at 11:47 PM, <rogpeppe@gmail.com> wrote:
>> Hello gri, rsc (cc: golang-dev@googlegroups.com),
>>
>> Please take another look.
>>
>>
>> http://codereview.appspot.com/4538053/
>>

[gri, 2011-05-17 20:37:12]

LGTM

I got it. I was expecting that you were also switching the
Int.Bit/SetBit index to uint. My suggestion before was to move the >=
0 check into the nat code (since that is also the place where you do
the 0, 1 bit check. But never mind this is fine. We can always refine.

On Tue, May 17, 2011 at 10:12 AM, roger peppe <rogpeppe@gmail.com> wrote:
> I'm fairly sure I didn't change it back, and the usual "View" link seems to
> show what I expect (with the nat index int->uint changes). I'm away from my
> computer currently, so I can't check properly until tomorrow.
>
> On 17 May 2011 16:55, "Robert Griesemer" <gri@golang.org> wrote:
>> It looks like it's unchanged. But when I look at patch set 13 your
>> changes (int -> uint) are there. Did you change it back? Please
>> advise.
>> - Robert
>>
>> On Mon, May 16, 2011 at 11:47 PM, <rogpeppe@gmail.com> wrote:
>>> Hello gri, rsc (cc: golang-dev@googlegroups.com),
>>>
>>> Please take another look.
>>>
>>>
>>> http://codereview.appspot.com/4538053/
>>>
>

[gri, 2011-05-17 20:38:25]

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

big: add Int methods to act on numbered bits.
Speeds up setting individual bits by ~75%, useful
when using big.Int as a bit set.

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

Committer: Robert Griesemer <gri@golang.org>