Why isn't G++ compiler treating these two functions the same way?

Question

I have an array A with zeros and ones. I want to find the sum of all numbers in A. I want to test two functions:

First function

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

Second function

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

I used the PAPI library to count the number of instructions, here is the entire experiment:

#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;
}

Here is the Statistics.h file:

#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

This is the output that I get from the first function when the size of A is 111,111

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

This is the output that I get from the second function when the size of A is 111,111

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

Why the difference in the results? The instructions reduce by half, the branch mispredictions are almost eliminated. What is happening here?

Answer 1

Your second function is tail-recursive. That means the compiler can optimize it to something like:

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

That reduces the number of instructions significantly. It also reduces the number of stack frames needed to (at most) one. As a result, it uses a lot less memory, which results in the reduction of cache misses.

The compiler is not able to make this optimization for the first function.

UPDATE: Some people have asked why the compiler cannot make that optimization on the first function.

Let's start by observing the function is not tail-recursive. A function is tail recursive if the very last thing that happens is a recursive call to the same function, followed by returning the result of that recursive call (if any).

Clearly, that is not the case for the first function, s+=A[curIndex]; is executed after the recursive call.

So then people have asked why the compiler cannot turn the first function into the second one.

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.

That should be the end of it, but of course people will want to know why nobody designed, implemented and tested this feature. Well, maybe nobody thought of doing it. But more importantly, the feature would be far from trivial.

First of all, the compiler would have to understand that

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

and

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

are equivalent. That is a non trivial observation, given that from a mechanical point of view they are not equivalent! Indeed, the first one effectively loops from the end of the array to the start, whereas the second one loops from the start to the end. Is that the same? It yields the same result when A is an int* (and s in an int), but it doesn't in other cases (e.g. when A is a double* and s is a double). Do we expect a compiler to be that smart?

So here we have a potential feature with a high cost to implement. But the cost may be worth it, if the benefit is high. Is the benefit high? I would guess that this happens very little in real code, i.e. developers are likely to write the second form anyway. So there you have it: an expensive feature with little benefit. IMHO, compiler developers are wise to spend their valuable time on more useful features.