Description
| Previous ID | SR-454 |
| Radar | None |
| Original Reporter | @lilyball |
| Type | Improvement |
| Status | Resolved |
| Resolution | Done |
Additional Detail from JIRA
| Votes | 0 |
| Component/s | Standard Library |
| Labels | Improvement |
| Assignee | @tbkka |
| Priority | Medium |
md5: 6d5a4cc175f95505ead8bf96760e0182
duplicates:
relates to:
- [SR-5961] JSONSerialization does not properly convert
1.1swift-corelibs-foundation#4412 - [SR-447] Parsing strings into floating-point performs badly #43064
Issue Description:
Right now, Swift uses the equivalent of printf with a format of %.*g and a precision of std::numeric_limits<T>::digits10 to convert floating-point values into strings. While being relatively simple, this has the downside of not being exact. It means that if you take any arbitrary floating-point value, convert it to a string, and back to the same floating-point type, you're not guaranteed to get the same value.
Instead we should reimplement this using some algorithm that does give an exact result. The ideal result is the "simplest" string that produces the input float when parsed again. But the only actual hard requirements should be an exact result.
Python uses David Gay's dtoa library for performing exact conversions. The downsides to his algorithm are it appears to be incredibly complex (and so we'd likely want to just use the C library directly instead of trying to reimplement the algorithm) and it uses allocation. I'm not sure how the actual performance is, and I don't know if we necessarily want to require allocation for basic functionality like this (i.e. if we ever want to have a subset of the stdlib that's allocation-free for use in embedded systems we'd need an algorithm that doesn't do allocation). FWIW, I believe this library is what's used in many libc's.
Around May of last year Rust switched its implementation to a combination of Grisu3 and Dragon4. David Gay's algorithm was evaluated but discarded because Rust needed an algorithm without allocation, and also because Rust wanted the implementation in Rust itself and Gay's algorithm was so complicated nobody wanted to try and reimplement it. According to the comments, both Grisu3 and Dragon4 are exact algorithms, and Grisu3 is fast but incomplete, whereas Dragon4 is slow but complete. I believe Rust tries to use Grisu3 and falls back to Dragon4 for values that can't be formatted by Grisu3.
Some links for context:
David Gay's algorithm (PDF)
David Gay's dtoa library
Florian Loitsch's Grisu3 (PDF)
Stack Overflow comment saying Grisu3 is much faster than dtoa
Steel & White's Dragon4 (PDF)
rust-lang/rust#24612 PR implementing Grisu3+Dragon4
rust-lang/rust#24556 issue with relevant discussion
rust-lang/rust#24557 issue with more discussion