Consider integration in core and std ?

[Urgau]

Have you consider replacing the dec2flt algorithm in the standard library by your crate ?

I remember have seen several members of the Rust Libs Team encouraging people how have better algorithm (fast, efficient, ...) to integrate their crate in the std library.

Source of dec2flt

[aldanor]

@Urgau I remember this has been already discussed somewhere in rustc GH issues and as I was searching for it, I noticed a related question has been raised again just yesterday - see rust-lang/rust#85198 for further details.

One of concerns to keep in mind: binary size; both dec2flt and the algo used here use lookup tables, but dec2flt will be a bit leaner, I believe.

[Urgau]

Yeah I saw this issue, it's the primary reason why I search crate that do really fast float parsing and ask you that question.

One of concerns to keep in mind: binary size; both dec2flt and the algo used here use lookup tables, but dec2flt will be a bit leaner, I believe.

I know that for certain target, like embedded object, binary size is a big deal but for vast majority of users who use Rust on computers, size is not really a big deal. I think that most people will accept +10/20 kio (just a guess not a actual number) increase for blazing performance improvement in float parsing and for size constraint environment a cfg with -Zbuild-std for disabling the fast algo and go to a slower one in exchange for binary size reduce.

If binary size is the only major concern I think you should consider making a pull request to the rust repository.

[lemire]

I think that what @Urgau wrote makes sense. The binary size can be important, but that's something one can tweak depending on one's needs.

[Alexhuszagh]

@aldanor I'm working on gradual integrations of faster float-parsing algorithms into dec2flt, although obviously, faster algorithms would be preferable if applicable (the benchmarks for this look really promising).

As detailed in this internals post, I'm looking to fix in the following order:

• Fix disguised fast-path algorithms.
• Fix the Bellerophon algorithm, which incorrectly requires arbitrary-precision arithmetic for the significant digits currently (making it very slow).
• Implement faster, arbitrary-precision algorithms (both use iterative scaling based on powers of 2, making them very slow).

My goal is gradual changes, since obviously, it's much easier to justify these changes with minimal differences to binary size but major overall performance improvements. Especially since @hanna-kruppe, the author of the float parsing algorithms, has retired from Rust development, meaning people reviewing these changes are less familiar with the codebase or float-parsing algorithms in general.

Any feedback however would be greatly appreciated.

EDIT In conversations a few years ago with @hanna-kruppe, it was very clear that both binary size was important, and there was at the time a tepid response to moving away from Big32x40 (which can only hold ~385 digits, which is insufficient for a lot of floating-point cases).

[Alexhuszagh]

I should add, I've got a working repository for implementing these changes into Rust's core library here, and the different branches provide improvements to different components of dec2flt.

• core: A minimal, extracted version identical to Rust's dec2flt implementation.
• disguised: Handle disguised fast-path cases for better performance.
• infer: Reduce binary sizes by inferring the binary exponent, rather than explicitly store them (no performance penalty).
• moderate: Fix major performance penalties in the Bellerophon algorithm.

I'll be working on slow-path algorithms later, and my goal is a quick but comprehensive fix of dec2flt in a way that should minimize the number of changes made initially, which hopefully should ease the burden of integrating these changes. I'm wholly amenable to making small, incremental changes and then having all improvements replaced by integration of this library, and if I can help in any way, let me know.

[lemire]

@Alexhuszagh

One point to consider is that the current library can effectively act as a fast path. That is, there is no need to throw away anything but maybe an existing fast path. So it can be non-invasive (and also, easily made optional).

In the Go runtime, the equivalent of the code in this repo. is running. All they did was to remove an existing fast path and replace it with a new one.

It is also relatively thin. Here is the gist of the code...

pub fn compute_float<F: Float>(q: i64, mut w: u64) -> AdjustedMantissa {
    let am_zero = AdjustedMantissa::zero_pow2(0);
    let am_inf = AdjustedMantissa::zero_pow2(F::INFINITE_POWER);
    let am_error = AdjustedMantissa::zero_pow2(-1);

    if w == 0 || q < F::SMALLEST_POWER_OF_TEN as i64 {
        return am_zero;
    } else if q > F::LARGEST_POWER_OF_TEN as i64 {
        return am_inf;
    }
    let lz = w.leading_zeros();
    w <<= lz;
    let (lo, hi) = compute_product_approx(q, w, F::MANTISSA_EXPLICIT_BITS + 3);
    if lo == 0xFFFF_FFFF_FFFF_FFFF {
        let inside_safe_exponent = (q >= -27) && (q <= 55);
        if !inside_safe_exponent {
            return am_error;
        }
    }
    let upperbit = (hi >> 63) as i32;
    let mut mantissa = hi >> (upperbit + 64 - F::MANTISSA_EXPLICIT_BITS as i32 - 3);
    let mut power2 = power(q as i32) + upperbit - lz as i32 - F::MINIMUM_EXPONENT;
    if power2 <= 0 {
        if -power2 + 1 >= 64 {
            return am_zero;
        }
        mantissa >>= -power2 + 1;
        mantissa += mantissa & 1;
        mantissa >>= 1;
        power2 = (mantissa >= (1_u64 << F::MANTISSA_EXPLICIT_BITS)) as i32;
        return AdjustedMantissa { mantissa, power2 };
    }
    if lo <= 1
        && q >= F::MIN_EXPONENT_ROUND_TO_EVEN as i64
        && q <= F::MAX_EXPONENT_ROUND_TO_EVEN as i64
        && mantissa & 3 == 1
        && (mantissa << (upperbit + 64 - F::MANTISSA_EXPLICIT_BITS as i32 - 3)) == hi
    {
        mantissa &= !1_u64;
    }
    mantissa += mantissa & 1;
    mantissa >>= 1;
    if mantissa >= (2_u64 << F::MANTISSA_EXPLICIT_BITS) {
        mantissa = 1_u64 << F::MANTISSA_EXPLICIT_BITS;
        power2 += 1;
    }
    mantissa &= !(1_u64 << F::MANTISSA_EXPLICIT_BITS);
    if power2 >= F::INFINITE_POWER {
        return am_inf;
    }
    AdjustedMantissa { mantissa, power2 }
}

[Alexhuszagh]

@lemire I've mostly been using the term "moderate" path for that, to disambiguate from the term "fast path" used in dec2flt. Since the above uses an extended-precision representation of the significant digits of the float, it would replace the Bellerophon algorithm, which is used if fast_path cannot be used. Rust's dec2flt has a function named fast_path which only works in cases where both the significant digits and the exponent can exactly be represented as native floats (see below). In my opinion, the whole thing should be thrown out and replaced with the above code sample, but I'm working on providing minimal changes with major performance tweaks in the meantime.

https://github.com/rust-lang/rust/blob/28e2b29b8952485679367cc05699fb5154f4e5c3/library/core/src/num/dec2flt/algorithm.rs#L109-L144

[Alexhuszagh]

Oh I should probably add: Rust's dec2flt doesn't parse the first 19-20 significant digits of the float except in the fast path, which is a major performance issue and trivial to fix (and then your algorithm could then be implemented into Rust's core library). The fast path just sees if there is less than 16-digits in the float's integral and fractional components, and then checks if these significant digits can be exactly represented as a native float.

If not, it defaults to creating a big integer from the significant digits, and then calls it's unoptimized Bellerophon algorithm, which can lead to extreme performance hits for no good reason.

In addition, the subsequent algorithm_r ideally prefers a value of z0 that is within 1 ULP of the correct value. This is trivial to implement, using your above algorithm, but would of course have to be modified for that purpose.

[lemire]

@Alexhuszagh

Right.

You have Clinger's fast path which is very cheap and handles things like (small) integers and so forth.

Otherwise, what you want to do is to grab, say, the first 19 digits. Most of the time, numbers won't have more than 17 digits. If you have no more than 19 digits, then the code above is good enough 99.99999% of the time, and even if you have more than 19 digits, the truncation is good enough almost all of the time. See section 11... https://arxiv.org/pdf/2101.11408.pdf

So it should be uncommon that you ever need to materialize a big integer.

[Alexhuszagh]

Yep. My modifications keep Clinger's algorithm (since I don't believe anyone currently on the Rust core team has worked on dec2flt before), but moves significant digit parsing outside of the fast path, and adds error calculation for truncated values, and only after that do we use their big-integer algorithms (which have major issues in nearly every facet, but that's a different story).

Ideally, we'd remove it, and replace it with your code, but I'm trying minor, incremental improvements at first. Ideally, my goals right now are:

1. Fix disguised fast path cases.
2. Improve the Bellerophon algorithm, to handle subnormal floats and avoid needlessly using big-integers.
3. Fix the glacially slow algorithm_m and algorithm_r with easy-to-implement slow-path algorithms.
4. Increase the size of the big-integer storage, so it can handle more than 385 digits (since we need up to 767, which means a lot of floats cannot be parsed by Rust).
5. Remove the last remaining Clinger algorithm, Bellerophon, and replace it with the Eisel-Lemire algorithm based on the code above.

[Urgau]

Ideally, we'd remove it, and replace it with your code, but I'm trying minor, incremental improvements at first. Ideally, my goals right now are:

1. Fix disguised fast path cases.

2. Improve the Bellerophon algorithm, to handle subnormal floats and avoid needlessly using big-integers.

3. Fix the glacially slow `algorithm_m` and `algorithm_r` with easy-to-implement slow-path algorithms.

4. Increase the size of the big-integer storage, so it can handle more than 385 digits
   (since we need up to 767, which means a lot of floats cannot be parsed by Rust).

5. Remove the last remaining Clinger algorithm, Bellerophon, and replace it with the Eisel-Lemire algorithm
   based on the code above.

From an outside point of view: Wouldn't be it simpler and faster to simply replace the actual rust code with the code of fast-float ?

As I see things, there is actual many faults in the rust std implementation, and you are proposing to do a 5 steps improvement (but not a total fix ?). I think that instead of trying to patch the std rust code to ideally be perfect we should take the fastest road and completely replace the actual suboptimal and broken (apparently) by a working one. In this case fast-float or another crate if it fits better the need of the std library.

[Alexhuszagh]

@Urgau Sure, if the maintainers are up for that. There's a few issues mentioned though, and that is:

1. The original implementer is no longer working on Rust, so no one is familiar with the codebase I believe.
2. There's a few assumptions internally that need to be addressed prior to making these changes.
3. The changes required here are relatively trivial, and therefore easy to justify, prior to making larger changes.

If you can justify the changes, that would be ideal. I'm going to test the binary sizes, but this crate should be pretty lean (likely leaner than core), actually. Also, sure it's not a total fix, but it's an improvement of like 10,000x for some floats, which is not insignificant.

[Alexhuszagh]

Ok I've run the numbers and the binary sizes are practically identical, albeit slightly smaller.

fast-float

opt-level	size	size(stripped)
0	3.3M	324K
1	3.3M	300K
2	1.3M	248K
3	1.3M	252K
s	1.3M	244K
z	1.3M	248K

core

opt-level	size	size(stripped)
0	3.6M	360K
1	3.5M	316K
2	1.3M	236K
3	1.3M	248K
s	1.3M	244K
z	1.3M	248K

If you can get the core team to approve of it, it would be a great addition to the core library. I'm still going to try to get incremental improvements implemented, for the reasons above (IMO, it's easier to justify), but ideally, this should be the end goal.

You would likely, however, have to use the [bignum[(https://github.com/rust-lang/rust/blob/master/library/core/src/num/bignum.rs) implementation for the Decimal struct.

As an FYI: I would recommend forking my dec2flt fork of Rust's num module if you're going to do this, since it allows you to implement these changes within the context of the Rust core library without having to build Rust from scratch every time. It's a minimal fork of the dec2flt library, in the context of the Rust core library, and should make it quick and easy to make changes, diffs, and then incorporate them back into the core library.

[Urgau]

@Urgau Sure, if the maintainers are up for that.

Posted an question on the zulip stream for T-Libs.

Ok I've run the numbers and the binary sizes are practically identical, albeit slightly smaller.

That great news.

As an FYI: I would recommend forking my dec2flt fork of Rust's num module if you're going to do this, since it allows you to implement these changes within the context of the Rust core library without having to build Rust from scratch every time. It's a minimal fork of the dec2flt library, in the context of the Rust core library, and should make it quick and easy to make changes, diffs, and then incorporate them back into the core library.

Thanks for the tips but I'm not sure I'm qualified to try doing the integration in std. In fact I barely understand how float are store internally. I will read the academic paper but I'm not sure it will be sufficient.

[Urgau]

@Alexhuszagh I have receive an response from Josh Triplett (who is co-lead of the Rust Libs Team). He said here:

[..] this seems like a great idea to me [...]

So if you want try to do the pull request replacing the dec2flt with the fast-float code, go for it.

There is however an legal concern also raised by Josh.

fast-float-rust says it's directly based on the C++ library. Is the Rust implementation derived from the C++ code or the algorithm in the paper? Asking because the C++ code is just Apache-2.0, but the Rust code says MIT/Apache-2.0.

If the Rust code were a derived work of the C++, it wouldn't be able to add the MIT dual license. (And the C++ code has had third-party contributions, so it isn't just the original author who would need to grant permission for that.)

@aldanor @lemire Would you mind clarifying for Josh Triplett the situation here or directly on zulip concerning the licenses.

Also I have being acting like your were okay for your implementation to be part of the rust standard library without never asking you if you were okay for that. So do you agree for your implementation to be part of the rust standard library ?