How to Optimize Scala Code Performance With Almost No Effort

How is it even possible?

In this article, I describe Scala performance tips based on my experience of optimizing Ergo's smart contracts interpreter. I found that some typical Scala code fragments have surprisingly much faster alternatives. The tips below can help you to avoid accidental performance issues and write faster Scala code for no additional effort. There is also source code with all the benchmarks.

Scala provides powerful constructs and idioms to build abstractions for correctness and clarity but may have runtime performance penalties. When solving a task, there may be several alternative solutions, each with its own performance characteristics. Even similar-looking code can have radically different performance.

Teams often specify things like formatting and documentation to make sure the code stays consistent and good quality. Similarly, tips on making the code run faster can also be useful. Performance improvement can come from almost no special effort. As such, it is a matter of coding style and habits rather than a matter of extensive code optimization, which shouldn't be premature.

The code speedups described below are only examples and not necessarily exact numbers, as there may be various factors that can impact the timings. Nevertheless, after systematically applying the outlined recommendations, I have observed strictly positive effects on performance.

Performance tips

Tip 1: Avoid Seq()

Let's start with the simplest. It's not uncommon to see the use of Seq() wherever an empty collection is required. However, this method involves the following:

1. an empty array is initiated
2. the array is wrapped into an instance of ArraySeq
3. the following methods called: SeqFactory$Delegate.apply -> IterableFactory.apply -> List.from -> Nil.prependAll
4. Nil object returned in the end

What to use instead

Simple Nil is 20-28% faster (see Benchmark: Seq) depending on whether the JIT is able to inline the Seq() invocation all the way down to Nil or not. So, why not help it and use Nil directly?

Tip 2: Avoid Map()

Next one is Map(). It is often used wherever an empty Map is required. However, as is the case with Seq(), this method involves allocations and many method calls.

What to use instead

Calling Map.empty is 25-85% faster, depending on the context (see Benchmark: Map)

Tip 3: Avoid for comprehensions

Looping pattern for (x <- xs) { ... } is used quite often due to its convenience. It looks very similar to the for loop in Java, but it is not.

In Scala, it is desugared by the compiler to xs.foreach { x => ... } which, besides execution of the block of code involves the following list of overheads:

1. foreach method call
2. allocation of lambda object
3. boxing (memory allocation) of the value x for every xs item (if xs values are not yet boxed)
4. hidden overhead of concrete implementation of foreach method

Such for comprehensions are particularly sub-optimal (see Benchmark: for over Range) for Range loops, where x is an Int.

What to use instead

There is a cfor macro from spire library.

I recommend the following code as a replacement when xs provides an O(1) indexing access, for example if xs is an Array or an array wrapped into Seq.

import spire.syntax.cfor._
cfor(0)(_ < xs.length, _ + 1) { i => 
  val x = xs(i)
      ...
}

The above xs collection can also be a Range in which case for (x <- 0 until n) { ... } can be replaced with

cforRange(0 until n) { x => ... }

These cfor macros are compiled to efficient Java loop without overhead points 1) - 4). Depending on xs.length it is 10-170x faster (see Benchmark: for over Range). And since foreach already implies a side effect operation, cfor doesn't make the code any less readable.

Note, however, that cfor is not a silver bullet. It is NOT a replacement for foreach in the case of non-indexed collections, when indexed access is NOT a fast O(1) operation. In many cases using cfor instead of foreach is a no-brainer and often increases the performance of any code which loops over an indexed collection (see for example Benchmark: dot-product and Benchmark: check brackets).

Tip 4: Avoid creating sequences with Seq(...)

It is tempting to use Seq.apply method where a Seq of items is required like Seq(1, 2, 3) because it is easy and concise. You can pass it as a method argument or as a method result.

However, the following happens under the hood:

1. new Array with the items 1, 2, 3 is created, and each item is boxed into its own Integer object
2. WrappedArray#ofInt wrapper is created and passed as vararg argument of Seq.apply
3. the above-mentioned methods down to Nil.prependAll are called
4. new ListBuffer is created and all items are copied from array to the buffer

Benchmarks show that JIT is not able to fully optimize this code.

What to use instead

Simple drop-in replacement Array(1, 2, 3) performs better. This code is 4-10x faster than using Seq(1, 2, 3). (see Benchmark: Seq vs Array). The speedup is even more significant when the number of items in the sequence grows (see Benchmark: Seq vs Array (from Range)).

What happens here is that:

1. native unboxed Java array is created and then

2. wrapped via implicit conversion into a WrappedArray#ofInt which is inherited from the Seq trait and can be used directly.

Why is this faster?

1. It avoids unnecessary allocations (only two new objects are allocated in the Array case). Note that to create Seq not only each Int is boxed into java.lang.Integer (or other primitive type), but also scala.collection.immutable.:: instances are created for each item of the list.

2. Creating Array avoids boxing (which is proportional to the size of Seq).

3. Accessing of array items is cache friendly both when the array is created and when it is later used.

4. Fewer allocations mean less garbage to collect later. This is especially important when the application is multithreaded because, in this case the garbage collector will compete with application threads for CPU resources, thus further slowing down the application.

Notice that using arrays like this doesn't make the code any less readable. Moreover, the arrays created in this way are only accessible via Seq interface, which is immutable. Thus, better performance is achieved without sacrificing other desirable code qualities like readability, safety, and conciseness.

Caveat: the array is not efficient if it is accessed using list operations head andtail. See, for example, Seq vs Array (list ops) benchmark. In this case, replacing Seq with Array may lead to performance degradation. However, using lists in a performance-critical code may not be a good idea as well.

Tip 5: Avoid extractors with Option

An extractor is an object with an unapply method taking an arbitrary argument and returning an Option of some (maybe different) type. Here is a simple example:

object IsEven:
  def unapply(n: Int): Option[Int] =
    if (n % 2 == 0) Some(n) else None

With extractors, pattern matching can be concise and expressive.

However, unapply returning an Option might have a negative impact on runtime performance because on every matching call an instance of Some needs to be created for each successful extraction.

What to use instead

Since version 2.11, Scala introduces name based extractors that no longer requires unapply to return an Option. Combined with value classes these two features allow implementing allocation-free extractors, which are 10-70% faster than the original Option based extractors (see Benchmark: Option vs Opt).

object IsEvenOpt:
  def unapply(n: Int): Opt[Int] =
    if (n % 2 == 0) Opt(n) else Opt.empty

A suitable implementation of Opt class can be found in the spire library.

Benchmarks Summary

The following tables summarize the results of the benchmarks run on the code snippets above and the following configuration: osArch: aarch64; osName: Mac OS X OpenJDK 64-Bit Server VM; vendor: Eclipse Adoptium; version: 17.0.5+8

You can reproduce the results on your computer by running the Benchmarks class.

Clone the repository and run sbt "Test/runMain benchmarks.Benchmark".

Benchmark: Seq

Benchmark: Map

Benchmark: foreach vs cfor

Benchmark: for over Range

Benchmark: Seq vs Array (from elems)

Benchmark: Seq vs Array (from Range)

Benchmark: Seq vs Array (list ops)

Benchmark: Option vs Opt

Benchmark: dot-product

Benchmark: check brackets

Concluding remarks

Program performance upkeep & optimization is the result of constant vigilance and work, rather than just a one-time job. There is no one size fits all solution as there are many trade-offs along the way.

The tips presented in this article are so simple that they can be applied by default and regardless of whether you have already identified the bottleneck or not. Back to my experience, once I systematically applied these tips all over the code base, those parts of code disappeared from the profiler's hot spots bringing up on the surface other bottlenecks

and simplifies profiling.

For further reading, I collected a list of useful references on the topic of Scala optimization. Happy optimizing!

References

1. Scala Style Guide
2. Scala High Performance Programming
3. Optimizing Higher-Order Functions in Scala (somewhat outdated)
4. Where to look first when optimizing Scala code?
5. Scala for comprehension performance
6. Performance characteristics of Scala collections
7. Java Performance: The Definitive Guide: Getting the Most Out of Your Code
8. Scala library benchmarks
9. JITWatch
10. Parallel Collections: Measuring Performance
11. JVM JIT optimization techniques
12. Name Based Extractors in Scala 2.11