Folds, reduces and scans
A fold is the purest boxing benchmark there is: no output collection, no structural work, just one lambda applied per element into an accumulator. Whatever a library's per-element crossing costs, a fold is nothing but that crossing, a hundred thousand times. That makes this page the cleanest view of the thesis: FArray's unboxing lives in method signatures; competitors' depends on the JIT inlining their shared generic loop.
The microbenchmark that can't tell anyone apart
The lone-fold baseline frames everything after it. A lone fold is the case
every JIT handles: one call site, one lambda class, the shared generic foldLeft (Stream.reduce
with a seed) inlines and specializes, and everyone's loop ends up load-add-load-add. Measured that
way, FArray and a bare int[] (IArray, Scala's immutable view of one, in the charts) sit together
at the hardware ceiling, within 1% at every size, and that tie is the correct
result:
The tie does not hold once the fold sits in a real method.
The part that matters: folds in real methods
The same method-size effect as map, with a fold's
own twist. Competitors' primitive folds run unboxed because the JIT inlines the shared generic
foldLeft and specializes it; the lone-fold tie above is paid out of the method's inlining budget.
With several folds in one method the budget runs out and the shared fold collapses to its generic
boxed signature, one call site at a time — and unlike map, where nothing boxed, what boxes here is
the accumulator, threaded through every element. We measured the collapse beginning at four folds
per method on C2 and around twelve on Graal.
FArray's fold surface is a tiny call to a compiled-once leaf, not inlined, so the sixth fold in a method compiles exactly like the first. The benchmark runs six reference folds in one measured method, and the sweep shows the whole arc:
The pair of numbers is the summary: 1.00× alone, 3.5× embedded.
reduce, min, max, sum
The reduce family is fold with the seed taken from the data, and the aggregations are folds with a fixed combiner. Same machinery, same result:
scan: the op that taught us about loop shape
scanLeft emits every intermediate accumulator: a fold that writes its state out as it goes. It
also carries a measure-don't-assume scar: the first implementation carried the
accumulator through the output array (out(o) = op(out(o - 1), v)), which reads back a value
written one iteration ago, a store-to-load dependency on the loop's serial chain. That one shape
decision ran at 0.22–0.40× of a raw array. Moving the accumulator into a register local (the change
is two lines) made it 4×, to a dead tie with IArray. Nothing about dispatch, boxing, or the
tree: just where a loop-carried value lives.
For completeness, the family's remaining members are all the same machinery pointed differently:
foldRight and reduceRight run the backward driver (no reverse-then-fold copy; the ~3.4× in the
chart above is exactly that saved pass), and reduceOption/reduceLeftOption/reduceRightOption
are the empty-safe spellings, one branch in front of the same loop.
When the fold ends a chain,
fusing the chain folds without materializing any stage at all, and
agg runs several folds in one pass.