Infer, Rather than Store, Binary Exponents when Float Parsing

[Alexhuszagh]

Issue

When float-parsing, precomputed powers-of-10, along with a binary exponent, are stored to scale the significant digits of an extended-precision (80-bit) floating-point type to the decimal exponent. The general appoach is as follows:

// Get our extended-precision float type from the significant digits and the decimal exponent.
let mantissa = "...";
let exp10 = "...";
let fp = Fp { f: mantissa, e: 0 };

// Get the scaling factor, so we can multiply the two.
let i = exp10 - table::MIN_E;
let sig = table::POWERS.0[i as usize];
let e = table::POWERS.1[i as usize];
let pow10 = Fp { sig, e };

// Multiply the two, then do float rounding.
let scaled = fp.mul(pow10);
...

However, the binary exponents (stored in table::POWERS.1) do not need to be explicitly stored, and there is no significant performance penalty for doing so. We can replace the above code with the following:

// Get our extended-precision float type from the significant digits and the decimal exponent.
let mantissa = "...";
let exp10 = "...";
let fp = Fp { f: mantissa, e: 0 };

// Get the scaling factor, so we can multiply the two.
let i = exp10 - table::MIN_E;
let sig = table::POWERS[i as usize];
let e = ((217706 * exp10 as i64) >> 16) - 63;
let pow10 = Fp { sig, e };

// Multiply the two, then do float rounding.
let scaled = fp.mul(pow10);
...

Related Work

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.

Binary Sizes

Overall, when compiling with opt-levels of s or z, binary sizes were ~4KB smaller than before.

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

infer

These are the binary sizes after making changes to infer the binary exponents.

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	244K

Performance

Overall, no significant change in performance was detected for any of the example floats.

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 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

infer

These are the benchmarks after making changes to infer the binary exponent.

float	speed
fast	31.753ns
disguised	124.73ns
moderate	229.22ns
halfway	319.39ns
large	266.29us
denormal	116.24us

Correctness Concerns

None, since the inferred exponents can be trivially shown using the Python code below to be identical to those stored in the dec2flt table. This only uses integer multiplication that cannot overflow, and a fixed shr of 16 bits.

Magic Number Generation

The code to generate the magic number to convert the decimal exponent to the binary exponent is as follows, which verifies the magic number is valid over the entire range.

import math

def get_range(max_exp, bitshift):
    den = 1 << bitshift
    num = int(math.ceil(math.log2(10) * den))
    for exp10 in range(0, max_exp):
        exp2_exact = int(math.log2(10**exp10))
        exp2_guess = num * exp10 // den
        if exp2_exact != exp2_guess:
            raise ValueError(f'{exp10}')
    return num, den

get_range(350, 16)    # (217706, 16)

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 infer branch contains the changes to infer the binary exponents rather than explicitly store them. I will also, if there is interest, gradually be making changes for the moderate and slow-path algorithms.