4

I've encountered a very strange discrepancy between Scala and Java performance. I've implemented an inversion counting routine in Java and then ported it line by line to Scala, because all idiomatic Scala versions (using List or Stream) were either very slow or crashing with stack overflow/out of memory error. But this version was slow as well—while the Java version takes 22ms to process an array of 100000 integers, the Scala version takes 3 seconds. Here's the relevant code from the Scala version:

  def mergeAndCountInversions(xs: Array[Int], aux: Array[Int], left: Int, right: Int) = {
    xs.copyToArray(aux)
    val m = left + (right - left) / 2

    var i = left
    var j = m + 1
    var inv: Long = 0

    for (k <- left to right) {
      if (i > m) {
        xs(k) = aux(j)
        j += 1
      } else if (j > right) {
        xs(k) = aux(i)
        i += 1
      } else if (aux(j) < aux(i)) {
        xs(k) = aux(j)
        j += 1
        inv += (m - i) + 1
      } else {
        xs(k) = aux(i)
        i += 1
      }
    }
    inv
  }

Any ideas on how to improve this routine's performance?

UPD: The poor performance of Scala version is completely my fault. The first statement unnecessarily copies whole array to auxiliary array. When changed to copy only the required part the performance is on par with Java as it's supposed to be.

5
  • Although I'm not enough of a Scala wiz to write an answer to this, consider that array indexing in Scala is calling the apply method on an array object – not quite the same thing as the pointer arithmetic Java performs under the hood when you use the array access syntax with square brackets!
    – kqr
    Sep 23, 2013 at 12:37
  • 5
    First of all: use jmh to measure performance after warm up. I guess you'll get the same performance after inlining. You could also enforce inlining at compile time using Scalaxy like this: for(k <- left to right optimized).
    – senia
    Sep 23, 2013 at 12:39
  • @senia I've updated the question with the benchmark routine used
    – synapse
    Sep 23, 2013 at 12:54
  • 2
    I've found that reconstructing scala's for comprehensions as tail-recursive algorithms often has performance benefits (if you can do it). The compiler seems to be better at optimizing those. Sep 23, 2013 at 13:13
  • Ah, synapse, I was just looking at your original Scala implementation of this over on CodeReview ;) You don't fully understand tail recursion/optimisation, I think. Have given an example, over there.
    – itsbruce
    Sep 23, 2013 at 22:52

1 Answer 1

1

Most likely it is because of the for-comprehension. It gets desugared to

Range(left, right).foreach { k =>
  // code...
}

In order to make it comparable with the Java solution, you have to replace it with a while loop.

var k = left

while (k <= right) {
  // code...

  k += 1
}

I'm pretty sure, that this solution will be on par with the Java version.

5
  • Yeah, I thought that could be the reason but performance was the same with while
    – synapse
    Sep 23, 2013 at 12:47
  • What I don't understand is why the Scala compiler doesn't find a way to optimize the Range(...).foreach construct into the same underlying bytecode as what gets generated for a Java for loop... Sep 23, 2013 at 12:58
  • @ErikAllik for in scala does a lot more than the usual java looping constructs. There is work being done (issues.scala-lang.org/browse/SI-1338) to optimize the simplest cases Sep 23, 2013 at 13:01
  • I tested it with for and while and while was way faster.
    – drexin
    Sep 23, 2013 at 13:06
  • @drexin that's really strange. What is your environment? I'm using Scala 2.10.2 and JDK 1.6 on Mac OS X.
    – synapse
    Sep 23, 2013 at 13:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.