miloyip/rapidjson — pull request #97 by miloyip (2014-08-09 14:09:14+00:00)
Title: Issue72customdtoa

## Custom dtoa()

After two weeks of research and implementation, a custom `dtoa()` was implemented to replace `sprintf()` in `Writer::Double()`. A performance benchmark can be checked in another repository [dtoa-benchmark](https://github.com/miloyip/dtoa-benchmark).

Simply put, the custom `dtoa()` is an optimized header-only C++ implementation of Grisu2 algorithm (~400 lines of code). It always generate correct-rounding output. And it can generate shortest representation for >99.9% of input. `sprintf()` cannot output shortest representation.

Also, it fixes the local issue in #72, always generate valid JSON number text.

## Removal of precision settings

Originally, `Writer::SetPrecision()` et al. APIs are added because `sprintf("%g)` has default precision of 6 decimal digits, that may lose precision in source values (thank to @pah 's effort in #19). The new `dtoa()` implementation makes this not necessary as it always generate output that can be convertible back to the source values, and it will try to make the output as short as possible.

So I think those APIs can be removed. A drawback is that user cannot reduce the precision in output as before.

## Better number parsing
During the implementation, it is found that `Reader::ParseNumber()` cannot parse `double` correctly. After some research, the current "naive" implementation can be slightly modified to implement the [fast path](http://www.exploringbinary.com/fast-path-decimal-to-floating-point-conversion/) conversion. It may increase a little bit overhead by using division in half of time, but at the same time it cut down the lookup table in `internal::Pow10()` by half. By this modification, normal ranges of numbers can be converted roundtrip exactly.

## Performance
During the benchmark, it is found that gcc (glib)'s `sprintf(..., "%.17g")` is very very slow, compared to VS2013 (Check [this](http://rawgit.com/miloyip/dtoa-benchmark/master/result/corei7920@2.67_cygwin64_gcc4.8.html) and [this](http://rawgit.com/miloyip/dtoa-benchmark/master/result/corei7920@2.67_win64_vc2013.html)). I have not investigated the reasons behind at the moment.

Anyway, new `dtoa()` implementation is much faster.

Before:
~~~~~~~~~
VC2013 x64
[ OK ] RapidJson.ReaderParseIterativeInsitu_DummyHandler_SSE42 (663 ms)
[ OK ] RapidJson.Writer_NullStream (325 ms)
[ OK ] RapidJson.Writer_StringBuffer (1020 ms)
[ OK ] RapidJson.PrettyWriter_StringBuffer (1420 ms)

Cygwin GCC x64
[ OK ] RapidJson.ReaderParseIterativeInsitu_DummyHandler_SSE42 (875 ms)
[ OK ] RapidJson.Writer_NullStream (5201 ms)
[ OK ] RapidJson.Writer_StringBuffer (5673 ms)
[ OK ] RapidJson.PrettyWriter_StringBuffer (6169 ms)
~~~~~~~~~

After:
~~~~~~~~~
VC2013 x64 After
[ OK ] RapidJson.ReaderParseIterativeInsitu_DummyHandler_SSE42 (661 ms)
[ OK ] RapidJson.Writer_NullStream (257 ms)
[ OK ] RapidJson.Writer_StringBuffer (697 ms)
[ OK ] RapidJson.PrettyWriter_StringBuffer (1037 ms)

Cygwin GCC x64 After
[ OK ] RapidJson.ReaderParseIterativeInsitu_DummyHandler_SSE42 (656 ms)
[ OK ] RapidJson.Writer_NullStream (250 ms)
[ OK ] RapidJson.Writer_StringBuffer (686 ms)
[ OK ] RapidJson.PrettyWriter_StringBuffer (1144 ms)
~~~~~~~~~

The JSON in these tests contains some JSON numbers, not extreme cases that most values are floating-point numbers. So these results only show part of improvement. Even this is not an extreme case, in `NullStream` tests VC2013 shows ~1.25x speedup, while gcc shows ~20x speedup.