code review 5413043: big/nat: Improve decimal string output from O(N^2) to ...

big/nat:  Improve decimal string output from O(N^2) to something less

Changes the decimal string output from successive div/mod
to divide-and-conquer by a large power of 10 of size roughly
half the number of decimal digits in the nat.  Uses this
algorithm until 4096 bits, at which point it reverts to the
prior successive div/mod algorithm.

No change to times for "small" nats, but significant for
thousands of bits or more:

Before:
big.BenchmarkStringShort10        100000             26828 ns/op
big.BenchmarkStringMedium10          500           3246320 ns/op
big.BenchmarkStringLong10              5         509510600 ns/op

After:
big.BenchmarkStringShort10        100000             28988 ns/op
big.BenchmarkStringMedium10         2000           1150566 ns/op
big.BenchmarkStringLong10             20          89172750 ns/op

[dga, 2011-11-17 22:38:31]

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

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

[gri, 2011-11-17 23:00:19]

Dave;

I might be wrong but I think this idea is already represented in the
other CL (by Michael Jones, cc:ed) that I mentioned to you; for all
bases not just base 10. Please correct me if I am wrong.

- Robert



On Thu, Nov 17, 2011 at 2:38 PM,  <dave.andersen@gmail.com> wrote:
> Reviewers: golang-dev_googlegroups.com,
>
> Message:
> Hello golang-dev@googlegroups.com (cc: golang-dev@googlegroups.com),
>
> I'd like you to review this change to
> https://go.googlecode.com/hg/
>
>
> Description:
> big/nat:  Improve decimal string output from O(N^2) to something less
>
> Changes the decimal string output from successive div/mod
> to divide-and-conquer by a large power of 10 of size roughly
> half the number of decimal digits in the nat.  Uses this
> algorithm until 4096 bits, at which point it reverts to the
> prior successive div/mod algorithm.
>
> No change to times for "small" nats, but significant for
> thousands of bits or more:
>
> Before:
> big.BenchmarkStringShort10        100000             26828 ns/op
> big.BenchmarkStringMedium10          500           3246320 ns/op
> big.BenchmarkStringLong10              5         509510600 ns/op
>
> After:
> big.BenchmarkStringShort10        100000             28988 ns/op
> big.BenchmarkStringMedium10         2000           1150566 ns/op
> big.BenchmarkStringLong10             20          89172750 ns/op
>
> Please review this at http://codereview.appspot.com/5413043/
>
> Affected files:
>  M src/pkg/math/big/nat.go
>
>
>

[mtj1, 2011-11-17 23:29:54]

Yes this is the case. Coded, submitted, and faster. Uses powers of
bigbase**(2**k) for 0<=k automatically, does (tries to) juggle the
intermediate "halves" of the big number smartly without unnecessary copies,
and simulates tail recursion to logarithmically reduce the number of
internal function calls.

I checked this all in immediately after the first approval (all done at
once but asked to check them in sequentially: first the simple and then the
clever.) That's been four to six months ago. The team has had a lot to do
and this code review has not yet risen to the top. It will, though, someday
make it out. Have faith.

Michael

P.S. If you can't wait or want to test against the to be approved code, see
attached. ;-)

On Thu, Nov 17, 2011 at 6:00 PM, Robert Griesemer <gri@golang.org> wrote:

> Dave;
>
> I might be wrong but I think this idea is already represented in the
> other CL (by Michael Jones, cc:ed) that I mentioned to you; for all
> bases not just base 10. Please correct me if I am wrong.
>
> - Robert
>
>
>
> On Thu, Nov 17, 2011 at 2:38 PM,  <dave.andersen@gmail.com> wrote:
> > Reviewers: golang-dev_googlegroups.com,
> >
> > Message:
> > Hello golang-dev@googlegroups.com (cc: golang-dev@googlegroups.com),
> >
> > I'd like you to review this change to
> > https://go.googlecode.com/hg/
> >
> >
> > Description:
> > big/nat:  Improve decimal string output from O(N^2) to something less
> >
> > Changes the decimal string output from successive div/mod
> > to divide-and-conquer by a large power of 10 of size roughly
> > half the number of decimal digits in the nat.  Uses this
> > algorithm until 4096 bits, at which point it reverts to the
> > prior successive div/mod algorithm.
> >
> > No change to times for "small" nats, but significant for
> > thousands of bits or more:
> >
> > Before:
> > big.BenchmarkStringShort10        100000             26828 ns/op
> > big.BenchmarkStringMedium10          500           3246320 ns/op
> > big.BenchmarkStringLong10              5         509510600 ns/op
> >
> > After:
> > big.BenchmarkStringShort10        100000             28988 ns/op
> > big.BenchmarkStringMedium10         2000           1150566 ns/op
> > big.BenchmarkStringLong10             20          89172750 ns/op
> >
> > Please review this at http://codereview.appspot.com/5413043/
> >
> > Affected files:
> >  M src/pkg/math/big/nat.go
> >
> >
> >
>



-- 
Michael T. Jones | Chief Technology Advocate  | mtj@google.com |  +1
650-335-5765

[dga, 2011-11-17 23:36:12]

Ah!  Now I see - it must be CL 4634075.  mtj's code is faster and
better than mine.  Apologies for not spotting that.

  -Dave



On Thu, Nov 17, 2011 at 6:29 PM, Michael Jones <mtj@google.com> wrote:
> Yes this is the case. Coded, submitted, and faster. Uses powers of
> bigbase**(2**k) for 0<=k automatically, does (tries to) juggle the
> intermediate "halves" of the big number smartly without unnecessary copies,
> and simulates tail recursion to logarithmically reduce the number of
> internal function calls.
> I checked this all in immediately after the first approval (all done at once
> but asked to check them in sequentially: first the simple and then the
> clever.) That's been four to six months ago. The team has had a lot to do
> and this code review has not yet risen to the top. It will, though, someday
> make it out. Have faith.
> Michael
> P.S. If you can't wait or want to test against the to be approved code, see
> attached. ;-)
>
> On Thu, Nov 17, 2011 at 6:00 PM, Robert Griesemer <gri@golang.org> wrote:
>>
>> Dave;
>>
>> I might be wrong but I think this idea is already represented in the
>> other CL (by Michael Jones, cc:ed) that I mentioned to you; for all
>> bases not just base 10. Please correct me if I am wrong.
>>
>> - Robert
>>
>>
>>
>> On Thu, Nov 17, 2011 at 2:38 PM,  <dave.andersen@gmail.com> wrote:
>> > Reviewers: golang-dev_googlegroups.com,
>> >
>> > Message:
>> > Hello golang-dev@googlegroups.com (cc: golang-dev@googlegroups.com),
>> >
>> > I'd like you to review this change to
>> > https://go.googlecode.com/hg/
>> >
>> >
>> > Description:
>> > big/nat:  Improve decimal string output from O(N^2) to something less
>> >
>> > Changes the decimal string output from successive div/mod
>> > to divide-and-conquer by a large power of 10 of size roughly
>> > half the number of decimal digits in the nat.  Uses this
>> > algorithm until 4096 bits, at which point it reverts to the
>> > prior successive div/mod algorithm.
>> >
>> > No change to times for "small" nats, but significant for
>> > thousands of bits or more:
>> >
>> > Before:
>> > big.BenchmarkStringShort10        100000             26828 ns/op
>> > big.BenchmarkStringMedium10          500           3246320 ns/op
>> > big.BenchmarkStringLong10              5         509510600 ns/op
>> >
>> > After:
>> > big.BenchmarkStringShort10        100000             28988 ns/op
>> > big.BenchmarkStringMedium10         2000           1150566 ns/op
>> > big.BenchmarkStringLong10             20          89172750 ns/op
>> >
>> > Please review this at http://codereview.appspot.com/5413043/
>> >
>> > Affected files:
>> >  M src/pkg/math/big/nat.go
>> >
>> >
>> >
>
>
>
> --
> Michael T. Jones | Chief Technology Advocate  | mtj@google.com |  +1
> 650-335-5765
>

[mtj1, 2011-11-17 23:38:44]

Oh, for some color, the code was completed (code, tests, tuning with and
without bounds checking, comment tweaks, internal parameter benchmarking,
and exhaustive performance profiling) in a day of coding in a Budapest
hotel room. Since the tuning benchmarks took 30 minutes to run between
parameter changes, I used the idle time to setup my camera, get out my
Sekonic lightmeter, position my tripod, and wait for the light to be just
so. Here's the resulting photograph:

http://michaeljonesphotography.smugmug.com/Street-Scenes/Budapest/19972428_jq...

This was my log log complexity Go big-multiply profile-patience pacifier.
;-)

On Thu, Nov 17, 2011 at 6:29 PM, Michael Jones <mtj@google.com> wrote:

> Yes this is the case. Coded, submitted, and faster. Uses powers of
> bigbase**(2**k) for 0<=k automatically, does (tries to) juggle the
> intermediate "halves" of the big number smartly without unnecessary copies,
> and simulates tail recursion to logarithmically reduce the number of
> internal function calls.
>
> I checked this all in immediately after the first approval (all done at
> once but asked to check them in sequentially: first the simple and then the
> clever.) That's been four to six months ago. The team has had a lot to do
> and this code review has not yet risen to the top. It will, though, someday
> make it out. Have faith.
>
> Michael
>
> P.S. If you can't wait or want to test against the to be approved code,
> see attached. ;-)
>
>
> On Thu, Nov 17, 2011 at 6:00 PM, Robert Griesemer <gri@golang.org> wrote:
>
>> Dave;
>>
>> I might be wrong but I think this idea is already represented in the
>> other CL (by Michael Jones, cc:ed) that I mentioned to you; for all
>> bases not just base 10. Please correct me if I am wrong.
>>
>> - Robert
>>
>>
>>
>> On Thu, Nov 17, 2011 at 2:38 PM,  <dave.andersen@gmail.com> wrote:
>> > Reviewers: golang-dev_googlegroups.com,
>> >
>> > Message:
>> > Hello golang-dev@googlegroups.com (cc: golang-dev@googlegroups.com),
>> >
>> > I'd like you to review this change to
>> > https://go.googlecode.com/hg/
>> >
>> >
>> > Description:
>> > big/nat:  Improve decimal string output from O(N^2) to something less
>> >
>> > Changes the decimal string output from successive div/mod
>> > to divide-and-conquer by a large power of 10 of size roughly
>> > half the number of decimal digits in the nat.  Uses this
>> > algorithm until 4096 bits, at which point it reverts to the
>> > prior successive div/mod algorithm.
>> >
>> > No change to times for "small" nats, but significant for
>> > thousands of bits or more:
>> >
>> > Before:
>> > big.BenchmarkStringShort10        100000             26828 ns/op
>> > big.BenchmarkStringMedium10          500           3246320 ns/op
>> > big.BenchmarkStringLong10              5         509510600 ns/op
>> >
>> > After:
>> > big.BenchmarkStringShort10        100000             28988 ns/op
>> > big.BenchmarkStringMedium10         2000           1150566 ns/op
>> > big.BenchmarkStringLong10             20          89172750 ns/op
>> >
>> > Please review this at http://codereview.appspot.com/5413043/
>> >
>> > Affected files:
>> >  M src/pkg/math/big/nat.go
>> >
>> >
>> >
>>
>
>
>
> --
> Michael T. Jones | Chief Technology Advocate  | mtj@google.com |  +1
> 650-335-5765
>
>


-- 
Michael T. Jones | Chief Technology Advocate  | mtj@google.com |  +1
650-335-5765

[gri, 2011-11-17 23:50:20]

Apologies for providing the wrong CL. I will use Michael Jones' CL
(which has been long in the waiting for a rewiew). Please abandon your
CL.
- Robert

On Thu, Nov 17, 2011 at 3:36 PM, David Andersen <dave.andersen@gmail.com> wrote:
> Ah!  Now I see - it must be CL 4634075.  mtj's code is faster and
> better than mine.  Apologies for not spotting that.
>
>  -Dave
>
>
>
> On Thu, Nov 17, 2011 at 6:29 PM, Michael Jones <mtj@google.com> wrote:
>> Yes this is the case. Coded, submitted, and faster. Uses powers of
>> bigbase**(2**k) for 0<=k automatically, does (tries to) juggle the
>> intermediate "halves" of the big number smartly without unnecessary copies,
>> and simulates tail recursion to logarithmically reduce the number of
>> internal function calls.
>> I checked this all in immediately after the first approval (all done at once
>> but asked to check them in sequentially: first the simple and then the
>> clever.) That's been four to six months ago. The team has had a lot to do
>> and this code review has not yet risen to the top. It will, though, someday
>> make it out. Have faith.
>> Michael
>> P.S. If you can't wait or want to test against the to be approved code, see
>> attached. ;-)
>>
>> On Thu, Nov 17, 2011 at 6:00 PM, Robert Griesemer <gri@golang.org> wrote:
>>>
>>> Dave;
>>>
>>> I might be wrong but I think this idea is already represented in the
>>> other CL (by Michael Jones, cc:ed) that I mentioned to you; for all
>>> bases not just base 10. Please correct me if I am wrong.
>>>
>>> - Robert
>>>
>>>
>>>
>>> On Thu, Nov 17, 2011 at 2:38 PM,  <dave.andersen@gmail.com> wrote:
>>> > Reviewers: golang-dev_googlegroups.com,
>>> >
>>> > Message:
>>> > Hello golang-dev@googlegroups.com (cc: golang-dev@googlegroups.com),
>>> >
>>> > I'd like you to review this change to
>>> > https://go.googlecode.com/hg/
>>> >
>>> >
>>> > Description:
>>> > big/nat:  Improve decimal string output from O(N^2) to something less
>>> >
>>> > Changes the decimal string output from successive div/mod
>>> > to divide-and-conquer by a large power of 10 of size roughly
>>> > half the number of decimal digits in the nat.  Uses this
>>> > algorithm until 4096 bits, at which point it reverts to the
>>> > prior successive div/mod algorithm.
>>> >
>>> > No change to times for "small" nats, but significant for
>>> > thousands of bits or more:
>>> >
>>> > Before:
>>> > big.BenchmarkStringShort10        100000             26828 ns/op
>>> > big.BenchmarkStringMedium10          500           3246320 ns/op
>>> > big.BenchmarkStringLong10              5         509510600 ns/op
>>> >
>>> > After:
>>> > big.BenchmarkStringShort10        100000             28988 ns/op
>>> > big.BenchmarkStringMedium10         2000           1150566 ns/op
>>> > big.BenchmarkStringLong10             20          89172750 ns/op
>>> >
>>> > Please review this at http://codereview.appspot.com/5413043/
>>> >
>>> > Affected files:
>>> >  M src/pkg/math/big/nat.go
>>> >
>>> >
>>> >
>>
>>
>>
>> --
>> Michael T. Jones | Chief Technology Advocate  | mtj@google.com |  +1
>> 650-335-5765
>>
>

[dga, 2011-11-18 00:29:54]

*** Abandoned ***