为什么用于斐波那契计算的简单Scala tailrec循环比Java循环快3倍
发布时间：2020-12-16 18:47:11 所属栏目：安全 来源：网络整理
导读：斯卡拉 码： @annotation.tailrecprivate def fastLoop(n: Int,a: Long = 0,b: Long = 1): Long = if (n 1) fastLoop(n - 1,b,a + b) else b 字节码： private long fastLoop(int,long,long); Code: 0: iload_1 1: iconst_1 2: if_icmple 21 5: iload_1 6: i
|
斯卡拉
码： @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 字节码： 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
结果是53879289.462±6289454.961 ops / s： https://travis-ci.org/plokhotnyuk/scala-vs-java/jobs/56117116#L2909 Java的 码： private long fastLoop(int n,long a,long b) {
while (n > 1) {
long c = a + b;
a = b;
b = c;
n--;
}
return b;
}
字节码： private long fastLoop(int,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
结果是17444340.812±9508030.117 ops / s： https://travis-ci.org/plokhotnyuk/scala-vs-java/jobs/56117116#L2881 是的,它取决于环境参数(JDK版本,CPU型号和RAM的频率)和动态.但是为什么在同一环境中大多数相同的字节码可以为函数参数范围产生稳定的2x-3x差异？ 以下是我的笔记本电脑的不同功能参数值的操作数字列表,其中包括Intel(R)Core(TM)i7-2640M CPU @ 2.80GHz(最大3.50GHz),RAM 12Gb DDR3-1333,Ubuntu 14.10,Oracle JDK 1.8.0_40-b25 64位： [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 另外一个问题是“为什么ops / s的值如上所述以非线性方式递减？” 解决方法
是的,我错了,错过了测试方法不仅仅是fastLoop调用：
斯卡拉 @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,1));
}
正如Aleksey所指出的那样,很多时间花在从Long / long到BigInt / BigInteger的转换上. 我编写了单独的基准测试,只测试fastLoop(n,1)调用.以下是他们的结果： [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 我学到的经验教训： > Scala暗示可以吃很多性能,但很容易被忽视;>与Java的BigInteger相比,Scala中的BigInt值的兑现可以加速某些功能. （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |