Why is a simple Scala tailrec loop for calculating fibonacci 3 times faster than a Java loop?

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 

result 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 

result 17444340.812 ± 9508030.117 ops/s :

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

Yes, it depends on the environment parameters (JDK version, processor model and RAM frequency) and dynamic state. But why can basically the same bytecode in the same environment create a stable 2x-3x difference for a range of function arguments?

Here is a list of ops / s numbers for different values ​​of the function arguments from my laptop with an Intel (R) Core (TM) i7-2640M processor with a frequency of 2.80 GHz (max. 3.50 GHz), 12 Gb RAM DDR3-1333, Ubuntu 14.10 , Oracle JDK 1.8.0_40-b25 64-bit:

 [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 

Additional question: "Why do ops / s values ​​decrease non-linearly as described above?"

Answer 1

Yes, I made a mistake and missed this proven method not only fastLoop calls:

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

As Alexey noted, a lot of time was spent in conversions from Long/long to BigInt/BigInteger .

I wrote separate tests that only check the fastLoop(n, 0, 1) call. Here are the results from them:

 [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 

Lessons I Learned:

• Scala implicits can eat a lot of performance, while they are easy to overlook;

• Compressing BigInt values ​​in Scala can speed up some functions compared to Java BigInteger.