Bignum implementation of Strtod.

Bignum implementation of Strtod.

This removes the dependency on Gay's strtod.

Committed: http://code.google.com/p/v8/source/detail?r=5778

[William Hesse, 2010-11-04 14:20:46]

Reviewed all but strtod.cc and the three test files.  Their reviews will follow.

http://codereview.chromium.org/4060001/diff/17001/18002
File src/bignum.cc (right):

http://codereview.chromium.org/4060001/diff/17001/18002#newcode164
src/bignum.cc:164: void Bignum::AddUInt16(uint16_t operand) {
Will you optimize this, either by making a special implementation, or by making
"Zero()" zero all values only on debug, and only zero the least significant
chunk otherwise?

http://codereview.chromium.org/4060001/diff/17001/18002#newcode191
src/bignum.cc:191: int offset = other.exponent_ - exponent_;
ASSERT(offset >= 0); ?
OK, I see that Align(other) does that.  Comment on this.
ASSERT(bigit_pos + other.used_digits < kBigitLength?  < used_digits?

http://codereview.chromium.org/4060001/diff/17001/18002#newcode224
src/bignum.cc:224: Chunk difference = bigits_[i + offset] - other.bigits_[i] -
borrow;
Note that borrow will always be 0 or 1, since 
difference >> (kChunkSize -1) is the high bit (sign bit) of an unsigned number,
logical right shifted to the LSB.
Otherwise, this seems wrong.  If you used a signed difference, couldn't you make
it parallel to AddBignum?

http://codereview.chromium.org/4060001/diff/17001/18002#newcode280
src/bignum.cc:280: uint64_t tmp = (carry & kBigitMask) + product;
Use product again instead of tmp, as in MultiplyUInt16.  If you make a temp
factor64 here, then why not do the same in MultiplyUInt16?  Or else just cast
factor here as well.

http://codereview.chromium.org/4060001/diff/17001/18002#newcode412
src/bignum.cc:412: while (bigit_index2 < used_digits_) {
Loop runs 0 times on last iteration, emptying accumulator.

http://codereview.chromium.org/4060001/diff/17001/18002#newcode419
src/bignum.cc:419: bigits_[i] = static_cast<Chunk>(accumulator) & kBigitMask;
Comment: The overwritten bigits_[i] will never be read in further loop
iterations, because bigit_index1 and bigit_index2 are always greater than i -
used_digits_.

http://codereview.chromium.org/4060001/diff/17001/18002#newcode524
src/bignum.cc:524: while (BigitLength() > other.BigitLength()) {
It seems to me this loop could run about 30,000 times.
this = 2, 0, 0, 0 
other = 0, 2^17 + 1, 0, 0

Instead, take other[used_digits_] and other[used_digits_ -1] and form a
DoubleChunk with them?

http://codereview.chromium.org/4060001/diff/17001/18002#newcode548
src/bignum.cc:548: int division_estimate = this_bigit / (other_bigit + 1);
If other_bigit = 1, then we may have a terrible division_estimate, and only
reduce this by about 1/2 each iteration.  Again, use a doublechunk, perhaps. 
You need a minimum # of digits of accuracy in your divisor estimate.

http://codereview.chromium.org/4060001/diff/17001/18002#newcode553
src/bignum.cc:553: // No need to even try to subtract. Even if other's remaining
digits were 0
I think you can leave this to the next iteration if you do double division each
time.

http://codereview.chromium.org/4060001/diff/17001/18002#newcode568
src/bignum.cc:568: int result = 0;
This will be an infinite loop with a signed type, and a negative number. 
Comment?
ASSERT( number >>4  < number) ?

http://codereview.chromium.org/4060001/diff/17001/18002#newcode674
src/bignum.cc:674: return +1;
How about:
else {
borrow = chunk_c + borrow - sum;
if borrow > 1 return -1
borrow <<= kBigitSize;
}

http://codereview.chromium.org/4060001/diff/17001/18002#newcode765
src/bignum.cc:765: DoubleChunk remove = borrow + product;
A single DoubleChunk variable can be used for both borrow and remove - their
livetimes are disjoint.

http://codereview.chromium.org/4060001/diff/17001/18003
File src/bignum.h (right):

http://codereview.chromium.org/4060001/diff/17001/18003#newcode61
src/bignum.h:61: void MultiplyUInt64(uint64_t value);
Why not "factor"?  Should the names say "MultiplyBy"?

http://codereview.chromium.org/4060001/diff/17001/18003#newcode69
src/bignum.h:69: bool HexString(char* buffer, int buffer_size) const;
Is this ToHexString?  Or AssignHexString?

http://codereview.chromium.org/4060001/diff/17001/18003#newcode122
src/bignum.h:122: int BigitLength() const { return used_digits_ + exponent_; }
Having a variable BigitLength() and a constant kBigitLength seems confusing. 
Should it be kMaxBigitLength instead?

http://codereview.chromium.org/4060001/diff/17001/18003#newcode127
src/bignum.h:127: Vector<Chunk> bigits_;
Add comment "A length-kBigitSize vector backed by bigits_buffer_."

http://codereview.chromium.org/4060001/diff/17001/18003#newcode129
src/bignum.h:129: int exponent_;  // Encodes "hidden" Bigits.
What does this really mean.  Why not just say BigNum represents value(bigits_) *
2^exponent_.

http://codereview.chromium.org/4060001/diff/17001/18009
File tools/gyp/v8.gyp (right):

http://codereview.chromium.org/4060001/diff/17001/18009#newcode284
tools/gyp/v8.gyp:284: '../../src/bignum.h',
Could you change the Visual Studio project files as well?
Are the Mac Xcode files automatically fixed?

[Florian Loitsch, 2010-11-06 00:07:47]

Adressed comments.
Please have another look.
I haven't yet looked at the xcode-files (will ask on monday if they are
auto-generated or not).

http://codereview.chromium.org/4060001/diff/17001/18002
File src/bignum.cc (right):

http://codereview.chromium.org/4060001/diff/17001/18002#newcode164
src/bignum.cc:164: void Bignum::AddUInt16(uint16_t operand) {
On 2010/11/04 14:20:46, William Hesse wrote:
> Will you optimize this, either by making a special implementation, or by
making
> "Zero()" zero all values only on debug, and only zero the least significant
> chunk otherwise?
AddUInt16 was unused (after changes to the AssignDecimalString function).
Removed.

We could optimize AddUInt64, but that's true for many of the classes' functions.

http://codereview.chromium.org/4060001/diff/17001/18002#newcode191
src/bignum.cc:191: int offset = other.exponent_ - exponent_;
On 2010/11/04 14:20:46, William Hesse wrote:
> ASSERT(offset >= 0); ?
> OK, I see that Align(other) does that.  Comment on this.
> ASSERT(bigit_pos + other.used_digits < kBigitLength?  < used_digits?

Changed comments. (There was also an EnsureCapacity missing.)

http://codereview.chromium.org/4060001/diff/17001/18002#newcode224
src/bignum.cc:224: Chunk difference = bigits_[i + offset] - other.bigits_[i] -
borrow;
On 2010/11/04 14:20:46, William Hesse wrote:
> Note that borrow will always be 0 or 1, since 
> difference >> (kChunkSize -1) is the high bit (sign bit) of an unsigned
number,
> logical right shifted to the LSB.
> Otherwise, this seems wrong.  If you used a signed difference, couldn't you
make
> it parallel to AddBignum?

Added ASSERT(borrow == 0 || borrow == 1).
I could make it more similar to the AddBignum. Not sure it's worth it though.

http://codereview.chromium.org/4060001/diff/17001/18002#newcode280
src/bignum.cc:280: uint64_t tmp = (carry & kBigitMask) + product;
On 2010/11/04 14:20:46, William Hesse wrote:
> Use product again instead of tmp, as in MultiplyUInt16.  If you make a temp
> factor64 here, then why not do the same in MultiplyUInt16?  Or else just cast
> factor here as well.
> 
> 
Merged MultiplyUint16 and Uint32.

http://codereview.chromium.org/4060001/diff/17001/18002#newcode412
src/bignum.cc:412: while (bigit_index2 < used_digits_) {
On 2010/11/04 14:20:46, William Hesse wrote:
> Loop runs 0 times on last iteration, emptying accumulator.

Added as comment.

http://codereview.chromium.org/4060001/diff/17001/18002#newcode419
src/bignum.cc:419: bigits_[i] = static_cast<Chunk>(accumulator) & kBigitMask;
On 2010/11/04 14:20:46, William Hesse wrote:
> Comment: The overwritten bigits_[i] will never be read in further loop
> iterations, because bigit_index1 and bigit_index2 are always greater than i -
> used_digits_.
> 

Done.

http://codereview.chromium.org/4060001/diff/17001/18002#newcode524
src/bignum.cc:524: while (BigitLength() > other.BigitLength()) {
On 2010/11/04 14:20:46, William Hesse wrote:
> It seems to me this loop could run about 30,000 times.
> this = 2, 0, 0, 0 
> other = 0, 2^17 + 1, 0, 0
> 
> Instead, take other[used_digits_] and other[used_digits_ -1] and form a
> DoubleChunk with them?

This function is only used in dtoa where the result should be less than 10. If
have added comments and added an assert that fails if the function is used with
values that would lead to bad behavior.

http://codereview.chromium.org/4060001/diff/17001/18002#newcode548
src/bignum.cc:548: int division_estimate = this_bigit / (other_bigit + 1);
On 2010/11/04 14:20:46, William Hesse wrote:
> If other_bigit = 1, then we may have a terrible division_estimate, and only
> reduce this by about 1/2 each iteration.  Again, use a doublechunk, perhaps. 
> You need a minimum # of digits of accuracy in your divisor estimate.

See above.

http://codereview.chromium.org/4060001/diff/17001/18002#newcode553
src/bignum.cc:553: // No need to even try to subtract. Even if other's remaining
digits were 0
On 2010/11/04 14:20:46, William Hesse wrote:
> I think you can leave this to the next iteration if you do double division
each
> time.

see above.

http://codereview.chromium.org/4060001/diff/17001/18002#newcode568
src/bignum.cc:568: int result = 0;
On 2010/11/04 14:20:46, William Hesse wrote:
> This will be an infinite loop with a signed type, and a negative number. 
> Comment?
> ASSERT( number >>4  < number) ?
> 
Added assert to verify that number is positive.

http://codereview.chromium.org/4060001/diff/17001/18002#newcode674
src/bignum.cc:674: return +1;
On 2010/11/04 14:20:46, William Hesse wrote:
> How about:
> else {
> borrow = chunk_c + borrow - sum;
> if borrow > 1 return -1
> borrow <<= kBigitSize;
> }

Done.

http://codereview.chromium.org/4060001/diff/17001/18002#newcode765
src/bignum.cc:765: DoubleChunk remove = borrow + product;
On 2010/11/04 14:20:46, William Hesse wrote:
> A single DoubleChunk variable can be used for both borrow and remove - their
> livetimes are disjoint.

I agree, but since I have to use two lines anyways (not enough space)...  The
compiler should figure that out by its own.

http://codereview.chromium.org/4060001/diff/17001/18003
File src/bignum.h (right):

http://codereview.chromium.org/4060001/diff/17001/18003#newcode61
src/bignum.h:61: void MultiplyUInt64(uint64_t value);
On 2010/11/04 14:20:46, William Hesse wrote:
> Why not "factor"?  Should the names say "MultiplyBy"?
renamed to 'factor'.
Renamed to MultiplyByUInt32/Uint64/PowerOfTen.

http://codereview.chromium.org/4060001/diff/17001/18003#newcode69
src/bignum.h:69: bool HexString(char* buffer, int buffer_size) const;
On 2010/11/04 14:20:46, William Hesse wrote:
> Is this ToHexString?  Or AssignHexString?

renamed to "toHexString".

http://codereview.chromium.org/4060001/diff/17001/18003#newcode122
src/bignum.h:122: int BigitLength() const { return used_digits_ + exponent_; }
On 2010/11/04 14:20:46, William Hesse wrote:
> Having a variable BigitLength() and a constant kBigitLength seems confusing. 
> Should it be kMaxBigitLength instead?
renamed kBigitLength to kBigitCapacity.

http://codereview.chromium.org/4060001/diff/17001/18003#newcode127
src/bignum.h:127: Vector<Chunk> bigits_;
On 2010/11/04 14:20:46, William Hesse wrote:
> Add comment "A length-kBigitSize vector backed by bigits_buffer_."

Done.

http://codereview.chromium.org/4060001/diff/17001/18003#newcode129
src/bignum.h:129: int exponent_;  // Encodes "hidden" Bigits.
On 2010/11/04 14:20:46, William Hesse wrote:
> What does this really mean.  Why not just say BigNum represents value(bigits_)
*
> 2^exponent_.
> 

Done.

[William Hesse, 2010-11-08 09:46:33]

LGTM, with comments.

http://codereview.chromium.org/4060001/diff/17001/18005
File src/strtod.cc (right):

http://codereview.chromium.org/4060001/diff/17001/18005#newcode365
src/strtod.cc:365: // or where the next double (i.e. the next closest double) is
the correct
either the correct double or its lower neighbor (the nearest double less than
the correct one).

http://codereview.chromium.org/4060001/diff/17001/18005#newcode402
src/strtod.cc:402: int comparison = Bignum::Compare(input, boundary);
Beautifully simple code.

http://codereview.chromium.org/4060001/diff/17001/18005#newcode426
src/strtod.cc:426: return Strtod(Vector<const char>(significant_buffer,
Instead of return Strtod(...) why not
trimmed = Vector<const char>(significant_buffer,kMaxSignificantDecimalDigits);
exponent = significant_exponent;

The recursion is merely a tail call to the rest of the function body, since the
previous stuff will have no impact.

http://codereview.chromium.org/4060001/diff/17001/18007
File test/cctest/test-bignum.cc (right):

http://codereview.chromium.org/4060001/diff/17001/18007#newcode1590
test/cctest/test-bignum.cc:1590: bignum.AssignPowerUInt16(10, 30);
Couldn't you try a different base, like 17, once?

http://codereview.chromium.org/4060001/diff/28001/29008
File test/cctest/test-strtod.cc (right):

http://codereview.chromium.org/4060001/diff/28001/29008#newcode368
test/cctest/test-strtod.cc:368: 
Is this test reproducible?  Is there an option to make random() use the same
seed?  What is random() - is it libc or one of our own functions?

[Florian Loitsch, 2010-11-08 10:20:04]

http://codereview.chromium.org/4060001/diff/17001/18005
File src/strtod.cc (right):

http://codereview.chromium.org/4060001/diff/17001/18005#newcode365
src/strtod.cc:365: // or where the next double (i.e. the next closest double) is
the correct
On 2010/11/08 09:46:34, William Hesse wrote:
> either the correct double or its lower neighbor (the nearest double less than
> the correct one).

Done.

http://codereview.chromium.org/4060001/diff/17001/18005#newcode402
src/strtod.cc:402: int comparison = Bignum::Compare(input, boundary);
On 2010/11/08 09:46:34, William Hesse wrote:
> Beautifully simple code.

thanks :)

http://codereview.chromium.org/4060001/diff/17001/18005#newcode426
src/strtod.cc:426: return Strtod(Vector<const char>(significant_buffer,
On 2010/11/08 09:46:34, William Hesse wrote:
> Instead of return Strtod(...) why not
> trimmed = Vector<const char>(significant_buffer,kMaxSignificantDecimalDigits);
> exponent = significant_exponent;
> 
> The recursion is merely a tail call to the rest of the function body, since
the
> previous stuff will have no impact.

Done.

http://codereview.chromium.org/4060001/diff/17001/18007
File test/cctest/test-bignum.cc (right):

http://codereview.chromium.org/4060001/diff/17001/18007#newcode1590
test/cctest/test-bignum.cc:1590: bignum.AssignPowerUInt16(10, 30);
On 2010/11/08 09:46:34, William Hesse wrote:
> Couldn't you try a different base, like 17, once?

Done.

http://codereview.chromium.org/4060001/diff/28001/29008
File test/cctest/test-strtod.cc (right):

http://codereview.chromium.org/4060001/diff/28001/29008#newcode368
test/cctest/test-strtod.cc:368: 
On 2010/11/08 09:46:34, William Hesse wrote:
> Is this test reproducible?  Is there an option to make random() use the same
> seed?  What is random() - is it libc or one of our own functions?

It was a libc function. I have copied v8's Random function and adapted it so it
is deterministic.