Warum ist die einfache Scala-Rücklaufschleife für die Fibonacci-Berechnung dreimal schneller als die Java-Schleife?

Question

Scala

Code:

@annotation.tailrec 
private def fastLoop(n: Int, a: Long = 0, b: Long = 1): Long = 
    if (n > 1) fastLoop(n - 1, b, a + b) else b 

Bytecode:

private long fastLoop(int, long, long); 
    Code: 
     0: iload_1 
     1: iconst_1 
     2: if_icmple  21 
     5: iload_1 
     6: iconst_1 
     7: isub 
     8: lload   4 
     10: lload_2 
     11: lload   4 
     13: ladd 
     14: lstore  4 
     16: lstore_2 
     17: istore_1 
     18: goto   0 
     21: lload   4 
     23: lreturn 

Ergebnis ist 53879289.462 ± 6289454.961 ops/s:

https://travis-ci.org/plokhotnyuk/scala-vs-java/jobs/56117116#L2909

Java

Code:

private long fastLoop(int n, long a, long b) { 
    while (n > 1) { 
     long c = a + b; 
     a = b; 
     b = c; 
     n--; 
    } 
    return b; 
} 

Bytecode:

private long fastLoop(int, long, long); 
    Code: 
     0: iload_1 
     1: iconst_1 
     2: if_icmple  24 
     5: lload_2 
     6: lload   4 
     8: ladd 
     9: lstore  6 
     11: lload   4 
     13: lstore_2 
     14: lload   6 
     16: lstore  4 
     18: iinc   1, -1 
     21: goto   0 
     24: lload   4 
     26: lreturn 

Ergebnis ist 17444340.812 ± 9508030.117 ops/s:

https://travis-ci.org/plokhotnyuk/scala-vs-java/jobs/56117116#L2881

Ja, es hängt von der Umgebung param eters (JDK-Version, CPU-Modell & Frequenz des RAM) und dynamischen Zustand. Aber warum kann der gleiche Bytecode in der gleichen Umgebung eine stabile 2x-3x Differenz für einen Bereich von Funktionsargumenten erzeugen?

Hier ist eine Liste von ops/s Zahlen für verschiedene Werte von Funktionen Argumente von meinem Notebook mit Intel (R) Core (TM) i7-2640M CPU @ 2.80GHz (max 3.50GHz), RAM 12 GB DDR3-1333, Ubuntu 14.10, Oracle JDK 1.8.0_40-b25 64-Bit: "warum Werte von ops/s wie oben in nicht-linearer Weise abnehmen"

[info] Benchmark   (n) Mode Cnt   Score   Error Units 
[info] JavaFibonacci.loop  2 thrpt 5 171776163.027 ± 4620419.353 ops/s 
[info] JavaFibonacci.loop  4 thrpt 5 144793748.362 ± 25506649.671 ops/s 
[info] JavaFibonacci.loop  8 thrpt 5 67271848.598 ± 15133193.309 ops/s 
[info] JavaFibonacci.loop 16 thrpt 5 54552795.336 ± 17398924.190 ops/s 
[info] JavaFibonacci.loop 32 thrpt 5 41156886.101 ± 12905023.289 ops/s 
[info] JavaFibonacci.loop 64 thrpt 5 24407771.671 ± 4614357.030 ops/s 
[info] ScalaFibonacci.loop 2 thrpt 5 148926292.076 ± 23673126.125 ops/s 
[info] ScalaFibonacci.loop 4 thrpt 5 139184195.527 ± 30616384.925 ops/s 
[info] ScalaFibonacci.loop 8 thrpt 5 109050091.514 ± 23506756.224 ops/s 
[info] ScalaFibonacci.loop 16 thrpt 5 81290743.288 ± 5214733.740 ops/s 
[info] ScalaFibonacci.loop 32 thrpt 5 38937420.431 ± 8324732.107 ops/s 
[info] ScalaFibonacci.loop 64 thrpt 5 22641295.988 ± 5961435.507 ops/s 

Zusätzliche Frage

Answer 1

Ja, ich war falsch, und verpasste das bewährte Methode nicht nur fastLoop Anrufe war:

Scala

@Benchmark 
    def loop(): BigInt = 
    if (n > 92) loop(n - 91, 4660046610375530309L, 7540113804746346429L) 
    else fastLoop(n) 

Java

@Benchmark 
    public BigInteger loop() { 
     return n > 92 ? 
       loop(n - 91, BigInteger.valueOf(4660046610375530309L), BigInteger.valueOf(7540113804746346429L)) : 
       BigInteger.valueOf(fastLoop(n, 0, 1)); 
    } 

Wie Aleksey viel bemerkt von Zeit wurde in Konvertierungen von Long/long zuverbracht.

Ich habe separate Benchmarks geschrieben, die nur fastLoop(n, 0, 1) Aufruf testen.Hier sind Ergebnisse von ihnen:

[info] JavaFibonacci.fastLoop  2 thrpt 5 338071686.910 ± 66146042.535 ops/s 
[info] JavaFibonacci.fastLoop  4 thrpt 5 231066635.073 ± 3702419.585 ops/s 
[info] JavaFibonacci.fastLoop  8 thrpt 5 174832245.690 ± 36491363.939 ops/s 
[info] JavaFibonacci.fastLoop 16 thrpt 5 95162799.968 ± 16151609.596 ops/s 
[info] JavaFibonacci.fastLoop 32 thrpt 5 60197918.766 ± 10662747.434 ops/s 
[info] JavaFibonacci.fastLoop 64 thrpt 5 29564087.602 ± 3610164.011 ops/s 
[info] ScalaFibonacci.fastLoop 2 thrpt 5 336588218.560 ± 56762496.725 ops/s 
[info] ScalaFibonacci.fastLoop 4 thrpt 5 224918874.670 ± 35499107.133 ops/s 
[info] ScalaFibonacci.fastLoop 8 thrpt 5 121952667.394 ± 17314931.711 ops/s 
[info] ScalaFibonacci.fastLoop 16 thrpt 5 96573968.960 ± 12757890.175 ops/s 
[info] ScalaFibonacci.fastLoop 32 thrpt 5 59462408.940 ± 14924369.138 ops/s 
[info] ScalaFibonacci.fastLoop 64 thrpt 5 28922994.377 ± 7209467.197 ops/s 

Lektionen, die ich gelernt:

• Scala implicits kann viel Leistung essen, während leicht übersehen zu werden;

• Das Einsparen von BigInt-Werten in Scala kann einige Funktionen im Vergleich zum Java-BigInteger beschleunigen.