Compared to the previous implementation:
* Faster
* Smaller code size
* Produces exactly the same output
* New! Float80 support in Swift!
(Float128 support is also here, tested and ready to go.
Just commented out until we actually have Float128. ;-)
This reimplements debugDescription for Float and Double using a new algorithm
based on Raffaello Guilietti's Schubfach paper, carrying over some performance
improvements from the previous Grisu-based implementation.
In practice, this is about twice as fast as the previous implementation,
and the code is both shorter and simpler.
Extensive testing shows that the new implementations produce identical
output to the previous implementations.
The basic idea is:
* Start by expressing the floating-point value as `s * 2^e` where `s`
and `e` are both integers.
* Estimate the power of 10 as `p = ceiling(e * log10(2))`
* Scale the upper bound of the rounding interval by `10^(-p)` to obtain
between 0 and 16 digits for Double (0 to 8 for Float)
* About 40% of the time, those initial digits (after pruning
any trailing zeros) are precisely the desired optimal form
* The remaining 60% of the time, we need exactly one additional digit.
* A slight adjustment allows us to directly compute one of only
two possibilities for that final digit. A quick test discriminates
between them.
On an M4 MacBook Air, the core `_Float32ToASCII` for single-precision
takes about 6ns to produce the final text in a local buffer.
`Float.debugDescription` based on this takes a total of 9ns.
The core double-precision implementation takes about 10ns,
with another 14ns required to allocate a `String` on the heap.
I have not yet converted Float16 and Float80 over to
the new algorithm. When I do so, I'd like to factor the Float80
tables a bit more carefully to further reduce overall code size.
The fact that `Double.debugDescription` is now dominated by heap
allocation means that we should explore APIs that
append to an existing buffer rather than allocating from scratch.
Observation: It would be possible to restructure the current code
into two functions:
* A base conversion that takes a pair of integers
(binary significand and power of 2)
and returns another pair of integers
(decimal significand and power of 10)
* A formatting routine that takes a decimal significand
and power of 10 and formats it appropriately.
This would be compelling if there were other uses for either
of these two functions.
This is possible because this replaces
* `InlineArray` with `internal _InlineArray`
* `UInt128` with `internal _UInt128`
And the replacements are not availability-restricted.
We don't need to do the same thing with `MutableSpan`
because that back-deploys to Swift 5.0, which is as
far back as the stdlib builds anyway.
For example, this avoids the need to do any explicit byte-by-byte
writes when expanding "123" out to "123000000.0".
This also required reworking the "back out extra digits" process
for Float64 to ensure the unused digits get written as '0' characters
instead of null bytes.
Tim Kientzle
Guillaume Lessard