Perché il semplice ciclo di coda di Scala per il calcolo di Fibonacci è più veloce in 3 volte rispetto al ciclo di Java?

Question

Scala

codice:

@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 

risultato è 53879289.462 ± 6289454.961 ops/s:

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

Java

codice:

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 

risultato è 17444340.812 ± 9508030.117 ops/s:

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

Sì, dipende dall'ambiente param eters (versione JDK, modello CPU & frequenza RAM) e stato dinamico. Ma perché lo stesso bytecode nello stesso ambiente è in grado di produrre una differenza 2x-3x stabile per gli argomenti della gamma di funzioni?

Ecco l'elenco dei numeri ops/s per i diversi valori degli argomenti delle funzioni dal mio notebook con Intel (R) Core (TM) i7-2640M CPU @ 2,80 GHz (max 3,50 GHz), RAM 12 Gb DDR3-1333, Ubuntu 14.10, Oracle JDK 1.8.0_40-b25 a 64 bit: "perché i valori di OPS/s stanno diminuendo in modo non lineare come sopra"

[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 

domanda supplementare è

Answer 1

Sì, mi sbagliavo, e perse quel metodo testato non solo fastLoop chiamate era:

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)); 
    } 

Come Aleksey notato molta il tempo trascorso nelle conversioni da Long/long a BigInt/BigInteger.

Ho scritto benchmark separati che verifica solo la chiamata fastLoop(n, 0, 1).Ecco i risultati da loro:

[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 

lezioni che ho imparato:

• Scala impliciti possono mangiare sacco di prestazioni, mentre sono facili da essere trascurato;

• L'incasso di valori BigInt in Scala può velocizzare alcune funzioni rispetto a BigInteger di Java.