Uploaded image for project: 'Swift'
  1. Swift
  2. SR-454

Reimplement float -> string with better algorithms

    XMLWordPrintable

    Details

    • Type: Improvement
    • Status: Resolved
    • Priority: Medium
    • Resolution: Done
    • Component/s: Standard Library
    • Labels:
      None

      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

        Attachments

          Issue Links

            Activity

              People

              Assignee:
              tbkka Tim Kientzle
              Reporter:
              lily Lily Ballard
              Votes:
              0 Vote for this issue
              Watchers:
              2 Start watching this issue

                Dates

                Created:
                Updated:
                Resolved: