CODEWITHSUNDEEP
algorithmscalasorting
synapse
synapse

Reputation: 5728

Scala vs. Java performance

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.

Upvotes: 4

Views: 1068

Answers (1)

drexin
drexin

Reputation: 24423

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.

Upvotes: 1

Related Questions