尾调用优化似乎会轻微降低性能

Question

尾调用优化似乎会轻微降低性能

c++algorithmoptimizationg++compiler-optimization

6

在快速排序的实现中，左侧的数据是针对纯粹使用-O2优化代码的情况，而右侧的数据则是开启了-fno-optimize-sibling-calls标志，即关闭尾递归优化的-O2优化代码。这是三次不同运行的平均值，变动似乎可以忽略不计。数值范围为1-1000，时间以毫秒为单位。编译器为MinGW g++，版本号为6.3.0。

size of array     with TLO(ms)    without TLO(ms)
      8M                35,083           34,051 
      4M                 8,952            8,627
      1M                   613              609

以下是我的代码：

#include <bits/stdc++.h>
using namespace std;

int N = 4000000;

void qsort(int* arr,int start=0,int finish=N-1){
    if(start>=finish) return ;
    int i=start+1,j = finish,temp;
    auto pivot = arr[start];
    while(i!=j){
        while (arr[j]>=pivot && j>i) --j;
        while (arr[i]<pivot && i<j) ++i;
        if(i==j) break;
        temp=arr[i];arr[i]=arr[j];arr[j]=temp; //swap big guy to right side
    }
    if(arr[i]>=arr[start]) --i;

    temp = arr[start];arr[start]=arr[i];arr[i]=temp; //swap pivot
    qsort(arr,start,i-1);
    qsort(arr,i+1,finish);
}

int main(){
    srand(time(NULL));
    int* arr = new int[N];
    for(int i=0;i<N;i++) {arr[i] = rand()%1000+1;}

    auto start = clock();
    qsort(arr);
    cout<<(clock()-start)<<endl;
    return 0;
}

我听说clock()不是衡量时间的完美方式。但这种影响似乎是一致的。

编辑：针对一条评论，我想问的问题是：请解释gcc尾调用优化器的工作原理、它是如何发生的以及我应该怎么做才能利用尾调用来加速我的程序？

- Shihab Shahriar Khan

3

第一行的数据是否应该是35083,34051？如果您将表格转换成固定宽度表格，并在其中加入空格，将非常有帮助。 - Martin Bonner supports Monica

2

注意：这是一种糟糕的实现，因为递归调用可能会使堆栈溢出。始终先处理最短的子数组！ - user1196549

2

@YvesDaoust：当然，只有编译器实际上消除尾调用才有帮助！ - Martin Bonner supports Monica

1

@BaummitAugen，我实现这个的部分原因是为了亲身体验尾调用优化的效果。 - Shihab Shahriar Khan

3

正如@YvesDaoust所说，快速排序中尾递归的主要目的不是为了加速快速排序，而是为了防止栈溢出。通过在较短的分区上进行递归，然后在较长的分区上进行循环，您可以保证递归深度小于元素数量的log2，这在大多数实际硬件上可以被认为是一个小常数(例如，远小于64)。 - rici

显示剩余4条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ead · Accepted Answer

关于速度：

正如评论中已经指出的那样，尾调用优化的主要目标是减少堆栈的使用。

然而，通常会有一个副作用：程序变得更快，因为不需要为函数的调用添加开销。如果函数本身的工作量不是很大，那么这种收益就最为明显，因为开销具有一定的权重。

如果在函数调用期间完成了大量的工作，那么可以忽略开销，并且没有明显的加速效果。

另一方面，如果进行了尾调用优化，那么可能无法进行其他优化，否则可以加速您的代码。

快速排序的情况并不是那么明确：有些调用具有大量的工作负载，而有些调用具有非常小的工作负载。

因此，在1M个元素的情况下，尾调用优化的缺点比优点多。在我的机器上，对于小于50000个元素的数组，尾调用优化的函数比未优化的函数更快。

我必须承认，仅从 assembly 上看，我无法说出为什么会出现这种情况。我所理解的是，生成的程序集非常不同，并且优化版本中的 quicksort 只被调用了一次。

有一个明显的例子，尾递归优化会更快（因为函数本身没有太多操作，开销很明显）：

//fib.cpp
#include <iostream>

unsigned long long int fib(unsigned long long int n){
  if (n==0 || n==1)
    return 1;
  return fib(n-1)+fib(n-2);
}

int main(){
  unsigned long long int N;
  std::cin >> N;
  std::cout << fib(N);
}

运行time echo "40" | ./fib，我得到了尾递归优化版本和非优化版本之间的1.1秒和1.6秒。实际上，我很惊讶编译器能够在这里使用尾递归优化 - 但它确实可以，正如godbolt.org上所看到的那样，第二个fib调用被优化了。

关于尾调用优化：

通常情况下，如果递归调用是函数中最后一次操作（在 return之前），则可以进行尾调用优化——栈上的变量可用于下一次调用，即函数应具有以下形式：

ResType f( InputType input){
    //do work
    InputType new_input = ...;
    return f(new_input);
}

有些语言根本不进行尾调用优化（例如Python），而有些语言可以明确要求编译器进行优化，如果无法进行，则编译器会失败（例如Clojure）。C++则介于两者之间：编译器尽最大努力进行优化（非常出色！），但不能保证一定成功，如果无法进行优化，则默默地转换为没有尾调用优化的版本。

让我们看一下这个简单且标准的尾调用递归实现：

//should be called fac(n,1)
unsigned long long int 
fac(unsigned long long int n, unsigned long long int res_so_far){
  if (n==0)
    return res_so_far;
  return fac(n-1, res_so_far*n);
}

这种经典的尾调用形式可以方便编译器进行优化：参见这里的结果 - 没有对fac的递归调用！

然而，gcc编译器也能够对不太明显的情况进行TCO：

unsigned long long int 
fac(unsigned long long int n){
  if (n==0)
    return 1;
  return n*fac(n-1);
}

我人类更容易阅读和书写，但编译器优化却更困难（有趣的事实：如果返回类型是int而不是unsigned long long int，则不执行TCO）：毕竟递归调用的结果在返回之前被用于进一步计算（乘法）。但是，gcc管理也在这里执行了TCO！

通过这个例子，我们可以看到TCO的工作结果：

//factorial.cpp
#include <iostream>

unsigned long long int 
fac(unsigned long long int n){
  if (n==0)
    return 1;
  return n*fac(n-1);
}

int main(){
  unsigned long long int N;
  std::cin >> N;
  std::cout << fac(N);
}

运行time echo "40000000" | ./factorial，如果启用了尾递归优化，则可以立即获得结果（0），否则会出现“段错误” - 这是由于递归深度导致的堆栈溢出。

实际上，这是一个简单的测试，用于检查是否执行了尾递归优化：非优化版本和大量递归深度会导致“段错误”。

推论：

正如评论中所指出的：只有第二次调用quick-sort被TLO优化。在您的实现中，如果不幸的是数组的后一半始终只包含一个元素，则需要在堆栈上使用O(n)的空间。

然而，如果第一次调用总是使用较小的一半，第二次调用使用较大的一半并且被TLO优化，那么您最多只需要O(log n)的递归深度，因此在堆栈上只需要O(log n)的空间。

这意味着您应该检查您调用quicksort的数组的哪一部分首先进行，因为它起着重要的作用。