scala speed when using get() method on hash tables? (are temporary Option() objects generated?)

Question

I am converting some code to Scala. It's code that sits in an inner loop with very large amounts of data so it needs to be fast, and it involves looking up keys in a hash table and computing probabilities. It needs to do different things depending on whether a key is found or not. The code would look like this using the "standard" idiom:

counts.get(word) match {
  case None => {
    WordDist.overall_word_probs.get(word) match {
      case None => (unseen_mass*WordDist.globally_unseen_word_prob
                    / WordDist.num_unseen_word_types)
      case Some(owprob) => unseen_mass * owprob / overall_unseen_mass
    }
  }
  case Some(wordcount) => wordcount.toDouble/total_tokens*(1.0 - unseen_mass)
}

but I am concerned that code of this sort is going to be very slow because of all these temporary Some() objects being created and then garbage-collected. The Scala2e book claims that a smart JVM "might" optimize these away so that the code does the right thing efficiency-wise, but does this actually happen using Sun's JVM? Anyone know?

Answer 1

This may happen if you enable escape analysis in the jvm, enabled with:

-XX:+DoEscapeAnalysis

on JRE 1.6. Essentially, it should detect objects being created which do not escape the method activation frame and either allocate them on the stack or GC them right after they're no longer needed.

One thing you could do is to micro benchmark your code using the scala.testing.Benchmark trait. Just extend it with a singleton object and implement the run method, compile it and run it. It will run the run method multiple times, and measure execution times.

Answer 2

Yes, Some objects will be created (None is a singleton). Unless, of course, JVM elides that -- that depends on many factors, including whether or not JVM thinks the code is called all that much.

Anyway, that code is not really the standard idiom. There's even a meme about it: once, one experienced Scala developer was written code like this, when the other one replied "What's this? Amateur hour? Flatmap that sh*t!"

Anyway, here's how I'd rewrite it:

( counts 
  get word
  map (_.toDouble / total_tokens * (1.0 - unseen_mass))
  getOrElse (
    WordDist.overall_word_probs
    get word
    map (unseen_mass * _ / overall_unseen_mass)
    getOrElse (unseen_mass * WordDist.globally_unseen_word_prob
                / WordDist.num_unseen_word_types)
  )
)

You can then refactor this -- both getOrElse parameters could be split in different method with nice names. Since they just return a value without input, they should be pretty fast.

Now, we call just two methods here on Option: map and getOrElse. Here's the beginning of their implementation:

@inline final def map
@inline final def getOrElse

As the parameter to getOrElse is passed by name, it involves an anonymous function creation. And, of course, the parameter to map is also a function. Other than that, the chance of these methods getting inlined is pretty good.

So, here's the refactored code, though I don't know enough about it to give good names.

def knownWordsFrequency = counts get word map computeKnownFrequency
def computeKnownFrenquency = 
  (_: Int).toDouble / total_tokens * (1.0 - unseen_mass)

def probableWordsFrequency = (
  WordDist.overall_word_probs 
  get word 
  map computeProbableFrequency
)
def computeProbableFrequency = unseen_mass * (_: Double) / overall_unseen_mass

def unknownFrequency = (unseen_mass * WordDist.globally_unseen_word_prob
  / WordDist.num_unseen_word_types)

def estimatedWordsFrequency = probablyWordsFrequency getOrElse unknownFrequency

knownWordsFrequency getOrElse estimatedWordsFrequency