3 ms·

So... before looking at the code, I compared the elapsed time between the fib.rs program compiled with `rustc -O` and `rustc -O -C lto`. This yielded, interesti

So... before looking at the code, I compared the elapsed time between the fib.rs program compiled with `rustc -O` and `rustc -O -C lto`. This yielded, interestingly, a ~500ms difference: ~6.45s vs ~6.95s (with LTO winning). Then I looked at the code, and it began to make no sense. Then I looked at the assembly, and it made even less sense: the main function, fib::fib, which is where the vast majority of the time is spent, is identical, except for addresses. I was starting to think, well, this might be related to instruction-cache lines... and it looks like it's not that: $ perf stat ./fib-lto 2971215073 Performance counter stats for './fib': 6474.410894 task-clock (msec) # 1.000 CPUs utilized 17 context-switches # 0.003 K/sec 0 cpu-migrations # 0.000 K/sec 112 page-faults # 0.017 K/sec 22,607,598,238 cycles # 3.492 GHz 55,325,512,417 instructions # 2.45 insn per cycle 13,021,149,180 branches # 2011.171 M/sec 76,737,179 branch-misses # 0.59% of all branches 6.474991613 seconds time elapsed 6.474816000 seconds user 0.000000000 seconds sys $ perf stat ./fib 2971215073 Performance counter stats for './fib': 6956.534790 task-clock (msec) # 1.000 CPUs utilized 11 context-switches # 0.002 K/sec 0 cpu-migrations # 0.000 K/sec 113 page-faults # 0.016 K/sec 24,290,924,647 cycles # 3.492 GHz 55,325,864,841 instructions # 2.28 insn per cycle 13,021,213,404 branches # 1871.796 M/sec 84,392,454 branch-misses # 0.65% of all branches 6.957260487 seconds time elapsed 6.956974000 seconds user 0.000000000 seconds sys I didn't know an address difference of 0x30 could influence the number of branch misses so much.

glandium 8y ago
Interestingly, the C and C++ versions have different performance for the same reason: they produce the exact same machine code, at different addresses. Thus one runs faster than the other. Edit: actually, there isn't a difference in branch-misses for those... only in cycles, which is even more intriguing. Another interesting fact: valgrind's branch simulator doesn't show a difference in branch mispredictions between both (it also shows a misprediction rate much larger than reality, it's likely based on an old model Edit: valgrind manual says: Cachegrind simulates branch predictors intended to be typical of mainstream desktop/server processors of around 2004.). More edit: I hacked a linker script to place the fib function from the C++ implementation at a fixed address, and tried different addresses, with interesting results: 0x10000: 5.117084095 seconds time elapsed, 17,866,364,962 cycles 0x10010: 5.206242916 seconds time elapsed, 18,090,712,907 cycles 0x10020: 6.096635146 seconds time elapsed, 21,285,484,583 cycles 0x10030: 4.955020420 seconds time elapsed, 17,297,162,836 cycles 0x10040: 5.146043048 seconds time elapsed, 17,954,722,919 cycles 0x10050: 5.252477508 seconds time elapsed, 18,335,804,193 cycles 0x10060: 6.100806292 seconds time elapsed, 21,300,089,284 cycles 0x10070: 4.936397948 seconds time elapsed, 17,216,051,020 cycles Even more edit: I vaguely remember there was someone doing some analysis (with performance counters) of some similar performance difference depending where the function was located, that was on HN a few months ago, but I can't find it anymore.
- jcranmer 8y ago
  An Intel engineer gave a presentation at the 2016 LLVM Developers' Meeting that gives some insight: http://llvm.org/devmtg/2016-11/Slides/Ansari-Code-Alignment.pdf http://llvm.org/devmtg/2016-11/Slides/Ansari-Code-Alignment.... (for the slides). Essentially, some of the loop heuristics work on a 32-byte window, not a 16-byte window. An interesting statistic would be to find where all the loops are in the code as relative offsets, and find how these shift based on starting alignment.
  - glandium 8y ago
    Thanks. This looks familiar, but I thought I had seen something similar in a blog form. Edit: Found it! https://dendibakh.github.io/blog/2018/01/18/Code_alignment_issues https://dendibakh.github.io/blog/2018/01/18/Code_alignment_i... https://news.ycombinator.com/item?id=16198171 https://news.ycombinator.com/item?id=16198171 FWIW, this is what the function looks like at 0x10070: 0000000000010070 <_Z3fibl>: 10070: 48 83 ff 01 cmp $0x1,%rdi 10074: 7e 32 jle 100a8 <_Z3fibl+0x38> 10076: 55 push %rbp 10077: 31 ed xor %ebp,%ebp 10079: 53 push %rbx 1007a: 48 89 fb mov %rdi,%rbx 1007d: 48 83 ec 08 sub $0x8,%rsp 10081: 48 8d 7b ff lea -0x1(%rbx),%rdi 10085: 48 83 eb 02 sub $0x2,%rbx 10089: e8 e2 ff ff ff callq 10070 <_Z3fibl> 1008e: 48 01 c5 add %rax,%rbp 10091: 48 83 fb 01 cmp $0x1,%rbx 10095: 7f ea jg 10081 <_Z3fibl+0x11> 10097: 48 83 c4 08 add $0x8,%rsp 1009b: 48 8d 45 01 lea 0x1(%rbp),%rax 1009f: 5b pop %rbx 100a0: 5d pop %rbp 100a1: c3 retq 100a2: 66 0f 1f 44 00 00 nopw 0x0(%rax,%rax,1) 100a8: b8 01 00 00 00 mov $0x1,%eax 100ad: c3 retq Edit: It's interesting to note that there's only one recursive call to the function, not two (you get two calls if you compile with -O1). It's also interesting to note that -Os generates an even smaller version with only one recursion, but that ends up slower (~6.5s).
    - 8y ago
BeeOnRope 8y ago
It looks like gcc is going backwards on this one (at least in performance, the gcc-8 code is smaller): gcc-8, which generates the compact code you show, is the slowest of all the versions I tested (at -O3). Here's what I got: gcc 4.8: 4.1 s gcc 4.9: 4.3 s gcc 5.5: 4.3 s gcc 7.3: 4.8 s gcc 8.1: 6.6 s The difference between the compilers isn't just alignment: gcc-8 is generating very different code than the others, which are generally generating a large fib function with several calls of fib inlined into it, so there are many fewer calls (around 300k calls for gcc 4.8 through 7, but around 3 million for gcc 8).
- stock_toaster 8y ago
  Doesnt gcc8 include spectre mitigations?
  - BeeOnRope 8y ago
    Many versions of GCC do, including the version of 5.5 I tested above, but the mitigation optional (enabled by specific command line arguments) and off by default, so they don't impact this test.

glandium 8y ago

Interestingly, the C and C++ versions have different performance for the same reason: they produce the exact same machine code, at different addresses. Thus one runs faster than the other. Edit: actually, there isn't a difference in branch-misses for those... only in cycles, which is even more intriguing. Another interesting fact: valgrind's branch simulator doesn't show a difference in branch mispredictions between both (it also shows a misprediction rate much larger than reality, it's likely based on an old model Edit: valgrind manual says: Cachegrind simulates branch predictors intended to be typical of mainstream desktop/server processors of around 2004.). More edit: I hacked a linker script to place the fib function from the C++ implementation at a fixed address, and tried different addresses, with interesting results: 0x10000: 5.117084095 seconds time elapsed, 17,866,364,962 cycles 0x10010: 5.206242916 seconds time elapsed, 18,090,712,907 cycles 0x10020: 6.096635146 seconds time elapsed, 21,285,484,583 cycles 0x10030: 4.955020420 seconds time elapsed, 17,297,162,836 cycles 0x10040: 5.146043048 seconds time elapsed, 17,954,722,919 cycles 0x10050: 5.252477508 seconds time elapsed, 18,335,804,193 cycles 0x10060: 6.100806292 seconds time elapsed, 21,300,089,284 cycles 0x10070: 4.936397948 seconds time elapsed, 17,216,051,020 cycles Even more edit: I vaguely remember there was someone doing some analysis (with performance counters) of some similar performance difference depending where the function was located, that was on HN a few months ago, but I can't find it anymore.

jcranmer 8y ago
An Intel engineer gave a presentation at the 2016 LLVM Developers' Meeting that gives some insight: http://llvm.org/devmtg/2016-11/Slides/Ansari-Code-Alignment.pdf http://llvm.org/devmtg/2016-11/Slides/Ansari-Code-Alignment.... (for the slides). Essentially, some of the loop heuristics work on a 32-byte window, not a 16-byte window. An interesting statistic would be to find where all the loops are in the code as relative offsets, and find how these shift based on starting alignment.
- glandium 8y ago
  Thanks. This looks familiar, but I thought I had seen something similar in a blog form. Edit: Found it! https://dendibakh.github.io/blog/2018/01/18/Code_alignment_issues https://dendibakh.github.io/blog/2018/01/18/Code_alignment_i... https://news.ycombinator.com/item?id=16198171 https://news.ycombinator.com/item?id=16198171 FWIW, this is what the function looks like at 0x10070: 0000000000010070 <_Z3fibl>: 10070: 48 83 ff 01 cmp $0x1,%rdi 10074: 7e 32 jle 100a8 <_Z3fibl+0x38> 10076: 55 push %rbp 10077: 31 ed xor %ebp,%ebp 10079: 53 push %rbx 1007a: 48 89 fb mov %rdi,%rbx 1007d: 48 83 ec 08 sub $0x8,%rsp 10081: 48 8d 7b ff lea -0x1(%rbx),%rdi 10085: 48 83 eb 02 sub $0x2,%rbx 10089: e8 e2 ff ff ff callq 10070 <_Z3fibl> 1008e: 48 01 c5 add %rax,%rbp 10091: 48 83 fb 01 cmp $0x1,%rbx 10095: 7f ea jg 10081 <_Z3fibl+0x11> 10097: 48 83 c4 08 add $0x8,%rsp 1009b: 48 8d 45 01 lea 0x1(%rbp),%rax 1009f: 5b pop %rbx 100a0: 5d pop %rbp 100a1: c3 retq 100a2: 66 0f 1f 44 00 00 nopw 0x0(%rax,%rax,1) 100a8: b8 01 00 00 00 mov $0x1,%eax 100ad: c3 retq Edit: It's interesting to note that there's only one recursive call to the function, not two (you get two calls if you compile with -O1). It's also interesting to note that -Os generates an even smaller version with only one recursion, but that ends up slower (~6.5s).
  - 8y ago

BeeOnRope 8y ago

It looks like gcc is going backwards on this one (at least in performance, the gcc-8 code is smaller): gcc-8, which generates the compact code you show, is the slowest of all the versions I tested (at -O3). Here's what I got: gcc 4.8: 4.1 s gcc 4.9: 4.3 s gcc 5.5: 4.3 s gcc 7.3: 4.8 s gcc 8.1: 6.6 s The difference between the compilers isn't just alignment: gcc-8 is generating very different code than the others, which are generally generating a large fib function with several calls of fib inlined into it, so there are many fewer calls (around 300k calls for gcc 4.8 through 7, but around 3 million for gcc 8).

stock_toaster 8y ago
Doesnt gcc8 include spectre mitigations?
- BeeOnRope 8y ago
  Many versions of GCC do, including the version of 5.5 I tested above, but the mitigation optional (enabled by specific command line arguments) and off by default, so they don't impact this test.