Scala Arrays and Buffers, in depth: ArrayBuffer growth, boxing, ArrayBuilder, ListBuffer aliasing and ArrayDeque

An array has a length fixed at allocation. Real programs rarely know their final size up front: they parse lines, collect results, batch requests. The usual answer in Scala is to accumulate into a growable buffer and, often, to freeze the result into an immutable collection or an array at the end. Which buffer you pick decides whether that loop is linear or quadratic, whether a million integers cost 4 MB or 20 MB, and whether a later mutation corrupts a list you already handed out.

This article covers the growable side of scala.collection.mutable: ArrayBuffer, ListBuffer, ArrayBuilder and ArrayDeque. Every structural claim was checked against the Scala 2.13 standard library source, which Scala 3 also uses. Arrays themselves, including ClassTag, ArrayOps and equality traps, have their own page, Scala Array, in depth; here they appear as the thing buffers are built on.

Arrays: the fixed layer underneath

On the JVM, Array[Int] is a Java int[]: one contiguous block of 4-byte values, no per-element object, fixed length, mutable in place. Array[String] is a block of references to separately allocated strings. That distinction, primitives stored inline versus references to boxed objects, is the single most important performance fact in this article, because the buffers differ in exactly this way.

Growing an array means allocating a larger one and copying. Doing that on every append makes n appends cost about n squared over two copies. Every buffer below avoids it the same way: keep spare capacity and grow geometrically, so the copying cost is spread across many cheap appends.

ArrayBuffer: how it grows

ArrayBuffer[A] is the default growable indexed sequence. Internally it holds a backing Array[AnyRef] and a size. new ArrayBuffer[A] and ArrayBuffer.empty allocate 16 slots. When an append would exceed capacity, the new length is max(target, max(length * 2, 16)), capped at the VM's maximum array size, and the old contents are copied over. Because capacity doubles, the total copying over n appends is below 2n element moves, so append is amortised O(1).

Concretely, appending 1,000,000 elements to an empty buffer resizes 16 times, from 16 up to 1,048,576 slots, and copies 1,048,560 references in total, about one extra move per element. If you know the size, call sizeHint(n) first, or build with ArrayBuffer.from on a collection with a known size, which allocates the right capacity once.

The operation table follows from the layout: indexed read and write O(1); append amortised O(1); insert, prepend and remove(i) shift the tail with Array.copy and are O(n - i), so removing from the front of a large buffer in a loop is quadratic. Two lifecycle details catch people. clear() sets the size to zero but keeps the backing array, which is ideal for a reused scratch buffer and a leak for a buffer that once held a million items; use clearAndShrink() or trimToSize() to release memory. And iterating while mutating is detected: ArrayBuffer counts mutations and its iterator goes through a checked view, so appending inside a for over the same buffer can throw ConcurrentModificationException.

Bulk and in-place operations

Buffers inherit a family of in-place operations from mutable.Buffer and mutable.IndexedSeq that avoid both per-element shifting and intermediate collections. They are the right tool whenever you are tempted to write an index loop that calls remove.

val buf = scala.collection.mutable.ArrayBuffer.from(1 to 1_000_000)

// Quadratic: each remove shifts the whole tail.
var i = 0
while (i < buf.length) if (buf(i) % 3 == 0) buf.remove(i) else i += 1

// Linear: one compaction pass, then one truncation.
buf.filterInPlace(_ % 3 != 0)

buf.mapInPlace(_ * 2)        // rewrite each slot, no new buffer
buf.sortInPlace()            // sorts the backing array
buf.dropInPlace(10)          // one shift of the remaining elements
buf.patchInPlace(0, Seq(-1, -2), 3)   // replace 3 elements with 2

filterInPlace walks the buffer once with a read index and a write index, copying survivors forward, and then truncates; that is O(n) however many elements it drops. Appending one ArrayBuffer to another with ++= resizes at most once and copies the source's backing array in a single Array.copy.

The boxing cost

Because the backing store is Array[AnyRef], an ArrayBuffer[Int] stores boxed java.lang.Integer objects. On a typical 64-bit JVM with compressed references, each slot is a 4-byte reference and each boxed integer is a 16-byte object. Small values from -128 to 127 come from a shared cache, but arbitrary values allocate. A million arbitrary ints therefore take about 4 MB of references plus 16 MB of boxes, around 20 MB and a million objects for the garbage collector to trace, against 4 MB and zero objects for an Array[Int]. Reading back unboxes on every access.

For object types this does not matter, because they are references anyway. For numeric accumulation it matters a great deal, and the answer is ArrayBuilder.

ArrayBuilder: growable arrays without boxing

ArrayBuilder[T] is a growable array whose only exit is result(): Array[T]. ArrayBuilder.make[T] uses the ClassTag to pick a specialised subclass: ArrayBuilder.ofInt grows a real int[], and there are matching classes for every primitive plus ofRef for objects. It reuses ArrayBuffer's growth rule, so appends are amortised O(1), and nothing is boxed as long as the static type is a primitive. Array.newBuilder[T] returns the same thing.

import scala.collection.mutable

// Parse one integer per line without boxing.
def readInts(lines: Iterator[String], expected: Int = 0): Array[Int] = {
  val b = new mutable.ArrayBuilder.ofInt
  if (expected > 0) b.sizeHint(expected)
  lines.foreach { line =>
    if (line.nonEmpty) b += line.trim.toInt   // stays a primitive int
  }
  b.result()                                  // trimmed copy of exactly the right length
}

// The tempting version boxes every element:
def readIntsBoxed(lines: Iterator[String]): Array[Int] = {
  val buf = mutable.ArrayBuffer.empty[Int]    // Array[AnyRef] inside
  lines.foreach(l => if (l.nonEmpty) buf += l.trim.toInt)
  buf.toArray                                 // unboxes into a new int[]
}

Both are linear. The second allocates one object per element and holds roughly five times the memory of the first. Use ArrayBuilder when the consumer wants an array, especially of primitives; use ArrayBuffer when you need to read and update elements while you are still adding them, which a builder does not offer.

ListBuffer: building lists, and the aliasing rule

ListBuffer[A] exists to build immutable Lists. It keeps a chain of cons cells with pointers to the first and last cell, so += is O(1) by linking a new last cell, and prepend is O(1) as well. Indexed access walks the chain and is O(i), as is remove(i). Do not use it as a general indexed buffer.

Its trick is toList: it returns the existing chain without copying, O(1), and marks the buffer aliased. If you mutate the buffer afterwards, the next mutation first copies all the cells, so the list you already returned is never changed. That makes the build-then-freeze pattern free, and it makes one pattern unexpectedly quadratic:

val lb = scala.collection.mutable.ListBuffer.empty[Event]

// Fine: build, then freeze once. toList is O(1).
events.foreach(lb += _)
val snapshot: List[Event] = lb.toList

// Quadratic: every toList aliases, so every following += copies all cells first.
events.foreach { e =>
  lb += e
  publish(lb.toList)     // n events -> about n*n/2 cell copies
}

The second loop is correct, just slow, which is why it survives code review. If you need a growing snapshot after every append, prepend to an immutable List and reverse at the end, or use an immutable Vector, whose appends share structure; see Scala Vector, in depth. For when an immutable list is the right destination at all, see Scala List.

ArrayDeque: both ends cheap

ArrayDeque[A] is a ring buffer: a backing array with start and end indices that wrap around. Appending and prepending are amortised O(1), removing from either end is O(1), and indexed reads stay O(1) because an index is just an offset from start modulo the capacity. In 2.13 mutable.Queue and mutable.Stack are both built on it.

Use it whenever you would otherwise call remove(0) on an ArrayBuffer: work queues, sliding windows, breadth-first search frontiers. removeHead() and removeLast() take an optional resizeInternalRepr flag that lets the deque shrink its backing array as it empties; by default it keeps capacity. Like ArrayBuffer, it stores references, so primitives are boxed.

Worked example: a rolling latency window

A log-processing job keeps the last 10,000 latency samples to report a rolling p99 and emits a sorted batch of request ids every minute. The first version used ArrayBuffer[Long] for the window, appending each sample and calling remove(0) once it was full, and a ListBuffer[String] for ids, publishing toList after each append so a dashboard could poll it.

At 5,000 requests per second it fell behind. Each remove(0) shifted 9,999 references: 50 million moves per second, plus a boxed Long for every sample. The id buffer copied its whole chain after every published snapshot. Three changes fixed it:

1. The window became a fixed ring over a primitive array, the same idea as ArrayDeque but unboxed: a long[] of 10,000 slots and a write index modulo 10,000. Each sample now costs one store; the p99 copies and sorts 10,000 longs once per report.
2. The id collection became an ArrayBuffer[String] that is cleared, not reallocated, each minute, so its capacity settles after the first busy minute; the dashboard reads a snapshot taken once per minute.
3. The final sorted batch is produced with toArray and sorted in place, avoiding an intermediate list.

The general lesson: buffers are cheap at their designed operation and expensive at everything else, so name the operations your loop performs before choosing one.

Choosing a buffer

Conversions copy unless documented otherwise. toArray, toList on an ArrayBuffer, toVector and to(ArraySeq) allocate new storage, which is what you want when freezing, because later mutations of the buffer cannot leak into the frozen value. Measure before replacing collections for speed; the method is in Scala collections performance.

Failure modes

• Front removal on ArrayBuffer: remove(0) in a loop is quadratic. Use ArrayDeque.
• Boxed numeric buffers: ArrayBuffer[Int] or ArrayBuffer[Double] holding millions of values, with GC pauses to match. Use ArrayBuilder or a primitive array.
• Snapshot-per-append on ListBuffer: each toList forces the next append to copy everything.
• Retained capacity: a long-lived buffer cleared with clear() after a spike keeps its peak backing array forever.
• Mutating while iterating: appending inside a traversal of the same buffer throws or misbehaves; collect changes separately and apply afterwards.
• Shared mutable buffers across threads: none of these classes is thread-safe. Confine each buffer to one thread, or hand off an immutable copy.
• Exposing the buffer: returning a mutable buffer from an API lets callers change your state; return toList, toVector or an immutable ArraySeq.

What to do next

1. Search your hot paths for ArrayBuffer[Int], ArrayBuffer[Long] and ArrayBuffer[Double]; replace those that only accumulate with ArrayBuilder.
2. Search for remove(0) and prepend on ArrayBuffer and switch those to ArrayDeque.
3. Call sizeHint wherever the final size is known or estimable.
4. Check every ListBuffer.toList for later mutation of the same buffer.
5. Audit long-lived buffers for clear() after peaks and use clearAndShrink() where memory matters.
6. Return immutable collections from public APIs and keep buffers local to a method or a single thread.
7. Benchmark the change with JMH on production-sized data before and after, and keep the benchmark in the repository.