尾部呼叫优化似乎略微恶化了性能

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

速度:

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

但是,通常会有一个抵押品:程序变得更快,因为调用函数不需要任何开销.如果函数本身的工作量不是很大,那么这种增益最为突出,因此开销有一定的分量.

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

另一方面,如果尾调用优化完成,则意味着可能无法进行其他优化,否则可能会加速代码.

快速排序的情况并不是那么明确:有些调用需要大量工作量,而且很多调用工作负载很小.

因此,对于1M元素,尾部调用优化作为优点存在更多缺点.在我的机器上,尾部调用优化函数比小于50000元素的数组的非优化函数更快.

我不得不承认,为什么仅仅通过观看集会就是这种情况.我可以理解的是,生成的程序集非常不同,并且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 ++在beetween中发挥作用:编译器尽力而为(这非常好!)但是你无法保证它会被取消,如果没有,它会无声地落入没有尾调用优化的版本.

让我们来看看尾调用递归的这个简单而标准的实现:

//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不是TCO,则不执行TCO unsigned long long int):在递归调用的所有结果用于进一步计算之后(乘法) )在它返回之前.但是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首先调用的数组的哪个部分,因为它起着重要作用.