为什么这种递归比等效迭代快得多？

Question

我听说过很多次递归由于函数调用而很慢，但在这段代码中，它似乎比迭代解快得多。充其量，我通常期望编译器将递归优化为迭代（从程序集的角度来看，这似乎确实发生了）。

#include <iostream>

bool isDivisable(int x, int y)
{
    for (int i = y; i != 1; --i)
        if (x % i != 0)
            return false;
    return true;
}
bool isDivisableRec(int x, int y)
{
    if (y == 1)
        return true;
    return x % y == 0 && isDivisableRec(x, y-1);
}

int findSmallest()
{
    int x = 20;
    for (; !isDivisable(x,20); ++x);
    return x;
}

int main()
{
    std::cout << findSmallest() << std::endl;
}

在这里组装：https://gist.github.com/PatrickAupperle/2b56e16e9e5a6a9b251e

我很想知道这里发生了什么。我相信这是一个复杂的编译器优化，我可以惊讶地了解。

编辑：我刚刚意识到我忘了提到，如果我使用递归版本，它运行在大约。25秒，迭代，大约。6.

编辑2：我正在使用-O3编译

$ g++ --version
g++ (Ubuntu 4.8.4-2ubuntu1~14.04) 4.8.4

不过，我真的不确定这有什么关系。

编辑3:Better benchmarking:
来源：http://gist.github.com/PatrickAupperle/ee8241ac51417437d012
输出：http://gist.github.com/PatrickAupperle/5870136a5552b83fd0f1
运行100次迭代显示出非常相似的结果

编辑4：
在Roman的建议下，我在编译标志中添加了-fno-内联-函数-fno-内联-小函数。效果对我来说极其奇怪。代码运行速度快了大约15倍，但是递归版本和迭代版本之间的比率保持相似。https://gist.github.com/PatrickAupperle/3a87eb53a9f11c1f0bec

Answer 1

使用这段代码，我还看到Cygwin中GCC 4.9.3的时间差异很大（有利于递归版本）。我明白了

13.411 seconds for iterative
4.29101 seconds for recursive

看看它用O3生成的汇编代码，我看到了两件事

>

编译器将isDivisableRec中的尾递归替换为循环，然后展开循环：机器代码中循环的每次迭代都覆盖原始递归的两个级别。

_Z14isDivisableRecii:
.LFB1467:
    .seh_endprologue
    movl    %edx, %r8d
.L15:
    cmpl    $1, %r8d
    je  .L18
    movl    %ecx, %eax          ; First unrolled divisibility check
    cltd
    idivl   %r8d
    testl   %edx, %edx
    je  .L20
.L19:
    xorl    %eax, %eax
    ret
    .p2align 4,,10
.L20:
    leal    -1(%r8), %r9d
    cmpl    $1, %r9d
    jne .L21
    .p2align 4,,10
.L18:
    movl    $1, %eax
    ret
    .p2align 4,,10
.L21:
    movl    %ecx, %eax          ; Second unrolled divisibility check
    cltd
    idivl   %r9d
    testl   %edx, %edx
    jne .L19
    subl    $2, %r8d
    jmp .L15
    .seh_endproc

编译器通过将其提升到findsmalestrec来内联isDivisableRec的几个迭代。由于isDivisableRec的参数y的值被硬编码为20，编译器设法替换了20的迭代，19<代码>15，一些“神奇”的代码直接内联到FindSalestrec。对isDivisableRec的实际调用仅针对14的参数值y（如果发生）。

这是findsmalestrec中的内联代码

    movl    $20, %ebx
    movl    $1717986919, %esi      ; Magic constants
    movl    $1808407283, %edi      ; for divisibility tests
    movl    $954437177, %ebp       ;
    movl    $2021161081, %r12d     ;
    movl    $-2004318071, %r13d    ;
    jmp .L28
    .p2align 4,,10
.L29:                              ; The main cycle
    addl    $1, %ebx
.L28:
    movl    %ebx, %eax             ; Divisibility by 20 test
    movl    %ebx, %ecx
    imull   %esi
    sarl    $31, %ecx
    sarl    $3, %edx
    subl    %ecx, %edx
    leal    (%rdx,%rdx,4), %eax
    sall    $2, %eax
    cmpl    %eax, %ebx
    jne .L29
    movl    %ebx, %eax             ; Divisibility by 19 test
    imull   %edi
    sarl    $3, %edx
    subl    %ecx, %edx
    leal    (%rdx,%rdx,8), %eax
    leal    (%rdx,%rax,2), %eax
    cmpl    %eax, %ebx
    jne .L29
    movl    %ebx, %eax             ; Divisibility by 18 test
    imull   %ebp
    sarl    $2, %edx
    subl    %ecx, %edx
    leal    (%rdx,%rdx,8), %eax
    addl    %eax, %eax
    cmpl    %eax, %ebx
    jne .L29
    movl    %ebx, %eax             ; Divisibility by 17 test
    imull   %r12d
    sarl    $3, %edx
    subl    %ecx, %edx
    movl    %edx, %eax
    sall    $4, %eax
    addl    %eax, %edx
    cmpl    %edx, %ebx
    jne .L29
    testb   $15, %bl               ; Divisibility by 16 test
    jne .L29
    movl    %ebx, %eax             ; Divisibility by 15 test
    imull   %r13d
    leal    (%rdx,%rbx), %eax
    sarl    $3, %eax
    subl    %ecx, %eax
    movl    %eax, %edx
    sall    $4, %edx
    subl    %eax, %edx
    cmpl    %edx, %ebx
    jne .L29
    movl    $14, %edx
    movl    %ebx, %ecx
    call    _Z14isDivisableRecii   ; call isDivisableRecii(x, 14)
    ...

上述机器指令块位于每个jne之前。L29跳转是20、19的可分性测试<代码>15直接提升到FindSalestrec中。显然，对于运行时值y，它们比isDivisableRec中使用的测试更有效。如您所见，16整除性测试简单地实现为testb$15，%bl。因此，上述高度优化的代码很早就发现了x不可被y的高值整除。

isDivisable和findSmallest都没有发生这种情况-它们基本上是按字面意思翻译的。甚至循环也没有展开。

我相信第二个优化最大限度地发挥了作用。编译器使用高度优化的方法来检查更高y值的可整除性，这些值恰好在编译时已知。

如果将isDivisableRec的第二个参数替换为“不可预测的”运行时值（而不是硬编码编译时常数），则应禁用此优化并使计时一致。我只是试了一下，结果是

12.9 seconds for iterative
13.26 seconds for recursive