Zmij: Faster floating point double-to-string conversion

Summary

There comes a time in every software engineer’s life when they come up with a new binary-to-decimal floating-point conversion method. I guess my time has come. I just wrote one, mostly over a weekend: https://github.com/vitaut/zmij.It incorporates lessons learned from implementing Dragon4, Grisu and Schubfach along with a few new ideas from myself and others. The main guiding principle is Alexandrescu’s “no work is less work than some work” so a number of improvements come from removing things from Schubfach (conditional branches, computations and even candidate numbers).PerformanceHere is how it performs on dtoa-benchmark:~68% faster than Dragonbox, the previous leader (at least among algorithms with correctness proofs)~2 times faster than my Schubfach implementation that closely follows the original paper~3.5 times faster than std::to_chars from libc++ (Ryu?)~6.8 times faster than Google’s double-conversion (Grisu3)~59 times (not percent!) faster than sprintf on macOS (Dragon4?)Converting a single double takes about 10 to 20 ns on Apple M1.What are the improvements?Here is a list of improvements compared to Schubfach:Selection from 1-3 candidates instead of 2-4Fewer integer multiplications in the shorter caseFaster logarithm approximationsFaster division and moduloFewer conditional branchesMore efficient significand and exponent outputLet’s take a look at some of them.The first small improvement is having a single branch to quickly check for special cases: NaN, infinity, zero or subnormals. There are still additional checks within that path but the common case is more streamlined.Another improvement is using faster fixed-point logarithm approximations. Schubfach does the following:// log10_2_sig = round(log10(2) * 2**log10_2_exp) constexpr int64_t log10_2_sig = 661'971'961'083; constexpr int log10_2_exp = 41; // Computes floor(log10(pow(2, e))) for e <= 5456721. auto floor_log10_pow2(int e) noexcept -> int { return e * log10_2_sig >> log10_2_exp; } which uses 64-b...