c++ - 为什么 G++ 编译器不以相同的方式处理这两个函数？

Question

我有一个数组 A 有零和一。我想找到 A 中所有数字的总和。我想测试两个功能:

第一个函数

void test1(int curIndex){
    if(curIndex == size) return;
    test1(curIndex+1);
    s+=A[curIndex];
}

第二个功能

void test2(int curIndex){
    if(curIndex == size) return;
    s+=A[curIndex];
    test2(curIndex+1);
}

我使用了PAPI library要计算指令的数量，这里是整个实验:

#include <iostream>
#include <fstream>
#include "Statistics.h"

using namespace std;


int size;
int *A;
int s;

void test3(int curIndex){
    if(curIndex == size) return;
    test3(curIndex+1);
    s+=A[curIndex];
}

int main(int argc, char* argv[]){

    size = atoi(argv[1]);
    if(argc!=2){
        cout<<"type ./executable size{odd integer}"<<endl;
        return 1;
    }
    if(size%2!=1){
        cout<<"size must be an odd number"<<endl;
        return 1;
    }
    A = new int[size];
    int i;
    for(i=0;i<size;i++){
        if(i%2==0){
            A[i] = false;
        }
        else{
            A[i] = true;
        }
    }

    Statistics stat(1);
    stat.start();
    test3(0);
    stat.stop();
    stat.printWithHelp();
    cout<<s<<endl;

    return 0;
}

这是 Statistics.h 文件:

#ifndef TRIPLETPARSER_STATISTICS_H
#define TRIPLETPARSER_STATISTICS_H

#include <time.h>
#include <unistd.h>
#include <fstream>
#include <papi.h>
#include <iostream>
#include <iostream>

#define BILLION  1000000000LL

using namespace std;

class Statistics {

private:
    timespec s, e;
    /*
    PAPI_BR_CN  Conditional branch instructions
    PAPI_BR_INS     Branch instructions
    PAPI_BR_MSP     Conditional branch instructions mispredicted
    PAPI_BR_NTK     Conditional branch instructions not taken
    PAPI_BR_PRC     Conditional branch instructions correctly predicted
    PAPI_BR_TKN     Conditional branch instructions taken
    PAPI_BR_UCN     Unconditional branch instructions
    PAPI_BRU_IDL    Cycles branch units are idle
    PAPI_BTAC_M     Branch target address cache misses

    PAPI_TLB_DM     Data translation lookaside buffer misses
    */
    int events[10];  // , PAPI_L2_TCA,PAPI_L3_TCM,PAPI_L3_TCA PAPI_BR_CN, PAPI_BR_PRC}; //type of events we are interested in
    int num_hwcntrs;  //total amount of events stored in 'events' array
    long long values[10];
    long long counters[10];

    void handle_error(int err){
        std::cerr << "PAPI error: " << err << std::endl;
    }

public:
    Statistics(int papi){
        for(size_t i = 0; i< 10; i++)
            counters[i]=0.0;

        switch(papi){
            case 0:
                num_hwcntrs = 0;
                break;
            case 1:
                num_hwcntrs = 6;
                events[0] = PAPI_L2_TCA;
                events[1] = PAPI_L3_TCA;
                events[2] = PAPI_L3_TCM;
                events[3] = PAPI_TOT_INS;
                events[4] = PAPI_BR_INS;
                events[5] = PAPI_BR_MSP;
                break;
        }

    }

    void start(){

        for(size_t i = 0; i< 10; i++)
            counters[i]=0.0;

        if (num_hwcntrs != 0 && PAPI_start_counters(events, num_hwcntrs) != PAPI_OK)
            handle_error(1);
    }


    void start(float ratio){

        if (num_hwcntrs != 0 && PAPI_start_counters(events, num_hwcntrs) != PAPI_OK)
            handle_error(1);
    }


    void stop(){
        if (num_hwcntrs != 0 && PAPI_stop_counters(values, num_hwcntrs) != PAPI_OK)
            handle_error(1);
        update();
    }

    void stop(float ratio){
        if (num_hwcntrs != 0 && PAPI_stop_counters(values, num_hwcntrs) != PAPI_OK)
            handle_error(1);
        update();
    }


    void update(){
        for(size_t i = 0; i < num_hwcntrs; i++)
            counters[i] += values[i];
    }

    void print(){
        for(int i=0;i<num_hwcntrs;i++)
            std::cout << counters[i] << "\t";
        //cout<<"L2 cache miss ratio: "<<counters[1]/(double)counters[0]<<endl;
        //cout<<"L3 cache miss ratio: "<<counters[3]/(double)counters[2]<<endl;
    }

    void printWithHelp(){
        cout<<"L2 accesses: "<<counters[0]<<endl;
        cout<<"L2 miss/access ratio: "<<(double)counters[1]/counters[0]<<endl;
        cout<<"L3 accesses: "<<counters[1]<<endl;
        cout<<"L3 misses: "<<counters[2]<<endl;
        cout<<"L3 miss/access ratio: "<<(double)counters[2]/counters[1]<<endl;
        cout<<"Instructions: "<<counters[3]<<endl;
        cout<<"Branches: "<<counters[4]<<endl;
        cout<<"Branch mispredictions: "<<counters[5]<<endl;
        cout<<"Branch miss/predict ratio: "<<(double)counters[5]/counters[4]<<endl;
    }

    void print(float avg_ratio){
        for (int i = 0; i<num_hwcntrs; i++)
            std::cout << (double)(avg_ratio*counters[i]) << "\t";
    }

};

#endif //TRIPLETPARSER_STATISTICS_H

这是我在 A 的大小为 111,111

时从 first 函数得到的输出

L2 accesses: 24126
L2 miss/access ratio: 0.131559
L3 accesses: 3174
L3 misses: 587
L3 miss/access ratio: 0.18494
Instructions: 1022776
Branches: 178113
Branch mispredictions: 6976
Branch miss/predict ratio: 0.0391661

这是我在 A 的大小为 111,111

时从 second 函数得到的输出

L2 accesses: 7090
L2 miss/access ratio: 0.163752
L3 accesses: 1161
L3 misses: 507
L3 miss/access ratio: 0.436693
Instructions: 555860
Branches: 111189
Branch mispredictions: 25
Branch miss/predict ratio: 0.000224842

为什么结果不同？指令减少了一半，几乎消除了分支错误预测。这里发生了什么？

Answer 1

您的第二个函数是尾递归的。这意味着编译器可以将其优化为:

void test2(int curIndex){
  while(true)
  {
    if(curIndex == size) return;
    s+=A[curIndex];
    curIndex = curIndex + 1;
  }
}

这显着减少了指令数量。它还减少了(最多)一个所需的堆栈帧数。因此，它使用的内存要少得多，从而减少缓存未命中。

编译器无法对第一个函数进行这种优化。

更新:有人问为什么编译器不能对第一个函数进行优化。

让我们从观察函数不是尾递归开始。如果最后发生的事情是对同一函数的递归调用，然后返回该递归调用的结果(如果有)，则该函数是尾递归的。

显然，第一个函数不是这样，s+=A[curIndex];是在递归调用之后执行的。

然后人们问为什么编译器不能把第一个函数变成第二个。

The question is "why does G++ not have this feature?" The answer to that question is always the same. Features are unimplemented by default; G++ does not have that feature because no one designed, implemented and shipped the feature to customers.

这应该是它的结束，但当然人们会想知道为什么没有人设计、实现和测试这个功能。好吧，也许没有人想过这样做。但更重要的是，该功能远非微不足道。

首先，编译器必须明白这一点

test1(curIndex+1);
s+=A[curIndex];

和

s+=A[curIndex];
test1(curIndex+1);

是等价的。这是一个重要的观察，因为从机械的角度来看，它们并不等同!实际上，第一个有效地从数组的末尾循环到开头，而第二个从数组的开头循环到结尾。那是一样的吗？当 A 是 int* (并且 s 在 int 中)时，它会产生相同的结果，但在其他情况下(例如，当 A 是 double* 而 s 是 double 时)则不会。我们是否期望编译器如此聪明？

因此，我们有一个潜在的功能，实现成本很高。但是，如果 yield 很高，那么成本可能是值得的。福利高吗？我猜这在实际代码中很少发生，即开发人员很可能无论如何都会编写第二种形式。所以你有它:一个昂贵的功能，几乎没有什么好处。恕我直言，编译器开发人员明智的做法是将宝贵的时间花在更有用的功能上。