Scala与Java性能比较

Question

Scala与Java性能比较

4

我在Scala和Java的性能上遇到了一个非常奇怪的差异。我已经在Java中实现了一个倒置计数例程，然后逐行将其移植到Scala，因为所有惯用的Scala版本（使用List或Stream）要么非常缓慢，要么会崩溃并出现堆栈溢出/内存错误。但是这个版本也很慢——而Java版本只需要22ms就可以处理100000个整数数组，而Scala版本需要3秒钟。下面是Scala版本的相关代码：

  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
  }

有什么想法可以改进这个例程的性能吗？

更新：Scala版本性能不佳完全是我的错。第一条语句不必要地将整个数组复制到辅助数组中。当只复制所需部分时，性能与Java相当，正如它应该的那样。

- synapse

虽然我不够熟练，无法为此编写Scala答案，但请注意，在Scala中，数组索引是调用数组对象上的“apply”方法 - 这与Java在使用带方括号的数组访问语法时在幕后执行的指针算术并不完全相同！ - kqr

5

首先：使用jmh来测量预热后的性能。我猜你会得到相同的性能结果在内联之后。你也可以使用Scalaxy在编译时强制内联，像这样：for(k <- left to right optimized)。 - senia

@senia 我已经更新了问题，并附上了使用的基准测试程序。 - synapse

2

我发现将Scala的for推导式重构为尾递归算法通常具有性能优势（如果您可以这样做）。编译器似乎更擅长优化这些算法。 - Ian McLaird

啊，Synapse，我刚在CodeReview上看了你的Scala原始实现;) 我认为你并没有完全理解尾递归/优化。我已经在那里给出了一个例子。 - itsbruce

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- drexin · Accepted Answer

很可能是由于for-comprehension。它会被解析为

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

为了使其与Java解决方案相媲美，您需要用while循环替换它。

var k = left

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

  k += 1
}

我相信，这个解决方案将与Java版本相媲美。