Scala vs. Java performance

Question

I came across a very strange discrepancy between Scala and Java performance. I performed the inversion counting procedure in Java and then ported it line by line to Scala, because all the idiomatic versions of Scala (using List or Stream ) were either very slow, or crash when overflowing / exiting the memory error stack. But this version was also slow - while the Java version took 22 ms to process an array of 100,000 integers, the Scala version took 3 seconds. Here is the corresponding 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 the performance of this program?

UPD: The poor performance of the Scala version is completely my fault. The first statement unnecessarily copies the entire array to the auxiliary array. When changing to copy only the required part, the performance is on par with Java, as expected.

Answer 1

Most likely, this is due to understanding. He is freed from

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

To make it comparable to a Java solution, you must replace it with a while loop.

 var k = left while (k <= right) { // code... k += 1 } 

I am sure that this solution will be consistent with the Java version.