Fast Multi-Accumulator Reducers

Why Pair Reducers Are Slow

Clojure’s reduce, clojure.core.reducers/reduce, and transduce all accept reducing functions, which combine an accumulator with each element of a collection. For multi-accumulator reductions, the idiomatic approach is to pack several values into a vector pair. A typical mean reducer looks like this:

(defn mean
  "A reducer to find the mean of a collection. Accumulators are [sum count] pairs."
  ([] [0 0])
  ([[sum count]] (/ sum count))
  ([[sum count] x]
    [(+ sum x) (inc count)]))

This works with any of Clojure’s reduction primitives:

(require '[criterium.core :refer [quick-bench bench]] '[clojure.core.reducers :as r])
(def numbers (vec (range 1e7)))
(mean (reduce mean (mean) numbers))
; => 9999999/2

The problem is performance. Elapsed time for finding the mean of 10^7 integers with (mean) comes to about 1.17 seconds, or roughly 8.5 MHz. Profiling shows the bottleneck is not arithmetic but the accumulator representation:

About 42% of total runtime is spent destructuring vector pairs via nth and constructing them with LazilyPersistentVector.createOwning. Since Clojure vectors are not primitive, each sum and count is also boxed as a Long. The overhead of creating a fresh immutable accumulator per element dominates the reduction.

A Compile-Time Fix

The reducer macro from the dom-top library takes a different approach. Its syntax resembles loop: a binding vector of accumulators, a binding for each collection element, an iteration body that recurs, and an optional final form that transforms the accumulators into a result.

(require '[dom-top.core :refer [reducer]])
(def mean
  "A reducer to find the mean of a collection."
  (reducer [sum 0, count 0]    ; Starting with a sum of 0 and count of 0,
           [x]                 ; Take each element, x, and:
           (recur (+ sum x)    ; Compute a new sum
                  (inc count)) ; And count
           (/ sum count)))     ; Finally dividing sum by count

Under the hood, reducer dynamically compiles a dedicated accumulator class with one mutable field per accumulator variable. It reuses a compiled class across reductions of the same arity. The iteration form is rewritten so variable references become direct field accesses, bypassing vector allocation. Instead of returning a new accumulator instance each step, the reducing function mutates the existing object’s fields in place, which reduces garbage-collection pressure.

This alone shrinks the mean benchmark to roughly 65% of its original runtime.

Primitive Accumulator Fields

Because the accumulator class is generated, its fields can be primitive if you hint the types. For mean, hinting sum as double and count as long compiles primitive fields:

(def mean
  (reducer [^long sum   0, 
            ^long count 0]     
           [^long x]                 
           (recur (+ sum (long x)) (inc count))
           (/ sum count))) 

The standard reduce functions still hand the reducer an Object element, so each value must be unboxed on entry. What you save is boxing of the accumulator fields themselves across iterations. The primitive version runs 43% faster than the vector-pair reducer.

A primitive-aware reduction engine could avoid even the per-step element unboxing.

Early Termination

reducer also handles early return. If the iteration body does not recur, the reduction stops and skips the rest of the collection. For example, a mean limited to the first 1000 elements uses an if inside the loop:

(def mean
  (reducer [^long sum   0,
            ^long count 0
            :as acc] ; In the final form, call the accumulator `acc`
           [^long x]
           (if (= count 1000)
             (/ sum count)                  ; Early return
             (recur (+ sum x) (inc count))) ; Keep going
           (if (number? acc) ; Depending on whether we returned early...
             acc
             (let [[sum count] acc]
               (/ sum count)))))

Control passes to the final form regardless of how the reduction ended, so the shape of the accumulator may vary. Declare a single binding such as acc in the final form; it receives either the premature return value from the iteration body or a vector of all accumulators. Consistency with transduce is preserved in both paths.

In the Wild

reducer is part of dom-top, available on Clojars. It has been used for several months in Jepsen’s checkers to speed up anomaly detection over histories of database operations. Justin Conklin contributed to the bytecode generation and dynamic class loading required to make it work.