Почему компилятор g++ не обрабатывает эти две функции одинаково?
У меня есть массив 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
Это результат, который я получаю от функции first, когда размер A равен 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
Это результат, который я получаю от функции второй, когда размер A равен 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
Почему разница в результатах? Инструкции сокращаются наполовину, неверные предсказания отрасли почти устранены. Что здесь происходит?
Ответы
Ответ 1
Ваша вторая функция является хвостовой рекурсивной. Это означает, что компилятор может оптимизировать его для чего-то вроде:
void test2(int curIndex){
while(true)
{
if(curIndex == size) return;
s+=A[curIndex];
curIndex = curIndex + 1;
}
}
Это значительно уменьшает количество инструкций. Он также уменьшает количество кадров стека, необходимых (не более) одному. В результате он использует намного меньше памяти, что приводит к уменьшению промахов в кэше.
Компилятор не может выполнить эту оптимизацию для первой функции.
UPDATE:
Некоторые люди спрашивают, почему компилятор не может сделать эту оптимизацию для первой функции.
Пусть начнется с наблюдения, функция не является хвост-рекурсивной. Функция является хвостовой рекурсивной, если последнее, что происходит, - это рекурсивный вызов той же функции, за которым следует возвращение результата этого рекурсивного вызова (если есть).
Ясно, что это не так для первой функции, s+=A[curIndex]; выполняется после рекурсивного вызова.
Итак, люди спросили, почему компилятор не может превратить первую функцию во вторую.
Вопрос: почему g++ не имеет этой функции? Ответ на этот вопрос всегда один и тот же. По умолчанию функции не реализованы; g++ не имеет этой функции, поскольку никто не проектировал, не реализовал и не отправил эту функцию клиентам.
Это должно быть концом этого, но, конечно, люди захотят узнать, почему никто не проектировал, не реализовывал и не тестировал эту функцию. Ну, может быть, никто не думал об этом. Но что более важно, функция будет далека от тривиальной.
Прежде всего, компилятор должен был бы понять, что
test1(curIndex+1);
s+=A[curIndex];
и
s+=A[curIndex];
test1(curIndex+1);
эквивалентны. Это нетривиальное наблюдение, учитывая, что с механической точки зрения они не эквивалентны! В самом деле, первый из них эффективно проходит от конца массива до начала, тогда как второй - от начала до конца. Это то же самое? Это дает тот же результат, когда A является int * (и s в int), но он не в других случаях (например, когда A является двойным * и s является двойным). Мы ожидаем, что компилятор будет таким умным?
Итак, у нас есть потенциальная возможность с высокой стоимостью для реализации. Но стоимость может стоить того, если выгода высока. Выгода высокая? Я бы предположил, что это происходит очень мало в реальном коде, т.е. Разработчики, скорее всего, напишут вторую форму. Итак, у вас есть это: дорогая функция с небольшой пользой. IMHO, разработчики компиляторов разумно тратить свое драгоценное время на более полезные функции.
