55

我遇到了这个老问题，并用 scala 2.10.3 做了以下实验。

我重写了 Scala 版本以使用显式尾递归：

import scala.annotation.tailrec

object ScalaMain {
  private val t = 20

  private def run() {
    var i = 10
    while(!isEvenlyDivisible(2, i, t))
      i += 2
    println(i)
  }

  @tailrec private def isEvenlyDivisible(i: Int, a: Int, b: Int): Boolean = {
    if (i > b) true
    else (a % i == 0) && isEvenlyDivisible(i+1, a, b)
  }

  def main(args: Array[String]) {
    val t1 = System.currentTimeMillis()
    var i = 0
    while (i < 20) {
      run()
      i += 1
    }
    val t2 = System.currentTimeMillis()
    println("time: " + (t2 - t1))
  }
}

并将其与以下 Java 版本进行比较。为了与 Scala 进行公平比较，我有意识地将函数设为非静态函数：

public class JavaMain {
    private final int t = 20;

    private void run() {
        int i = 10;
        while (!isEvenlyDivisible(2, i, t))
            i += 2;
        System.out.println(i);
    }

    private boolean isEvenlyDivisible(int i, int a, int b) {
        if (i > b) return true;
        else return (a % i == 0) && isEvenlyDivisible(i+1, a, b);
    }

    public static void main(String[] args) {
        JavaMain o = new JavaMain();
        long t1 = System.currentTimeMillis();
        for (int i = 0; i < 20; ++i)
          o.run();
        long t2 = System.currentTimeMillis();
        System.out.println("time: " + (t2 - t1));
    }
}

以下是我电脑上的结果：

> java JavaMain
....
time: 9651
> scala ScalaMain
....
time: 20592

这是 (Java HotSpot(TM) 64-Bit Server VM, Java 1.7.0_51) 上的 scala 2.10.3。

我的问题是 scala 版本的隐藏成本是多少？

非常感谢。

4

4 回答 4

135

好吧，OP 的基准测试并不是理想的。需要减轻大量影响，包括预热、死代码消除、分叉等。幸运的是，JMH已经处理了很多事情，并且对 Java 和 Scala 都有绑定。请按照 JMH 页面上的程序获取 benchmark 项目，然后您可以在那里移植下面的 benchmark。

这是示例 Java 基准测试：

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
@State(Scope.Benchmark)
@Fork(3)
@Warmup(iterations = 5)
@Measurement(iterations = 5)
public class JavaBench {

    @Param({"1", "5", "10", "15", "20"})
    int t;

    private int run() {
        int i = 10;
        while(!isEvenlyDivisible(2, i, t))
            i += 2;
        return i;
    }

    private boolean isEvenlyDivisible(int i, int a, int b) {
        if (i > b)
            return true;
        else
            return (a % i == 0) && isEvenlyDivisible(i + 1, a, b);
    }

    @GenerateMicroBenchmark
    public int test() {
        return run();
    }

}

...这是示例 Scala 基准测试：

@BenchmarkMode(Array(Mode.AverageTime))
@OutputTimeUnit(TimeUnit.MICROSECONDS)
@State(Scope.Benchmark)
@Fork(3)
@Warmup(iterations = 5)
@Measurement(iterations = 5)
class ScalaBench {

  @Param(Array("1", "5", "10", "15", "20"))
  var t: Int = _

  private def run(): Int = {
    var i = 10
    while(!isEvenlyDivisible(2, i, t))
      i += 2
    i
  }

  @tailrec private def isEvenlyDivisible(i: Int, a: Int, b: Int): Boolean = {
    if (i > b) true
    else (a % i == 0) && isEvenlyDivisible(i + 1, a, b)
  }

  @GenerateMicroBenchmark
  def test(): Int = {
    run()
  }

}

如果您在 JDK 8 GA、Linux x86_64 上运行这些，您将获得：

Benchmark             (t)   Mode   Samples         Mean   Mean error    Units
o.s.ScalaBench.test     1   avgt        15        0.005        0.000    us/op
o.s.ScalaBench.test     5   avgt        15        0.489        0.001    us/op
o.s.ScalaBench.test    10   avgt        15       23.672        0.087    us/op
o.s.ScalaBench.test    15   avgt        15     3406.492        9.239    us/op
o.s.ScalaBench.test    20   avgt        15  2483221.694     5973.236    us/op

Benchmark            (t)   Mode   Samples         Mean   Mean error    Units
o.s.JavaBench.test     1   avgt        15        0.002        0.000    us/op
o.s.JavaBench.test     5   avgt        15        0.254        0.007    us/op
o.s.JavaBench.test    10   avgt        15       12.578        0.098    us/op
o.s.JavaBench.test    15   avgt        15     1628.694       11.282    us/op
o.s.JavaBench.test    20   avgt        15  1066113.157    11274.385    us/op

请注意，我们t要查看效果是否对于 的特定值是局部的t。不是，效果系统，Java版快一倍。

PrintAssembly将对此有所了解。这是 Scala 基准测试中最热门的块：

0x00007fe759199d42: test   %r8d,%r8d
0x00007fe759199d45: je     0x00007fe759199d76  ;*irem
                                               ; - org.sample.ScalaBench::isEvenlyDivisible@11 (line 52)
                                               ; - org.sample.ScalaBench::run@10 (line 45)
0x00007fe759199d47: mov    %ecx,%eax
0x00007fe759199d49: cmp    $0x80000000,%eax
0x00007fe759199d4e: jne    0x00007fe759199d58
0x00007fe759199d50: xor    %edx,%edx
0x00007fe759199d52: cmp    $0xffffffffffffffff,%r8d
0x00007fe759199d56: je     0x00007fe759199d5c
0x00007fe759199d58: cltd   
0x00007fe759199d59: idiv   %r8d

...这是Java中的类似块：

0x00007f4a811848cf: movslq %ebp,%r10
0x00007f4a811848d2: mov    %ebp,%r9d
0x00007f4a811848d5: sar    $0x1f,%r9d
0x00007f4a811848d9: imul   $0x55555556,%r10,%r10
0x00007f4a811848e0: sar    $0x20,%r10
0x00007f4a811848e4: mov    %r10d,%r11d
0x00007f4a811848e7: sub    %r9d,%r11d         ;*irem
                                              ; - org.sample.JavaBench::isEvenlyDivisible@9 (line 63)
                                              ; - org.sample.JavaBench::isEvenlyDivisible@19 (line 63)
                                              ; - org.sample.JavaBench::run@10 (line 54)

请注意，在 Java 版本中，编译器如何使用将整数余数计算转换为乘法和右移的技巧（参见 Hacker's Delight，第 10 章，第 19 节）。当编译器检测到我们根据常量计算余数时，这是可能的，这表明 Java 版本达到了那个甜蜜的优化，但 Scala 版本没有。您可以深入研究字节码反汇编以找出 scalac 中的哪些怪癖已经介入，但本练习的重点是代码生成中令人惊讶的微小差异被基准放大了很多。

PS 这么多@tailrec...

更新：对效果的更彻底解释：http: //shipilev.net/blog/2014/java-scala-divided-we-fail/

于 2014-03-24T08:20:22.713 回答
23

我改变了val

private val t = 20

到一个常数定义

private final val t = 20

并获得了显着的性能提升，现在看来两个版本的性能几乎相同[在我的系统上，请参阅更新和评论]。

我还没有研究过字节码，但是如果你使用val t = 20你可以看到使用javap有一种方法（并且那个版本和带有 的那个版本一样慢private val）。

所以我假设即使 aprivate val涉及调用一个方法，这也不能与finalJava 中的 a 直接比较。

更新

在我的系统上，我得到了这些结果

Java版本：时间：14725

Scala 版本：时间：13228

在 32 位 Linux 上使用 OpenJDK 1.7。

根据我的经验，Oracle 在 64 位系统上的 JDK 确实表现得更好，所以这可能解释了其他测量产生更好的结果，有利于 Scala 版本。

至于性能更好的 Scala 版本，我假设尾递归优化确实在这里产生了影响（参见 Phil 的回答，如果 Java 版本被重写为使用循环而不是递归，它再次执行同样的操作）。

于 2014-03-22T18:56:59.960 回答
7

我查看了这个问题并编辑了 Scala 版本以包含t在里面run：

object ScalaMain {
  private def run() {
    val t = 20
    var i = 10
    while(!isEvenlyDivisible(2, i, t))
      i += 2
    println(i)
  }

  @tailrec private def isEvenlyDivisible(i: Int, a: Int, b: Int): Boolean = {
    if (i > b) true
    else (a % i == 0) && isEvenlyDivisible(i+1, a, b)
  }

  def main(args: Array[String]) {
    val t1 = System.currentTimeMillis()
    var i = 0
    while (i < 20) {
      run()
      i += 1
    }
    val t2 = System.currentTimeMillis()
    println("time: " + (t2 - t1))
  }
}

新的 Scala 版本现在的运行速度是原始 Java 版本的两倍：

> fsc ScalaMain.scala
> scala ScalaMain
....
time: 6373
> fsc -optimize ScalaMain.scala
....
time: 4703

我发现这是因为 Java 没有尾调用。使用循环而不是递归的优化 Java 运行速度同样快：

public class JavaMain {
    private static final int t = 20;

    private void run() {
        int i = 10;
        while (!isEvenlyDivisible(i, t))
            i += 2;
        System.out.println(i);
    }

    private boolean isEvenlyDivisible(int a, int b) {
        for (int i = 2; i <= b; ++i) {
            if (a % i != 0)
                 return false;
        }
        return true;
    }

    public static void main(String[] args) {
        JavaMain o = new JavaMain();
        long t1 = System.currentTimeMillis();
        for (int i = 0; i < 20; ++i)
            o.run();
        long t2 = System.currentTimeMillis();
        System.out.println("time: " + (t2 - t1));
    }
}

现在我的困惑完全解决了：

> java JavaMain
....
time: 4795

总之，最初的 Scala 版本很慢，因为我没有声明（t直接final或间接地，正如Beryllium的回答所指出的那样）。由于缺少尾调用，原始 Java 版本运行缓慢。

于 2014-03-22T19:16:34.297 回答
1

要使 Java 版本完全等同于您的 Scala 代码，您需要像这样进行更改。

private int t = 20;


private int t() {
    return this.t;
}

private void run() {
    int i = 10;
    while (!isEvenlyDivisible(2, i, t()))
        i += 2;
    System.out.println(i);
}

它比较慢，因为 JVM 无法优化方法调用。

于 2014-03-22T19:05:53.020 回答