About collections performace...

[Roman Janusz]

Lately I did some very simple benchmarks on Scala's mutable.HashMap versus Scala-wrapped java.util.HashMap and I found out the latter to be much faster.

I guess this is a result that is well known, as this blog post shows: http://capecoder.wordpress.com/2012/07/29/scalamapbenchmark/ and I expect it to have been thoroughly discussed somewhere already.

Unfortunately, I was unable to find the answer to fundamental question that bugs me and author of mentioned blog post: so why EVER use scala.collection.mutable.HashMap? Why does it even exists when java.util.HashMap wrapped as scala map provides the same features while being a lot faster? What's the point of reinventing a wheel?

Cheers,
Roman

[Simon Ochsenreither]

Hi Roman,

usually there are people looking into optimizing the performance of the collection classes like here: https://groups.google.com/d/topic/scala-internals/zY5KhFddqR4/discussion

I think there is no reason why a Scala collection should be slower or only as fast as the Java ones, it's just that nobody had time yet to optimize all of them yet. As far as I remember, every release had improvements to some collection classes, it's just that HashMap hasn't been the lucky one yet.

In practice, I try to keep the dependencies to the underlying platform as small as possible, so that people who want to run Scala on X don't have to reimplement/port half of the JDK.
Other offenders include BigInt, where we're wrapping the Java's BigInteger and inherit its poor performance. That's what I'm investigating in https://github.com/soc/spire/tree/bigint.

Bye,

Simon

[Roman Janusz]

Thanks for your answer. I didn't mean to complain in my question, I just didn't make sense to me why Scala authors go through all the effort of reimplementing and optimizing something that already exists and probably underwent many optimizations over the time. So if I understand you correctly, it is a part of general effort to make scala-library as little dependent on JDK classes as possible, right?

[Josh Suereth]

While I could go into various trade-offs, pros/cons, etc, the reality I don't really know the full reason.  I've heard that we want to have a "complete" collections library (i.e. it has all the collections you'd want to reach for).   

I do know this:

wrapping Java collections can lead to "strange" behavior, if you aren't aware of what you're doing.   E.g. 

import collections.JavaConverters._

javaHashMap.asScala == javaHashMap  // What should this return?

javaHashMap == javaHashMap.asScala  // What should this return?

I'd say a goal of the scala collections library is to be as complete an implementation as possible, i.e. it should provide all the general purpose collections one needs.   It certainly has some performance issues on some collections that we need to rectify.   

Also, our collections are under a different license.  Not sure if there's any practical difference, but hey!

That said ->  I'd be more than happy if someone had time to improve mutable.HashMap to get up-to-par with Java's implementation.

--
You received this message because you are subscribed to the Google Groups "scala-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-user+...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Rex Kerr]

On Sat, May 11, 2013 at 3:45 PM, Josh Suereth <joshua....@gmail.com> wrote:

That said ->  I'd be more than happy if someone had time to improve mutable.HashMap to get up-to-par with Java's implementation.

With or without changing the interface?  One nontrivial problem is that maps allow both a (k,v) and a bunch-of-keys and bunch-of-values view of the data, and the underlying data structures aren't exactly consistent with either, and yet another datastructure (DefaultEntry) is used to pack the key and value together.  So a good bit of time is wasted in grouping the data in various ways.  You are limited in what you can do until you throw HashEntry/DefaultEntry away completely.  Look at this add method:

  def += (kv: (A, B)): this.type = {
    val e = findOrAddEntry(kv._1, kv._2)  // Look, we break it apart!
    if (e ne null) e.value = kv._2
    this
  }
  protected def findOrAddEntry[B](key: A, value: B): Entry = {
    val h = index(elemHashCode(key))
    val e = findEntry0(key, h)
    if (e ne null) e else { addEntry0(createNewEntry(key, value), h); null }

            // And create it again!   ^^^^^^^^^^^^^^^^^^^^^^^^^^
  }

This is not exactly what I would call a good idea for performance.  IIRC it was important for sharing implementation details.

Anyway, IIRC we pretty much have to rip out HashTable and try again since HashTable works on Entry and HashMap works on tuples.  Maybe it's possible to make Entry an AnyVal of tuples...I'm not sure.

  --Rex

[Or Peles]

I recently found out that Scala contains a mutable map implementation called OpenHashMap. Some simple benchmarks showed its performance to be much faster than the default mutable map implementation, about on par with java's hashmap.

You can see the scaladoc here: http://www.scala-lang.org/api/current/index.html#scala.collection.mutable.OpenHashMap

I suggest you take a look. 

I don't know why it has not been promoted to being the default implementation, and if/how it solves some of the issues Rex mentioned above. 

On a related note, the immutable hashmap performance can be terrible. In a micro-benchmark I ran recently, it did not even exhibit the expected O(1) behavior - adding keys caused subsequent search times to rise dramatically.

Or

[Rex Kerr]

How did you benchmark it?  It's specifically supposed to implement a map that is good with consecutive hash values.  If you used something like a map from consecutive integers in your test, then of course it will do better.

It suffers from the same Entry creation problem as the regular HashMap, though.  We can do better.

  --Rex