stillwater-sc / universal / 32074964540

85%

master: 84%

Build Type

push

github

Committed by web-flow

Commit Message

perf(utility): make decimal string parsing 12-58x faster (#1319) (#1336)

* test(utility): validate decimal parsing against exact integer arithmetic

Preparation for universal#1319. Parsing is about to be optimized, and
optimizing a converter without an exact reference is how a rounding change
ships as a speedup.

test_decimal_to_binary.cpp checks this machinery against std::stod, which caps
verification at 53 bits: it can say a double came out right and nothing at all
about the 106, 159 and 212-bit results the multi-component types ask for.

The reference here is the decimal string's own exact value in integer
arithmetic, so it is correct at any precision and shares no code with the
converter - including its own hand-written scanner, since an oracle that
shares a front end cannot detect a fault in that front end.

The comparison carries no rounding. A parsed value is a sum of doubles, so it
is a dyadic rational; a decimal string is M * 10^E, which is dyadic only for
E >= 0 because 10^E = 2^E * 5^E. For negative E both sides are scaled by
5^|E|, which preserves the inequality and leaves every term dyadic:

    |D - M*10^E| <= tol * |M*10^E|
    |D*5^|E| - M*2^E| <= tol * |M*2^E|

One thing the oracle had to learn, after three large-negative-exponent vectors
flagged and an independent check showed the converter was right: the budget is
not the nominal 53*N bits. Near the bottom of the exponent range a trailing
component would need an exponent below 2^-1022 and becomes subnormal, so
parsing 1e-300 into a double-double yields about 78 bits rather than 106 no
matter how good the converter is. representable_bits() computes the budget
from the leading component's exponent, which is a property of the format worth
having written down.

Mutation-tested, because a suite that only ever passes proves nothing:
asking for 20 fewer mantissa bits fails 18 cases on the cascade types, and
dropping one decimal digit in the shared converter fails 16 cases on all five.
Th... (continued)

Coverage Stats

79 of 80 new or added lines in 1 file covered. (98.75%)

9 existing lines in 2 files now uncovered.

42790 of 50070 relevant lines covered (85.46%)

6941874.57 hits per line