Add FloatPrinter based on Grisu3

[will]

This improves the speed of transforming floats to their string
representation. It is based on the 2004 paper "Printing Floating-Point
Numbers Quickly and Accurately with Integers" by Florian Loitsch[1].

Most of the code is a port from the BSD-licensed C++ project
"double-conversion"[2], which was extracted from the V8 engine.

The Grisu3 algorithm is fast because it deals only with fixed-sized
integer arithmetic. It takes advantage extra bits leftover from the
53-bit significand in a 64 bit number to help find the optimal string
representation. However this only works for 95.5% of floats and it
rejects the remaining 0.5%. Rejected numbers still need to be printed
with some other, slower method.

1: http://www.cs.tufts.edu/~nr/cs257/archive/florian-loitsch/printf.pdf
2: https://github.com/google/double-conversion

Previous issues #4308 #2220

[will]

edit: This patch now has Float32 support, disregard the rest of this comment

---

From #4308

I tried to cast to Float64 in the current algorithm but the float changes its value and the end result is different than the original. I don't understand why, but that's what happened. You could probably try it with grisu3 and see what happens. If it works, we should do it :-)

I ran into the same thing. I'm going to look at Float32s can be added by using https://github.com/google/double-conversion/blob/9ed0dec708a18f0bbdf1a1edaee1b6b86be2043a/double-conversion/ieee.h#L263 but I'll do that in a separate PR if it works

[Sija]

Almost there, there's just one failing formatter check:

Error: formatting 'src/float_printer.cr' produced changes

[bcardiff]

@will what was the problem with -NaN? it is a valid float -NaN AFAIK.

I haven't review the code, I am asking just because commit message says remove -NaN test.

[will]

@bcardiff it was working locally, but was failing on travis. I wasn't actually sure if -NaN was a valid float, and assumed if it was a platform issue if it was failing on travis.

If -NaN is valid, I can try spinning up an instance and try and debug why it was printing as NaN on travis.

[will]

["nan", "-nan"].each {|s| a = s.to_f; puts [s, pointerof(a).as(UInt64*).value.to_s(16)]}

on Linux 4.10.10-200.fc25.x86_64 #1 SMP Thu Apr 13 01:11:51 UTC 2017 x86_64 x86_64 x86_64 GNU/Linux

["nan", "7ff8000000000000"]
["-nan", "7ff8000000000000"]

on Darwin 16.5.0 Darwin Kernel Version 16.5.0: Fri Mar 3 16:52:33 PST 2017; root:xnu-3789.51.2~3/RELEASE_X86_64 x86_64

["nan", "7ff8000000000000"]
["-nan", "fff8000000000000"]

It looks like crystal on linux is not setting the negative bit. I wonder though if this is a bug in String#to_f

[bcardiff]

Crystal String#to_f relies on LibC.strtod. I read that the NaN treatment differs from platform to platform.

The only way I was able to build a -NaN in osx and crystal 0.22.0 is to parse a -NaN as you did

fs = [0.0 / 0.0,
-0.0 / 0.0,
0.0 / -0.0,
-0.0 / -0.0,
"NaN".to_f64,
"-NaN".to_f64]

fs.each do |f|
  {f , f.to_s, pointerof(f).as(UInt64*).value.to_s(16), f.nan? }
  # 5 times => nan.0	"nan.0"	"7ff8000000000000" true
  # 1 time  => nan.0	"nan.0"	"fff8000000000000" true
end

From https://linux.die.net/man/3/snprintf it seems that -NaN's are not defined in SUSv2.

I now notice that the test_str spec you removed was original introduced by you. Maybe we are just fine with unsigned NaN.

[will]

I updated the test to use the memory representation of -nan and nan. This way, even if it's unlikely to come across a -NaN on linux, the tests should work cross platform.

[Sija]

typo: converst -> converts

[will]

thanks

[will]

Just for fun, wanted to bench this in a different way. This is just the most straightforward way in each lang. I wouldn't be surprised if there were fancy ways to eek out performance here and there, but that really wasn't the point

This is the average speed it takes to generate 1Gb of floats with newlines to stdout

./crystal_old | pv -Ss 1g > /dev/null
   1GiB 0:01:39 [10.2MiB/s] [=================>] 100%
./crystal_new | pv -Ss 1g > /dev/null
   1GiB 0:00:51 [19.9MiB/s] [=================>] 100%
./c_float | pv -Ss 1g > /dev/null
   1GiB 0:00:39 [  26MiB/s] [=================>] 100%
ruby f.rb | pv -Ss 1g > /dev/null
   1GiB 0:01:39 [10.3MiB/s] [=================>] 100%
./go_float | pv -Ss 1g > /dev/null
   1GiB 0:01:15 [13.6MiB/s] [=================>] 100%
./rust_float | pv -Ss 1g > /dev/null
   1GiB 0:01:19 [12.8MiB/s] [=================>] 100%

# crystal complied —release
a = 1.0
loop { puts a += 1.1 }

// C
/// compiled with -O on LLVM version 8.1.0 (clang-802.0.38)
#include <stdio.h>

int main() {
  double a = 1.0;
  for (;;) {
    printf("%.17g\n", a);
    a = a + 1.1;
  }
}

# ruby v3.4.1p111
a = 1.0
loop { puts a += 1.1 }

// go 1.8.1
package main
import "fmt"
func main() {
  a := 1.0
  for {
    fmt.Println(a);
    a += 1.1;
  }
}

// rust 1.17.0, built with -O
fn main() {
  let mut a = 1.0;
  loop {
    println!("{}",a);
    a += 1.1;
  }
}

I wanted to also do node because grisu3 is used in V8, but I had problems with it:

a = 1.0
for (;;) {
  console.log(a);
  a += 1.1
}

node f.js | pv -Ss 1g > /dev/null
^C37MiB 0:02:11 [ 0 B/s] [=> ] 13% ETA 0:14:04

It was at 0B/s when I killed it there, and it would switch from like 200Kb/s to 0 after a while, something is obviously wrong here, but eh.

[Fryguy]

Minor, but would it be a better file organization to have the class be nested under Float instead of a new top-level class? (i.e. Float::Printer instead of FloatPrinter)

[asterite]

@will Thank you so much for this!!

After this I will do a few minor changes, like probably move FloatPrinter inside Float, and introduce an Object#bitcast method to avoid all those pointerof(var).as(T*).value (which can be used in a few other places too).

[RX14]

@asterite can you explain the bitcast name? It doesn't seem to fit to me.

[asterite]

@RX14 LLVM uses bitcast. It casts an object to another by just using the same bits. C++ uses reinterpret_cast. But since we don't have other casts (well, as) I think that's a good name.

[asterite]

Any other suggestion, though?

[RX14]

How about unsafe_as? It's basically as but works on a lot more types, because it's unsafe.

[asterite]

Hmmm... I think I like that name :-)

For example you can't do 1.as(Float32), so I was going to say that it's a bit strange that 1.unsafe_as(Float32) would work, but it makes sense because it's reinterpreting the value as another type, even though there's no "safe" way to make that work.

[RX14]

@asterite yes, that was exactly what I was trying to get at.