Skip to content

Improved Performance for Disguised Fast-Path Cases in Float Parsing #85198

Closed

Description

Summary

Rust's float-parsing algorithm dec2flt uses a slower parsing algorithm than necessary than required to parse numbers like "1.2345e30", which can slow down parsing times by nearly 300%. Adding trivial changes to dec2flt leads to dramatically improved parsing times, without increasing binary sizes, or slowing down other parse cases. Please see the "Sample Repository" below for the exact specifics, or in order to replicate these changes. This is an initial attempt as part of an ongoing effort to speed up float parsing in Rust, and aims to integrate algorithms I've implemented (currently used in nom and serde-json) back in the core library.

Issue

When parsing floating-point numbers, there is a fast-path algorithm that uses native floats to parse the float if applicable. This only occurs if:

  • The significant digits of the float, or mantissa, can be represented in mantissa_size+1 bits.
  • The exponent can be exactly represented, or the absolute value is less than ⌊(mantissa_size+1) / log2(5) ⌋.

Please note that this is the exponent relative to the significant digits, for example, for "1.2345e5", this exponent would be 1, but for "12345e5" this exponent would be 5.

The reason why we use mantissa_size+1 is due to the implicit, hidden bit of the float. A longer post detailing the attempts to improve float parsing on rust-internals can be found here. The exact values for f32 are as follows:

f32:

  • significant digit bits: 24
  • exponent range: [-10, 10]

f64:

  • significant digit bits: 53
  • exponent range: [-22, 22]

However, there is an exception: if the value has less significant bits than the maximum, but has an exponent larger than our range, we can shift powers-of-10 from the exponent to the significant digits. For example, "1.2345e30" would have significant digits of 12345 and an exponent of 26, which is outside our range of [-22, 22]. However, if we shift 10^4 from the exponent to the significant digits, we get significant digits of 123450000 and an exponent of 22, which is a valid fast-path case. This leads to a massive performance improvement with a large number of real-world float cases, and has an insignificant impact on other cases.

Binary Sizes

These were compiled on a target of x86_64-unknown-linux-gnu, running kernel version 5.11.16-100, on a Rust version of rustc 1.53.0-nightly (132b4e5d1 2021-04-13). The sizes reflect the binary sizes reported by ls -sh, both before and after running the strip command. The debug profile was used for opt-levels 0 and 1, and was as follows:

[profile.dev]
opt-level = "..."
debug = true
lto = false

The release profile was used for opt-levels 2, 3, s and z and was as follows:

[profile.release]
opt-level = "..."
debug = false
debug-assertions = false
lto = true

core

These are the binary sizes prior to making changes.

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

disguised

These are the binary sizes after making changes to speed up disguised fast-path cases.

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

Performance

Overall, the changes to speed up disguised fast-path cases led to ~-75% change in performance relative to core, without impacting any other benchmarks.

These benchmarks were run on an i7-6560U CPU @ 2.20GHz, on a target of x86_64-unknown-linux-gnu, running kernel version 5.11.16-100, on a Rust version of rustc 1.53.0-nightly (132b4e5d1 2021-04-13). The performance CPU governor was used for all benchmarks, and were run consecutively on A/C power with only tmux and Sublime Text open for all benchmarks. The floats that were parsed are as follows:

// Example fast-path value.
const FAST: &str = "1.2345e22";
// Example disguised fast-path value.
const DISGUISED: &str = "1.2345e30";
// Example moderate path value: clearly not halfway `1 << 53`.
const MODERATE: &str = "9007199254740992.0";
// Example exactly-halfway value `(1<<53) + 1`.
const HALFWAY: &str = "9007199254740993.0";
// Example large, near-halfway value.
const LARGE: &str = "8.988465674311580536566680e307";
// Example denormal, near-halfway value.
const DENORMAL: &str = "8.442911973260991817129021e-309";

core

These are the benchmarks prior to making changes.

float speed
fast 32.952ns
disguised 129.86ns
moderate 237.08ns
halfway 371.21ns
large 287.81us
denormal 122.36us

disguised

These are the benchmarks after making changes to speed up disguised fast-path cases.

float speed
fast 32.572ns
disguised 33.813ns
moderate 233.03ns
halfway 350.99ns
large 300.29us
denormal 129.36us

Correctness Concerns

None, since this merely transfer powers-of-10 from the exponent to the significant digits, using integer multiplication, and therefore can trivially be verified for correctness.

Changes

The diff, which would be relative to library/core/src/num, is as follows:

diff --git a/src/dec2flt/algorithm.rs b/src/dec2flt/algorithm.rs
index 2b0b4cb..76d8105 100644
--- a/src/dec2flt/algorithm.rs
+++ b/src/dec2flt/algorithm.rs
@@ -110,7 +110,7 @@ mod fpu_precision {
 ///
 /// This is extracted into a separate function so that it can be attempted before constructing
 /// a bignum.
-pub fn fast_path<T: RawFloat>(integral: &[u8], fractional: &[u8], e: i64) -> Option<T> {
+pub fn fast_path<T: RawFloat>(integral: &[u8], fractional: &[u8], mut e: i64) -> Option<T> {
     let num_digits = integral.len() + fractional.len();
     // log_10(f64::MAX_SIG) ~ 15.95. We compare the exact value to MAX_SIG near the end,
     // this is just a quick, cheap rejection (and also frees the rest of the code from
@@ -118,14 +118,29 @@ pub fn fast_path<T: RawFloat>(integral: &[u8], fractional: &[u8], e: i64) -> Opt
     if num_digits > 16 {
         return None;
     }
-    if e.abs() >= T::CEIL_LOG5_OF_MAX_SIG as i64 {
+    let max_exp = T::FLOOR_LOG5_OF_MAX_SIG as i64;
+    let min_exp = -max_exp;
+    let shift_exp = T::FLOOR_LOG10_OF_MAX_SIG as i64;
+    let disguised_exp = max_exp + shift_exp;
+    if e < min_exp || e > disguised_exp {
         return None;
     }
-    let f = num::from_str_unchecked(integral.iter().chain(fractional.iter()));
+    let mut f = num::from_str_unchecked(integral.iter().chain(fractional.iter()));
     if f > T::MAX_SIG {
         return None;
     }
 
+    // Handle a disguised fast path case here.
+    if e > max_exp {
+        let shift = e - max_exp;
+        let value = f.checked_mul(T::short_int_pow10(shift as usize))?;
+        if value > T::MAX_SIG {
+            return None;
+        }
+        f = value;
+        e = max_exp;
+    }
+
     // The fast path crucially depends on arithmetic being rounded to the correct number of bits
     // without any intermediate rounding. On x86 (without SSE or SSE2) this requires the precision
     // of the x87 FPU stack to be changed so that it directly rounds to 64/32 bit.
diff --git a/src/dec2flt/rawfp.rs b/src/dec2flt/rawfp.rs
index a3acf3d..15a5839 100644
--- a/src/dec2flt/rawfp.rs
+++ b/src/dec2flt/rawfp.rs
@@ -73,13 +73,21 @@ pub trait RawFloat:
     /// represented, the other code in this module makes sure to never let that happen.
     fn from_int(x: u64) -> Self;
 
+    fn short_int_pow10(e: usize) -> u64 {
+        table::SHORT_POWERS[e]
+    }
+
     /// Gets the value 10<sup>e</sup> from a pre-computed table.
-    /// Panics for `e >= CEIL_LOG5_OF_MAX_SIG`.
+    /// Panics for `e >= FLOOR_LOG5_OF_MAX_SIG`.
     fn short_fast_pow10(e: usize) -> Self;
 
     /// What the name says. It's easier to hard code than juggling intrinsics and
     /// hoping LLVM constant folds it.
-    const CEIL_LOG5_OF_MAX_SIG: i16;
+    const FLOOR_LOG5_OF_MAX_SIG: i16;
+
+    /// What the name says. It's easier to hard code than juggling intrinsics and
+    /// hoping LLVM constant folds it.
+    const FLOOR_LOG10_OF_MAX_SIG: i16;
 
     // A conservative bound on the decimal digits of inputs that can't produce overflow or zero or
     /// subnormals. Probably the decimal exponent of the maximum normal value, hence the name.
@@ -147,7 +155,8 @@ impl RawFloat for f32 {
 
     const SIG_BITS: u8 = 24;
     const EXP_BITS: u8 = 8;
-    const CEIL_LOG5_OF_MAX_SIG: i16 = 11;
+    const FLOOR_LOG5_OF_MAX_SIG: i16 = 10;
+    const FLOOR_LOG10_OF_MAX_SIG: i16 = 7;
     const MAX_NORMAL_DIGITS: usize = 35;
     const INF_CUTOFF: i64 = 40;
     const ZERO_CUTOFF: i64 = -48;
@@ -196,7 +205,8 @@ impl RawFloat for f64 {
 
     const SIG_BITS: u8 = 53;
     const EXP_BITS: u8 = 11;
-    const CEIL_LOG5_OF_MAX_SIG: i16 = 23;
+    const FLOOR_LOG5_OF_MAX_SIG: i16 = 22;
+    const FLOOR_LOG10_OF_MAX_SIG: i16 = 15;
     const MAX_NORMAL_DIGITS: usize = 305;
     const INF_CUTOFF: i64 = 310;
     const ZERO_CUTOFF: i64 = -326;
diff --git a/src/dec2flt/table.rs b/src/dec2flt/table.rs
index 97b497e..bd9e53d 100644
--- a/src/dec2flt/table.rs
+++ b/src/dec2flt/table.rs
@@ -1234,6 +1234,30 @@ pub static POWERS: ([u64; 611], [i16; 611]) = (
     ],
 );
 
+#[rustfmt::skip]
+pub const SHORT_POWERS: [u64; 20] = [
+    1,
+    10,
+    100,
+    1000,
+    10000,
+    100000,
+    1000000,
+    10000000,
+    100000000,
+    1000000000,
+    10000000000,
+    100000000000,
+    1000000000000,
+    10000000000000,
+    100000000000000,
+    1000000000000000,
+    10000000000000000,
+    100000000000000000,
+    1000000000000000000,
+    10000000000000000000,
+];
+
 #[rustfmt::skip]
 pub const F32_SHORT_POWERS: [f32; 11] = [
     1e0,

I'd be happy to submit a pull request with these changes, if they are satisfactory to you.

Sample Repository

I've created a simple, minimal repository tracking these changes on rust-dec2flt, which has a core branch that is identical to Rust's current implementation in the core library. The disguised branch contains the changes to improve parsing speeds for disguised fast-path cases. I will also, if there is interest, gradually be making changes for the moderate and slow-path algorithms.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Assignees

No one assigned

    Labels

    A-floating-pointArea: Floating point numbers and arithmeticC-enhancementCategory: An issue proposing an enhancement or a PR with one.T-libsRelevant to the library team, which will review and decide on the PR/issue.

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions