Scala Vector, in depth: the radix-balanced tree, index arithmetic, path copying, prefix and suffix arrays, builders and benchmarks

What Vector promises

The library's own header comment describes Vector as providing random access and updates in O(log n) time, and very fast append, prepend, tail and init: amortized O(1), worst case O(log n). The logarithm has base 32, because every internal node is an array of 32 references. That base changes the practical meaning of O(log n). A vector of a thousand elements is two levels deep; a million is four; the maximum size, a little over two billion, is six. In practice the depth is a small constant and each level is one array read.

The boundaries are approximate because of the prefix and suffix arrays described below, which can hold some elements outside the main tree. Every class except Vector0 and Vector1 extends an internal BigVector base. You never name these classes in your code; the factory and every operation pick the right one.

From an index to a path

Because every node has 32 slots, an index can be read as a sequence of 5-bit digits. In a two-level tree, bits 9 to 5 choose a slot in the root and bits 4 to 0 choose an element in the leaf. Index 40 is 00001 01000 in binary, so it lives in root slot 1, leaf slot 8. No comparisons and no searching are involved; each level is a shift, a mask and an array load. The model below is a simplified radix tree, not the library source, but it is exactly the arithmetic Vector uses inside its main data tree.

// A simplified radix tree: every level is a 32-slot array. Not the library code.
final class RadixVec[A](root: Array[AnyRef], depth: Int, val size: Int) {
  private final val Bits = 5
  private final val Mask = 31

  def apply(i: Int): A = {
    require(0 <= i && i < size)
    var node  = root
    var level = depth - 1
    while (level > 0) {                       // walk interior levels
      node = node((i >>> (Bits * level)) & Mask).asInstanceOf[Array[AnyRef]]
      level -= 1
    }
    node(i & Mask).asInstanceOf[A]            // leaf slot
  }
}

Updates are path copies

An immutable update cannot change an array that another version might be reading. Instead it copies the arrays along the path to the element, changes the copies, and returns a new root. Every array not on the path is shared. For a million-element vector that is four arrays of 32 references, about 128 references copied, regardless of the size of the vector. The old vector is still valid and still sees the old value.

// Path copying, same simplified model: copy each array on the way down.
def updated(node: Array[AnyRef], level: Int, i: Int, x: AnyRef): Array[AnyRef] = {
  val copy = node.clone()
  val slot = (i >>> (5 * level)) & 31
  if (level == 0) copy(slot) = x
  else copy(slot) = updated(node(slot).asInstanceOf[Array[AnyRef]], level - 1, i, x)
  copy
}

This is cheap compared with copying a whole array, but it is not free: a loop that calls updated once per element of a large vector allocates four small arrays per call and produces a lot of short-lived garbage. If you are going to change many elements in one step, map, a builder or a temporary mutable array followed by one conversion is much faster.

Prefix and suffix arrays: why the ends are cheap

If append had to walk the tree and copy a path each time, it would cost the same as an update. Vector avoids that with two extra arrays held directly by the vector object: a prefix at the front and a suffix at the back, each of up to 32 elements, around the main tree. The source comments state the invariants: the prefix and suffix at the first level are never empty, and balancing does not cross the main data array, so prepending never touches the suffix and appending never touches the prefix.

Appending one element copies only the suffix array, at most 32 references, plus the small vector object. When the suffix is full, it is pushed into the tree as a complete leaf and a new one-element suffix starts; that push is the occasional O(log n) step behind the amortized O(1). When the tree itself is full at its current depth, the vector moves up a class, for example from Vector2 to Vector3. Prepending works symmetrically on the prefix. Because the ends live outside the tree, head, last, tail and init are all fast, which makes Vector a reasonable immutable double-ended queue.

There is a cost hidden in amortized O(1): each :+ still copies the current suffix, on average around 16 references. That is fine for occasional appends and wasteful in a tight loop that builds a large vector one element at a time.

Builders, concatenation and slicing

To build a vector from many elements, use a builder. Vector.newBuilder returns a VectorBuilder that fills mutable arrays level by level and freezes them into a vector at the end, with no per-element copying. Conversions such as iterator.to(Vector) and Vector.from(...) use the same machinery.

// Slow: a new suffix copy and vector object per element
var v = Vector.empty[Int]
for (i <- 0 until 1_000_000) v = v :+ i

// Fast: one builder, arrays filled in place, frozen once
val b = Vector.newBuilder[Int]
b.sizeHint(1_000_000)
for (i <- 0 until 1_000_000) b += i
val v2 = b.result()

// Also fast, and usually clearest
val v3 = Vector.tabulate(1_000_000)(identity)

Concatenation with ++ is where Vector differs from some other persistent vectors. Scala's Vector is not a relaxed radix-balanced tree, so two large vectors cannot be joined by linking their trees. The implementation appends small right-hand sides element by element and uses a builder that is aligned to the left vector for larger ones, so the cost depends on the shape of the operands: appending a chunk to a large vector shares the left side's interior and costs roughly the size of the chunk, but a join that breaks alignment, such as gluing two halves back together around a deleted element, has to copy one side element by element. It is never the logarithmic join of a relaxed radix-balanced vector, so loops of misaligned joins can go quadratic; collect the parts and build once.

Slicing with take, drop and slice goes through an internal slice builder that reuses whole interior arrays where they line up and copies only the partial arrays at the edges. Slices are cheap relative to their length and they share memory with the original vector, which also means a small slice can keep a larger structure's arrays alive.

Vector against the alternatives

The pattern is simple. List wins when you only push and pop at the front and pattern-match on head and tail. ArraySeq wins when the sequence is built once and then only read, especially for primitives. Vector wins when you need indexed access and modification while keeping immutability. Scala collections performance has the full cost tables for the library.

Boxing and memory

Vector stores elements in arrays of object references. A Vector[Int] therefore boxes every integer: each element is a reference to an Integer object, apart from small values that the JVM caches. A million integers cost the leaves' 4 to 8 MB of references plus the boxes themselves, several times the 4 MB of a plain Array[Int], and reading them adds a pointer dereference that the CPU cannot always prefetch. The tree overhead itself is small, about one array header per 32 elements.

For numeric work, use Array[Int] inside a function and expose an immutable ArraySeq, which wraps a primitive array without boxing. Keep Vector for collections of objects, where the references are needed anyway.

Measuring it with JMH

Micro-benchmarks on the JVM lie unless the harness handles warm-up, dead code elimination and forking. Use JMH through the sbt-jmh plugin and compare the operations you actually perform, at the sizes you actually have.

// project/plugins.sbt: addSbtPlugin("pl.project13.scala" % "sbt-jmh" % "<current version>")
// build.sbt: enablePlugins(JmhPlugin)
import org.openjdk.jmh.annotations._
import java.util.concurrent.TimeUnit

@State(Scope.Benchmark)
@BenchmarkMode(Array(Mode.AverageTime))
@OutputTimeUnit(TimeUnit.NANOSECONDS)
class VectorBench {
  @Param(Array("1000", "1000000")) var size: Int = _
  var vec: Vector[String] = _
  var arr: Array[String]  = _
  var idx: Array[Int]     = _

  @Setup def setup(): Unit = {
    vec = Vector.tabulate(size)(_.toString)
    arr = vec.toArray
    idx = Array.fill(1024)(scala.util.Random.nextInt(size))
  }

  @Benchmark def vectorRandomRead(): Int = { var s = 0; for (i <- idx) s += vec(i).length; s }
  @Benchmark def arrayRandomRead(): Int  = { var s = 0; for (i <- idx) s += arr(i).length; s }
  @Benchmark def vectorUpdate(): Vector[String] = vec.updated(idx(0), "x")
}
// run: sbt "Jmh/run -i 5 -wi 5 -f 2 .*VectorBench.*"

Return results or consume them, as the methods above do, so the JIT cannot delete the work. Expect Vector reads to be a small multiple of array reads at large sizes, mostly from cache misses on the extra levels, and expect updates to be dominated by allocation. If the difference matters to you, it will show up here before it shows up in production.

Worked example: an undo history

A document editor keeps its paragraphs as a Vector[Paragraph] and its undo history as a list of earlier vectors. Each edit replaces one paragraph with updated, appends with :+ or removes with a slice and a concatenation. A 5,000-paragraph document is three levels deep, so an edit copies three arrays of 32 references; 500 undo steps keep 500 versions alive while sharing almost all of their arrays. Memory grows by roughly the copied paths per edit, not by a full copy of the document, which is what makes unlimited undo affordable.

One operation in the editor needed care. Deleting a paragraph in the middle was written as v.take(i) ++ v.drop(i + 1), which is linear because of the concatenation. That is acceptable at 5,000 paragraphs and an edit per keystroke, but the same code in a batch import that deleted thousands of paragraphs in a loop became quadratic. The import was rewritten to compute the surviving paragraphs with one filter and build the vector once.

Failure modes

• Building a large vector with :+ or ++ in a loop: use a builder, tabulate or to(Vector).
• Treating ++ as logarithmic: it can copy most of one operand, so loops of misaligned joins such as repeated middle deletions go quadratic.
• Calling updated once per element to transform a whole vector: use map or an array, then convert once.
• Using Vector[Int] or Vector[Double] for large numeric data: the boxes cost memory and cache misses; use ArraySeq over a primitive array.
• Keeping a small slice of a huge vector: the slice can retain arrays of the original; copy it with Vector.from if the original should be collected.
• Comparing or hashing large vectors on a hot path: equality and hashCode visit every element.

What to do next

1. Search your code for :+ and ++ inside loops and replace them with builders or a single to(Vector).
2. Check numeric collections for boxing and switch large ones to arrays or ArraySeq.
3. Pick List, Vector or ArraySeq per use from the table above, not by habit, and write down why.
4. Add the JMH benchmark above to your build, with your element type and sizes, and run it before arguing about performance.
5. Read the header comment and the updated and appended methods in scala/collection/immutable/Vector.scala for the real prefix and suffix handling.
6. Practise with the fold, map and filter patterns that build vectors in one pass.