Pourquoi le compilateur G ++ ne traite-t-il pas ces deux fonctions de la même manière?

Question

J'ai un tableau A avec des zéros et des uns. Je veux trouver la somme de tous les nombres en A. Je veux tester les deux fonctions:

Première fonction

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

La seconde fonction

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

J'ai utilisé le PAPI de la bibliothèque à compter le nombre d'instructions, voici la toute l'expérience:

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

Voici l' Statistics.h le fichier:

#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

C'est le résultat que j'obtiens à partir de la première fonction lorsque la taille de l' A est 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

C'est le résultat que j'obtiens à partir de la deuxième fonction lorsque la taille de l' A est 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

Pourquoi cette différence dans les résultats? Les instructions de réduire de moitié, la direction générale mispredictions sont presque éliminés. Ce qui se passe ici?

Answer 1

Votre deuxième fonction est la queue-récursive. Cela signifie que le compilateur peut optimiser pour quelque chose comme:

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

Qui réduit le nombre d'instructions de manière significative. Il réduit également le nombre de pile nombre de trames (au plus) une. En conséquence, il utilise beaucoup moins de mémoire, ce qui entraîne une réduction des défauts de cache.

Le compilateur n'est pas capable de faire cette optimisation pour la première fonction.

Mise à JOUR: Certaines personnes ont demandé pourquoi le compilateur ne peut pas faire que de l'optimisation sur la première fonction.

Commençons par l'observation de la fonction n'est pas de la queue-récursive. Une fonction est la queue récursive si la dernière chose qui se passe est un appel récursif de la même fonction, suivi par retourner le résultat de l'appel récursif (le cas échéant).

Clairement, ce n'est pas le cas pour la première fonction, s+=A[curIndex]; est exécutée après l'appel récursif.

Alors les gens se demandent pourquoi le compilateur ne peut pas tourner à la première fonction dans le second.

La question est "pourquoi ne G++ disposent pas de cette fonction?" La réponse à cette question est toujours la même. Les fonctionnalités sont appliqués par défaut; G++ ne possède pas cette fonctionnalité, car personne n'est mis en place et expédié la fonctionnalité pour les clients.

Cela devrait être la fin de celui-ci, mais bien sûr, les gens veulent savoir pourquoi personne ne les a conçus, mis en œuvre et testé cette fonctionnalité. Eh bien, peut-être que personne n'a pensé à le faire. Mais plus important encore, la fonctionnalité serait loin d'être négligeable.

Tout d'abord, le compilateur aurait du comprendre que

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

et

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

sont équivalentes. C'est un non trivial d'observation, étant donné que, d'un point de vue mécanique qu'ils ne sont pas équivalentes! En effet, la première efficacement des boucles à partir de la fin du tableau le début, tandis que la seconde boucle du début à la fin. C'est que la même chose? Il donne le même résultat lorsque A est un entier (int)* (et de s dans un int), mais il n'a pas dans d'autres cas (par exemple, lorsque A est un double* et s est un double). Attendons-nous à un compilateur pour être aussi intelligent que ça?

Nous avons donc ici un potentiel de fonctionnalité avec un coût élevé pour les mettre en œuvre. Mais le coût peut être la peine, si le bénéfice est élevé. Est l'avantage des haut? Je suppose que cela arrive très peu dans le code réel, c'est à dire les développeurs sont susceptibles d'écrire la deuxième forme de toute façon. Donc là vous l'avez: un cher fonctionnalité avec peu d'avantages. À mon humble avis, les développeurs de compilateurs sont sage de passer leur temps précieux à d'autres fonctionnalités utiles.