Float parsing can fail on valid float literals #31407
Comments
|
cc me |
|
can't we just have a slowpath that uses 3072-bit bignums or something? I mean, for numbers with a very long number of digits, we could:
Certainly, at the worst-case, we do need to compare our string with an halfway-float, After all, |
|
@arielb1 How would you actually implement the second step? Keep in mind that this is in libcore, so we can't use float formatting because that would allocate. (Maybe you could use the underlying functions that are also in libcore, but this probably complicates everything significantly. However I have to admit that I don't even know what the interface of those functions looks like, so maybe it's not that bad.) |
|
I actually read the paper, and its Algorithm R is a variant of what I've came up with. I guess we just need to enlarge our bignums to sufficiently-many bits and use sticky bits+rounding (we don't really need 1075 digits = 3571 bits because we can skip the powers-of-2). |
|
I've gathered a collection of String to Double test cases proved to be problematic in various projects during the past few decades: Rust 1.14.0 (e8a0123 2016-12-16) for Windows fails on 17 of 81 conversion tests (C21, C22, C23, C25, C29, C37, C38, C39, C40, C64, C65, C66, C67, C68, C69, C76, C79), with the following being the shortest one (C29): fn main() {
println!("{}", 2.47032822920623272e-324);
} |
|
@ahrvoje That's a very nice collection of test cases, thanks for sharing! |
|
This is a regression from 1.7.0 to 1.8.0. It broke my crate (lol). |
aturon
added
regression-from-stable-to-beta
eddyb
added
I-nominated
T-libs-api
|
I've nominated this for discussion in the T-libs. This is T-libs area, because error comes from the floating number parsing routines in libstd/core. This is an annoying regression to me and not a nice regression to have in the compiler overall, as one cannot feed any sort of non-normal floating point numbers to the compiler (compile-time) or the parser (run-time). You can’t do something like |
|
@nagisa AFAIK for every floating point value [*] there's a canonical literal that is parsed correctly, it's just that some literals that would also result in the value don't work. Do you have a counter example? [*] Other than the bazillion NaNs with different payloads, of course, but we don't have literals for them anyway. |
|
@rkruppe my counter example is that I have no idea what the canonical literals for my denormals are and am in general paranoid enough about floats to always write them down with some extra precision. That being said, I’m gonna believe you and retract my statement that there’s no way at all to write the denormals down. |
|
If you know the bit pattern you want, you can construct the right float value via transmute and format it (either To be clear, I don't want to deflect attention away from this issue — far from it, I'd really love to see it addressed somehow, and would do so right now I had the time and energy. I'm just trying to understand how it's causing you trouble and offer workarounds in the mean time. |
|
discussed during libs triage today conclusion was we'd definitely like to fix but otherwise doesn't seem P-high, so P-medium |
|
What about falling back to a C library in the meantime? For example, using https://crates.io/crates/strtod instead of Rust's built-in parser seems to fix this bug for me. |
|
The problem is that float parsing is in |
Per rust-lang/rust#31407, rustc's float parser may drop some valid float literals. For now use an external parser that does not have these problems. Closes #147
Per rust-lang/rust#31407, rustc's float parser may drop some valid float literals. For now use an external parser that does not have these problems. Closes #147
- Parse negative exponent reals - Produces errors on certain float literals, see rust-lang/rust#31407 - Switch order of checking for type references in init exprs - Report an error when using type references as initializer values in var and const decls - Don't use empty exprs when reporting the wrong number of init values - Report when a forward type is not resolved - Report errors on zero sized ranges in normal arrays - Report errros on non-index type range specifiers in arrays - Don't print out code unit
This comment has been minimized.
This comment has been minimized.
|
I've added a test case to this issue that also takes into account the 17 failures encountered in this comment: #31407 (comment) . As of this writing all 18 of these literals still fail to parse with |
|
#86761 looks like it might fix these problems? |
Update Rust Float-Parsing Algorithms to use the Eisel-Lemire algorithm. # Summary Rust, although it implements a correct float parser, has major performance issues in float parsing. Even for common floats, the performance can be 3-10x [slower](https://arxiv.org/pdf/2101.11408.pdf) than external libraries such as [lexical](https://github.com/Alexhuszagh/rust-lexical) and [fast-float-rust](https://github.com/aldanor/fast-float-rust). Recently, major advances in float-parsing algorithms have been developed by Daniel Lemire, along with others, and implement a fast, performant, and correct float parser, with speeds up to 1200 MiB/s on Apple's M1 architecture for the [canada](https://github.com/lemire/simple_fastfloat_benchmark/blob/0e2b5d163d4074cc0bde2acdaae78546d6e5c5f1/data/canada.txt) dataset, 10x faster than Rust's 130 MiB/s. In addition, [edge-cases](rust-lang#85234) in Rust's [dec2flt](https://github.com/rust-lang/rust/tree/868c702d0c9a471a28fb55f0148eb1e3e8b1dcc5/library/core/src/num/dec2flt) algorithm can lead to over a 1600x slowdown relative to efficient algorithms. This is due to the use of Clinger's correct, but slow [AlgorithmM and Bellepheron](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.45.4152&rep=rep1&type=pdf), which have been improved by faster big-integer algorithms and the Eisel-Lemire algorithm, respectively. Finally, this algorithm provides substantial improvements in the number of floats the Rust core library can parse. Denormal floats with a large number of digits cannot be parsed, due to use of the `Big32x40`, which simply does not have enough digits to round a float correctly. Using a custom decimal class, with much simpler logic, we can parse all valid decimal strings of any digit count. ```rust // Issue in Rust's dec2fly. "2.47032822920623272088284396434110686182e-324".parse::<f64>(); // Err(ParseFloatError { kind: Invalid }) ``` # Solution This pull request implements the Eisel-Lemire algorithm, modified from [fast-float-rust](https://github.com/aldanor/fast-float-rust) (which is licensed under Apache 2.0/MIT), along with numerous modifications to make it more amenable to inclusion in the Rust core library. The following describes both features in fast-float-rust and improvements in fast-float-rust for inclusion in core. **Documentation** Extensive documentation has been added to ensure the code base may be maintained by others, which explains the algorithms as well as various associated constants and routines. For example, two seemingly magical constants include documentation to describe how they were derived as follows: ```rust // Round-to-even only happens for negative values of q // when q ≥ −4 in the 64-bit case and when q ≥ −17 in // the 32-bitcase. // // When q ≥ 0,we have that 5^q ≤ 2m+1. In the 64-bit case,we // have 5^q ≤ 2m+1 ≤ 2^54 or q ≤ 23. In the 32-bit case,we have // 5^q ≤ 2m+1 ≤ 2^25 or q ≤ 10. // // When q < 0, we have w ≥ (2m+1)×5^−q. We must have that w < 2^64 // so (2m+1)×5^−q < 2^64. We have that 2m+1 > 2^53 (64-bit case) // or 2m+1 > 2^24 (32-bit case). Hence,we must have 2^53×5^−q < 2^64 // (64-bit) and 2^24×5^−q < 2^64 (32-bit). Hence we have 5^−q < 2^11 // or q ≥ −4 (64-bit case) and 5^−q < 2^40 or q ≥ −17 (32-bitcase). // // Thus we have that we only need to round ties to even when // we have that q ∈ [−4,23](in the 64-bit case) or q∈[−17,10] // (in the 32-bit case). In both cases,the power of five(5^|q|) // fits in a 64-bit word. const MIN_EXPONENT_ROUND_TO_EVEN: i32; const MAX_EXPONENT_ROUND_TO_EVEN: i32; ``` This ensures maintainability of the code base. **Improvements for Disguised Fast-Path Cases** The fast path in float parsing algorithms attempts to use native, machine floats to represent both the significant digits and the exponent, which is only possible if both can be exactly represented without rounding. In practice, this means that the significant digits must be 53-bits or less and the then exponent must be in the range `[-22, 22]` (for an f64). This is similar to the existing dec2flt implementation. However, disguised fast-path cases exist, where there are few significant digits and an exponent above the valid range, such as `1.23e25`. In this case, powers-of-10 may be shifted from the exponent to the significant digits, discussed at length in rust-lang#85198. **Digit Parsing Improvements** Typically, integers are parsed from string 1-at-a-time, requiring unnecessary multiplications which can slow down parsing. An approach to parse 8 digits at a time using only 3 multiplications is described in length [here](https://johnnylee-sde.github.io/Fast-numeric-string-to-int/). This leads to significant performance improvements, and is implemented for both big and little-endian systems. **Unsafe Changes** Relative to fast-float-rust, this library makes less use of unsafe functionality and clearly documents it. This includes the refactoring and documentation of numerous unsafe methods undesirably marked as safe. The original code would look something like this, which is deceptively marked as safe for unsafe functionality. ```rust impl AsciiStr { #[inline] pub fn step_by(&mut self, n: usize) -> &mut Self { unsafe { self.ptr = self.ptr.add(n) }; self } } ... #[inline] fn parse_scientific(s: &mut AsciiStr<'_>) -> i64 { // the first character is 'e'/'E' and scientific mode is enabled let start = *s; s.step(); ... } ``` The new code clearly documents safety concerns, and does not mark unsafe functionality as safe, leading to better safety guarantees. ```rust impl AsciiStr { /// Advance the view by n, advancing it in-place to (n..). pub unsafe fn step_by(&mut self, n: usize) -> &mut Self { // SAFETY: same as step_by, safe as long n is less than the buffer length self.ptr = unsafe { self.ptr.add(n) }; self } } ... /// Parse the scientific notation component of a float. fn parse_scientific(s: &mut AsciiStr<'_>) -> i64 { let start = *s; // SAFETY: the first character is 'e'/'E' and scientific mode is enabled unsafe { s.step(); } ... } ``` This allows us to trivially demonstrate the new implementation of dec2flt is safe. **Inline Annotations Have Been Removed** In the previous implementation of dec2flt, inline annotations exist practically nowhere in the entire module. Therefore, these annotations have been removed, which mostly does not impact [performance](aldanor/fast-float-rust#15 (comment)). **Fixed Correctness Tests** Numerous compile errors in `src/etc/test-float-parse` were present, due to deprecation of `time.clock()`, as well as the crate dependencies with `rand`. The tests have therefore been reworked as a [crate](https://github.com/Alexhuszagh/rust/tree/master/src/etc/test-float-parse), and any errors in `runtests.py` have been patched. **Undefined Behavior** An implementation of `check_len` which relied on undefined behavior (in fast-float-rust) has been refactored, to ensure that the behavior is well-defined. The original code is as follows: ```rust #[inline] pub fn check_len(&self, n: usize) -> bool { unsafe { self.ptr.add(n) <= self.end } } ``` And the new implementation is as follows: ```rust /// Check if the slice at least `n` length. fn check_len(&self, n: usize) -> bool { n <= self.as_ref().len() } ``` Note that this has since been fixed in [fast-float-rust](aldanor/fast-float-rust#29). **Inferring Binary Exponents** Rather than explicitly store binary exponents, this new implementation infers them from the decimal exponent, reducing the amount of static storage required. This removes the requirement to store [611 i16s](https://github.com/rust-lang/rust/blob/868c702d0c9a471a28fb55f0148eb1e3e8b1dcc5/library/core/src/num/dec2flt/table.rs#L8). # Code Size The code size, for all optimizations, does not considerably change relative to before for stripped builds, however it is **significantly** smaller prior to stripping the resulting binaries. These binary sizes were calculated on x86_64-unknown-linux-gnu. **new** Using rustc version 1.55.0-dev. opt-level|size|size(stripped) |:-:|:-:|:-:| 0|400k|300K 1|396k|292K 2|392k|292K 3|392k|296K s|396k|292K z|396k|292K **old** Using rustc version 1.53.0-nightly. opt-level|size|size(stripped) |:-:|:-:|:-:| 0|3.2M|304K 1|3.2M|292K 2|3.1M|284K 3|3.1M|284K s|3.1M|284K z|3.1M|284K # Correctness The dec2flt implementation passes all of Rust's unittests and comprehensive float parsing tests, along with numerous other tests such as Nigel Toa's comprehensive float [tests](https://github.com/nigeltao/parse-number-fxx-test-data) and Hrvoje Abraham [strtod_tests](https://github.com/ahrvoje/numerics/blob/master/strtod/strtod_tests.toml). Therefore, it is unlikely that this algorithm will incorrectly round parsed floats. # Issues Addressed This will fix and close the following issues: - resolves rust-lang#85198 - resolves rust-lang#85214 - resolves rust-lang#85234 - fixes rust-lang#31407 - fixes rust-lang#31109 - fixes rust-lang#53015 - resolves rust-lang#68396 - closes aldanor/fast-float-rust#15
and others
That is, it returns
Err(..)on inputs with lots of digits and extreme exponents — it doesn't (shouldn't) panic.This is a limitation of the current code that has been known since that code was originally written, but is quite nontrivial to fix, so I didn't get around to it yet. Basically one would have to implement an algorithm similar to glib's strtod and replace the current slow paths (Algorithm M and possibly Algorithm R) with it. If someone wants to have a crack at it, go ahead, just give me a heads up so we don't duplicate work. See also #27307 for some discussion.
This bug doesn't affect reasonably short (17-ish decimal digits) representations of finite (even subnormal) floats, and neither does it affect most inputs that are rounded down to zero or rounded up to infinity. The only problem are very small exponents with so many integer digits that the number can't just be rounded down to zero and can't be represented with our custom 1280-bit bignums. One example, for
f64, is1234567890123456789012345678901234567890e-340(which is a finite and normal float, about1.23456789e-301). This would be annoying on its own, but it also trips up constant evaluation in the compiler (see #31109).Edit 2021-07-03: added test case:
The text was updated successfully, but these errors were encountered: