Why FArray
what FArray buys
The introduction led with fusion, FArray's headline trick, which has
its own section. This page is the plain library: no .fuse
anywhere, just eager FArray, and it already beats the field. Single ops tie a raw
array; chaining is where it pulls ahead, so that is what these benchmarks show, Int on the left and
String on the right.
The rivals throughout:
List— Scala's immutable linked list, notjava.util.ListVector— a persistent treeIArray— an immutable view of a raw arrayfs2.Chunk— the array-backed chunk from the fs2 streaming libraryzio.Chunk— the array-backed chunk from the ZIO streaming library
First the totals. Every size of every chained-operation benchmark class in the suite, eager FArray
only, no .fuse:
Three effects compound down a chain:
Boxing is paid per stage. A three-stage pipeline over boxed elements boxes at every crossing; chaining multiplies the tax rather than amortizing it. FArray's stages hand each other primitive arrays.
Structural stages cost nothing. A
take,droporreversein the middle of a chain is an O(1) lazy node for FArray and a full copy for every array-backed rival, a copy of data whose only purpose is to be consumed by the next stage.Big (calling) methods slow the rivals down. The array-backed collections run every lambda you pass to
map/filterthrough one shared, generic copy of that method. Pack several different lambdas into one method and the JIT can no longer keep that shared copy specialized, so it deoptimizes and slows down. FArray compiles each lambda into its own loop, so there is nothing shared to spoil. This is what turns a one-line benchmark tie into a loss in real code, detailed on the map page.
flatMap → filter → take
flatMap doubles the sequence, filter thins it, and take throws a chunk of it away. FArray's
take is an O(1) SliceNode, so it discards the tail for free — everyone else copies out what they
just finished building. With flat-leaf flatMap feeding an unboxed filter on top, eager FArray
runs this shape up to 22× past List and 6–10× past Vector and the Chunks, before a single
.fuse:
map → filter → fold
Transform, select, aggregate: the shape of half the collection code ever written. One boxed
crossing per stage for the field; int[] end to end for FArray:
take → drop → map → fold
Slice stages are FArray's freebie: a lazy window over the source, no copy. A map then transforms
through the window, and the fold reads straight out of the result:
filter → map → reverse
The mirror case: the structural stage last. FArray's reverse is a node pointing at the result;
everyone else allocates a third collection just to flip the second one:
flatMap → flatMap → map → fold
Chained expansion stresses what a library hands its next stage. Each FArray flatMap produces one
flat leaf, so the following stage reads a tight array rather than a fragment chain:
A long interleaved structural chain
The last chain alternates +:, :+, ++ (prepend, append, concat) and
reverse, forced by one final map. For FArray that's a string of O(1) nodes and a single O(n)
traversal; for array-copying structures it's a full copy per op:
No warmup lap
Every number above is steady-state, measured after the JIT has compiled the loop. FArray doesn't need that lap. Its unboxing and monomorphic reads are in the bytecode from compile time, not something the VM discovers at runtime, so it starts fast rather than warming up to fast. Measured cold — single-shot, zero warmup, the JVM still interpreting — eager FArray is already ahead of the whole field, before anything is compiled:
The whole suite, one number per structure
The charts above argue from selected benchmarks; this is the unselected version. Every operation at every size, boiled down per structure, losses included; the benchmarks page has every chart behind it.
There is one speed above this: handing the whole chain to the compiler. Fusion takes these same pipelines and emits a single loop; the 14-stage version runs ~15× past even FArray's own eager chains. The eager ops above are already the strongest field; fusion is the ceiling.