It’s hard to choose between Scala’s List and Vector.
On one hand, List is the most popular sequence. It is the default Seq, and most libraries including the Scala 3 compiler use it extensively. List is very fast in the usecases it is designed for, which are O(n) traversals, head/tail destructuring, and construction with prepend.
Vector is theoretically better than List. It adds O(1) length, O(1) access, O(1) update, and O(1) append methods. Vector is more complicated than List, which could affect its real-world performance. Of course, List is not so simple either.
Hypothesis: If Vector can match List’s performance in the common usecases, then we should prefer Vector.
Usecase 1: O(n) Traversals
Which is faster?
If you have one million elements, Vector can do this 4 milliseconds faster. Not a very significant difference. So, Vector meets our requirement for O(n) traversals.
Usecase 2: Construction with Prepend + Traversals
Of course, every collection needs to be constructed before being used. So lets look at construction followed by traversal.
If we construct using prepend, List wins.
List is 28 ms faster in the case of 1 million elements. Which is starting to get significant; don’t use Vector as a ‘functional Stack’.
Usecase 3: Construction with Append + Traversals
In-order construction with append is more common in everyday code. Lists are O(n) in this case so the only way to fairly compare is with their mutable builders:
Besides being faster than List’s builder, the Vector builder is about 20% faster than building a List with prepend. It’s also much faster than using :+ on Vector:
So use the builder when constructing a Vector item by item.
Do Views help?
Each filter and map create a new collection. Will using a view help?
Views are lazy, which makes debugging & resource safety harder. The performance difference on million-element collections is only a few milliseconds. So don’t use them unless you measure.
If you are using List like a functional Stack, keep using it.
Otherwise, Vector is just as fast and more flexible.
Results are using JDK 18 preview, Scala 3.1.1, Linux.