Пусть A - массив, содержащий нечетное число нулей и единиц. Если n - размер A, то A построен таким образом, что первые ceil(n/2) элементы 0, а остальные элементы 1.
Итак, если n = 9, A будет выглядеть так:
0,0,0,0,0,1,1,1,1
Цель состоит в том, чтобы найти сумму 1s в массиве, и мы делаем это, используя эту функцию:
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];
}
Эта функция довольно глупо для заданной проблемы, но это симуляция другой функции, которую я хочу выглядеть так и производит такое же количество неверных предсказаний.
Вот весь код эксперимента:
#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;
}
Скомпилируйте, набрав g++ -O3 -std=c++11 file.cpp и запустите, набрав ./executable size{odd integer}.
Я использую процессор Intel Core i5-3470 с частотой 8 ГБ, 8 ГБ оперативной памяти, кеш L1 256 КБ, кеш второго уровня 1 МБ, кеш-память L3 6 МБ.
Запуск perf stat -B -e branches,branch-misses ./cachetests 111111 дает мне следующее:
Performance counter stats for './cachetests 111111':
32,639,932 branches
1,404,836 branch-misses # 4.30% of all branches
0.060349641 seconds time elapsed
если я удалю строку
s += A[curIndex+1] + A[size-curIndex-1];
Я получаю следующий вывод от perf:
Performance counter stats for './cachetests 111111':
24,079,109 branches
39,078 branch-misses # 0.16% of all branches
0.027679521 seconds time elapsed
Что эта линия должна делать с предсказаниями ветвей, когда она даже не является выражением if?
Как я вижу это в первых вызовах ceil(n/2) - 1 test1(), оба оператора if будут ложными. В вызове ceil(n/2)-th значение if(curIndex == ceil(n/2)) будет истинным. В остальных вызовах n-ceil(n/2) первый оператор будет ложным, а второй оператор будет истинным.
Почему Intel не может предсказать такое простое поведение?
Теперь посмотрим на второй случай. Предположим, что A теперь имеет чередующиеся нули и единицы. Мы всегда будем начинать с 0. Поэтому, если n = 9 A будет выглядеть так:
0,1,0,1,0,1,0,1,0
Функция, которую мы будем использовать, следующая:
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];
}
И вот весь код эксперимента:
#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;
}
Я запускаю perf, используя те же команды, что и раньше:
Performance counter stats for './cachetests2 111111':
28,560,183 branches
54,204 branch-misses # 0.19% of all branches
0.037134196 seconds time elapsed
И удаление этой строки еще немного улучшило ситуацию:
Performance counter stats for './cachetests2 111111':
28,419,557 branches
16,636 branch-misses # 0.06% of all branches
0.009977772 seconds time elapsed
Теперь, если мы проанализируем функцию, if(curIndex == size-1) будет false n-1 раз, а if(A[curIndex] == 1) будет чередоваться от true к false.
Как я вижу, обе функции должны быть легко предсказать, однако это не относится к первой функции. В то же время я не уверен, что происходит с этой линией и почему она играет роль в улучшении поведения ветвей.
