Optimization Hints

This page is intended to document things that we should do and things we should avoid when writing code that needs to be fast.

Map#mapValues creates a view, not a new Map

One common problem is that people think mapValues behaves like map, and actually eagerly creates a new map. This is not true. Going against the grain, because it can, mapValues actually creates a view instead, that calls the function passed to mapValues every single time a value is accessed. If your function is doing some crazy things, then this will be a big performance problem.

There are 2 things you can do to skirt this issue.

1. Just eagerly create the map after (with map identity or perhaps implicitly from a CanBuildFrom by setting the final value to be an immutable.Map, not Map).

2. Import com.precog.util._ and use lazyMapValues instead. This won't eagerly create a map, but will guarantee the function is called at most once for each value. This laziness comes at the cost of a lock.

Preallocate Buffers

Instead of relying on the ability of buffers to resize, when you know the size or an upper bound, pre-allocate the buffer in that size to prevent costly growing of the buffer.

Function2 isn't @specialized

In Scala 2.9, Function2 isn't specialized. If you find yourself creating, eg, (Int, A) => B, then every single Int passed to the function in the first parameter will be boxed! Either refactor to a Function1, which is specialized, or create a trait with a single method to wrap the functionality of the Function2.

Range boxes

Range tries hard to be a collection. This means all the Ints it gives you are boxed when you pull them out. We've introduced an object to help with this: com.precog.util.Loop. Anytime you would have looped over a range you can use this instead. For example:

// before
(0 until n) foreach (i => ...)

// after
Loop.range(0, n)(i => ...)

Note that this will still create an instance of Function1[Int, Unit]. In many cases this doesn't matter, but if you're in the critical path you may want to use a while-loop or @tailrec method directly for even more speed!

Scala's BitSet boxes

BitSet suffers from the same problems as Range. We have a replacement named com.precog.util.BitSet (which is a slightly modified version of javolution.util.BitSet). Unfortunately, this Java class lacks a lot of the Scala collections methods (which is OK since most of those box). Some of the more common constructions can be solved by using the com.precog.util.BitSetUtil object:

import com.precog.util.{BitSet, BitSetUtil}

val all = BitSetUtil.range(0, 200)
val evens = BitSetUtil.filteredRange(0, 200)(i => i % 2 == 0)

import BitSetUtil.Implicits._

// provided by implicits
all.foreach { i => ... }
all += 4000
val intersect = all & evens

It's better not to rely on these implicits to avoid creating temporary wrappers, but they are there to help with compatibility. Feel free to add more useful constructors to BitSetUtil.

Scala's & Scalaz's Ordering & Order both box

Comparing some Ints? Ordering & Order will box. Solution? There isn't really a general one in the code base yet (cough Spire cough).

Set & Map methods

We use Sets & Maps a lot. This is great, but at a row level they may not be the most efficient. A lot of operations come from the IterableLike interface, which will allocate iterators and whatnot to perform things like existence checks. It is faster to allocate something like an Array at the Slice-level, then use this on a per-row basis to avoid the allocations.