Skip to main content

The unboxed builder

Sometimes you don't have the elements up front: you push them one at a time and want an FArray at the end. That's what a builder is for, and it's the one place the standard-library abstraction actively works against a primitive-first library: reusing scala.collection.mutable.Builder would box every primitive at the interface. So FArray has its own, FBuilder[A], and it beats even the specialized unboxed int[] builder from the standard library.

Why the standard builder boxes​

Builder[A, To] has one append entry point: def addOne(elem: A): this.type. A is an ordinary erased type parameter, so at the bytecode level the descriptor is addOne(Object). There is no addOne(int); there can't be, the trait (Scala's interface) is generic. So when you write b += anInt, the compiler must box the int to an Integer before the call, because the callee only accepts a reference:

b += 42
  ⇓  Integer.valueOf(42)      // allocation, at the call boundary
  ⇓  b.addOne(theInteger)     // box already made, and the builder can't undo it

Specialized builders like ArrayBuilder.ofInt store a real int[] internally, but they still inherit addOne(Object) from the trait, so held at the trait's static type (which is how any generic code holds them), every append still round-trips through a box and an unbox. The only escape is to hold the concrete ArrayBuilder.ofInt type so the overloaded addOne(Int) is picked statically, which is brittle, and impossible through a generic signature. It's the same wall that makes java.util.stream ship IntStream.builder() as its own type: a generic Stream.Builder<Integer> boxes.

The design: the same dispatch, for appends​

There's no new machinery here: it's exactly the inline, compile-time kind dispatch from map, pointed at an append instead of a transform. FBuilder[A] is an opaque type (a compile-time-only wrapper, erased at runtime) over a generated FBuilderBase whose concrete subclasses are the per-kind ${K}Group growable buffers that already back groupBy and collect. Only the hot append is kind-dispatched; everything else is a plain call on the base:

inline def += (elem: A): FBuilder[A] = { builderAddImpl[A](b, elem); b }
//                                        summonFrom[${K}Repr[A]] → IntGroup → store an int

Every other method (++=, result) is a plain virtual call on the base; none of them touch a primitive element type, so none can box. result() hands the internal buffer to a leaf under the house slack rules, with no defensive copy, and because appends only ever write past the end, that shared buffer is safe: result() can be called repeatedly while appending continues, and every snapshot stays valid (there's no clear(), the one op that could break it).

The API​

val b = FArray.newBuilder[Int](1024) // kind resolved HERE; capacity in ONE allocation
b += 1                     // inline, UNBOXED: an int straight into an int[]
b += 2
b ++= FArray(3, 4, 5)      // bulk: leaves arraycopy'd, trees materialized once
val fa = b.result()        // slack-wrap into a leaf, no defensive copy

Plus addOne/addAll aliases, length/knownSize/isEmpty/nonEmpty, and, for stdlib interop, b.asScala, a real mutable.Builder[A, FArray[A]] for Factory/to(...). That adapter is second-class by design: it's the boxing path, there so generic collection code can target FArray, not a fast path.

Beating the specialized int[] builder​

Every builder here grows from nothing: none is told the size up front, which is the whole reason you reach for a builder. Two things differ across the field, and both are real. The append: scala's ArrayBuilder held at its trait type boxes every int through addOne(Object); zio's ChunkBuilder.Int (from the ZIO streaming library) held concretely is genuinely unboxed; FBuilder's inline += is unboxed by construction. The finish: result() on the array builders trim-copies: ArrayBuilder.ofInt allocates a right-sized array and copies whenever the buffer isn't exactly full (the normal case, since it doubles), and zio's builder delegates to it. They have no choice: a raw int[] can't carry slack, its length is its count. FBuilder's result() is an O(1) slack-wrap: a leaf stores a logical length distinct from the array length, so no trim is needed. So part of the win over the array builders is a cheaper finish, not just a cheaper append, a property of FArray's representation. Every builder here finalizes to an immutable (ArrayBuffer, Scala's ArrayList, via toArray, like the rest), so the comparison is like-for-like end to end; the O(1)-slack-wrap-vs-O(n)-trim-copy gap is the whole story on refs, where nobody boxes.

measuring…

Pre-size when you know the count​

There is no sizeHint method; pass the count to the constructor instead: FArray.newBuilder[A](n) (or FBuilder[A](n)). The reason is one allocation, not two: a sizeHint called after construction would allocate the default 16-element array and immediately throw it away on the resize, whereas the ctor sizes the backing array once. When you don't know the count, the default doubling growth is the standard amortized-O(1) append.

The fair version of the sizeHint question is everyone pre-sized, each by its own idiomatic means (FArray via the ctor, the rest via sizeHint):

measuring…

Two builders can't meaningfully pre-size (Vector.newBuilder and List.newBuilder have sizeHint but it's a no-op for their structures), so they look the same as unsized; that's their structure, not a handicap. One caveat lives under the win: on the fill loop alone (reference elements), against a raw hand-written Object[] fill as the ceiling, ArrayBuffer reaches 0.95× while FBuilder reaches 0.84×. Both do the minimal work (one array, store-and-increment, plus a per-element capacity check), so the gap isn't the cast or an allocation (both ruled out by measurement); HotSpot compiles stdlib's ubiquitous addOne almost to a bare loop, and our leaner RefGroup.add doesn't get the same field-hoisting. It's more than repaid by the O(1) result() (ArrayBuffer pays O(n) to finalize), so the end-to-end number is a win.