c++ - 尾调用优化似乎会稍微降低性能

Question

在快速排序实现中，左侧的数据是针对纯-O2优化的代码，右侧的数据是针对-O2优化的代码(已启用-fno-optimize-sibling-calls标志)，即关闭了尾部调用优化功能。这是3次不同运行的平均值，变化似乎可以忽略不计。值的范围是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的尾部调用优化器是如何工作的，这是如何发生的，我应该怎么利用尾部调用来加速我的程序？

Answer 1

速度:

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

但是，通常会有附带要求:程序变得更快，因为调用函数不需要任何开销。如果函数本身的工作量不那么大，则此 yield 最为显着，因此开销会有一定的负担。

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

另一方面，如果完成了尾部调用优化，则意味着可能无法进行其他优化，否则可能会加速您的代码。

快速排序的情况不是很明确:有些电话的工作量很大，而很多电话的工作量很小。

因此，对于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);
}

这种经典形式的尾部调用使编译器易于优化:请参见结果 here-无需递归调用 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 manages也可以在这里执行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)，否则运行“Segmentation fault”(否则将导致段错误)-由于递归深度导致堆栈溢出。

实际上，这是查看是否执行了尾调用优化的简单测试:未优化版本和较大递归深度的“段错误”。

推论:

如注释中已经指出的那样:仅第二个 quick-sort调用是通过TLO优化的。在实现中，如果很不幸，并且数组的后半部分始终仅包含一个元素，则堆栈上需要 O(n)空间。

但是，如果第一次调用总是使用较小的一半，而第二次调用使用较大的一半是TLO，则最多需要 O(log n)递归深度，因此堆栈上仅需要 O(log n)空间。

这意味着您应该先检查数组的哪一部分，然后再调用 quicksort，因为它起着巨大的作用。