3 ms·

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

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).
  - BeeOnRope 8y ago
    The compiler has determined that the second call `fib(n - 2)` is "almost" tail-recursive (there is probably a better term for this), and so was able to convert that call into the loop you see at 10081 to 10095. This loop repeatedly calls the `fib(n - 1)` part. In other words, the function was transformed from: uint64_t fib(uint64_t n) { if (n <= 1) return 1; return fib(n - 1) + fib(n - 2); } into the equivalent of: uint64_t fib2(uint64_t n) { if (n <= 1) return 1; uint64_t sum = 1; for (; n > 1; n -= 2) { sum += fib2(n - 1); } return sum; } Unfortunately, the result isn't too great as the initial part of the function is pretty heavy, and this bottlenecks computation. It would be better to inline some copies of fib into itself which might even allow some small amount of CSE, but importantly would reduce the number of calls. The alignment you show is "special" (fast) because it's the point at which the top of the main loop (10081) is near the start of a 32-byte region, which allows multiple uops to be efficiently dispatched after jumping there.

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).
- BeeOnRope 8y ago
  The compiler has determined that the second call `fib(n - 2)` is "almost" tail-recursive (there is probably a better term for this), and so was able to convert that call into the loop you see at 10081 to 10095. This loop repeatedly calls the `fib(n - 1)` part. In other words, the function was transformed from: uint64_t fib(uint64_t n) { if (n <= 1) return 1; return fib(n - 1) + fib(n - 2); } into the equivalent of: uint64_t fib2(uint64_t n) { if (n <= 1) return 1; uint64_t sum = 1; for (; n > 1; n -= 2) { sum += fib2(n - 1); } return sum; } Unfortunately, the result isn't too great as the initial part of the function is pretty heavy, and this bottlenecks computation. It would be better to inline some copies of fib into itself which might even allow some small amount of CSE, but importantly would reduce the number of calls. The alignment you show is "special" (fast) because it's the point at which the top of the main loop (10081) is near the start of a 32-byte region, which allows multiple uops to be efficiently dispatched after jumping there.