Fast algorithm for double->string conversion.

Fast algorithm for double->string conversion.

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

[Florian Loitsch, 2010-02-17 12:05:57]

This is not the final version of the patch. In particular powers_ten.h and
cached_powers.h are not yet cleaned.
The other files are already mostly cleaned.
There are still things to do, but if you have the time I would appreciate some
comments.

[William Hesse, 2010-02-18 10:21:12]

Here are some comments.

http://codereview.chromium.org/619005/diff/1/3
File src/conversions.cc (left):

http://codereview.chromium.org/619005/diff/1/3#oldcode684
src/conversions.cc:684: // efficiently, we probably have to modify dtoa.
Could you quickly do a check if you are generating 3 0s or 3 9s in a row, and
only then check to see if you should truncate them?

http://codereview.chromium.org/619005/diff/1/7
File src/diy_fp.h (right):

http://codereview.chromium.org/619005/diff/1/7#newcode63
src/diy_fp.h:63: }
How about a private constructor DiyFp(a, b) f_(a.f - b.f), e_(a.e_) { ASSERT ...
  }
Could this be more efficient?  Then Minus(a, b) { return DiyFp(a,b); }

http://codereview.chromium.org/619005/diff/1/7#newcode85
src/diy_fp.h:85: }
Can we do an assembly language version for ia32, and keep the portable version
for all other platforms?  Then we have 80-bit FP in hardware.

http://codereview.chromium.org/619005/diff/1/7#newcode97
src/diy_fp.h:97: 
Could you add a 
while (!(f & top12bits)) {
f <<= 12;
e -= 12;
}, for example, to speed up the loop?

http://codereview.chromium.org/619005/diff/1/8
File src/double.h (right):

http://codereview.chromium.org/619005/diff/1/8#newcode46
src/double.h:46: converter_t tmp; tmp.d = d; return tmp.n;
If this was done with a reference, or a macro, could it be done in-place (ie   
#define DOUBLE_TO_UINT64(d)  \
          reinterpret_cast<converter_t *>(& (d))->n

or inline uint_64t& double_to_uint(double &d){
return reinterpret_cast<converter_t *>(& (d))->n;
}

Or is this unsave due to the spec and pointer aliasing optimizations?

http://codereview.chromium.org/619005/diff/1/8#newcode58
src/double.h:58: Double() : d_(0.0) {}
Would all the methods work faster if d64_ was a uint64_t, and the constructor
was Double(double d) : d64_(double_to_uint64(d)) {}?

http://codereview.chromium.org/619005/diff/1/4
File src/grisu3.cc (right):

http://codereview.chromium.org/619005/diff/1/4#newcode322
src/grisu3.cc:322: //      fractionals.f >>= 1; fractionals.e++; // idempotent
idempotent means if you do something more than once, the result is the same as
if you do it only once.  I think you mean "leaves value unchanged".

http://codereview.chromium.org/619005/diff/1/9
File src/powers_ten.h (right):

http://codereview.chromium.org/619005/diff/1/9#newcode41
src/powers_ten.h:41: GRISU_UINT64_C(0xbf29dcab,a82fdeae) ,
GRISU_UINT64_C(0xeef453d6,923bd65a) , GRISU_UINT64_C(0x9558b466,1b6565f8) ,
GRISU_UINT64_C(0xbaaee17f,a23ebf76) , GRISU_UINT64_C(0xe95a99df,8ace6f54) ,
GRISU_UINT64_C(0x91d8a02b,b6c10594) , GRISU_UINT64_C(0xb64ec836,a47146fa) ,
GRISU_UINT64_C(0xe3e27a44,4d8d98b8) , GRISU_UINT64_C(0x8e6d8c6a,b0787f73) ,
GRISU_UINT64_C(0xb208ef85,5c969f50) , GRISU_UINT64_C(0xde8b2b66,b3bc4724) ,
GRISU_UINT64_C(0x8b16fb20,3055ac76) , GRISU_UINT64_C(0xaddcb9e8,3c6b1794) ,
GRISU_UINT64_C(0xd953e862,4b85dd79) , GRISU_UINT64_C(0x87d4713d,6f33aa6c) ,
GRISU_UINT64_C(0xa9c98d8c,cb009506) , GRISU_UINT64_C(0xd43bf0ef,fdc0ba48) ,
GRISU_UINT64_C(0x84a57695,fe98746d) , GRISU_UINT64_C(0xa5ced43b,7e3e9188) ,
GRISU_UINT64_C(0xcf42894a,5dce35ea) , GRISU_UINT64_C(0x818995ce,7aa0e1b2) ,
GRISU_UINT64_C(0xa1ebfb42,19491a1f) , GRISU_UINT64_C(0xca66fa12,9f9b60a7) ,
GRISU_UINT64_C(0xfd00b897,478238d1) , GRISU_UINT64_C(0x9e20735e,8cb16382) ,
GRISU_UINT64_C(0xc5a89036,2fddbc63) , GRISU_UINT64_C(0xf712b443,bbd52b7c) ,
GRISU_UINT64_C(0x9a6bb0aa,55653b2d) , GRISU_UINT64_C(0xc1069cd4,eabe89f9) ,
GRISU_UINT64_C(0xf148440a,256e2c77) , GRISU_UINT64_C(0x96cd2a86,5764dbca) ,
GRISU_UINT64_C(0xbc807527,ed3e12bd) , GRISU_UINT64_C(0xeba09271,e88d976c) ,
GRISU_UINT64_C(0x93445b87,31587ea3) , GRISU_UINT64_C(0xb8157268,fdae9e4c) ,
GRISU_UINT64_C(0xe61acf03,3d1a45df) , GRISU_UINT64_C(0x8fd0c162,06306bac) ,
GRISU_UINT64_C(0xb3c4f1ba,87bc8697) , GRISU_UINT64_C(0xe0b62e29,29aba83c) ,
GRISU_UINT64_C(0x8c71dcd9,ba0b4926) , GRISU_UINT64_C(0xaf8e5410,288e1b6f) ,
GRISU_UINT64_C(0xdb71e914,32b1a24b) , GRISU_UINT64_C(0x892731ac,9faf056f) ,
GRISU_UINT64_C(0xab70fe17,c79ac6ca) , GRISU_UINT64_C(0xd64d3d9d,b981787d) ,
GRISU_UINT64_C(0x85f04682,93f0eb4e) , GRISU_UINT64_C(0xa76c5823,38ed2622) ,
GRISU_UINT64_C(0xd1476e2c,07286faa) , GRISU_UINT64_C(0x82cca4db,847945ca) ,
GRISU_UINT64_C(0xa37fce12,6597973d) , GRISU_UINT64_C(0xcc5fc196,fefd7d0c) ,
GRISU_UINT64_C(0xff77b1fc,bebcdc4f) , GRISU_UINT64_C(0x9faacf3d,f73609b1) ,
GRISU_UINT64_C(0xc795830d,75038c1e) , GRISU_UINT64_C(0xf97ae3d0,d2446f25) ,
GRISU_UINT64_C(0x9becce62,836ac577) , GRISU_UINT64_C(0xc2e801fb,244576d5) ,
GRISU_UINT64_C(0xf3a20279,ed56d48a) , GRISU_UINT64_C(0x9845418c,345644d7) ,
GRISU_UINT64_C(0xbe5691ef,416bd60c) , GRISU_UINT64_C(0xedec366b,11c6cb8f) ,
GRISU_UINT64_C(0x94b3a202,eb1c3f39) , GRISU_UINT64_C(0xb9e08a83,a5e34f08) ,
GRISU_UINT64_C(0xe858ad24,8f5c22ca) , GRISU_UINT64_C(0x91376c36,d99995be) ,
GRISU_UINT64_C(0xb5854744,8ffffb2e) ,
Could this be formatted into 80-character lines?

[Søren Thygesen Gjesse, 2010-02-18 10:29:38]

http://codereview.chromium.org/619005/diff/1/5
File src/SConscript (right):

http://codereview.chromium.org/619005/diff/1/5#newcode67
src/SConscript:67: grisu3.cc
When adding new files please update the other build systems as well. Updating
tools/gyp/v8.gyp is required for Chromium build. And if possibly also update
relevant files in tools/v8.xcodeproj and tools/visual_studio.

[floitsch, 2010-02-19 14:50:05]

Cleaner version of patch.
I still would like to add a little bit of functionality, but otherwise I would
consider committing the code.

http://codereview.chromium.org/619005/diff/1/5
File src/SConscript (right):

http://codereview.chromium.org/619005/diff/1/5#newcode67
src/SConscript:67: grisu3.cc
On 2010/02/18 10:29:38, Søren Gjesse wrote:
> When adding new files please update the other build systems as well. Updating
> tools/gyp/v8.gyp is required for Chromium build. And if possibly also update
> relevant files in tools/v8.xcodeproj and tools/visual_studio.

I have modified the gyp-file. I hope it's correct.

http://codereview.chromium.org/619005/diff/1/3
File src/conversions.cc (left):

http://codereview.chromium.org/619005/diff/1/3#oldcode684
src/conversions.cc:684: // efficiently, we probably have to modify dtoa.
On 2010/02/18 10:21:12, William Hesse wrote:
> Could you quickly do a check if you are generating 3 0s or 3 9s in a row, and
> only then check to see if you should truncate them?
> 
Not that easy. For one '9's are not the issue since we are talking about a
radix!=10 here.
I agree: the best would be to update/replace dtoa.

http://codereview.chromium.org/619005/diff/1/7
File src/diy_fp.h (right):

http://codereview.chromium.org/619005/diff/1/7#newcode63
src/diy_fp.h:63: }
On 2010/02/18 10:21:12, William Hesse wrote:
> How about a private constructor DiyFp(a, b) f_(a.f - b.f), e_(a.e_) { ASSERT
...
>   }
> Could this be more efficient?  Then Minus(a, b) { return DiyFp(a,b); }
Just tested it:
===
int diffGrisu3TMP(int a, int b) {
  DiyFp diy_a = DiyFp(a, 0);
  DiyFp diy_b = DiyFp(b, 0);
  DiyFp diff = DiyFp::Minus(diy_a, diy_b);
  return static_cast<int>(diff.f());
}
===
is compiled to:
===
00000000 <_ZN2v88internal13diffGrisu3TMPEii>:
   0:   53                      push   %ebx
   1:   8b 44 24 0c             mov    0xc(%esp),%eax
   5:   8b 4c 24 08             mov    0x8(%esp),%ecx
   9:   5b                      pop    %ebx
   a:   29 c1                   sub    %eax,%ecx
   c:   89 c8                   mov    %ecx,%eax
   e:   c3                      ret
===
So no need to optimize this.

http://codereview.chromium.org/619005/diff/1/7#newcode85
src/diy_fp.h:85: }
On 2010/02/18 10:21:12, William Hesse wrote:
> Can we do an assembly language version for ia32, and keep the portable version
> for all other platforms?  Then we have 80-bit FP in hardware.

This should be optimized for all platforms. Yes. For now it's fast enough,
though.

http://codereview.chromium.org/619005/diff/1/7#newcode97
src/diy_fp.h:97: 
On 2010/02/18 10:21:12, William Hesse wrote:
> Could you add a 
> while (!(f & top12bits)) {
> f <<= 12;
> e -= 12;
> }, for example, to speed up the loop?

The most common case 10 bits. So I will optimize for that.

http://codereview.chromium.org/619005/diff/1/8
File src/double.h (right):

http://codereview.chromium.org/619005/diff/1/8#newcode46
src/double.h:46: converter_t tmp; tmp.d = d; return tmp.n;
On 2010/02/18 10:21:12, William Hesse wrote:
> If this was done with a reference, or a macro, could it be done in-place (ie  

> #define DOUBLE_TO_UINT64(d)  \
>           reinterpret_cast<converter_t *>(& (d))->n
> 
> or inline uint_64t& double_to_uint(double &d){
> return reinterpret_cast<converter_t *>(& (d))->n;
> }
> 
> Or is this unsave due to the spec and pointer aliasing optimizations?
I haven't found any more efficient ways. Just reinterpret_casting is illegal
(breaks strict-aliasing rules). I agree this is slow, but let's just hope future
compilers optimize this away. gcc 4.2 is too dumb for it.

http://codereview.chromium.org/619005/diff/1/8#newcode58
src/double.h:58: Double() : d_(0.0) {}
On 2010/02/18 10:21:12, William Hesse wrote:
> Would all the methods work faster if d64_ was a uint64_t, and the constructor
> was Double(double d) : d64_(double_to_uint64(d)) {}?

I had hoped compilers were sufficiently smart to avoid the recomputations.
Apparently they aren't.
Done.

http://codereview.chromium.org/619005/diff/1/4
File src/grisu3.cc (right):

http://codereview.chromium.org/619005/diff/1/4#newcode322
src/grisu3.cc:322: //      fractionals.f >>= 1; fractionals.e++; // idempotent
On 2010/02/18 10:21:12, William Hesse wrote:
> idempotent means if you do something more than once, the result is the same as
> if you do it only once.  I think you mean "leaves value unchanged".

Done.

http://codereview.chromium.org/619005/diff/1/9
File src/powers_ten.h (right):

http://codereview.chromium.org/619005/diff/1/9#newcode41
src/powers_ten.h:41: GRISU_UINT64_C(0xbf29dcab,a82fdeae) ,
GRISU_UINT64_C(0xeef453d6,923bd65a) , GRISU_UINT64_C(0x9558b466,1b6565f8) ,
GRISU_UINT64_C(0xbaaee17f,a23ebf76) , GRISU_UINT64_C(0xe95a99df,8ace6f54) ,
GRISU_UINT64_C(0x91d8a02b,b6c10594) , GRISU_UINT64_C(0xb64ec836,a47146fa) ,
GRISU_UINT64_C(0xe3e27a44,4d8d98b8) , GRISU_UINT64_C(0x8e6d8c6a,b0787f73) ,
GRISU_UINT64_C(0xb208ef85,5c969f50) , GRISU_UINT64_C(0xde8b2b66,b3bc4724) ,
GRISU_UINT64_C(0x8b16fb20,3055ac76) , GRISU_UINT64_C(0xaddcb9e8,3c6b1794) ,
GRISU_UINT64_C(0xd953e862,4b85dd79) , GRISU_UINT64_C(0x87d4713d,6f33aa6c) ,
GRISU_UINT64_C(0xa9c98d8c,cb009506) , GRISU_UINT64_C(0xd43bf0ef,fdc0ba48) ,
GRISU_UINT64_C(0x84a57695,fe98746d) , GRISU_UINT64_C(0xa5ced43b,7e3e9188) ,
GRISU_UINT64_C(0xcf42894a,5dce35ea) , GRISU_UINT64_C(0x818995ce,7aa0e1b2) ,
GRISU_UINT64_C(0xa1ebfb42,19491a1f) , GRISU_UINT64_C(0xca66fa12,9f9b60a7) ,
GRISU_UINT64_C(0xfd00b897,478238d1) , GRISU_UINT64_C(0x9e20735e,8cb16382) ,
GRISU_UINT64_C(0xc5a89036,2fddbc63) , GRISU_UINT64_C(0xf712b443,bbd52b7c) ,
GRISU_UINT64_C(0x9a6bb0aa,55653b2d) , GRISU_UINT64_C(0xc1069cd4,eabe89f9) ,
GRISU_UINT64_C(0xf148440a,256e2c77) , GRISU_UINT64_C(0x96cd2a86,5764dbca) ,
GRISU_UINT64_C(0xbc807527,ed3e12bd) , GRISU_UINT64_C(0xeba09271,e88d976c) ,
GRISU_UINT64_C(0x93445b87,31587ea3) , GRISU_UINT64_C(0xb8157268,fdae9e4c) ,
GRISU_UINT64_C(0xe61acf03,3d1a45df) , GRISU_UINT64_C(0x8fd0c162,06306bac) ,
GRISU_UINT64_C(0xb3c4f1ba,87bc8697) , GRISU_UINT64_C(0xe0b62e29,29aba83c) ,
GRISU_UINT64_C(0x8c71dcd9,ba0b4926) , GRISU_UINT64_C(0xaf8e5410,288e1b6f) ,
GRISU_UINT64_C(0xdb71e914,32b1a24b) , GRISU_UINT64_C(0x892731ac,9faf056f) ,
GRISU_UINT64_C(0xab70fe17,c79ac6ca) , GRISU_UINT64_C(0xd64d3d9d,b981787d) ,
GRISU_UINT64_C(0x85f04682,93f0eb4e) , GRISU_UINT64_C(0xa76c5823,38ed2622) ,
GRISU_UINT64_C(0xd1476e2c,07286faa) , GRISU_UINT64_C(0x82cca4db,847945ca) ,
GRISU_UINT64_C(0xa37fce12,6597973d) , GRISU_UINT64_C(0xcc5fc196,fefd7d0c) ,
GRISU_UINT64_C(0xff77b1fc,bebcdc4f) , GRISU_UINT64_C(0x9faacf3d,f73609b1) ,
GRISU_UINT64_C(0xc795830d,75038c1e) , GRISU_UINT64_C(0xf97ae3d0,d2446f25) ,
GRISU_UINT64_C(0x9becce62,836ac577) , GRISU_UINT64_C(0xc2e801fb,244576d5) ,
GRISU_UINT64_C(0xf3a20279,ed56d48a) , GRISU_UINT64_C(0x9845418c,345644d7) ,
GRISU_UINT64_C(0xbe5691ef,416bd60c) , GRISU_UINT64_C(0xedec366b,11c6cb8f) ,
GRISU_UINT64_C(0x94b3a202,eb1c3f39) , GRISU_UINT64_C(0xb9e08a83,a5e34f08) ,
GRISU_UINT64_C(0xe858ad24,8f5c22ca) , GRISU_UINT64_C(0x91376c36,d99995be) ,
GRISU_UINT64_C(0xb5854744,8ffffb2e) ,
On 2010/02/18 10:21:12, William Hesse wrote:
> Could this be formatted into 80-character lines?
This is generated code. In the new version this is easier to see. I could adapt
the program to output not more than 80chars/line.
However if there are long lines it is easier to see what variables are actually
declared.

[Lasse Reichstein, 2010-02-22 11:31:36]

Style and nitpick comments only.

http://codereview.chromium.org/619005/diff/6030/6036
File src/diy_fp.h (right):

http://codereview.chromium.org/619005/diff/6030/6036#newcode68
src/diy_fp.h:68: // are only used for rounding the first 64 bits.
Which bits are first and last? Do you mean low and high/most or least
signficant?

http://codereview.chromium.org/619005/diff/6030/6036#newcode69
src/diy_fp.h:69: const uint64_t kM32 = 0xFFFFFFFF;
Put a "u" on the end of the literal to make it unsigned.

http://codereview.chromium.org/619005/diff/6030/6037
File src/double.h (right):

http://codereview.chromium.org/619005/diff/6030/6037#newcode31
src/double.h:31: #include "diy_fp.h"
For consistency with the remaining code, please don't include .h files from .h
files. Instead include the them both in any file that uses this .h file.

http://codereview.chromium.org/619005/diff/6030/6037#newcode36
src/double.h:36: typedef union {
Using a union to convert is bound to give problems with strict-aliasing (if we
ever get to enabling that).
Have you considered using the BitCast template instead?
It uses memcpy to copy the bits, but is optimized very efficiently by compilers.

http://codereview.chromium.org/619005/diff/6030/6037#newcode58
src/double.h:58: static const int kSignificandSize = 52;  // excluding the
hidden bit
Format comments as full sentences (capital start letter, full stop at end).

http://codereview.chromium.org/619005/diff/6030/6037#newcode64
src/double.h:64: DiyFp AsDiyFp() const {
Do you have any suggested pronunciation of DiyFp? :)

http://codereview.chromium.org/619005/diff/6030/6046
File src/globals.h (right):

http://codereview.chromium.org/619005/diff/6030/6046#newcode103
src/globals.h:103: //      write GRISU_UINT64_C(0x12345678,90123456);
GRISU -> V8_2PART

http://codereview.chromium.org/619005/diff/6030/6046#newcode104
src/globals.h:104: #define V8_2PART_UINT64_C(a, b)  (((static_cast<uint64_t>(a)
<< 32) + 0x ## b))
Put a "## u" after the b to make it an unsigned constant. Just to be safe.

http://codereview.chromium.org/619005/diff/6030/6033
File src/grisu3.cc (right):

http://codereview.chromium.org/619005/diff/6030/6033#newcode167
src/grisu3.cc:167: case 32:
For readability, could you reverse the order of the cases in each group, so they
come in decreasing order

http://codereview.chromium.org/619005/diff/6030/6033#newcode447
src/grisu3.cc:447: int K;
Lower case variable names (and preferably not single-letter names).

http://codereview.chromium.org/619005/diff/6030/6038
File src/powers_ten.h (right):

http://codereview.chromium.org/619005/diff/6030/6038#newcode2
src/powers_ten.h:2: // command used:  tools/generate-ten-powers --from -308 --to
342 --mantissa-size 64 --round round -o src/powers_ten.h
Is this line correct (or should there be a .scm after the file name?).

http://codereview.chromium.org/619005/diff/6030/6038#newcode3
src/powers_ten.h:3: 
Even if it's generated, do generate it with some newlines.
It's going to blow someone's editor :)

Also, does it lint? (Or how is it omitted from lint checking?)

[Florian Loitsch, 2010-02-22 15:52:52]

I have addressed all mentioned issues.
Please give it another look.

http://codereview.chromium.org/619005/diff/6030/6036
File src/diy_fp.h (right):

http://codereview.chromium.org/619005/diff/6030/6036#newcode68
src/diy_fp.h:68: // are only used for rounding the first 64 bits.
On 2010/02/22 11:31:36, Lasse Reichstein wrote:
> Which bits are first and last? Do you mean low and high/most or least
> signficant?

Done.

http://codereview.chromium.org/619005/diff/6030/6036#newcode69
src/diy_fp.h:69: const uint64_t kM32 = 0xFFFFFFFF;
On 2010/02/22 11:31:36, Lasse Reichstein wrote:
> Put a "u" on the end of the literal to make it unsigned.

Done.

http://codereview.chromium.org/619005/diff/6030/6037
File src/double.h (right):

http://codereview.chromium.org/619005/diff/6030/6037#newcode31
src/double.h:31: #include "diy_fp.h"
On 2010/02/22 11:31:36, Lasse Reichstein wrote:
> For consistency with the remaining code, please don't include .h files from .h
> files. Instead include the them both in any file that uses this .h file.

Done.

http://codereview.chromium.org/619005/diff/6030/6037#newcode36
src/double.h:36: typedef union {
On 2010/02/22 11:31:36, Lasse Reichstein wrote:
> Using a union to convert is bound to give problems with strict-aliasing (if we
> ever get to enabling that).
> Have you considered using the BitCast template instead?
> It uses memcpy to copy the bits, but is optimized very efficiently by
compilers.

Done.

http://codereview.chromium.org/619005/diff/6030/6037#newcode58
src/double.h:58: static const int kSignificandSize = 52;  // excluding the
hidden bit
On 2010/02/22 11:31:36, Lasse Reichstein wrote:
> Format comments as full sentences (capital start letter, full stop at end).

Done.

http://codereview.chromium.org/619005/diff/6030/6037#newcode64
src/double.h:64: DiyFp AsDiyFp() const {
On 2010/02/22 11:31:36, Lasse Reichstein wrote:
> Do you have any suggested pronunciation of DiyFp? :)

Do It Yourself Floating Point. Name is copied from underlying paper. But I'm
willing to change it.

http://codereview.chromium.org/619005/diff/6030/6046
File src/globals.h (right):

http://codereview.chromium.org/619005/diff/6030/6046#newcode103
src/globals.h:103: //      write GRISU_UINT64_C(0x12345678,90123456);
On 2010/02/22 11:31:36, Lasse Reichstein wrote:
> GRISU -> V8_2PART

Done.

http://codereview.chromium.org/619005/diff/6030/6046#newcode104
src/globals.h:104: #define V8_2PART_UINT64_C(a, b)  (((static_cast<uint64_t>(a)
<< 32) + 0x ## b))
On 2010/02/22 11:31:36, Lasse Reichstein wrote:
> Put a "## u" after the b to make it an unsigned constant. Just to be safe.

Done.

http://codereview.chromium.org/619005/diff/6030/6033
File src/grisu3.cc (right):

http://codereview.chromium.org/619005/diff/6030/6033#newcode167
src/grisu3.cc:167: case 32:
On 2010/02/22 11:31:36, Lasse Reichstein wrote:
> For readability, could you reverse the order of the cases in each group, so
they
> come in decreasing order

Done.

http://codereview.chromium.org/619005/diff/6030/6033#newcode447
src/grisu3.cc:447: int K;
On 2010/02/22 11:31:36, Lasse Reichstein wrote:
> Lower case variable names (and preferably not single-letter names).

Done.

http://codereview.chromium.org/619005/diff/6030/6038
File src/powers_ten.h (right):

http://codereview.chromium.org/619005/diff/6030/6038#newcode2
src/powers_ten.h:2: // command used:  tools/generate-ten-powers --from -308 --to
342 --mantissa-size 64 --round round -o src/powers_ten.h
On 2010/02/22 11:31:36, Lasse Reichstein wrote:
> Is this line correct (or should there be a .scm after the file name?).
Line is correct. The scm-file must be compiled first. I have added a comment in
the scm file.

http://codereview.chromium.org/619005/diff/6030/6038#newcode3
src/powers_ten.h:3: 
On 2010/02/22 11:31:36, Lasse Reichstein wrote:
> Even if it's generated, do generate it with some newlines.
> It's going to blow someone's editor :)
> 
> Also, does it lint? (Or how is it omitted from lint checking?)
Lints now.

[fschneider, 2010-02-22 16:25:24]

Interesting stuff!

A few random drive-by comments.

http://codereview.chromium.org/619005/diff/6030/6032
File src/conversions.cc (right):

http://codereview.chromium.org/619005/diff/6030/6032#newcode392
src/conversions.cc:392: decimal_rep = &grisu_buffer[0];
You can just write: decimal_rep = grisu_buffer;

http://codereview.chromium.org/619005/diff/6030/6033
File src/grisu3.cc (right):

http://codereview.chromium.org/619005/diff/6030/6033#newcode129
src/grisu3.cc:129: // Remark: this procedure takes into account the imprecission
of its input
Typo: -> precision

http://codereview.chromium.org/619005/diff/7002/7007
File src/cached_powers.h (right):

http://codereview.chromium.org/619005/diff/7002/7007#newcode40
src/cached_powers.h:40: #define GRISU_CACHE_STRUCT CachedPower
No reason for this macro?

http://codereview.chromium.org/619005/diff/7002/7007#newcode43
src/cached_powers.h:43: #define GRISU_CACHE_OFFSET kCachedPowerOffset
No reason for this macro either.

http://codereview.chromium.org/619005/diff/7002/7007#newcode44
src/cached_powers.h:44: #define GRISU_UINT64_C V8_2PART_UINT64_C
And this one.

http://codereview.chromium.org/619005/diff/7002/7007#newcode50
src/cached_powers.h:50: #define COMPUTE_FOR_CACHE(i) \
If this is performance-critical make an inline function, not a macro.

http://codereview.chromium.org/619005/diff/7002/7007#newcode76
src/cached_powers.h:76: if (!found && (gamma - alpha + 1 >=
GRISU_CACHE_MAX_DISTANCE(8))) {
Remove. This is the same as:

COMPUTE_FOR_CACHE(8)

which you have already below.

[Florian Loitsch, 2010-02-23 09:05:10]

The .h files do not seem to follow V8 (and Google) standards. Any suggestions on
improving that?
I could create -inl.h files, but I'm not really sure that would help much.

http://codereview.chromium.org/619005/diff/6030/6032
File src/conversions.cc (right):

http://codereview.chromium.org/619005/diff/6030/6032#newcode392
src/conversions.cc:392: decimal_rep = &grisu_buffer[0];
On 2010/02/22 16:25:24, fschneider wrote:
> You can just write: decimal_rep = grisu_buffer;

Done.

http://codereview.chromium.org/619005/diff/6030/6033
File src/grisu3.cc (right):

http://codereview.chromium.org/619005/diff/6030/6033#newcode129
src/grisu3.cc:129: // Remark: this procedure takes into account the imprecission
of its input
On 2010/02/22 16:25:24, fschneider wrote:
> Typo: -> precision

Done.

[Florian Loitsch, 2010-03-04 11:52:30]

updated to latest revision.
Mostly small changes.
I have another patch pending for conversions.cc which is why I haven't changed
that file more than necessary. Also in the pending patch grisu3 will only be
called on positive numbers (which is why its unit-test only tests positive
numbers).

[William Hesse, 2010-03-09 12:21:57]

Everything except grisu3.cc reviewed.

http://codereview.chromium.org/619005/diff/10032/10037
File src/cached_powers.h (right):

http://codereview.chromium.org/619005/diff/10032/10037#newcode42
src/cached_powers.h:42: // The following defines "implement" the interface
between this file and the
Avoid using quotes to qualify or weaken words.  Just say implement.

http://codereview.chromium.org/619005/diff/10032/10037#newcode45
src/cached_powers.h:45: // GRISU_CACHE_NAME(i) contains GRISU_CACHE_NAME(1)
where only every every 'i'th
every every

http://codereview.chromium.org/619005/diff/10032/10037#newcode48
src/cached_powers.h:48: // The higher 'i' is the less elements we use.
fewer elements

http://codereview.chromium.org/619005/diff/10032/10047
File src/checks.h (right):

http://codereview.chromium.org/619005/diff/10032/10047#newcode105
src/checks.h:105: 
Make sure this works on all platforms, without introducing compilation failures,
by checking it in separately.  Or else drop it.  We have had troubles with this
in the past.

http://codereview.chromium.org/619005/diff/10032/10038
File src/diy_fp.h (right):

http://codereview.chromium.org/619005/diff/10032/10038#newcode34
src/diy_fp.h:34: // This "Do It Yourself Floating Point" class implements a
64bit significand/int
implements a floating point number with a uint64 significand and an int
exponent.  Normalized DiyFp numbers will have the top bit of the significand
set, and multiplication and subtraction do not normalize their results.

http://codereview.chromium.org/619005/diff/10032/10038#newcode48
src/diy_fp.h:48: // than other. The result will not be normalized.
and the significand of this must be bigger than the significand of other.

http://codereview.chromium.org/619005/diff/10032/10040
File src/powers_ten.h (right):

http://codereview.chromium.org/619005/diff/10032/10040#newcode4
src/powers_ten.h:4: 
Add comment: When this header file is used by xxxx.h, only one of the arrays
below is accessed, the smallest array that will work with the given values of
alpha and gamma.  The intention is that only this array will be linked into the
compiled code by the compiler.

http://codereview.chromium.org/619005/diff/10032/10044
File test/cctest/test-double.cc (right):

http://codereview.chromium.org/619005/diff/10032/10044#newcode31
test/cctest/test-double.cc:31: // The last 52 bits + 1 hidden bit a position 52.
The 52 mantissa bits, plus the implicit 1 in bit 52, as a UINT64.

http://codereview.chromium.org/619005/diff/10032/10044#newcode94
test/cctest/test-double.cc:94:
CHECK(!Double(1.7976931348623157e308).IsSpecial());
What about negative numbers?

http://codereview.chromium.org/619005/diff/10032/10046
File tools/generate-ten-powers.scm (right):

http://codereview.chromium.org/619005/diff/10032/10046#newcode30
tools/generate-ten-powers.scm:30: ;;   bigloo -static-bigloo -o
generate-ten-powers generate-ten-powers.scm
Mention that this is a scheme script, and that bigloo is a scheme compiler?

[William Hesse, 2010-03-09 13:22:04]

LGTM.

http://codereview.chromium.org/619005/diff/10032/10035
File src/grisu3.cc (right):

http://codereview.chromium.org/619005/diff/10032/10035#newcode56
src/grisu3.cc:56: static bool RoundWeed(char* buffer, int len, uint64_t wp_W,
uint64_t Delta,
Comment these with a statement describing what they do.

http://codereview.chromium.org/619005/diff/10032/10035#newcode69
src/grisu3.cc:69: // boundary_minus and boundary_plus are the boundaries between
w and its
Don't mix v and w in this comment.  Probably use v only.  Don't use y - just say
x again.  You could say "any number strictly between b_m and b_p will round to v
when converted to double.

http://codereview.chromium.org/619005/diff/10032/10035#newcode89
src/grisu3.cc:89: // In fact: scaled_w - w*10^k < 1ulp (unit in the last place)
of scaled_w.
Can't this be exactly 1 lulp off?  If cached_power is off by 1/2 lulp, and the
multiplication is off by 1/2 lulp?

http://codereview.chromium.org/619005/diff/10032/10035#newcode106
src/grisu3.cc:106: // comma-number it will be updated.
What is a comma-number?

[Florian Loitsch, 2010-03-09 15:32:00]

I have addressed all your concerns. Please have another look.

http://codereview.chromium.org/619005/diff/10032/10037
File src/cached_powers.h (right):

http://codereview.chromium.org/619005/diff/10032/10037#newcode42
src/cached_powers.h:42: // The following defines "implement" the interface
between this file and the
On 2010/03/09 12:21:57, William Hesse wrote:
> Avoid using quotes to qualify or weaken words.  Just say implement.

Done.

http://codereview.chromium.org/619005/diff/10032/10037#newcode45
src/cached_powers.h:45: // GRISU_CACHE_NAME(i) contains GRISU_CACHE_NAME(1)
where only every every 'i'th
On 2010/03/09 12:21:57, William Hesse wrote:
> every every

Done.

http://codereview.chromium.org/619005/diff/10032/10037#newcode48
src/cached_powers.h:48: // The higher 'i' is the less elements we use.
On 2010/03/09 12:21:57, William Hesse wrote:
> fewer elements

Done.

http://codereview.chromium.org/619005/diff/10032/10047
File src/checks.h (right):

http://codereview.chromium.org/619005/diff/10032/10047#newcode105
src/checks.h:105: 
On 2010/03/09 12:21:57, William Hesse wrote:
> Make sure this works on all platforms, without introducing compilation
failures,
> by checking it in separately.  Or else drop it.  We have had troubles with
this
> in the past.
Removed.

http://codereview.chromium.org/619005/diff/10032/10038
File src/diy_fp.h (right):

http://codereview.chromium.org/619005/diff/10032/10038#newcode34
src/diy_fp.h:34: // This "Do It Yourself Floating Point" class implements a
64bit significand/int
On 2010/03/09 12:21:57, William Hesse wrote:
> implements a floating point number with a uint64 significand and an int
> exponent.  Normalized DiyFp numbers will have the top bit of the significand
> set, and multiplication and subtraction do not normalize their results. 

Done.

http://codereview.chromium.org/619005/diff/10032/10038#newcode48
src/diy_fp.h:48: // than other. The result will not be normalized.
On 2010/03/09 12:21:57, William Hesse wrote:
> and the significand of this must be bigger than the significand of other.

Done.

http://codereview.chromium.org/619005/diff/10032/10035
File src/grisu3.cc (right):

http://codereview.chromium.org/619005/diff/10032/10035#newcode56
src/grisu3.cc:56: static bool RoundWeed(char* buffer, int len, uint64_t wp_W,
uint64_t Delta,
On 2010/03/09 13:22:05, William Hesse wrote:
> Comment these with a statement describing what they do.

Done.

http://codereview.chromium.org/619005/diff/10032/10035#newcode69
src/grisu3.cc:69: // boundary_minus and boundary_plus are the boundaries between
w and its
On 2010/03/09 13:22:05, William Hesse wrote:
> Don't mix v and w in this comment.  Probably use v only.  Don't use y - just
say
> x again.  You could say "any number strictly between b_m and b_p will round to
v
> when converted to double.

Done.

http://codereview.chromium.org/619005/diff/10032/10035#newcode89
src/grisu3.cc:89: // In fact: scaled_w - w*10^k < 1ulp (unit in the last place)
of scaled_w.
On 2010/03/09 13:22:05, William Hesse wrote:
> Can't this be exactly 1 lulp off?  If cached_power is off by 1/2 lulp, and the
> multiplication is off by 1/2 lulp? 

I have proved in the paper that the error is still less than 1 ulp. Should I add
more comments?

http://codereview.chromium.org/619005/diff/10032/10035#newcode106
src/grisu3.cc:106: // comma-number it will be updated.
On 2010/03/09 13:22:05, William Hesse wrote:
> What is a comma-number?

Done.

http://codereview.chromium.org/619005/diff/10032/10040
File src/powers_ten.h (right):

http://codereview.chromium.org/619005/diff/10032/10040#newcode4
src/powers_ten.h:4: 
On 2010/03/09 12:21:57, William Hesse wrote:
> Add comment: When this header file is used by xxxx.h, only one of the arrays
> below is accessed, the smallest array that will work with the given values of
> alpha and gamma.  The intention is that only this array will be linked into
the
> compiled code by the compiler.

added comments.

http://codereview.chromium.org/619005/diff/10032/10044
File test/cctest/test-double.cc (right):

http://codereview.chromium.org/619005/diff/10032/10044#newcode31
test/cctest/test-double.cc:31: // The last 52 bits + 1 hidden bit a position 52.
On 2010/03/09 12:21:57, William Hesse wrote:
> The 52 mantissa bits, plus the implicit 1 in bit 52, as a UINT64.

Done.

http://codereview.chromium.org/619005/diff/10032/10044#newcode94
test/cctest/test-double.cc:94:
CHECK(!Double(1.7976931348623157e308).IsSpecial());
On 2010/03/09 12:21:57, William Hesse wrote:
> What about negative numbers?

Done.

http://codereview.chromium.org/619005/diff/10032/10046
File tools/generate-ten-powers.scm (right):

http://codereview.chromium.org/619005/diff/10032/10046#newcode30
tools/generate-ten-powers.scm:30: ;;   bigloo -static-bigloo -o
generate-ten-powers generate-ten-powers.scm
On 2010/03/09 12:21:57, William Hesse wrote:
> Mention that this is a scheme script, and that bigloo is a scheme compiler?

Done.

[floitsch, 2012-04-10 15:54:33]

Sorry about the noise. Just discovered that there were still comments pending on
this review.

https://chromiumcodereview.appspot.com/619005/diff/6030/src/diy_fp.h
File src/diy_fp.h (right):

https://chromiumcodereview.appspot.com/619005/diff/6030/src/diy_fp.h#newcode68
src/diy_fp.h:68: // are only used for rounding the first 64 bits.
On 2010/02/22 11:31:36, Lasse Reichstein wrote:
> Which bits are first and last? Do you mean low and high/most or least
> signficant?

Done.

https://chromiumcodereview.appspot.com/619005/diff/6030/src/diy_fp.h#newcode69
src/diy_fp.h:69: const uint64_t kM32 = 0xFFFFFFFF;
On 2010/02/22 11:31:36, Lasse Reichstein wrote:
> Put a "u" on the end of the literal to make it unsigned.

Done.

https://chromiumcodereview.appspot.com/619005/diff/6030/src/double.h
File src/double.h (right):

https://chromiumcodereview.appspot.com/619005/diff/6030/src/double.h#newcode31
src/double.h:31: #include "diy_fp.h"
On 2010/02/22 11:31:36, Lasse Reichstein wrote:
> For consistency with the remaining code, please don't include .h files from .h
> files. Instead include the them both in any file that uses this .h file.

Done.

https://chromiumcodereview.appspot.com/619005/diff/6030/src/double.h#newcode36
src/double.h:36: typedef union {
On 2010/02/22 11:31:36, Lasse Reichstein wrote:
> Using a union to convert is bound to give problems with strict-aliasing (if we
> ever get to enabling that).
> Have you considered using the BitCast template instead?
> It uses memcpy to copy the bits, but is optimized very efficiently by
compilers.

Done.

https://chromiumcodereview.appspot.com/619005/diff/6030/src/double.h#newcode58
src/double.h:58: static const int kSignificandSize = 52;  // excluding the
hidden bit
On 2010/02/22 11:31:36, Lasse Reichstein wrote:
> Format comments as full sentences (capital start letter, full stop at end).

Done.

https://chromiumcodereview.appspot.com/619005/diff/6030/src/double.h#newcode64
src/double.h:64: DiyFp AsDiyFp() const {
On 2010/02/22 11:31:36, Lasse Reichstein wrote:
> Do you have any suggested pronunciation of DiyFp? :)

Do It Yourself Floating Point. This name is copied from the associated paper. I
could change it, though.

https://chromiumcodereview.appspot.com/619005/diff/6030/src/globals.h
File src/globals.h (right):

https://chromiumcodereview.appspot.com/619005/diff/6030/src/globals.h#newcode103
src/globals.h:103: //      write GRISU_UINT64_C(0x12345678,90123456);
On 2010/02/22 11:31:36, Lasse Reichstein wrote:
> GRISU -> V8_2PART

Done.

https://chromiumcodereview.appspot.com/619005/diff/6030/src/globals.h#newcode104
src/globals.h:104: #define V8_2PART_UINT64_C(a, b)  (((static_cast<uint64_t>(a)
<< 32) + 0x ## b))
On 2010/02/22 11:31:36, Lasse Reichstein wrote:
> Put a "## u" after the b to make it an unsigned constant. Just to be safe.

Done.

https://chromiumcodereview.appspot.com/619005/diff/6030/src/grisu3.cc
File src/grisu3.cc (right):

https://chromiumcodereview.appspot.com/619005/diff/6030/src/grisu3.cc#newcode167
src/grisu3.cc:167: case 32:
On 2010/02/22 11:31:36, Lasse Reichstein wrote:
> For readability, could you reverse the order of the cases in each group, so
they
> come in decreasing order

Done.

https://chromiumcodereview.appspot.com/619005/diff/6030/src/grisu3.cc#newcode447
src/grisu3.cc:447: int K;
On 2010/02/22 11:31:36, Lasse Reichstein wrote:
> Lower case variable names (and preferably not single-letter names).

Done.

https://chromiumcodereview.appspot.com/619005/diff/6030/src/powers_ten.h
File src/powers_ten.h (right):

https://chromiumcodereview.appspot.com/619005/diff/6030/src/powers_ten.h#newc...
src/powers_ten.h:2: // command used:  tools/generate-ten-powers --from -308 --to
342 --mantissa-size 64 --round round -o src/powers_ten.h
On 2010/02/22 11:31:36, Lasse Reichstein wrote:
> Is this line correct (or should there be a .scm after the file name?).
The scm file has to be compiled first. So this line is correct.

https://chromiumcodereview.appspot.com/619005/diff/6030/src/powers_ten.h#newc...
src/powers_ten.h:3: 
On 2010/02/22 11:31:36, Lasse Reichstein wrote:
> Even if it's generated, do generate it with some newlines.
> It's going to blow someone's editor :)
> 
> Also, does it lint? (Or how is it omitted from lint checking?)
Will fix output so it lints.

https://chromiumcodereview.appspot.com/619005/diff/7002/src/cached_powers.h
File src/cached_powers.h (right):

https://chromiumcodereview.appspot.com/619005/diff/7002/src/cached_powers.h#n...
src/cached_powers.h:76: if (!found && (gamma - alpha + 1 >=
GRISU_CACHE_MAX_DISTANCE(8))) {
On 2010/02/22 16:25:24, fschneider wrote:
> Remove. This is the same as:
> 
> COMPUTE_FOR_CACHE(8)
> 
> which you have already below.
> 

Done.