百科问答小站 logo
百科问答小站 font logo
首页



为什么下面程序递归计算斐波那契数列java比c++要快？ 第1页

  1 

user avatar   rednaxelafx 网友的相关建议: 
      

前面已有的回答一个都没答到点上啊。

（就跟其他答主提到的一样，题主的电脑似乎有点慢…）

其实这个例子反映出来的跟Java与C++语言上的差异没有任何关系，只是反映出了在这个特定例子上某个编译器（及JIT编译器）的优化的差异。

本文后面用到的编译器生成的代码的样子我都记录下来放在这个传送门了，欢迎参考：

gist.github.com/rednaxe

这个例子的重点是函数调用次数特别高，而每次调用在函数内部做的事情特别少，所以比拼的是降低函数调用开销——要么减少未内联的函数调用次数，要么让函数调用自身的开销减少。

题主只给出了测试代码，没有说明测试性能用的环境（后来补充说C++编译器是VS2015里的MSVC）。从截图看至少可知是Windows上做的测试 ，但看不出来C++版本所使用的编译器是哪个；Java的话想来应该是用的Oracle JDK的某个版本，所以Java代码是在HotSpot VM上运行的。

这里根据题主给的例子来给出一组对比用的测试代码：

（拜托题主（们）以后请直接贴代码的文本，不要只贴截图）

C++版本：fib.cc

       #include <ctime> #include <iostream>  using namespace std;  int o = 0;  int fib(int a) {   o++;   return a <= 2 ? 1 : fib(a - 1) + fib(a - 2); }  clock_t to_duration_in_ms(clock_t start, clock_t end) {   return 1000 * (end - start) / CLOCKS_PER_SEC; }  int main() {   int n;    cin >> n;    clock_t start = clock();   int answer = fib(n);   clock_t end = clock();    cout << answer << ", run time: " << to_duration_in_ms(start, end) << "ms, repeat times: " << o << endl;    return 0; }

Java版本：Fib.java

       import java.util.*;  public class Fib {   static int o = 0;    public static void main(String[] args) {     Scanner in = new Scanner(System.in);     int n = in.nextInt();     long start = System.currentTimeMillis();     int answer = fib(n);     long end = System.currentTimeMillis();     System.out.printf("%d, run time: %dms, repeat times: %d
", answer, (end - start), o);   }    public static int fib(int a) {     o++;     return a <= 2 ? 1 : fib(a - 1) + fib(a - 2);   } }

这里C++版与Java版的 fib(int) 函数的语义是基本一样的，并不会体现出语言层面的语义差异。

事实上Java的 int 跟C/C++的 int32_t 是基本一样的，唯一的差别就是Java的 int 在算术运算溢出的时候有明确规定要用signed wrapping语义，而C/C++的 int / int32_t 在算术溢出时则是undefined behavior。

这里两个版本的测试剩下的一个差异就是，Java版由JVM规范规定说要在方法调用即将导致栈溢出的时候要抛出StackOverflowException，所以大部分JVM都会在方法入口处做一些检查，所以即便方法的内容相同，JVM的JIT编译器给这个Java版 fib(int) 生成的机器码也可能会比C++版代码被编译后生成的机器码要在方法入口处多一丁点代码。

然后有些JVM通过safepoint polling方式来实现VM对Java线程的暂停（例如stop-the-world）的功能，例如HotSpot VM至少会在所有JIT编译后代码的返回处添加safepoint polling来保证在VM需要暂停Java线程时，Java线程可以及时响应。这里又会多一丁点代码。

除此之外就没有任何差异了。Java的静态方法的调用语义跟C/C++的非虚函数的调用语义并没有显著差异，如果由同样优化的编译器来编译的话，就会得到同样级别性能的代码。

在Mac OS X 10.9上分别用Oracle JDK8u101和Clang 3.5 -O2来测试，两边用的编译命令分别为：

       $ clang++ -O2 fib.cc $ javac Fib.java

然后运行各自运行5次的结果：

C++：

       $ ./a.out 40 102334155, run time: 426ms, repeat times: 204668309 $ ./a.out 40 102334155, run time: 420ms, repeat times: 204668309 $ ./a.out 40 102334155, run time: 418ms, repeat times: 204668309 $ ./a.out 40  102334155, run time: 410ms, repeat times: 204668309 $ ./a.out 40 102334155, run time: 432ms, repeat times: 204668309

（使用同版本Clang用 clang++ -O3 fib.cc 来编译的话，测试时间结果在完全相同的范围。这是因为这个版本的Clang在-O2和-O3下编译这个程序得到的是完全一样的代码。）

Java：

       $ java Fib 40 102334155, run time: 357ms, repeat times: 204668309 $ java Fib 40 102334155, run time: 323ms, repeat times: 204668309 $ java Fib 40 102334155, run time: 319ms, repeat times: 204668309 $ java Fib 40 102334155, run time: 325ms, repeat times: 204668309 $ java Fib 40 102334155, run time: 341ms, repeat times: 204668309

有同学好奇多跑一会儿的话会怎样。那我们就在同一环境运行同一测试对比一下 fib(n = 46) 的情况：

       $ java Fib 46 1836311903, run time: 6423ms, repeat times: -622343491 $ java Fib 46 1836311903, run time: 5815ms, repeat times: -622343491 $ java Fib 46 1836311903, run time: 6063ms, repeat times: -622343491  $ clang++ -O3 zz.cc $ ./a.out 46 1836311903, run time: 7442ms, repeat times: -622343491 $ ./a.out 46 1836311903, run time: 7392ms, repeat times: -622343491 $ ./a.out 46 1836311903, run time: 7379ms, repeat times: -622343491

（是的，repeat times已经溢出了，但这里我们先不管它）

尴尬？顺带在我的环境上就算用最新的Clang 5.0 svn-trunk也是这样的。

可以看到Java版确实更快一些。这里没有“作弊”的因素，双方也都开启了编译器优化，并没有说一方因为是debug版本编译而影响了优化选项。

在上述的测试环境中，Java版本的 fib(int) 方法一开始由HotSpot VM的解释器解释执行，经过若干次调用之后会被JIT编译为机器码来执行。由于这里计算Fibonacci数列所用的是最直观的递归算法，调用次数会非常高，因而很快就会达到JIT编译的条件进而触发JIT编译。

在 fib(n = 40) 的用例中，这个测试程序只会有很小部分时间在解释器里执行，而绝大部分时间都在JIT编译优化过的代码中执行。所以它正好规避了一般Java程序在启动时有很大部分时间耗在解释器里使得启动慢的状况，而跟C++版的代码基本上在同一起跑线上——拼编译器优化。

在这个测试环境中，Java版本的 fib(int) 最终会被HotSpot VM的Server Compiler（“C2”）所编译。这是一个还算优化的编译器，它的优化程度大致上能跟GCC、Clang的-O2相似（或略弱于GCC / Clang）。

C2并不会做尾调用（tail call）或者尾递归（tail recursion）优化，但是它默认可以对递归调用的方法做1层递归内联。在这里具体来说就是会把一层 fib(a - 1) 与 fib(a - 2) 给内联进来。所以经过它的优化后，实际被编译出来的 fib(int) 代码是类似这样的：

         public static int fib(int a) {     ++o;     if (a <= 2) return 1;      int result;      // inlined fib(a - 1)     ++o;     if ((a - 1) <= 2) {       result = 1;     } else {       result = fib(a - 2) + fib(a - 3);     }      // inlined fib(a - 2)     ++o;     if ((a - 2) <= 2) {       result += 1;     } else {       result += fib(a - 3) + fib(a - 4);     }      return result;   }

这样比起原本的代码就大幅度降低了未内联方法的调用次数，从而正中靶心降低了这个测试用例里最大头的开销。

而C++版的测试环境中，Clang 3.5在-O2级别上做的优化是：把两个对 fib(int) 的递归调用的其中一个当作尾调用并做优化，另一个仍然实现为递归调用。重要：Clang+LLVM是不会对递归函数做递归内联的，一层都不会内联，但它可以做尾调用 / 尾递归优化。这个具体用例优化后的代码是类似这样的：

       int fib(int a) {   ++o;   int result = 1;   while (a > 2) {     result += fib(a - 1);     a -= 2;     ++o;   }   return result; }

这是个相当简洁漂亮的形式，它可以看作是把 fib(a) = fib(a - 1) + fib(a - 2) 中的 fib(a - 2) 部分当作尾递归（于是就消除了这个调用，变为内联的循环形式），而保留 fib(a - 1) 为未内联的函数调用。

可惜这个形式在这个具体例子上性能却不如前面C2编译出来的版本好。让我们来对比一下两个优化后版本的代码的实际未内联调用次数的情况。下面给出的两列数据，左边是该次调用自身调用未内联函数的次数，右边是该次调用总共引起的未内联函数调用的次数。

Java版经过C2编译后：

       fib(1) = 0 calls / 0 calls fib(2) = 0 calls / 0 calls fib(3) = 0 calls / 0 calls fib(4) = 2 calls / 2 calls fib(5) = 4 calls / 4 calls fib(6) = 4 calls / 6 calls fib(7) = 4 calls / 12 calls fib(8) = 4 calls / 20 calls fib(9) = 4 calls / 32 calls fib(10) = 4 calls / 54 calls fib(11) = 4 calls / 88 calls fib(12) = 4 calls / 142 calls fib(13) = 4 calls / 232 calls fib(14) = 4 calls / 376 calls fib(15) = 4 calls / 608 calls fib(16) = 4 calls / 986 calls fib(17) = 4 calls / 1596 calls fib(18) = 4 calls / 2582 calls fib(19) = 4 calls / 4180 calls fib(20) = 4 calls / 6764 calls fib(21) = 4 calls / 10944 calls fib(22) = 4 calls / 17710 calls fib(23) = 4 calls / 28656 calls fib(24) = 4 calls / 46366 calls fib(25) = 4 calls / 75024 calls fib(26) = 4 calls / 121392 calls fib(27) = 4 calls / 196416 calls fib(28) = 4 calls / 317810 calls fib(29) = 4 calls / 514228 calls fib(30) = 4 calls / 832038 calls fib(31) = 4 calls / 1346268 calls fib(32) = 4 calls / 2178308 calls fib(33) = 4 calls / 3524576 calls fib(34) = 4 calls / 5702886 calls fib(35) = 4 calls / 9227464 calls fib(36) = 4 calls / 14930350 calls fib(37) = 4 calls / 24157816 calls fib(38) = 4 calls / 39088168 calls fib(39) = 4 calls / 63245984 calls fib(40) = 4 calls / 102334154 calls

C++版经过 Clang 3.5 -O2 编译后：

       fib(1) = 0 calls / 0 calls fib(2) = 0 calls / 0 calls fib(3) = 1 calls / 1 calls fib(4) = 1 calls / 2 calls fib(5) = 2 calls / 4 calls fib(6) = 2 calls / 7 calls fib(7) = 3 calls / 12 calls fib(8) = 3 calls / 20 calls fib(9) = 4 calls / 33 calls fib(10) = 4 calls / 54 calls fib(11) = 5 calls / 88 calls fib(12) = 5 calls / 143 calls fib(13) = 6 calls / 232 calls fib(14) = 6 calls / 376 calls fib(15) = 7 calls / 609 calls fib(16) = 7 calls / 986 calls fib(17) = 8 calls / 1596 calls fib(18) = 8 calls / 2583 calls fib(19) = 9 calls / 4180 calls fib(20) = 9 calls / 6764 calls fib(21) = 10 calls / 10945 calls fib(22) = 10 calls / 17710 calls fib(23) = 11 calls / 28656 calls fib(24) = 11 calls / 46367 calls fib(25) = 12 calls / 75024 calls fib(26) = 12 calls / 121392 calls fib(27) = 13 calls / 196417 calls fib(28) = 13 calls / 317810 calls fib(29) = 14 calls / 514228 calls fib(30) = 14 calls / 832039 calls fib(31) = 15 calls / 1346268 calls fib(32) = 15 calls / 2178308 calls fib(33) = 16 calls / 3524577 calls fib(34) = 16 calls / 5702886 calls fib(35) = 17 calls / 9227464 calls fib(36) = 17 calls / 14930351 calls fib(37) = 18 calls / 24157816 calls fib(38) = 18 calls / 39088168 calls fib(39) = 19 calls / 63245985 calls fib(40) = 19 calls / 102334154 calls

可以看到在未内联函数的总调用次数上，两个版本在过程中是几乎一样的，在 fib(n = 40) 的用例中是正好一样。但C2版的代码只有函数调用而没有循环，而Clang版代码则在函数调用之外还有循环的开销，这么一加上去后者的开销就比前者大，造成了题主看到的“C++比Java慢”的现象。

如果我们模拟C2的优化方式，人肉把C++的测试代码改为：

       __attribute__((__noinline__)) int fib(int a) {   ++o;   if (a <= 2) return 1;    int result;    // emulate inlining fib(a - 1)   ++o;   if ((a - 1) <= 2) {     result = 1;   } else {     result = fib(a - 2) + fib(a - 3);   }    // emulate inlining fib(a - 2)   ++o;   if ((a - 2) <= 2) {     result += 1;   } else {     result += fib(a - 3) + fib(a - 4);   }    return result; }

同样用 Clang 3.5 -O2 来编译，在我的机器上运行的结果就变成：

       $ ./a.out 40 102334155, run time: 333ms, repeat times: 204668309 $ ./a.out 40 102334155, run time: 341ms, repeat times: 204668309 $ ./a.out 40 102334155, run time: 347ms, repeat times: 204668309 $ ./a.out 40 102334155, run time: 327ms, repeat times: 204668309 $ ./a.out 40 102334155, run time: 332ms, repeat times: 204668309

跟Java版测试的结果就几乎一样了。

顺带一题，MSVC编译器在/Ox（打开所有优化）的情况下对本文开头的C++版 fib(int) 函数也没做多少优化，既没有做递归内联也没有做尾递归优化，所以经过它编译后的代码仍然后 fib(a) = fib(a - 1) + fib(a - 2) 这样的代码结构，未内联函数调用的次数就跟代码中全局变量“o”的值一样多。

然后，GCC在-O2级别上生成的代码跟上面演示的 Clang 3.5 -O2 的形式基本上是一样的，性能自然也差不多。

GCC 7 -O2在Linux/x86-64上生成的代码是这样的：

       int foo(int a) {   ++o;   if (a <= 2) return 1;      int limit = (a - 3) & 1;   --a;   int result = 0;    while (a != limit) {     result += fib(a);     a -= 2;     ++o;   }    return result + 1; }

是不是跟前面举例的Clang 3.5 -O2非常相似？

而GCC在-O3级别生成的代码则复杂许多，会做多层展开，可以进一步提高性能。

它做的优化反映在这个例子上，主要是：既像C2那样做的内联展开，又非常聪明地做了尾递归优化，还能够智能地发现内联后多次调用诸如 fib(a - 3) 应该得到相同的结果于是进行了合并，最后它还大幅减少了更新全局变量o所需要的内存写操作，而是把o的中间值都放在寄存器里，最后再一口气把最终o应有的值写回内存。

我在另一个测试环境，一台Skylake服务器上用本文开头原始版本的C++版 fib(int) 用GCC 5.4测试，分别以-O2 / -O3来编译，结果如下：

       $ g++ -O2 fib.cc $ ./a.out  40 102334155, run time: 390ms, repeat times: 204668309 $ ./a.out  40 102334155, run time: 357ms, repeat times: 204668309 $ ./a.out  40 102334155, run time: 388ms, repeat times: 204668309 $ g++ -O3 fib.cc $ ./a.out  40 102334155, run time: 189ms, repeat times: 204668309 $ ./a.out  40 102334155, run time: 194ms, repeat times: 204668309 $ ./a.out  40 102334155, run time: 191ms, repeat times: 204668309

在同一环境中用Oracle JDK8u25来运行本文最初的Java版代码：

       $ ~/sdk/jdk1.8.0_25/bin/java Fib 40 102334155, run time: 375ms, repeat times: 204668309 $ ~/sdk/jdk1.8.0_25/bin/java Fib 40 102334155, run time: 378ms, repeat times: 204668309 $ ~/sdk/jdk1.8.0_25/bin/java Fib 40 102334155, run time: 376ms, repeat times: 204668309

群众喜闻乐见的C++比Java快又回来了（误

（重要提醒：这里仍然只是反映了GCC 5.4 -O3比HotSpot C2更加优化而已，跟C++与Java的语言差异没有任何关系）

再更新一点。如果我想让这个Java版的“成绩”再稍微提高那么一丁点，只要加两行代码就好：

       import java.util.*;  public class Fib {   static int o = 0;    public static void main(String[] args) {     Scanner in = new Scanner(System.in);     int n = in.nextInt();     fib(n);   // add this line     o = 0;    // and add this line     long start = System.currentTimeMillis();     int answer = fib(n);     long end = System.currentTimeMillis();     System.out.printf("%d, run time: %dms, repeat times: %d
", answer, (end - start), o);   }    public static int fib(int a) {     o++;     return a <= 2 ? 1 : fib(a - 1) + fib(a - 2);   } }

在跟上面相同的我的Mac上用JDK8u101来跑：

       $ java Fib 40 102334155, run time: 313ms, repeat times: 204668309 $ java Fib 40 102334155, run time: 321ms, repeat times: 204668309 $ java Fib 40 102334155, run time: 320ms, repeat times: 204668309 $ java Fib 40 102334155, run time: 331ms, repeat times: 204668309 $ java Fib 40 102334155, run time: 327ms, repeat times: 204668309 $ java Fib 40 102334155, run time: 319ms, repeat times: 204668309

对HotSpot VM的执行方式有一定了解的同学肯定一下就能明白这么做的意图是什么，所以就不多写，留作习题吧 ^_^

就这样嗯。
为什么下面程序递归计算斐波那契数列java比c++要快？ 的其他答案 点击这里
  1 

相关话题

  Java 中接口为什么可以调用 toString 方法，接口中根本就没有 toString 方法？ 
  编程那么难，为什么不弄一个大众一学就会的计算机语言呢? 
  异常处理(exception handling)和错误处理（error handling）有什么区别？ 
  C# 和 Java 哪个更像 C++？ 
  天天P图中我的小学生证件照功能怎么实现的？算法是什么样？ 
  Java里面的封装是不是多此一举？ 
  变量名用中文的优缺点? 
  C#中函数中参数问题？ 
  知乎上三位大牛“温赵轮”有什么离奇的身世？ 
  你在 GitHub 上看到过的最有意思的项目是什么？ 
前一个讨论
怎么反驳汉族血统不纯论？
下一个讨论
vector 使用 emplace_back 会调用复制构造函数吗?



服务条款
联系我们
关于我们
隐私政策


© 2024-09-27 - tinynew.org. All Rights Reserved.
© 2024-09-27 - tinynew.org. 保留所有权利