An independent set of benchmarks for testing common Scala idioms.

• Functional Programming
  • Folding
  • Chained Higher-Order Functions
  • Concatenation
• Mutable Data
  • List, IList and Array
  • Builder Classes
  • Mutable Set and Java’s ConcurrentHashMap
• Pattern Matching
  • Deconstructing Containers
  • Guard Patterns

We often want to collapse a collection into some summary of its elements.
This is known as a fold, a reduce, or a catamorphism:

List(1,2,3).foldLeft(0)(_ + _)  // 6

How fast is this operation in the face of the JVM’s while and mutable
variables? For instance the familiar, manual, and error-prone:

var n: Int = 0
var i: Int = coll.length - 1

while (i >= 0) {
  n += coll(i)
  i -= 1
}

FoldBench compares List, scalaz.IList, Vector, Array, Stream, and
Iterator for their speeds in various fold operations over Ints.
FoldClassBench tries these same operations over a simple wrapping class to see
how boxing/references affect things.

Int Results:

All times are in microseconds. Entries marked with an asterisk are sped up by
optimization flags. Entries marked with two are slowed down by them.

Pair Class Results:

All times are in microseconds.

Observations:

• foldLeft is always better than both foldRight and manual tail recursion for
  catamorphisms (reduction to a single value).
• sum should be avoided.
• Iterator benefits from while, but not enough to beat List.
• Collections with random access (especially Array) benefit from while
  loops.
• Array has no advantage over List when holding non-primitive types!

Recommendation:

List.foldLeft is concise and performant for both primitive and boxed types.
If you were already dealing with an Array[Int] or likewise, then a while
loop will be faster.

It’s common to string together multiple operations over a collection, say:

List(1,2,3,4).map(foo).filter(pred).map(bar)

which is certainly shorter and cleaner in its intent than manually manipulating
a mutable collection in a while loop. Are higher-order operations like these
still fast? People used to Haskell’s list fusion might point out that these
operations typically don’t fuse in Scala, meaning that each chained operation
fully iterates over the entire collection and allocates a new copy. Stream and
Iterator are supposed to be the exceptions, however.

Stream in particular is what people wanting Haskell’s lazy lists may reach for
first, on the claim that the elements memoize, chained operations fuse, and they
support infinite streams of values. Let’s see how everything performs.

StreamBench performs the following operations on List, scalaz.IList,
Vector, Array, Stream, scalaz.EphemeralStream and Iterator. We test:

• Head: map-filter-map-head. Which collections “short-circuit”, only
  fully processing the head and nothing else?
• Max: map-filter-map-max. How quickly can each collection fully process itself?
  Does fusion occur (esp. with Stream)?
• Reverse: reverse-head. Can any of the collections “cheat” and grab the last
  element quickly?
• Sort: map-filter-map-sorted-head. Does Stream still leverage laziness with
  a “mangling” operation like sort?

Results:

All times are in microseconds.

Observations:

• Stream won’t do work it doesn’t have to, as advertised (re: Head).
• Stream is very slow to fully evaluate, implying no operation fusion.
  Nothing clever happens with sorting.
• Iterator overall is the fastest collection to chain higher-order
  functions.
• List has the fastest reverse.

Recommendation:

If you want to chain higher-order operations in Scala, use an Iterator.
If you have something like a List instead, create an Iterator first
with .iterator before you chain.

Sometimes we need to merge two instances of a container together, end-to-end.
This is embodied by the classic operator ++, available for all the major
collection types.

We know that the collection types are implemented differently. Are some better
than others when it comes to ++? For instance, we might imagine that the
singly-linked List type would be quite bad at this. The lazy Stream types
should be instantaneous.

ConcatBench tests List, scalaz.IList, Array, Vector, Stream, and
scalaz.EphemeralStream for their performance with the ++ operator. Two
results are offered for Array: one with Int and one for a simple Pair
class, to see if primitive Arrays can somehow be optimized here by the JVM, as
they usually are. Otherwise, the results are all for collections of Int.

All times are in microseconds.

Observations:

• The Stream types were instantaneous, as expected.
• Array is quick! Somehow quicker for classes, though.
• The drastic slowdown for Array at the millions-of-elements scale is strange.
• IList beats List until millions-of-elements scale.
• Vector has no advantage here, despite rumours to the contrary.

Recommendation:

If your algorithm requires concatenation of large collections, use Array.
If you’re worried about passing a mutable collection around your API, consider
scalaz.ImmutableArray, a simple wrapper that prevents careless misuse.

Above we saw that List performs strongly against Array when it comes to
chaining multiple higher-order functions together. What happens when we just
need to make a single transformation pass over our collection – in other words,
a .map? Array with a while loop is supposed to be the fastest iterating
operation on the JVM. Can List and IList still stand up to it?

MapBench compares these operations over increasing larger collection sizes of
both Int and a simple wrapper class.

Results:

All times are in microseconds.

Observations:

• For List, there isn’t too much difference between Ints and classes.
• Array is fast to do a single-pass iteration.

Recommendation:

If your code involves Array, primitives, and simple single-pass
transformations, then while loops will be fast for you. Otherwise, your code
will be cleaner and comparitively performant if you stick to immutable
collections and chained higher-order functions.

You want to build up a new collection, perhaps iterating over an existing one,
perhaps from some live, dynamic process. For whatever reason .map and
.foldLeft are not an option. Which collection is best for this? VectorBench
tests how fast each of List, scalaz.IList, ListBuffer, Vector,
VectorBuilder, Array, ArrayBuilder, and IndexedSeq can create themselves
and accumulate values. For List, this is done with tail recursion. For
IndexedSeq, this is done via a naive for-comprehension. For all others, this
is done with while loops. The Buffer and Builder classes perform a
.result call at the end of iterating to take their non-builder forms (i.e.
VectorBuilder => Vector). ArrayBuilder is given an overshot size hint (with
.sizeHint) in order to realistically minimize inner Array copying.

Results:

All times are in microseconds.

Observations:

• For primitives, Array is king.
• Avoid appending to immutable Vectors.
• Avoid repeated use of ListBuffer.prepend! Your runtime will slow by an order of magnitude vs +=:.
• For classes, at small scales (~1000 elements) there is mostly no difference between
  the various approaches.
• ArrayBuilder can be useful if you’re able to ballpark what the final result size will be.
• VectorBuilder fulfills the promise of Builders, but can only append to the right.
  You’d have to deal with the fact that your elements are reversed.

Recommendation:

The best choice here depends on what your next step is.

If you plan to perform while -based numeric calculations over primitives only,
stick to Array. If using ArrayBuilder with primitives, avoid the .make
method. Use something like .ofInt instead. Also make sure that you use
.sizeHint to avoid redundant inner Array copying as your collection grows.
Failing to do so can introduce a 5x slowdown.

Otherwise, consider whether your algorithm can’t be reexpressed entirely in
terms of Iterator. This will always give the best performance for subsequent
chained, higher-order functions.

If the algorithm can’t be expressed in terms of Iterator from the get-go, try
building your collection with VectorBuilder, call .iterator once filled,
then continue.

You’d like to build up a unique set of values and for some reason calling
.toSet on your original collection isn’t enough. Perhaps you don’t have an
original collection. Scala’s collections have been criticized for their
performance, with one famous complaint saying how their team had to fallback to
using Java collection types entirely because the Scala ones couldn’t compare
(that was for Scala 2.8, mind you).

Is this true? UniquesBench compares both of Scala’s mutable and immutable
Set types with Java’s ConcurrentHashMap to see which can accumulate unique
values faster.

Results:

All values are in microseconds.

Note: About half the time the 10000-value benchmark for mutable.Set
optimizes down to ~600us instead of the ~800us shown in the chart.

Observations:

• mutable.Set is fastest at least for small amounts of data, and might be
  fastest at scale.
• immutable.Set is slower and has worse growth, as expected.

Recommendation:

First consider whether your algorithm can’t be rewritten in terms of the usual
FP idioms, followed by a .toSet call to make the collection unique.

If that isn’t possible, then trust in the performance of native Scala
collections and use mutable.Set.

It’s common to decontruct containers like this in recursive algorithms:

def safeHead[A](s: Seq[A]): Option[A] = s match {
  case Seq() => None
  case h +: _ => Some(h)
}

But List and Stream have special “cons” operators, namely :: and #::
respectively. The List version of the above looks like:

def safeHead[A](l: List[A]): Option[A] = l match {
  case Nil => None
  case h :: _ => Some(h)
}

How do these operators compare? Also, is it any slower to do it this way than a
more Java-like:

def safeHead[A](l: List[A]): Option[A] =
  if (l.isEmpty) None else l.head

The MatchContainersBench benchmarks use a tail-recursive algorithm to find the
last element of each of List, scalaz.IList, Vector, Array, Seq, and
Stream.

Results:

All times are in microseconds.

Observations:

• Canonical List and IList matching is fast.
• Seq matching with +:, its canonical operator, is ironically slow.
• Pattern matching with +: should be avoided in general.
• if is generally faster than pattern matching, but the code isn’t as nice.
• Avoid recursion with Vector and Array!
• Array.tail is pure evil. Each call incurs ArrayOps wrapping and
  seems to reallocate the entire Array. Vector.tail incurs a similar
  slowdown, but not as drasticly.

Recommendation:

Recursion involving containers should be done with List and pattern matching
for the best balance of speed and simplicity. If you can take scalaz as a
dependency, its IList will be even faster.

It can sometimes be cleaner to check multiple Boolean conditions using a match:

def foo(i: Int): Whatever = i match {
  case _ if bar(i) => ???
  case _ if baz(i) => ???
  case _ if zoo(i) => ???
  case _ => someDefault
}

where we don’t really care about the pattern match, just the guard. This is in
constrast to if branches:

def foo(i: Int): Whatever = {
  if (bar(i)) ???
  else if (baz(i)) ???
  else if (zoo(i)) ???
  else someDefault
}

which of course would often be made more verbose by many {} pairs. Are we
punished for the empty pattern matches? MatchBench tests this, with various
numbers of branches.

Results:

All times are in nanoseconds.

Identical! Feel free to use whichever you think is cleaner.