Rename grisu to fast_dtoa. Get rid of template.

Rename grisu to fast-dtoa. Get rid of template.

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

[Florian Loitsch, 2010-03-17 17:48:34]

Just learned that filenames should not contain underscores. I will prepare
another patch for the already checked-in files.

[William Hesse, 2010-03-18 10:00:11]

Looking at this, I don't think the flexibility given by an arbitrary alpha and
gamma is used anywhere, and the extra framework added isn't really likely to be
that helpful to an implementer who wants to change them.

http://codereview.chromium.org/1032007/diff/9001/10010
File src/fast-dtoa.cc (right):

http://codereview.chromium.org/1032007/diff/9001/10010#newcode40
src/fast-dtoa.cc:40: // the result of multiplying the input number with the
cached powers-of-ten.
the range (2^32, 2^60)
or 2^32 ... 2^60

multiplying the input by a cached power of ten.

A different range might be chosen on a different platform, to optimize digit
generation, but a smaller range
requires more powers of ten to be cached.

http://codereview.chromium.org/1032007/diff/9001/10010#newcode50
src/fast-dtoa.cc:50: // representation.
Adjusts the last digit of the generated number, and screens out generated
solutions that may be inaccurate.  A solution may be inaccurate if it is outside
the safe interval, or if we cannot prove that it is closer to the input than a
neighboring representable number.

http://codereview.chromium.org/1032007/diff/9001/10010#newcode58
src/fast-dtoa.cc:58: // Output: returns true on success.
returns true if the buffer is guaranteed to contain the closest representable
number to the input.

http://codereview.chromium.org/1032007/diff/9001/10010#newcode74
src/fast-dtoa.cc:74: // ]w-; w+[ (often written as "(w-; w+)")
I would write 
(w-, w+)  (sometimes written "]w-, w+[")
Maybe w_low and w_high would be better names?

http://codereview.chromium.org/1032007/diff/9001/10010#newcode79
src/fast-dtoa.cc:79: // By generating the digits of too_high we got the biggest
last digit.
Could you document this by saying "There are three nested intervals, represented
in our internal floating-point format that is more accurate than 64-bit double
format.

Unsafe interval, between xxxx and xxxx.  A number outside this interval cannot
be the closest representable number to the input.

Safe interval, between xxxxx and xxxxx.  A number inside this interval is
guaranteed to be ?  Do we even use this interval?

Input interval, between w_low=xxxx and w_high=xxxx
The input number is guaranteed to be between these two values.

These intervals are approximately equal to  input +/- 1/2 double ULP and input
+/- internal representation ULP.

http://codereview.chromium.org/1032007/diff/9001/10010#newcode110
src/fast-dtoa.cc:110: //   Since too_low = too_high - unsafe_interval this is
equivalent too
equivalent to

What is the safe interval used for?

http://codereview.chromium.org/1032007/diff/9001/10010#newcode229
src/fast-dtoa.cc:229: // Same comments as for DigitGen (see below) but with
additional precondition:
DigitGen does (approximately) nothing now, and could easily be recreated if
someone wanted a general max_exponent and min_exponent for the range.  I think
DigitGen should just be deleted from the file, and its comments put here.  This
could be renamed DigitGen.

http://codereview.chromium.org/1032007/diff/9001/10010#newcode375
src/fast-dtoa.cc:375: bool DigitGen(DiyFp low,
This function does nothing, and doesn't really help anyone except a hypothetical
library extender, and doesn't even really help them much.

http://codereview.chromium.org/1032007/diff/9001/10010#newcode404
src/fast-dtoa.cc:404: // Returns true if it succeeds, otherwise the result can
not be trusted.
cannot

http://codereview.chromium.org/1032007/diff/9001/10010#newcode409
src/fast-dtoa.cc:409: // 0.099999999999 instead of 0.1.
This is inaccurate - if 0.099999999999 is closer than 0.1, then 0.09999999999 is
returned.  You mean no 0.10000 instead of 0.1.

http://codereview.chromium.org/1032007/diff/9001/10010#newcode415
src/fast-dtoa.cc:415: // boundary_minus and boundary_plus are the boundaries
between v and its
its closest representable neighbors

http://codereview.chromium.org/1032007/diff/9001/10010#newcode417
src/fast-dtoa.cc:417: // will round to v when read as double.
when converted to double?

http://codereview.chromium.org/1032007/diff/9001/10006
File src/grisu3.cc (left):

http://codereview.chromium.org/1032007/diff/9001/10006#oldcode39
src/grisu3.cc:39: template <int alpha = -60, int gamma = -32>
I thought you were getting rid of the template?

http://codereview.chromium.org/1032007/diff/9001/10004
File src/grisu3.h (left):

http://codereview.chromium.org/1032007/diff/9001/10004#oldcode39
src/grisu3.h:39: //   v must satisfy v != 0 and it must not be Infinity or NaN.
v must not be (positive or negative) zero, Infinity, or NaN.

[Florian Loitsch, 2010-03-18 11:56:55]

http://codereview.chromium.org/1032007/diff/9001/10010
File src/fast-dtoa.cc (right):

http://codereview.chromium.org/1032007/diff/9001/10010#newcode40
src/fast-dtoa.cc:40: // the result of multiplying the input number with the
cached powers-of-ten.
On 2010/03/18 10:00:11, William Hesse wrote:
> the range (2^32, 2^60)
> or 2^32 ... 2^60
> 
> multiplying the input by a cached power of ten.
> 
> A different range might be chosen on a different platform, to optimize digit
> generation, but a smaller range
> requires more powers of ten to be cached.

Done.

http://codereview.chromium.org/1032007/diff/9001/10010#newcode50
src/fast-dtoa.cc:50: // representation.
On 2010/03/18 10:00:11, William Hesse wrote:
> Adjusts the last digit of the generated number, and screens out generated
> solutions that may be inaccurate.  A solution may be inaccurate if it is
outside
> the safe interval, or if we cannot prove that it is closer to the input than a
> neighboring representable number.

Done.

http://codereview.chromium.org/1032007/diff/9001/10010#newcode58
src/fast-dtoa.cc:58: // Output: returns true on success.
On 2010/03/18 10:00:11, William Hesse wrote:
> returns true if the buffer is guaranteed to contain the closest representable
> number to the input.

Done.

http://codereview.chromium.org/1032007/diff/9001/10010#newcode74
src/fast-dtoa.cc:74: // ]w-; w+[ (often written as "(w-; w+)")
On 2010/03/18 10:00:11, William Hesse wrote:
> I would write 
> (w-, w+)  (sometimes written "]w-, w+[")
> Maybe w_low and w_high would be better names?
> 

Done.

http://codereview.chromium.org/1032007/diff/9001/10010#newcode79
src/fast-dtoa.cc:79: // By generating the digits of too_high we got the biggest
last digit.
On 2010/03/18 10:00:11, William Hesse wrote:
> Could you document this by saying "There are three nested intervals,
represented
> in our internal floating-point format that is more accurate than 64-bit double
> format.
> 
> Unsafe interval, between xxxx and xxxx.  A number outside this interval cannot
> be the closest representable number to the input.
> 
> Safe interval, between xxxxx and xxxxx.  A number inside this interval is
> guaranteed to be ?  Do we even use this interval?
> 
> Input interval, between w_low=xxxx and w_high=xxxx
> The input number is guaranteed to be between these two values.
> 
> These intervals are approximately equal to  input +/- 1/2 double ULP and input
> +/- internal representation ULP.

Done.

http://codereview.chromium.org/1032007/diff/9001/10010#newcode110
src/fast-dtoa.cc:110: //   Since too_low = too_high - unsafe_interval this is
equivalent too
On 2010/03/18 10:00:11, William Hesse wrote:
> equivalent to
> 
> What is the safe interval used for?

Done.

http://codereview.chromium.org/1032007/diff/9001/10010#newcode229
src/fast-dtoa.cc:229: // Same comments as for DigitGen (see below) but with
additional precondition:
On 2010/03/18 10:00:11, William Hesse wrote:
> DigitGen does (approximately) nothing now, and could easily be recreated if
> someone wanted a general max_exponent and min_exponent for the range.  I think
> DigitGen should just be deleted from the file, and its comments put here. 
This
> could be renamed DigitGen.
> 

Done.

http://codereview.chromium.org/1032007/diff/9001/10010#newcode375
src/fast-dtoa.cc:375: bool DigitGen(DiyFp low,
On 2010/03/18 10:00:11, William Hesse wrote:
> This function does nothing, and doesn't really help anyone except a
hypothetical
> library extender, and doesn't even really help them much.

Done.

http://codereview.chromium.org/1032007/diff/9001/10010#newcode404
src/fast-dtoa.cc:404: // Returns true if it succeeds, otherwise the result can
not be trusted.
On 2010/03/18 10:00:11, William Hesse wrote:
> cannot
> 

Done.

http://codereview.chromium.org/1032007/diff/9001/10010#newcode409
src/fast-dtoa.cc:409: // 0.099999999999 instead of 0.1.
On 2010/03/18 10:00:11, William Hesse wrote:
> This is inaccurate - if 0.099999999999 is closer than 0.1, then 0.09999999999
is
> returned.  You mean no 0.10000 instead of 0.1.
Comment was correct. But I clarified.

http://codereview.chromium.org/1032007/diff/9001/10010#newcode415
src/fast-dtoa.cc:415: // boundary_minus and boundary_plus are the boundaries
between v and its
On 2010/03/18 10:00:11, William Hesse wrote:
> its closest representable neighbors
its closest floating-point neighbors.

http://codereview.chromium.org/1032007/diff/9001/10010#newcode417
src/fast-dtoa.cc:417: // will round to v when read as double.
On 2010/03/18 10:00:11, William Hesse wrote:
> when converted to double?

Done.

http://codereview.chromium.org/1032007/diff/9001/10006
File src/grisu3.cc (left):

http://codereview.chromium.org/1032007/diff/9001/10006#oldcode39
src/grisu3.cc:39: template <int alpha = -60, int gamma = -32>
On 2010/03/18 10:00:11, William Hesse wrote:
> I thought you were getting rid of the template?

inside deleted file.

http://codereview.chromium.org/1032007/diff/9001/10004
File src/grisu3.h (left):

http://codereview.chromium.org/1032007/diff/9001/10004#oldcode39
src/grisu3.h:39: //   v must satisfy v != 0 and it must not be Infinity or NaN.
On 2010/03/18 10:00:11, William Hesse wrote:
> v must not be (positive or negative) zero, Infinity, or NaN.

Done.

[William Hesse, 2010-03-18 12:36:44]

LGTM, with comments.

http://codereview.chromium.org/1032007/diff/21001/22010
File src/fast-dtoa.cc (right):

http://codereview.chromium.org/1032007/diff/21001/22010#newcode43
src/fast-dtoa.cc:43: // The bigger the range, the fewer cached numbers we need.
Goodbye line.

http://codereview.chromium.org/1032007/diff/21001/22010#newcode111
src/fast-dtoa.cc:111: // Note that buffer could lie anywhere inside the range
too_low to too_high.
the value of buffer

http://codereview.chromium.org/1032007/diff/21001/22010#newcode127
src/fast-dtoa.cc:127: // that the chosen one is closer to any number within the
range w_low to
is closer to both w_low and w_high, since v can be anywhere between them.

http://codereview.chromium.org/1032007/diff/21001/22010#newcode130
src/fast-dtoa.cc:130: // By generating the digits of too_high we got the biggest
last digit.
we got the largest buffer that might round to v.

http://codereview.chromium.org/1032007/diff/21001/22010#newcode145
src/fast-dtoa.cc:145: small_distance - rest >= rest + ten_kappa -
small_distance)) {
Aren't tests 1 and 3 redundant:
small_distance - rest > 0

(small_distance - rest > ten_kappa ||
small_distance - rest >= ten_kappa/2)

http://codereview.chromium.org/1032007/diff/21001/22010#newcode177
src/fast-dtoa.cc:177: // Returns the biggest power of ten that is less or equal
than the given
less than or equal to

http://codereview.chromium.org/1032007/diff/21001/22010#newcode179
src/fast-dtoa.cc:179: // If number_bits == 0 then 0^-1 is returned
Precondition: (1 << (number_bits + 1)) > number >= (1 << number_bits)

[Florian Loitsch, 2010-03-18 13:16:11]

http://codereview.chromium.org/1032007/diff/21001/22010
File src/fast-dtoa.cc (right):

http://codereview.chromium.org/1032007/diff/21001/22010#newcode43
src/fast-dtoa.cc:43: // The bigger the range, the fewer cached numbers we need.
On 2010/03/18 12:36:45, William Hesse wrote:
> Goodbye line.

Done.

http://codereview.chromium.org/1032007/diff/21001/22010#newcode111
src/fast-dtoa.cc:111: // Note that buffer could lie anywhere inside the range
too_low to too_high.
On 2010/03/18 12:36:45, William Hesse wrote:
> the value of buffer

Done.

http://codereview.chromium.org/1032007/diff/21001/22010#newcode127
src/fast-dtoa.cc:127: // that the chosen one is closer to any number within the
range w_low to
On 2010/03/18 12:36:45, William Hesse wrote:
> is closer to both w_low and w_high, since v can be anywhere between them.

Done.

http://codereview.chromium.org/1032007/diff/21001/22010#newcode130
src/fast-dtoa.cc:130: // By generating the digits of too_high we got the biggest
last digit.
On 2010/03/18 12:36:45, William Hesse wrote:
> we got the largest buffer that might round to v.

Done.

http://codereview.chromium.org/1032007/diff/21001/22010#newcode145
src/fast-dtoa.cc:145: small_distance - rest >= rest + ten_kappa -
small_distance)) {
On 2010/03/18 12:36:45, William Hesse wrote:
> Aren't tests 1 and 3 redundant:
> small_distance - rest > 0
> 
> (small_distance - rest > ten_kappa ||
> small_distance - rest >= ten_kappa/2)
> 
> 
> 
They are redundant, but only if we don't take into account overflows.
If rest > small_distance, then small_distance - rest underflows which would make
the third test fail. Maybe there are other ways to get around this, but a simple
test in the beginning seems to be the easiest solution.

http://codereview.chromium.org/1032007/diff/21001/22010#newcode177
src/fast-dtoa.cc:177: // Returns the biggest power of ten that is less or equal
than the given
On 2010/03/18 12:36:45, William Hesse wrote:
> less than or equal to

Done.

http://codereview.chromium.org/1032007/diff/21001/22010#newcode179
src/fast-dtoa.cc:179: // If number_bits == 0 then 0^-1 is returned
On 2010/03/18 12:36:45, William Hesse wrote:
> Precondition: (1 << (number_bits + 1)) > number >= (1 << number_bits)

Done.