folly::reproducible_accumulator

Description

Guarantees bitwise-identical sums regardless of summation order, assuming IEEE 754 arithmetic. Based on the ReproBLAS algorithm by Ahrens, Nguyen, and Demmel (https://bebop.cs.berkeley.edu/reproblas/).

Accuracy: the error has two components (see error_bound()). The first grows as O(N * epsilon * max_abs_val), proportional to element count and the largest element magnitude — not the condition number. The second is O(epsilon * |sum|), independent of N. This is much more accurate than naive summation (whose error grows as O(N * epsilon * |sum|) and is sensitive to catastrophic cancellation), and comparable to Kahan summation in practice — though the asymptotic bound has an N-dependent term that Kahan lacks. The tradeoff is order-independence: unlike Kahan, the result is bitwise identical regardless of summation order.

Note: error_bound() uses a tighter formula based on the internal bin scale factor, which can be violated on highly ill-conditioned data (condition number >> 1). The O(N * epsilon * max_abs_val) bound above always holds.

Performance: operator+= (one-at-a-time) costs roughly 4x a naive FP add due to the serial dependency chain through Fold bin levels. The batch add(first, last) method uses multiple independent accumulators for instruction-level parallelism, reducing this to roughly 3x for inputs of 128 elements or more. For smaller inputs, add() falls back to the serial path to avoid accumulator merge overhead.

Cross-type conversion (e.g., between reproducible_accumulator<float> and reproducible_accumulator<double>) is intentionally not supported. The internal bin structures are incompatible across types, so any conversion must collapse the accumulator to a scalar, discarding the bin state. Use .value() to extract the scalar and construct/assign from that explicitly:

reproducible_accumulator<double> d = acc_float.value();