Why is Scala hashmap slow?

Question

And what can be done about it?

I have run some tests and it seems that Scala Hashmap is much slower than a Java HashMap. Please prove me wrong!

For me the whole point of Hashmap is to get quick access to a value from a given key. So I find myself resorting to using a Java HashMap when speed matters, which is a bit sad. I'm not experienced enough to say for sure but it seems that the more you mix Java and Scala the more problems you are likely to face.

test("that scala hashmap is slower than java") {
    val javaMap = new util.HashMap[Int,Int](){
      for (i <- 1 to 20)
      put(i,i+1)
    }

    import collection.JavaConverters._
    val scalaMap = javaMap.asScala.toMap

    // check is a scala hashmap
    assert(scalaMap.getClass.getSuperclass === classOf[scala.collection.immutable.HashMap[Int,Int]])

    def slow = {
      val start = System.nanoTime()
      for (i <- 1 to 1000) {
        for (i <- 1 to 20) {
          scalaMap(i)
        }
      }
      System.nanoTime() - start
    }

    def fast = {
      val start = System.nanoTime()
      for (i <- 1 to 1000) {
        for (i <- 1 to 20) {
          javaMap.get(i)
        }
      }
      System.nanoTime() - start
    }

    val elapses: IndexedSeq[(Long, Long)] = {
      (1 to 1000).map({_ => (slow,fast)})
    }

    var elapsedSlow = 0L
    var elapsedFast = 0L
    for ((eSlow,eFast) <- elapses) {
      elapsedSlow += eSlow
      elapsedFast += eFast
    }

    assert(elapsedSlow > elapsedFast)

    val fraction : Double = elapsedFast.toDouble/elapsedSlow
    println(s"slower by factor of: $fraction")
}

Am I missing something?

Answer Summary

As of now, when comparing Java 8 to Scala 2.11, it appears that Java HashMap is notably speedier at lookups (for a low number of keys) than the Scala offerings - with the exception of LongMap (if your keys are Ints/Longs).

The performance difference is not so great that it should matter in most use cases. Hopefully Scala will improve the speed of their Maps. In the mean time, if you need performance (with non-integer keys) use Java.

Int keys, n=20
Long(60), Java(93), Open(170), MutableSc(243), ImmutableSc(317)

case object keys, n=20
Java(195), AnyRef(230)

Catsup

If you are going to use a Java map I recommend using import scala.collection.JavaConversions._ – Catsup

Answer 1

First of all: doing JVM benchmarks using nanoTime is extremely error-prone. Use a microbenchmarking framework such as Thyme, Caliper or JMH

Second: you are comparing a mutable java hash map with an immutable scala hash map. Immutable collections can be remarkably fast, but there are some cases where they will never be as fast as mutable data structures.

Here is a proper microbenchmark of mutable java hash map vs. immutable scala hash map: https://gist.github.com/rklaehn/26c277b2b5666ec4b372

As you can see, the scala immutable map is a bit faster than the java mutable map. Note that this will not be the case once you go to larger maps, because an immutable data structure has to do some compromises to enable structural sharing. I would guess that in both cases, the dominant performance issue is boxing of the ints to Integer.

Update: if you really want a mutable hash hap with ints as keys, the right choice from the scala collections library is scala.collection.mutable.LongMap. This uses a long as key, and has much better performance than the generic Map because it does not have to box the value. See results from the gist.

Update 2: If your key extends from AnyRef (like e.g. a String), your best bet for a high performance mutable map is scala.collection.mutable.AnyRefMap

Realm

Can you explain and/or cite a source as to why using System.nanoTime() is extremely error-prone? – Adagietto

Here's a pretty good presentation about the pitfalls of relying upon System.nanoTime() for benchmarking (and the difficulties with JVM benchmarking in general): shipilev.net/blog/2014/nanotrusting-nanotime – Painless

basically the issues are: you need to give the JVM enough time for optimizing the code (so-called warmup), you need to make sure that the benchmark is not optimized away entirely. That is why a benchmark method must always return a result. – Lordly

@Rüdiger Thank you for an excellent response, however, I have tried out your test, with one amendment: I removed the accumulation computation: r += javaMap.get(i) so it is instead r = javaMap.get(i) in each case. I also added the OpenHashMap out of interest. The results do not match your own! I get: Java 127.9 vs Scala Immutable 534.5, and Java 126.8 vs Scala Long 88.59, Java 126.2 vs Scala Open 245.2. So Scala only wins when using a LongMap and is significantly worse in the other cases. But I think the reason for this comes down to the one given by @mohit – Catsup

@RüdigerKlaehn - OP runs each function 1000 times. His each function runs get calls another 1000 times. OP then aggregates the result from both the functions and then divides it to get the factor which is same as taking average. JVM is warmed up by running the functions multiple times and the functions return the times, so why is his method wrong? – Jennajenne

@mohit: the benchmark sums up all the times, including the time that the JIT spent with warmup. java.util.HashMap has an advantage here because it is probably already warmed up by the time main() is called. Usually you do a warmup and throw away the results, and then only measure once things are warmed up. That is, if you are interested in the performance for a long-running process. – Lordly

@Catsup you should not remove the aggregation. That has the risk of the JVM optimizing away all but the last lookup, since the previous ones do not contribute to the result. Did you try with Thyme, or stay with nanoTime? – Lordly

@Rüdiger I have added the aggregation back in and my test is now identical to yours, I am using Thyme, but the results I get do not match yours! Java is still significantly faster than Scala except for LongMap. I have run the tests several times. These are the times typical for me: Long(60), Java(93), Open(170), MutableSc(243), ImmutableSc(317). In another test I've compared AnyRef for my actual scenario with case objects and it is the best Scala option: Java(195), AnyRef(230). I am using Java 8. – Catsup

I guess that's the difference: I am using Java 7. The performance of Java and AnyRefMap seems to be pretty similar. So if you really need the tiny bit of extra performance, there is nothing wrong with using java data structures from scala. – Lordly

I did some benchmarks once, and consistently got better results with mutable.Map. Both using Caliper and not. I'm mot sure how you could have seen different results, will try your code later. Also I should try using integer keys too. My test focused on updating, though, not just reading. github.com/nlw0/scala-datastructure-benchmark – Orbiculate

Answer 2

Instead of calling apply i.e scalaMap(i), if you do scalaMap.get(i) then it is as fast as javaMap.get(i)

From source, the code for apply is

def apply(key: A): B = get(key) match {
    case None => default(key)
    case Some(value) => value
  }

which shows that apply method first calls the get method and then pattern matches on it. Having an extra hop for each call in case of an option does have performance penalty and has already been discussed on SO(can't find the link though)

Jennajenne

Have you tried? I got similar benchmark result as apply. – Polycotyledon

@ArieShaw Yes, I tried. I am using scala-2.11 and there was hardly any performance penalty. Sometimes, scalaMap was faster(courtesy of JVM) – Jennajenne

@Jennajenne Thanks, I should have thought of that! Though I think that the main reason this slows you down is the creation of an object: Some - rather than the pattern matching. – Catsup

@Catsup - calling scalaMap.get(i) and javaMap.get(i) didn't show difference whenever I tested. Calling apply had a good performance penalty. If there was no pattern match after apply, then it was same as calling get directly. The extra step is the pattern match which makes me think that this is what causing the slowness. – Jennajenne

Some is created in the get method itself. case statement simply calls the unapply.. – Antler

Answer 3

Scala 2.13 (June 2019) do introduce new, faster HashMap/Set implementations

Both immutable (d5ae93e) and mutable (#7348) versions were completely replaced. - They substantially outperform the old implementations in most scenarios. - The mutable versions now perform on par with the Java standard library's implementations.

For the immutable HashSet and HashMap:

The reimplementations are based upon Compressed Hash-Array Mapped Prefix-trees (CHAMP).

See paper "Optimizing Hash-Array Mapped Tries for Fast and Lean Immutable JVM Collections" by Steindorfer and Vinju (OOPSLA'15) for more details and descriptions of low-level performance optimizations (a pre-print of the paper is available).

Navy