Soit A être un tableau qui contient un nombre impair de zéros et de uns. Si n est la taille de A alors A est construit de telle sorte que le premier ceil(n/2) Les éléments sont 0 et les éléments restants 1 .
Donc si n = 9 , A ressemblerait à ceci :
0,0,0,0,0,1,1,1,1
Le but est de trouver la somme de 1s dans le tableau et nous le faisons en utilisant cette fonction :
s = 0;
void test1(int curIndex){
//A is 0,0,0,...,0,1,1,1,1,1...,1
if(curIndex == ceil(n/2)) return;
if(A[curIndex] == 1) return;
test1(curIndex+1);
test1(size-curIndex-1);
s += A[curIndex+1] + A[size-curIndex-1];
}Cette fonction est plutôt stupide pour le problème donné, mais c'est une simulation d'une fonction différente que je veux voir ressembler à celle-ci et qui produit la même quantité de mauvaises prédictions de branche.
Voici le code complet de l'expérience :
#include <iostream>
#include <fstream>
using namespace std;
int size;
int *A;
int half;
int s;
void test1(int curIndex){
//A is 0,0,0,...,0,1,1,1,1,1...,1
if(curIndex == half) return;
if(A[curIndex] == 1) return;
test1(curIndex+1);
test1(size - curIndex - 1);
s += A[curIndex+1] + A[size-curIndex-1];
}
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];
half = size/2;
int i;
for(i=0;i<=half;i++){
A[i] = 0;
}
for(i=half+1;i<size;i++){
A[i] = 1;
}
for(i=0;i<100;i++) {
test1(0);
}
cout<<s<<endl;
return 0;
}Compilez en tapant g++ -O3 -std=c++11 file.cpp et l'exécuter en tapant ./executable size{odd integer} .
J'utilise un processeur Intel(R) Core(TM) i5-3470 à 3,20 GHz avec 8 Go de RAM, cache L1 256 Ko, cache L2 1 Mo, cache L3 6 Mo.
Ejecutar perf stat -B -e branches,branch-misses ./cachetests 111111 me donne ce qui suit :
Performance counter stats for './cachetests 111111':
32,639,932 branches
1,404,836 branch-misses # 4.30% of all branches
0.060349641 seconds time elapsedsi je supprime la ligne
s += A[curIndex+1] + A[size-curIndex-1];J'obtiens la sortie suivante de perf :
Performance counter stats for './cachetests 111111':
24,079,109 branches
39,078 branch-misses # 0.16% of all branches
0.027679521 seconds time elapsedQu'est-ce que cette ligne a à voir avec les prédictions de branche alors qu'il ne s'agit même pas d'une instruction if ?
La façon dont je le vois, dans le premier ceil(n/2) - 1 appels de test1() les deux déclarations if seront fausses. Dans le ceil(n/2)-th appeler, if(curIndex == ceil(n/2)) sera vrai. Dans les autres n-ceil(n/2) appelle, la première affirmation sera fausse, et la seconde sera vraie.
Pourquoi Intel ne parvient-il pas à prévoir un comportement aussi simple ?
Examinons maintenant un deuxième cas. Supposons que A a maintenant des zéros et des uns alternés. Nous commencerons toujours à partir de 0. Donc si n = 9 A ressemblera à ceci :
0,1,0,1,0,1,0,1,0
La fonction que nous allons utiliser est la suivante :
void test2(int curIndex){
//A is 0,1,0,1,0,1,0,1,....
if(curIndex == size-1) return;
if(A[curIndex] == 1) return;
test2(curIndex+1);
test2(curIndex+2);
s += A[curIndex+1] + A[curIndex+2];
}Et voici le code complet de l'expérience :
#include <iostream>
#include <fstream>
using namespace std;
int size;
int *A;
int s;
void test2(int curIndex){
//A is 0,1,0,1,0,1,0,1,....
if(curIndex == size-1) return;
if(A[curIndex] == 1) return;
test2(curIndex+1);
test2(curIndex+2);
s += A[curIndex+1] + A[curIndex+2];
}
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;
}
}
for(i=0;i<100;i++) {
test2(0);
}
cout<<s<<endl;
return 0;
}J'exécute perf en utilisant les mêmes commandes que précédemment :
Performance counter stats for './cachetests2 111111':
28,560,183 branches
54,204 branch-misses # 0.19% of all branches
0.037134196 seconds time elapsedEt enlever cette ligne a encore amélioré un peu les choses :
Performance counter stats for './cachetests2 111111':
28,419,557 branches
16,636 branch-misses # 0.06% of all branches
0.009977772 seconds time elapsedMaintenant, si nous analysons la fonction, if(curIndex == size-1) sera faux n-1 temps, et if(A[curIndex] == 1) passe alternativement de vrai à faux.
Comme je le vois, les deux fonctions devraient être faciles à prévoir, mais ce n'est pas le cas pour la première fonction. En même temps, je ne suis pas sûr de ce qui se passe avec cette ligne et pourquoi elle joue un rôle dans l'amélioration du comportement des branches.
