lexical

The lexical-write-integer benchmarks use several distinct data generation strategies to evaluate performance across different numeric distributions and complexities. These datasets are categorized into Random and JSON types:

Random Datasets

• Uniform: Numbers uniformly distributed over the entire range of the type.
• Simple: Small numbers with few digits (e.g., [0, 1000] or [0, 50] for u8).
• Large: Large numbers with many digits.
• Simple Negative: Small positive and negative numbers (e.g., [-1000, 1000]).
• Large Negative: Large negative numbers with many digits.

JSON Datasets

These use pre-computed values (often generated via NumPy) to simulate real-world JSON serialization workloads:

• Simple: Pre-computed simple values for various unsigned integer types (u8, u16, u32, u64) and a generic range.
• Random: Pre-computed uniformly random values for unsigned and signed integer types across all bit-widths.
• Chained Random: A hybrid approach that randomly switches between simple and random data using a PRNG. This is used to prevent branch prediction from skewing results in algorithms that might branch based on the number of digits.

The lexical-write-float package includes several benchmark datasets used to evaluate performance across different types of floating-point data. These datasets represent various distributions and complexities of numbers that a float-writing library must handle:

• JSON: Randomly-generated numbers sourced from a JSON document.
• Random Uniform: Uniformly, randomly-generated floats.
• Random Uniform32: Uniform, randomly-generated 32-bit integers treated as floats.
• Random Simple Int32: Randomly-generated floats that are simple 32-bit integers.
• Random Simple Int64: Randomly-generated floats that are simple 64-bit integers.
• Random 1/Rand32: Randomly-generated floats following the distribution of 1/u32(..), where u32 is uniformly distributed.
• Random BigInts: Randomly-generated floats consisting of three consecutive uniform 64-bit integers.
• Random BigInt.Int: Randomly-generated floats consisting of large integral and fractional components.

The lexical-parse-integer benchmarks evaluate parsing performance across different data distributions. These benchmarks are categorized into two main types:

Random Benchmarks

These use randomly-generated numbers to test various scenarios:

• Uniform: Numbers uniformly distributed over the entire range.
• Simple: Numbers with few digits (e.g., range [0, 1000] or [0, 50] for u8).
• Large: Numbers with many digits to test high-digit parsing.
• Simple Negative: Simple positive and negative numbers (e.g., range [-1000, 1000] or [-50, 50] for u8).
• Large Negative: Large negative numbers with many digits.

JSON Benchmarks

These use pre-computed values generated via NumPy to simulate structured data parsing. They include:

• Simple: Pre-computed simple values across various unsigned integer types (uint8, uint16, uint32, uint64) and standard Python integers.
• Random: Pre-computed uniformly random values across various unsigned and signed integer types (including int8 through int64 and large Python integers).

To maximize performance, lexical employs several optimizations during the digit parsing phase:

• Parsing Multiple Digits: Instead of parsing one digit at a time, lexical parses digits in blocks (e.g., 8 digits at once). It validates digits using bitmasks and normalizes them by subtracting 0x30. This reduces the number of multiplications required (e.g., parsing 8 digits takes 3 multiplies instead of 7).
• Overflow Checking: Rather than performing checked arithmetic in every loop iteration (which causes branching), lexical parses a known 'safe' number of digits (step) and checks for overflow only after the loop. If an overflow is detected, it performs a slower re-parse of the input.
• Power-of-Two Radices: If the radix is a power-of-two, intermediate rounding is avoided entirely. The only ambiguity occurs if the truncated digits are exactly at a halfway representation, which is resolved by rounding up if any truncated digits are non-zero.

The library uses the grade school multiplication algorithm rather than Karatsuba. While Karatsuba has a better asymptotic complexity ($O(N^{1.58})$ vs $O(N^2)$), grade school multiplication is faster for the small big-integers used in this project.

The algorithm iterates through the limbs of the multiplier y, performing a scalar multiplication (small_mul) for each limb and adding the result to the accumulator at the appropriate offset (large_add_from).

/// Grade-school multiplication algorithm.
pub fn long_mul(x: &[u64], y: &[u64]) -> StackVec {
    let mut z = StackVec::try_from(x).unwrap();
    if !y.is_empty() {
        let y0 = y[0];
        small_mul(&mut z, y0);

        for index in 1..y.len() {
            let yi = y[index];
            if yi != 0 {
                let mut zi = StackVec::try_from(x).unwrap();
                small_mul(&mut zi, yi);
                large_add_from(&mut z, &zi, index);
            }
        }
    }
    z
}

The lexical library uses different algorithms to handle the conversion of decimal strings to floating-point numbers, specifically focusing on accuracy near 'halfway' cases (where a string is equidistant between two representable floats).

Core Algorithms

• digit_comp (Default): The primary algorithm used by lexical-core. It is a high-performance approach using big-integer arithmetic. For positive exponents, it scales significant digits and rounds to the nearest float. For negative exponents, it compares the parsed ratio of the input string against the theoretical halfway point (b+h) to decide whether to round up or down. It is significantly faster than decimal-based approaches.
• byte_comp (Fallback): Used as the default algorithm if the radix is odd (since binary representations of odd-radix numbers may not terminate). It is also used as a fallback for lexical-core when the radix feature is enabled. It creates an exact representation of the halfway point and compares theoretical digits to the input string digits.
• Algorithm M: Represents significant digits as a fraction of arbitrary-precision integers (e.g., 1.23 becomes 123/100). It scales the numerator and denominator by powers of 2 until the quotient is in the range [2^52, 2^53) to generate the mantissa. While accurate, it is generally slower than digit_comp or byte_comp.
• decimal: A representation that uses a fixed number of bytes for significant digits (one byte per digit). While faster than Algorithm M, it is much slower than digit_comp or byte_comp for most input sizes.

The Digits struct is a generic iterator designed to resolve format-specific branching at compile time. It is optimized to be as efficient as a standard slice iterator while providing advantages for partial parsing and error handling.

Key Features

• Index Tracking: The index is explicitly stored, making it easy to identify the exact position for error handling without pointer arithmetic.
• Peek/Next Pattern: Implements efficient peek/next algorithms by peeking and then incrementing the index.
• Skip Conditions: The iterator uses four skip conditions to handle different separator rules:
  • [L]: Leading
  • [I]: Internal
  • [T]: Trailing
  • [C]: Consecutive

For example, a peek_iltc operation skips internal, leading, trailing, and consecutive digit separators.

Component-Based Design

To ensure correct rules are applied to different parts of a number (integral, fractional, and exponential), Digits is composed of specialized iterators rather than being a single monolithic iterator:

• integer_iter
• fraction_iter
• exponent_iter
• special_iter

If no digits are skipped for a component, the library enables optimizations for 'no-skip' iterators, allowing multiple digits to be parsed simultaneously using fewer multiplication instructions.

pub struct Digits<'a> {
    slc: &'a [u8],
    index: usize,
}