gcc的asm不稳定是否等同于gfortran的递归默认设置？

Question

我只是在C++和Fortran中玩递归函数，我意识到Fortran中的一个简单递归函数的速度几乎是它的等效C++函数的两倍。现在，在讨论这个问题之前，我知道这里有类似的问题，特别是：

1. Why does adding assembly comments cause such radical change in generated code?
2. (“” : : : “memory”)
3. Equivalent to asm volatile in gfortran

但是，由于Fortran编译器似乎在做asm volatile在gcc中可以实现的任务，所以我更加具体和困惑。为了给您提供一些上下文，让我们考虑下面的递归Fibonacci number实现：

Fortran代码：

module test
implicit none
private
public fib

contains

! Fibonacci function
integer recursive function fib(n) result(r)
    integer, intent(in) :: n
    if (n < 2) then
        r = n
    else
        r = fib(n-1) + fib(n-2)
    end if
end function  ! end of Fibonacci function
end module

program fibonacci
use test, only: fib
implicit none
integer :: r,i 
integer :: n = 1e09
real(8) :: start, finish, cum_time

cum_time=0
do i= 1,n 
    call cpu_time(start)
    r = fib(20)
    call cpu_time(finish) 
    cum_time = cum_time + (finish - start)
    if (cum_time >0.5) exit
enddo  

print*,i,'runs, average elapsed time is', cum_time/i/1e-06, 'us' 
end program

编撰：

gfortran -O3 -march=native

C++代码：

#include <iostream>
#include <chrono>
using namespace std;

// Fib function
int fib(const int n)
{
    int r;
    if (n < 2)
        r = n;
    else
        r = fib(n-1) + fib(n-2);
    return r;
} // end of fib

template<typename T, typename ... Args>
double timeit(T (*func)(Args...), Args...args)
{
    double counter = 1.0;
    double mean_time = 0.0;
    for (auto iter=0; iter<1e09; ++iter){
        std::chrono::time_point<std::chrono::system_clock> start, end;
        start = std::chrono::system_clock::now();

        func(args...);

        end = std::chrono::system_clock::now();
        std::chrono::duration<double> elapsed_seconds = end-start;

        mean_time += elapsed_seconds.count();
        counter++;

        if (mean_time > 0.5){
            mean_time /= counter;
            std::cout << static_cast<long int>(counter)
            << " runs, average elapsed time is "
            << mean_time/1.0e-06 << " \xC2\xB5s" << std::endl; 
            break;
        }
    }
    return mean_time;
}

int main(){
    timeit(fib,20);
    return 0;
}

编撰：

g++ -O3 -march=native

定时：

Fortran: 24991 runs, average elapsed time is 20.087 us
C++    : 12355 runs, average elapsed time is 40.471 µs

因此，gfortran的速度是gcc的两倍。看看组装代码，我得到了

大会(Fortran):

.L28:
    cmpl    $1, %r13d
    jle .L29
    leal    -8(%rbx), %eax
    movl    %ecx, 12(%rsp)
    movl    %eax, 48(%rsp)
    leaq    48(%rsp), %rdi
    leal    -9(%rbx), %eax
    movl    %eax, 16(%rsp)
    call    __bench_MOD_fib
    leaq    16(%rsp), %rdi
    movl    %eax, %r13d
    call    __bench_MOD_fib
    movl    12(%rsp), %ecx
    addl    %eax, %r13d

程序集(C++):

.L28:
    movl    72(%rsp), %edx
    cmpl    $1, %edx
    movl    %edx, %eax
    jle .L33
    subl    $3, %eax
    movl    $0, 52(%rsp)
    movl    %eax, %esi
    movl    %eax, 96(%rsp)
    movl    92(%rsp), %eax
    shrl    %eax
    movl    %eax, 128(%rsp)
    addl    %eax, %eax
    subl    %eax, %esi
    movl    %edx, %eax
    subl    $1, %eax
    movl    %esi, 124(%rsp)
    movl    %eax, 76(%rsp)

两个程序集代码都是由几乎相似的块/标签组成的，它们一次又一次地重复。如您所见，Fortran程序集对fib函数进行了两次调用，而在C++程序集中，gcc可能已经展开了所有递归调用，这可能需要更多的堆栈push/pop和尾跳。

现在，如果我只是在C++代码中放置一个内联程序集注释，如下所示

修改的C++代码：

// Fib function
int fib(const int n)
{
    int r;
    if (n < 2)
        r = n;
    else
        r = fib(n-1) + fib(n-2);
    asm("");
    return r;
} // end of fib

生成的程序集代码，更改为

程序集(C++修改)：

.L7:
    cmpl    $1, %edx
    jle .L17
    leal    -4(%rbx), %r13d
    leal    -5(%rbx), %edx
    cmpl    $1, %r13d
    jle .L19
    leal    -5(%rbx), %r14d
    cmpl    $1, %r14d
    jle .L55
    leal    -6(%rbx), %r13d
    movl    %r13d, %edi
    call    _Z3fibi
    leal    -7(%rbx), %edi
    movl    %eax, %r15d
    call    _Z3fibi
    movl    %r13d, %edi
    addl    %eax, %r15d

现在您可以看到对fib函数的两个调用。给我计时

定时：

Fortran: 24991 runs, average elapsed time is 20.087 us
C++    : 25757 runs, average elapsed time is 19.412 µs

我知道没有输出的asm和asm volatile的作用是抑制激进的编译器优化，但在这种情况下，gcc认为它太聪明了，但最终产生了一个效率较低的代码。

所以问题是

• 为什么gcc不能看到这种“优化”，而gfortan显然可以呢？
• 内联装配线必须在返回语句之前。如果把它放到其他地方，它就不会有任何效果。为什么？
• 此行为编译器是否特定？例如，您能模仿clang/MSVC的相同行为吗？
• 在C或C++中是否有更安全的方法使递归更快(而不依赖内联组装或迭代式编码)？也许是各种模板？

更新：

• 上面显示的结果都是用gcc 4.8.4显示的。我还尝试用gcc 4.9.2和gcc 5.2编译它，得到了相同的结果。
• 这个问题也可以复制(修复？)如果不使用asm，而是将输入参数声明为易失性的，即(volatile int n)而不是(const int n)，尽管这将导致机器上运行时稍微慢一点。
• 正如Michael Karcher所提到的，我们可以传递-fno-optimize-sibling-calls标志来解决这个问题。由于此标志是在-O2级别及以后激活的，即使使用-O1进行编译也解决了这个问题。
• 我已经用clang 3.5.1和-O3 -march=native运行了相同的例子，虽然情况不一样，但是clang似乎也用asm生成了更快的代码。

Clang计时：

clang++ w/o asm    :  8846 runs, average elapsed time is 56.4555 µs
clang++ with asm   : 10427 runs, average elapsed time is 47.8991 µs 

Answer 1

请看这个答案结尾处的粗体，是关于如何获得gcc生成的快速程序的。阅读回答这四个问题的答案。

您的第一个问题假设gfortran能够看到gcc看不到的优化可能性。事实上，事实恰恰相反。gcc发现了它认为是一种优化的可能性，而gfortran却忽略了它。唉，gcc是错误的，它所应用的优化结果是在您的系统上100%的速度损失(在我的系统上是相当的)。

为了解决您的第二个问题：asm语句阻止了使gcc产生错误优化可能性的内部转换。如果没有asm语句，您的代码(有效地)转换为：

int fib(const int n)
{
    if (n < 2)
        return n;
    else
        return fib(n-1) + fib(n-2);
}

包含递归调用的返回语句触发“同级调用优化”，这会使您的代码感到悲观。包含asm语句可防止返回指令在其上移动。

目前，我手头只有gcc，所以我不能尝试其他编译器的行为来回答你的第三个问题，但这似乎绝对依赖于编译器。您遇到gcc的一个怪癖(或错误，无论您如何称呼它)，它在试图优化代码时生成错误代码。不同编译器的优化器非常不同，因此很可能其他编译器不会像gcc那样错误地优化代码。另一方面，用于优化的代码转换是一个经过充分研究的主题，而且大多数编译器都在实现类似的优化方法，因此可能会有另一个编译器陷入与gcc相同的陷阱。

最后一个问题是:这不是C/C++和Fortan的问题，而是gcc的问题，它破坏了这个示例程序(可能还有类似的生产程序)。因此，没有办法使递归在C++中更快，但是有一种方法可以通过禁用有问题的优化来加快gcc中的示例：C++(在我的系统上，在一个测试运行中)比插入asm语句更快的代码。