4 ms·

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_alignme

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.

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.