为什么下面程序递归计算斐波那契数列java比c++要快？ 第1页
1
rednaxelafx 网友的相关建议:
前面已有的回答一个都没答到点上啊。
（就跟其他答主提到的一样，题主的电脑似乎有点慢…）
其实这个例子反映出来的跟Java与C++语言上的差异没有任何关系，只是反映出了在这个特定例子上某个编译器（及JIT编译器）的优化的差异。
本文后面用到的编译器生成的代码的样子我都记录下来放在这个传送门了，欢迎参考：
https:// gist.github.com/rednaxe lafx/e4fb905718d7fbb3c8b1a0ecf94c84f0这个例子的重点是函数调用次数特别高，而每次调用在函数内部做的事情特别少，所以比拼的是降低函数调用开销——要么减少未内联的函数调用次数，要么让函数调用自身的开销减少。
题主只给出了测试代码，没有说明测试性能用的环境（后来补充说C++编译器是VS2015里的MSVC）。从截图看至少可知是Windows上做的测试 ，但看不出来C++版本所使用的编译器是哪个；Java的话想来应该是用的Oracle JDK的某个版本，所以Java代码是在HotSpot VM上运行的。
这里根据题主给的例子来给出一组对比用的测试代码：
（拜托题主（们）以后请直接贴代码的文本，不要只贴截图）
C++版本：http://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 http://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的执行方式有一定了解的同学肯定一下就能明白这么做的意图是什么，所以就不多写，留作习题吧 ^_^
就这样嗯。
1
相关话题
你写代码的起手式是什么样的？Qt 真的比 Java 更加跨平台吗？
编程教育以后会成为一门通识教育吗？
[题]两个数的最小公倍数是36，最大公因数是6，这两个数可能是多少？
你在阅读源代码或设计文档时，看到哪些惊艳的技巧？
老程序员解 bug 有哪些通用套路？
计算机行业是不是自砸饭碗的行业？
在计算机科学领域，为何不使用拼音代替英文做为关键字?
程序员开发进度太慢被公司告上法庭，索赔 90 万，如何评价该公司的这种行为？
怎样衡量一个机器学习工程师对算法的掌握程度？
前一个讨论
相关的话题
java设计request body为什么设计成只允许读取一次???大型项目中面向过程思想 vs 面向对象思想，哪种开发效率更高？
2019年，程序员眼中最好的互联网公司是哪些家？
为什么 Java 只有值传递，但 C# 既有值传递，又有引用传递，这种语言设计有哪些好处？
谁能最简单的详解椭圆曲线算法，secp256k1 是如何生成公钥和私钥的？
如何理解动态规划？
为什么程序代码被编译成机器码就不能跨平台运行？
GitHub 上有些什么好玩的项目？
为什么C++的 extern "C" 里面可以使用C里面不存在的STL和引用&等C++才有的特性 ?
请各位前辈指导下简练代码的思路？
Java 为什么不采用 360 垃圾清理来进行垃圾回收呢？
Qt 为什么在桌面应用（Windows 平台）中不流行呢？
可以在非中文的网站使用中文吗？
C++中开多个数组和用struct封装起来哪个速度更快？
一些编程机构把编程课送到山区里了，你们觉得有没有必要让边远山区孩子体验学编程？
程序员讲到底就是”增删改查“吗？
如何评价CSDN？
lua这种的违反直觉的用法怎么理解?
何时使用 Protected 继承？
不同语言代码量大致换算？
为什么大部分程序员都喜欢用黑色界面？
如何把一段简单的代码变复杂？
Windows 的路径中表示文件层级为什么会用反斜杠 “”，而 UNIX 系统都用斜杠 “/”？
在Auto ML的冲击下，ML算法人员是否会在前者成熟后失业的情况？
C++的move构造是否是设计失败的？
字节跳动面试难吗，应该如何应对？
如何评价《鸟哥的Linux私房菜》说BSD和GPL很类似以及Windows不跨处理器架构等内容？
如何理解 Golang 中“不要通过共享内存来通信，而应该通过通信来共享内存”？
救救编程小白，请告诉我如何学编程？怎么入门啊？
一个Java的对象大小等于序列化的大小吗？