Skip to main content

Fusion, from first principles

the fusion engine

The front page claimed a fourteen-stage collection pipeline running ~36× past the fastest rival, on the same JVM, from the same source-code shape. This section is the full account: what the problem is, what compiling a pipeline buys, and each moving part of the machine, one concept at a time. Each emitted block is a golden test checked into the repo, and each number is a JMH measurement.

The problem, stated the way a profiler states it​

Every JVM collections pipeline (Scala collections, Java Streams, the wrapper libraries) pays some mix of three taxes:

  • Intermediates. Eager stages each allocate a collection that the next stage reads once and throws away. Three stages over 100k elements is two garbage arrays, and on primitives often two garbage arrays of boxes.

  • The lambda tax. Lazy views and streams fix the intermediates by threading elements through stored Function1s (Scala's function-object interface, like java.util.function.Function): an interface call per element per stage. One call site serving ≥3 lambda classes goes megamorphic and stops devirtualizing; on primitives, every crossing boxes. java.util.stream is the Java face of the same trade: it fuses your pipeline, but at runtime, by pushing each element through a chain of virtual Sink.accept calls, one per stage, with the same megamorphic fate in real code, and boxed outside the three primitive specializations. .fuse removes that chain at compile time, so the runtime sees one loop.

  • The JIT gamble. Escape analysis and inlining can sometimes claw both back, until the enclosing method grows past an inlining budget, a call site gets polluted, or one trailing virtual call silently turns escape analysis off. We measured that cliff at 35× on this very library before designing around it.

The fast code is known: a while loop over the backing array with the logic written inline. Writing it by hand trades away every abstraction collections provide.

The move: compile the pipeline​

Fusion makes the compiler write that loop. The stages you chain are inert markers; the terminal call at the end is a macro (code that runs inside the compiler and rewrites the typed syntax tree; javac has no counterpart at expression level, annotation processors only see declarations) that reads the entire chain off the typed syntax tree and emits the hand-written loop, with your lambdas spliced into the body, element types resolved, nothing boxed, and nothing allocated between stages:

you write

loading source…

the macro emits

loading source…

The output contains no Function1: _ + 1 became the add instruction in the loop body. The filter is an if wrapping everything downstream. There is one output array, sized once, and no trace of the pipeline objects themselves: the source lands in src0 as a bare reference.

Because this happens at compile time, none of it is a JIT bet. The specialization is in the bytecode: monomorphic, unboxed, allocation-free before the VM has compiled a single method. That is why a fused pipeline leads even measured cold, and why the lead persists when the enclosing method grows or a call site gets shared. The taxes are avoided in the emitted bytecode rather than optimized away at runtime.

The machine​

Everything in this section builds from five ideas, each with its own page, each depending only on the ones before it:

  • Sources: where elements come from. An in-memory FArray, a chunked stream pulled in constant memory, or raw bytes framed into records. A pipeline's source shape is part of its type.

  • Stages: the pipeline vocabulary. map, filter, collect, zip, and the clustered-data family are markers that cost nothing and compile to nothing but their spliced bodies.

  • Terminals: the call that ends the chain is the compiler invocation. Which terminals a pipeline has is decided per source shape by a typeclass (an interface implementation the compiler selects by type, like a ServiceLoader resolved at compile time), which is what makes the engine extensible.

  • The optimizer: the shared brain. Products are decomposed into columns, dead columns are never computed, and expensive columns are computed only for survivors.

  • The integration surface: a JSON decoder plugged in as a typeclass instance that beats jsoniter-scala's fastest idiom, showing the engine is not collection-specific. Using it with FArray and the benchmarks close the section.

The contract​

The purity rule is load-bearing

Fused stage lambdas must be pure. The optimizer reorders, sinks and deletes computations on that assumption, and nothing checks it: a logger or counter inside a fused stage compiles fine and is a semantic bug. Sharp edges spells out what can happen.

Four rules:

  • Stage lambdas are assumed pure. A fused pipeline is lazy and short-circuiting: under take, find, exists a stage function may run fewer times than in the strict List version, and a column read only after a filter is computed only for elements that pass. Pure functions produce identical results; side-effecting ones can observe the difference.

  • Element kinds are checked at compile time. Int/Long/ Double or a reference type; a primitive pipeline widened to Any is a compile error, never a silent deoptimization.

  • The chain must be written out at the call site. It's read off the syntax tree, not built at runtime; a pipeline assembled dynamically is a job for the eager ops. You can still factor out shared stages into an inline def and call it in the chain — it splices in and fuses exactly as if written in place, so reuse doesn't cost the fusion.

  • Unsupported means "does not compile". A terminal a source shape doesn't support is not a member of the pipeline's type; a stage the record path can't fuse is an error naming the stage. There is no fallback path that silently runs slow.