Back to Scala community Open

Scala DISCUSSION

Scala List vs Vector vs Seq: why is appending to a List in a loop so slow, and what should I use?

Started by btbx Scala List vs Vectorimmutable collections performanceappend complexitySeq defaultArrayBuffer
4 replies 248 views 5 participants
Latest activity · 30 Sep 2026

Scala List vs Vector vs Seq: why is appending to a List in a loop so slow, and what should I use?

btbx Scala Forum
#1

I collect parsed samples with var samples = List.empty[Double] and samples = samples :+ value in a loop, then read them back by index with samples(i). At 200,000 samples the program spends most of its time in these two operations. A colleague suggested Vector; the API documentation mostly talks about Seq.

What are the performance characteristics of these types, and which should be the default choice?

Community replies 4

Re: Scala List vs Vector vs Seq: why is appending to a List in a loop so slow, and what should I use?

#2

List is an immutable singly linked list. Prepending with :: and taking head or tail are constant time. Everything that involves the far end is linear: :+ has to copy the entire list to attach one element, and samples(i) walks i links. Appending 200,000 elements one at a time therefore copies about 200,000² / 2 = 20 billion cells in total, and indexed reads add a similar amount.

If you stay with a list, build it in reverse: prepend with value :: samples and call .reverse once at the end, which is a single linear pass.

Re: Scala List vs Vector vs Seq: why is appending to a List in a loop so slow, and what should I use?

#3

Vector is an immutable tree of small arrays with a branching factor of 32. Indexing, updating, appending and prepending all take a number of steps proportional to the depth of the tree, and the depth grows very slowly: 32 × 32 × 32 × 32 is 1,048,576, so a million elements are at most four levels deep. The documentation calls this effectively constant time.

That makes Vector a sound default for an immutable sequence that you index or append to. A List is still slightly faster for pure head-and-tail recursion and pattern matching with case head :: tail.

Re: Scala List vs Vector vs Seq: why is appending to a List in a loop so slow, and what should I use?

#4

Seq is a trait, not an implementation. It promises a defined order and nothing about speed. Seq(1, 2, 3) currently gives you a List, and IndexedSeq(1, 2, 3) gives a Vector. When a method takes a Seq parameter and then calls apply(i) or length in a loop, its cost depends entirely on what the caller passes in.

So declare what you need: accept IndexedSeq if the code indexes, accept Seq or Iterable if it only traverses with map, foreach or foldLeft, and avoid list.length or list.size inside loop conditions, since each call counts the whole list again.

Re: Scala List vs Vector vs Seq: why is appending to a List in a loop so slow, and what should I use?

#5

For building a collection inside a loop, a local mutable builder is normal Scala, not a style violation. val buf = scala.collection.mutable.ArrayBuffer.empty[Double], then buf += value (amortised constant time), and at the end buf.toVector or buf.toArray to hand out an immutable or fixed result. The mutation never escapes the method.

For numeric data specifically, Array[Double] is the most compact: it is a JVM double[] with 8 bytes per element, whereas List[Double] and Vector[Double] store boxed objects. When you compare alternatives, use a benchmarking harness such as JMH; timing a loop once with System.nanoTime mostly measures JIT warm-up.

TEP COMMUNITY