stillwater-sc / universal / 32099078201

85%

master: 84%

push

github

perf(floatcascade): merge the operands of add_cascades<4> instead of sorting them (#1340) (#1341)

* perf(floatcascade): merge the operands of add_cascades<4> instead of sorting them (#1340)

The two operands of a cascade addition are non-overlapping expansions already
in decreasing magnitude. add_cascades<4> bubble-sorted all eight components
anyway -- 28 comparisons on data that arrives sorted -- then accumulated them
smallest-first and emitted the two_sum errors as they fell out.

Merging the two sequences is linear, and a single two_sum chain over the merged
sequence is Shewchuk's fast_expansion_sum. Results are bit-identical to the
previous formulation over 40,000 random full-width additions and subtractions,
so this is a speed change and nothing else. Addition cost, i7-12700K -O3:

    gcc 13.3     69.6 -> 50.1 nsec/op     -28%
    clang 18.1   80.1 -> 83.0 nsec/op     +3.6%

The clang direction is the same compiler flip #1315 recorded for these
benchmarks generally. Three formulations of the merge -- branchy, branchless and
register-resident -- measured within 1 nsec of each other there, so nothing in
the merge explains it. Reported rather than tuned away.

The COMPRESS pass stays, and the assessment that motivated this change was wrong
about why it was there. It is not repairing sloppiness that a better addition
formulation avoids: the 2N -> N step needs a NONADJACENT expansion, not merely a
non-overlapping one. Feeding it the raw chain output costs a factor of three on
the composite identities -- sqrt(x)^2 - x goes from 0.42 to 1.61 ulps -- and
folding the compression into that step instead measured both slower and less
accurate. The redundant work was the sort, not the pass.

This adds a precondition the sort used to absorb: both operands must be
canonical cascades. Every caller builds its operands from cascade arithmetic or
by negating one componentwise, and both preserve the ordering. It is documented
at the function.

132/132 tests pass u... (continued)

27 of 27 new or added lines in 1 file covered. (100.0%)

43032 of 50377 relevant lines covered (85.42%)

6899612.9 hits per line