Скрытая производительность в Scala?

Ответ 1

Ну, бенчмаркинг OP не является идеальным. Тонны эффектов должны быть смягчены, включая разминку, удаление мертвого кода, разветвление и т.д. К счастью, JMH уже позаботится о многом, и имеет привязки для Java и Scala. Пожалуйста, следуйте процедурам на странице JMH, чтобы получить контрольный проект, затем вы можете пересадить контрольные показатели ниже.

Это пример теста 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::[email protected] (line 52)
                                               ; - org.sample.ScalaBench::[email protected] (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::[email protected] (line 63)
                                              ; - org.sample.JavaBench::[email protected] (line 63)
                                              ; - org.sample.JavaBench::[email protected] (line 54)

Обратите внимание, что в версии Java компилятор использовал трюк для перевода вычисления целочисленного остатка в умножение и смещение вправо (см. Hacker Delight, глава 10, раздел 19). Это возможно, когда компилятор обнаруживает, что мы вычисляем остаток по отношению к константе, что предполагает, что версия Java поражает эту слабую оптимизацию, но версия Scala не указала. Вы можете разобраться в разборке байт-кода, чтобы выяснить, какие причуды в scalac вмешались, но суть этого упражнения в том, что удивительные небольшие различия в генерации кода значительно увеличиваются с помощью тестов.

P.S. Так много для @tailrec...

UPDATE: более подробное объяснение эффекта: http://shipilev.net/blog/2014/java-scala-divided-we-fail/

Ответ 2

Я изменил val

private val t = 20

к постоянному определению

private final val t = 20

и получил значительное повышение производительности, теперь кажется, что обе версии работают почти одинаково [в моей системе, см. обновление и комментарии].

Я не изучал байт-код, но если вы используете val t = 20, вы можете использовать javap, чтобы существовал метод (и эта версия была такой же медленной, как и с private val).

Поэтому я предполагаю, что даже a private val включает вызов метода и тот, который напрямую не сопоставляется с final в Java.

Обновление

В моей системе я получил эти результаты

Java-версия: время: 14725

Scala версия: время: 13228

Использование OpenJDK 1.7 в 32-разрядной Linux.

По моему опыту Oracle JDK в 64-битной системе действительно работает лучше, поэтому это, вероятно, объясняет, что другие измерения дают еще лучшие результаты в пользу версии Scala.

Что касается улучшения версии Scala, я предполагаю, что оптимизация хвостовой рекурсии имеет здесь эффект (см. ответ Фила, если версия Java переписана для использования цикла вместо рекурсии, она выполняет одинаково снова).

Ответ 3

Я просмотрел этот вопрос и отредактировал версию 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 была медленной из-за отсутствия хвостовых вызовов.

Ответ 4

Чтобы сделать версию 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 не может оптимизировать вызовы методов.