Question about parse(Float) in Base

General Usage Performance
, ,
1

I’ve been trying to add speed to XLSX.jl as it reads data from Excel in response to this issue.

I’ve been working with Claude and achieving some good results but one suggestion it made surprised me. It recommended replacing parse with what it calls “Clinger’s exact fast path” for a subset of possible Floats. Specifically:

For a plain decimal (-?digits[.digits][e±digits]) with at most 15 significant digits and a decimal exponent p with |p| ≤ 22:

  • the digits form an integer m < 10¹⁵ < 2⁵³, which is exact in Float64;
  • 10^|p| is also exact, since 5²² < 2⁵³;
  • so the single IEEE operation m * 10^p (or m / 10^-p) is correctly rounded, which is the same result a correct strtod (the C library method Claude says Base uses) returns.

It puts everything else through the standard path in Base unchanged.

In Windows 11, it measures this as follows:

Input parse(Float64, s) fast path
typical values, e.g. “1234.5678” 323 ns 13.6 ns (24×)
17-significant-digit values (fall through) 403 ns 396 ns (no overhead)

I have always understood that Base was pretty well optimised, so my naïve reasoning is that, if Claude is right, Base must be handling a range of possible inputs that do not arise with Excel, so can be ignored in XLSX.jl. I have no idea if this is right.

So, three questions:

  • Is Claude’s proposal credible?
  • Will similar improvements be seen on Linux/MacOS and other supported systems?
  • Should I consider including this change?

Any advice very welcome because this is well outside my expertise!

2

All I can say is that the argument seems a bit incoherent. If you consider all the significant digits as an integer, you need to shift the exponent correspondingly to compensate for decimal positions. But the shifted exponent wouldn’t stay within ±22, which the rest of the analysis assumes.

3

It’s possible I’ve over simplified too far. Claude gave me an extensive explanation but I didn’t paste it here verbatim because to do so would probably violate forum rules. It is hard to summarise something you don’t fully understand!

4

In hopes of escaping censure:

Title: parse(Float64, s) is ~24x slower than an exact fast path on Windows. Worth adding to Base?

While fixing a read-performance regression in XLSX.jl (JuliaData/XLSX.jl#462), I found that parse(Float64, s) was the largest single cost of reading a numeric spreadsheet: 16–19% of readtable time in a profile. In 1.13, Base’s method is a ccall to jl_try_substrtod, the C library’s strtod.

I added Clinger’s exact fast path in front of it. For a plain decimal (-?digits[.digits][e±digits]) with at most 15 significant digits and a decimal exponent p with |p| ≤ 22:

  • the digits form an integer m < 10¹⁵ < 2⁵³, which is exact in Float64;
  • 10^|p| is also exact, since 5²² < 2⁵³;
  • so the single IEEE operation m * 10^p (or m / 10^-p) is correctly rounded, which is the same result a correct strtod returns.

Anything else falls through to parse(Float64, s) unchanged: more digits, larger exponents, whitespace, inf/nan, hex, or malformed input. So results and errors outside the fast path are identical. The code is a ~60-line loop over the code units, with no allocation: [link to _fast_decimal in src/cell.jl on the branch]

Measurements (Windows 11, x86_64, Julia 1.13.1, SubString{String} inputs):

Input parse(Float64, s) fast path
typical values, e.g. “1234.5678” 323 ns 13.6 ns (24x)
17-significant-digit values (fall through) 403 ns 396 ns (no overhead)

Correctness. Over 3 million random strings, 2.06 million took the fast path, with 0 mismatches against parse (compared with reinterpret(UInt64, …)). XLSX.jl’s tests add 1.5 million strings in the forms Excel writes, every numeric cell in its test files, and edge cases (-0, 1E22 vs 1E23, 15 vs 16 digits, .5, 1., rejected inputs).

End to end. With only this change, XLSX.jl’s readtable on a 30,000 × 84 Excel-style sheet went from 3.14 s to 2.60 s (−17%), and from 4.61 s to 3.68 s (−20%) on a 50,000 × 70 sheet.

Questions:

  1. Is strtod known to be slow on Windows in particular? I’ve only measured there. Linux and macOS numbers would help show whether this is general.
  2. Would Base take a pure-Julia fast path like this ahead of the ccall? Or go further, with something like Eisel–Lemire (as in fast_float, Rust and, I believe, Parsers.jl), which covers 16–19 digits as well? Many real values are 16–17-digit computed results.
  3. Is there a reason for keeping C strtod that I’m missing (locale, error semantics, platform behaviour)?

The fast path relies on IEEE binary64 arithmetic without x87 extended precision. My understanding is that this holds on all of Julia’s supported platforms (SSE2 on i686).

5

Parsers.jl provides optimized numeric parsers that work directly on Vector{UInt8} buffers and views thereof without going through strings.

6

But strings are what Excel provides - they’re the starting point. (Edit: Maybe I’ve misunderstood. Need to check this out with XML.jl)

7

You can also use Parsers.jl on a string, or the low-level functions on codeunits(string), of course. But you’re probably losing performance by allocating a bunch of individual String objects just to parse them.

8

XML.jl returns a SubString{String} that points into the document buffer. It only copies when the text contains entities, which numbers never do. So codeunits(sv) is already a free AbstractVector{UInt8} view. I’ll evaluate Parsers.jl with this against Claude’s proposed fast path.

Thanks!

9

And recently with the Parsers.jl 3.0 release, the float parsing got an upgrade, so we now implement the clinger fast-path algorithm, along with the eisel-lemire fallback, and a native arbitrary precision further fallback that avoids all MPFR/GMP dependency. Let me know if you run into any missing methods; sometimes its hard to get all the sub-array/sub-string types covered correctly.

10

As far as I can tell Claude’s proposal is too broad. Although the idea of multiplying or dividing two exact floating point numbers is fine, the claimed ranges where it applies are too large. For example, 1.00000002e-17 would become 100000002 / 1e25 = 1.0000000199999998e-17 because 1e25 is not exactly represented.

11

I’ve abandoned Claude’s proposal and have gone with Parsers.jl. It offers the same speed improvement while avoiding Claude’s custom implementation.

My only remaining question is, why does the parser in Base remain so slow? Why not adopt the parser(s) in Parsers.jl?

12

I thought MPFR/GMP dependency needed for BigInt and BigFloat, what I would like to get rid of from Base (could be phase II after integrating Parsers.jl there, or at least part of it), I think you’re saying Base could adopt your methods, and still parse them with out those dependencies? And be faster… any downside? Larger sysimage, or not even?

I see this in your code:
Parsers.parse(BigInt, "123456789012345678901234567890") # strictly speaking Int128
Parsers.parse(BigFloat, "0.1")

Julia’s JuliaSyntax.jl parser can’t parse BigFloat, or doesn’t I believe by design, e.g.:

julia> a = 1234567890123456789012345678900000000000000.0
1.2345678901234567e42

julia> typeof(ans)
Float64

though can indirectly:

julia> a = [1.0, 1234567890123456789012345678900000000000000]
2-element Vector{BigFloat}:
 1.0
 1.2345678901234567890123456789e42

I.e. must parse as BigInt then promote to BigFloat. I suppose it then uses promote, and might be suboptimal since in some cases you might not know ahead of time of the promotion though you could know it there.

I didn’t know what the Clinger fast-path algorithm is, while heard of the more recent Eisel–Lemire, I understand (both) also helpful for regular Float64, and neither in Base, explaining why slow there. Would such parsing there have used MPFR/GMP dependency?

This fallback function is never called in practice. We prove that the fallback is unnecessary.

Apparently not (might even be bad to use, unless “your application intentionally relies on the OS environment to parse native user strings like "3,14" as a float”); this is a fascinating topic, and last question in my AI chat here Google Search