code review 168480043: test/fibo: a stand-alone bignum/allocation benchmark an...

test/fibo: a stand-alone bignum/allocation benchmark and test

Usage:
fibo <n>        compute fibonacci(n), n must be >= 0
fibo -bench     benchmark fibonacci computation (takes about 1 min)

Additional flags:
-half           add values using two half-digit additions
-opt            optimize memory allocation through reuse
-short          only print the first 10 digits of very large fibonacci numbers

[gri, 2014-11-11 01:46:01]

Hello adonovan@google.com (cc: golang-codereviews@googlegroups.com),

I'd like you to review this change to
https://code.google.com/p/go/

[adonovan, 2014-11-11 14:59:37]

LGTM

https://codereview.appspot.com/168480043/diff/40001/test/fibo.go
File test/fibo.go (right):

https://codereview.appspot.com/168480043/diff/40001/test/fibo.go#newcode15
test/fibo.go:15: // entirely in Go.
Would be good to state that this code is derived from the other code in
math/big.

https://codereview.appspot.com/168480043/diff/40001/test/fibo.go#newcode36
test/fibo.go:36: // a big.Word; the value zero corresponds to the emty nat
slice.
typo: empty

https://codereview.appspot.com/168480043/diff/40001/test/fibo.go#newcode42
test/fibo.go:42: // stand-alone program that can easily be run w/o dependencies
and
"without"

https://codereview.appspot.com/168480043/diff/40001/test/fibo.go#newcode47
test/fibo.go:47: return z[0:n] // reuse z
z[:n]

https://codereview.appspot.com/168480043/diff/40001/test/fibo.go#newcode55
test/fibo.go:55: // z = x
Intriguingly this works even if the two slices alias each other.

(It's a funny thing about slices: you have to consider this case to ensure that
you've covered the necessary possibilities, but there's neither a convenient
vocabulary to describe it precisely, nor a "safe" way to test for it.)

https://codereview.appspot.com/168480043/diff/40001/test/fibo.go#newcode64
test/fibo.go:64: m := len(x)
nx, ny would be easier to remember.

https://codereview.appspot.com/168480043/diff/40001/test/fibo.go#newcode188
test/fibo.go:188: fmt.Printf("error: unexpected wordsize %d", W)
"BUG: ..."

or exit nonzero.

https://codereview.appspot.com/168480043/diff/40001/test/fibo.go#newcode195
test/fibo.go:195: fmt.Printf("error: got std fibo(%d) = %s; want %s\n", test.n,
gotStd, test.want)
ditto

https://codereview.appspot.com/168480043/diff/40001/test/fibo.go#newcode199
test/fibo.go:199: fmt.Printf("error: got opt fibo(%d) = %s; want %s\n", test.n,
gotOpt, test.want)
ditto

[gri, 2014-11-11 17:35:07]

https://codereview.appspot.com/168480043/diff/40001/test/fibo.go
File test/fibo.go (right):

https://codereview.appspot.com/168480043/diff/40001/test/fibo.go#newcode15
test/fibo.go:15: // entirely in Go.
On 2014/11/11 14:59:36, adonovan wrote:
> Would be good to state that this code is derived from the other code in
> math/big.

stated in a comment below

https://codereview.appspot.com/168480043/diff/40001/test/fibo.go#newcode36
test/fibo.go:36: // a big.Word; the value zero corresponds to the emty nat
slice.
On 2014/11/11 14:59:36, adonovan wrote:
> typo: empty

Done.

https://codereview.appspot.com/168480043/diff/40001/test/fibo.go#newcode42
test/fibo.go:42: // stand-alone program that can easily be run w/o dependencies
and
On 2014/11/11 14:59:36, adonovan wrote:
> "without"

Done.

https://codereview.appspot.com/168480043/diff/40001/test/fibo.go#newcode47
test/fibo.go:47: return z[0:n] // reuse z
On 2014/11/11 14:59:36, adonovan wrote:
> z[:n]

Done.

https://codereview.appspot.com/168480043/diff/40001/test/fibo.go#newcode55
test/fibo.go:55: // z = x
On 2014/11/11 14:59:37, adonovan wrote:
> Intriguingly this works even if the two slices alias each other.
> 
> (It's a funny thing about slices: you have to consider this case to ensure
that
> you've covered the necessary possibilities, but there's neither a convenient
> vocabulary to describe it precisely, nor a "safe" way to test for it.)

Acknowledged.

https://codereview.appspot.com/168480043/diff/40001/test/fibo.go#newcode64
test/fibo.go:64: m := len(x)
On 2014/11/11 14:59:36, adonovan wrote:
> nx, ny would be easier to remember.

x, y and m, n are used systematically in bi.nat where this code was lifted from

https://codereview.appspot.com/168480043/diff/40001/test/fibo.go#newcode188
test/fibo.go:188: fmt.Printf("error: unexpected wordsize %d", W)
On 2014/11/11 14:59:36, adonovan wrote:
> "BUG: ..."
> 
> or exit nonzero.

Done.

https://codereview.appspot.com/168480043/diff/40001/test/fibo.go#newcode195
test/fibo.go:195: fmt.Printf("error: got std fibo(%d) = %s; want %s\n", test.n,
gotStd, test.want)
On 2014/11/11 14:59:36, adonovan wrote:
> ditto

Done.

https://codereview.appspot.com/168480043/diff/40001/test/fibo.go#newcode199
test/fibo.go:199: fmt.Printf("error: got opt fibo(%d) = %s; want %s\n", test.n,
gotOpt, test.want)
On 2014/11/11 14:59:36, adonovan wrote:
> ditto

Done.

[gri, 2014-11-11 23:43:53]

PTAL. Added a 2nd mode (-half) to emulate half-digit addition to compare
with an implementation that operates on 32bits (or 16).

On Tue Nov 11 2014 at 9:35:08 AM <gri@golang.org> wrote:

>
> https://codereview.appspot.com/168480043/diff/40001/test/fibo.go
> File test/fibo.go (right):
>
> https://codereview.appspot.com/168480043/diff/40001/test/fibo.go#newcode15
> test/fibo.go:15
>
<https://codereview.appspot.com/168480043/diff/40001/test/fibo.go#newcode15tes...>:
> // entirely in Go.
> On 2014/11/11 14:59:36, adonovan wrote:
> > Would be good to state that this code is derived from the other code
> in
> > math/big.
>
> stated in a comment below
>
> https://codereview.appspot.com/168480043/diff/40001/test/fibo.go#newcode36
> test/fibo.go:36
>
<https://codereview.appspot.com/168480043/diff/40001/test/fibo.go#newcode36tes...>:
> // a big.Word; the value zero corresponds to the emty
> nat slice.
> On 2014/11/11 14:59:36, adonovan wrote:
> > typo: empty
>
> Done.
>
> https://codereview.appspot.com/168480043/diff/40001/test/fibo.go#newcode42
> test/fibo.go:42
>
<https://codereview.appspot.com/168480043/diff/40001/test/fibo.go#newcode42tes...>:
> // stand-alone program that can easily be run w/o
> dependencies and
> On 2014/11/11 14:59:36, adonovan wrote:
> > "without"
>
> Done.
>
> https://codereview.appspot.com/168480043/diff/40001/test/fibo.go#newcode47
> test/fibo.go:47
>
<https://codereview.appspot.com/168480043/diff/40001/test/fibo.go#newcode47tes...>:
> return z[0:n] // reuse z
> On 2014/11/11 14:59:36, adonovan wrote:
> > z[:n]
>
> Done.
>
> https://codereview.appspot.com/168480043/diff/40001/test/fibo.go#newcode55
> test/fibo.go:55
>
<https://codereview.appspot.com/168480043/diff/40001/test/fibo.go#newcode55tes...>:
> // z = x
> On 2014/11/11 14:59:37, adonovan wrote:
> > Intriguingly this works even if the two slices alias each other.
>
> > (It's a funny thing about slices: you have to consider this case to
> ensure that
> > you've covered the necessary possibilities, but there's neither a
> convenient
> > vocabulary to describe it precisely, nor a "safe" way to test for it.)
>
> Acknowledged.
>
> https://codereview.appspot.com/168480043/diff/40001/test/fibo.go#newcode64
> test/fibo.go:64
>
<https://codereview.appspot.com/168480043/diff/40001/test/fibo.go#newcode64tes...>:
> m := len(x)
> On 2014/11/11 14:59:36, adonovan wrote:
> > nx, ny would be easier to remember.
>
> x, y and m, n are used systematically in bi.nat where this code was
> lifted from
>
> https://codereview.appspot.com/168480043/diff/40001/test/
> fibo.go#newcode188
> test/fibo.go:188
>
<https://codereview.appspot.com/168480043/diff/40001/test/fibo.go#newcode188te...>:
> fmt.Printf("error: unexpected wordsize %d", W)
> On 2014/11/11 14:59:36, adonovan wrote:
> > "BUG: ..."
>
> > or exit nonzero.
>
> Done.
>
> https://codereview.appspot.com/168480043/diff/40001/test/
> fibo.go#newcode195
> test/fibo.go:195
>
<https://codereview.appspot.com/168480043/diff/40001/test/fibo.go#newcode195te...>:
> fmt.Printf("error: got std fibo(%d) = %s; want %s\n",
> test.n, gotStd, test.want)
> On 2014/11/11 14:59:36, adonovan wrote:
> > ditto
>
> Done.
>
> https://codereview.appspot.com/168480043/diff/40001/test/
> fibo.go#newcode199
> test/fibo.go:199
>
<https://codereview.appspot.com/168480043/diff/40001/test/fibo.go#newcode199te...>:
> fmt.Printf("error: got opt fibo(%d) = %s; want %s\n",
> test.n, gotOpt, test.want)
> On 2014/11/11 14:59:36, adonovan wrote:
> > ditto
>
> Done.
>
> https://codereview.appspot.com/168480043/
>

[adonovan, 2014-11-13 18:17:16]

LGTM

https://codereview.appspot.com/168480043/diff/60001/test/fibo.go
File test/fibo.go (right):

https://codereview.appspot.com/168480043/diff/60001/test/fibo.go#newcode9
test/fibo.go:9: // Additional flags:
The concept of half-digits could use some explanation.

https://codereview.appspot.com/168480043/diff/60001/test/fibo.go#newcode83
test/fibo.go:83: const M2 = (1 << W2) - 1
// lower half-digit mask

[gri, 2014-11-13 18:27:32]

https://codereview.appspot.com/168480043/diff/60001/test/fibo.go
File test/fibo.go (right):

https://codereview.appspot.com/168480043/diff/60001/test/fibo.go#newcode9
test/fibo.go:9: // Additional flags:
On 2014/11/13 18:17:16, adonovan wrote:
> The concept of half-digits could use some explanation.

yes - but whoever looks at this test will have to look at the code anyway - and
the code is pretty clear

leaving as is, especially because as a test it doesn't require any settings - it
either passes or fails

https://codereview.appspot.com/168480043/diff/60001/test/fibo.go#newcode83
test/fibo.go:83: const M2 = (1 << W2) - 1
On 2014/11/13 18:17:16, adonovan wrote:
> // lower half-digit mask

Done.

[gobot, 2014-12-19 05:15:21]

R=close

To the author of this CL:

The Go project has moved to Gerrit Code Review.

If this CL should be continued, please see the latest version of
https://golang.org/doc/contribute.html for instructions on
how to set up Git and the Go project's Gerrit codereview plugin,
and then create a new change with your current code.

If there has been discussion on this CL, please give a link to it
(golang.org/cl/168480043 is best) in the description in your
new CL.

Thanks very much.