Каков эффект упорядочения, если... еще, если утверждения по вероятности?
В частности, если у меня есть серия if...else if заявления, и я как-то заранее знаю относительную вероятность того, что каждое утверждение будет trueКакова разница во времени выполнения, чтобы отсортировать их по вероятности? Например, я должен предпочесть это:
if (highly_likely)
//do something
else if (somewhat_likely)
//do something
else if (unlikely)
//do something
к этому?:
if (unlikely)
//do something
else if (somewhat_likely)
//do something
else if (highly_likely)
//do something
Кажется очевидным, что отсортированная версия будет быстрее, однако из-за читабельности или наличия побочных эффектов мы можем захотеть упорядочить их неоптимально. Также трудно сказать, насколько хорошо процессор будет делать с предсказанием ветвлений, пока вы на самом деле не запустите код.
Итак, в ходе экспериментов с этим я закончил тем, что отвечал на свой собственный вопрос для конкретного случая, однако я также хотел бы услышать другие мнения / идеи.
Важно: этот вопрос предполагает, что if операторы могут быть произвольно переупорядочены без какого-либо другого влияния на поведение программы. В моем ответе три условных теста являются взаимоисключающими и не дают побочных эффектов. Конечно, если утверждения должны оцениваться в определенном порядке для достижения желаемого поведения, тогда вопрос эффективности является спорным.
10 ответов
Как правило, большинство, если не все процессоры Intel, предполагают, что прямые ветви не берутся с первого раза. Смотрите работу Годболта.
После этого ветвь переходит в кэш предсказания ветвления, и для информирования о будущем предсказании ветвления используется прошлое поведение.
Так что в тесной петле, эффект неправильного порядка будет относительно небольшим. Предиктор ветвей собирается узнать, какой набор веток наиболее вероятен, и если у вас нет нетривиального объема работы в цикле, небольшие различия не будут сильно складываться.
В общем коде большинство компиляторов по умолчанию (без другой причины) упорядочивают полученный машинный код примерно так, как вы его упорядочили в своем коде. Таким образом, если операторы являются прямыми ветвями, когда они терпят неудачу.
Таким образом, вы должны упорядочить свои ветви в порядке уменьшения вероятности, чтобы получить лучший прогноз ветвления из "первого столкновения".
Микробенчмарк, который многократно зацикливается на множестве условий и выполняет тривиальную работу, будет зависеть от крошечных эффектов подсчета команд и т. П., А также от проблем с прогнозированием относительных ветвлений. Так что в этом случае вы должны зарегистрироваться, так как практические правила не будут надежными.
Кроме того, векторизация и многие другие оптимизации применяются к крошечным узким циклам.
Итак, в общем коде, поместите наиболее вероятный код в if блок, и это приведет к наименьшему количеству пропущенных некэшируемых предсказаний ветвлений. В тесных циклах следуйте общему правилу, чтобы начать, и если вам нужно знать больше, у вас нет другого выбора, кроме как профилировать.
Естественно, все это выходит за рамки, если некоторые тесты намного дешевле, чем другие.
Я составил следующий тест, чтобы рассчитать время выполнения двух разных if...else if блоки, один отсортированный в порядке вероятности, другой отсортированный в обратном порядке:
#include <chrono>
#include <iostream>
#include <random>
#include <algorithm>
#include <iterator>
#include <functional>
using namespace std;
int main()
{
long long sortedTime = 0;
long long reverseTime = 0;
for (int n = 0; n != 500; ++n)
{
//Generate a vector of 5000 random integers from 1 to 100
random_device rnd_device;
mt19937 rnd_engine(rnd_device());
uniform_int_distribution<int> rnd_dist(1, 100);
auto gen = std::bind(rnd_dist, rnd_engine);
vector<int> rand_vec(5000);
generate(begin(rand_vec), end(rand_vec), gen);
volatile int nLow, nMid, nHigh;
chrono::time_point<chrono::high_resolution_clock> start, end;
//Sort the conditional statements in order of increasing likelyhood
nLow = nMid = nHigh = 0;
start = chrono::high_resolution_clock::now();
for (int& i : rand_vec) {
if (i >= 95) ++nHigh; //Least likely branch
else if (i < 20) ++nLow;
else if (i >= 20 && i < 95) ++nMid; //Most likely branch
}
end = chrono::high_resolution_clock::now();
reverseTime += chrono::duration_cast<chrono::nanoseconds>(end-start).count();
//Sort the conditional statements in order of decreasing likelyhood
nLow = nMid = nHigh = 0;
start = chrono::high_resolution_clock::now();
for (int& i : rand_vec) {
if (i >= 20 && i < 95) ++nMid; //Most likely branch
else if (i < 20) ++nLow;
else if (i >= 95) ++nHigh; //Least likely branch
}
end = chrono::high_resolution_clock::now();
sortedTime += chrono::duration_cast<chrono::nanoseconds>(end-start).count();
}
cout << "Percentage difference: " << 100 * (double(reverseTime) - double(sortedTime)) / double(sortedTime) << endl << endl;
}
При использовании MSVC2017 с /O2 результаты показывают, что отсортированная версия постоянно примерно на 28% быстрее, чем несортированная версия. Согласно комментарию luk32, я также поменял порядок двух тестов, что делает заметную разницу (22% против 28%). Код был запущен под Windows 7 на Intel Xeon E5-2697 v2. Это, конечно, очень специфично для проблемы и не должно интерпретироваться как окончательный ответ.
Просто мои 5 центов. Кажется, эффект упорядочения, если заявления должны зависеть от:
Вероятность каждого оператора if.
Количество итераций, чтобы можно было использовать предсказатель ветвления.
Вероятные / маловероятные подсказки компилятора, то есть расположение кода.
Чтобы изучить эти факторы, я протестировал следующие функции:
ordered_ifs ()
for (i = 0; i < data_sz * 1024; i++) {
if (data[i] < check_point) // highly likely
s += 3;
else if (data[i] > check_point) // samewhat likely
s += 2;
else if (data[i] == check_point) // very unlikely
s += 1;
}
reversed_ifs ()
for (i = 0; i < data_sz * 1024; i++) {
if (data[i] == check_point) // very unlikely
s += 1;
else if (data[i] > check_point) // samewhat likely
s += 2;
else if (data[i] < check_point) // highly likely
s += 3;
}
ordered_ifs_with_hints ()
for (i = 0; i < data_sz * 1024; i++) {
if (likely(data[i] < check_point)) // highly likely
s += 3;
else if (data[i] > check_point) // samewhat likely
s += 2;
else if (unlikely(data[i] == check_point)) // very unlikely
s += 1;
}
reversed_ifs_with_hints ()
for (i = 0; i < data_sz * 1024; i++) {
if (unlikely(data[i] == check_point)) // very unlikely
s += 1;
else if (data[i] > check_point) // samewhat likely
s += 2;
else if (likely(data[i] < check_point)) // highly likely
s += 3;
}
данные
Массив данных содержит случайные числа от 0 до 100:
const int RANGE_MAX = 100;
uint8_t data[DATA_MAX * 1024];
static void data_init(int data_sz)
{
int i;
srand(0);
for (i = 0; i < data_sz * 1024; i++)
data[i] = rand() % RANGE_MAX;
}
Результаты, достижения
Следующие результаты приведены для Intel i5@3,2 ГГц и G++ 6.3.0. Первый аргумент - это check_point (т. Е. Вероятность в %% для оператора с высокой вероятностью if), второй аргумент - data_sz (т. Е. Количество итераций).
---------------------------------------------------------------------
Benchmark Time CPU Iterations
---------------------------------------------------------------------
ordered_ifs/50/4 4660 ns 4658 ns 150948
ordered_ifs/50/8 25636 ns 25635 ns 27852
ordered_ifs/75/4 4326 ns 4325 ns 162613
ordered_ifs/75/8 18242 ns 18242 ns 37931
ordered_ifs/100/4 1673 ns 1673 ns 417073
ordered_ifs/100/8 3381 ns 3381 ns 207612
reversed_ifs/50/4 5342 ns 5341 ns 126800
reversed_ifs/50/8 26050 ns 26050 ns 26894
reversed_ifs/75/4 3616 ns 3616 ns 193130
reversed_ifs/75/8 15697 ns 15696 ns 44618
reversed_ifs/100/4 3738 ns 3738 ns 188087
reversed_ifs/100/8 7476 ns 7476 ns 93752
ordered_ifs_with_hints/50/4 5551 ns 5551 ns 125160
ordered_ifs_with_hints/50/8 23191 ns 23190 ns 30028
ordered_ifs_with_hints/75/4 3165 ns 3165 ns 218492
ordered_ifs_with_hints/75/8 13785 ns 13785 ns 50574
ordered_ifs_with_hints/100/4 1575 ns 1575 ns 437687
ordered_ifs_with_hints/100/8 3130 ns 3130 ns 221205
reversed_ifs_with_hints/50/4 6573 ns 6572 ns 105629
reversed_ifs_with_hints/50/8 27351 ns 27351 ns 25568
reversed_ifs_with_hints/75/4 3537 ns 3537 ns 197470
reversed_ifs_with_hints/75/8 16130 ns 16130 ns 43279
reversed_ifs_with_hints/100/4 3737 ns 3737 ns 187583
reversed_ifs_with_hints/100/8 7446 ns 7446 ns 93782
Анализ
1. Порядок имеет значение
Для 4K итераций и (почти) 100% вероятности очень популярного утверждения разница огромна: 223%:
---------------------------------------------------------------------
Benchmark Time CPU Iterations
---------------------------------------------------------------------
ordered_ifs/100/4 1673 ns 1673 ns 417073
reversed_ifs/100/4 3738 ns 3738 ns 188087
Для 4K итераций и 50% вероятности очень понравившегося утверждения разница составляет около 14%:
---------------------------------------------------------------------
Benchmark Time CPU Iterations
---------------------------------------------------------------------
ordered_ifs/50/4 4660 ns 4658 ns 150948
reversed_ifs/50/4 5342 ns 5341 ns 126800
2. Количество итераций имеет значение
Разница между 4K и 8K итерациями для (почти) 100% вероятности очень понравившегося утверждения составляет около двух раз (как и ожидалось):
---------------------------------------------------------------------
Benchmark Time CPU Iterations
---------------------------------------------------------------------
ordered_ifs/100/4 1673 ns 1673 ns 417073
ordered_ifs/100/8 3381 ns 3381 ns 207612
Но разница между 4K и 8K итерациями для 50% вероятности очень популярного утверждения составляет 5,5 раз:
---------------------------------------------------------------------
Benchmark Time CPU Iterations
---------------------------------------------------------------------
ordered_ifs/50/4 4660 ns 4658 ns 150948
ordered_ifs/50/8 25636 ns 25635 ns 27852
Почему так? Из-за ветки предсказатель промахивается. Вот ветка промахов для каждого упомянутого выше случая:
ordered_ifs/100/4 0.01% of branch-misses
ordered_ifs/100/8 0.01% of branch-misses
ordered_ifs/50/4 3.18% of branch-misses
ordered_ifs/50/8 15.22% of branch-misses
Таким образом, на моем i5 предиктор ветвлений не работает с удивительной вероятностью для не слишком вероятных ветвей и больших наборов данных.
3. Подсказки помогают немного
Для итераций 4K результаты несколько хуже для вероятности 50% и несколько лучше для вероятности, близкой к 100%:
---------------------------------------------------------------------
Benchmark Time CPU Iterations
---------------------------------------------------------------------
ordered_ifs/50/4 4660 ns 4658 ns 150948
ordered_ifs/100/4 1673 ns 1673 ns 417073
ordered_ifs_with_hints/50/4 5551 ns 5551 ns 125160
ordered_ifs_with_hints/100/4 1575 ns 1575 ns 437687
Но для 8К итераций результаты всегда немного лучше:
---------------------------------------------------------------------
Benchmark Time CPU Iterations
---------------------------------------------------------------------
ordered_ifs/50/8 25636 ns 25635 ns 27852
ordered_ifs/100/8 3381 ns 3381 ns 207612
ordered_ifs_with_hints/50/8 23191 ns 23190 ns 30028
ordered_ifs_with_hints/100/8 3130 ns 3130 ns 221205
Так что подсказки тоже помогают, но совсем чуть-чуть.
Общий вывод: всегда проверяйте код, потому что результаты могут удивить.
Надеюсь, это поможет.
Нет, вы не должны, если вы действительно не уверены, что целевая система затронута. По умолчанию идут по читабельности.
Я очень сомневаюсь в ваших результатах. Я немного изменил ваш пример, чтобы отменить выполнение стало проще. Ideone довольно последовательно показывает, что обратный порядок быстрее, хотя и не намного. На некоторых трассах даже это иногда переворачивается. Я бы сказал, что результаты неубедительны. Coliru также не сообщает никакой разницы. Я могу проверить процессор Exynos5422 на моем odroid xu4 позже.
Дело в том, что современные процессоры имеют предикторы ветвления. Существует много логики, предназначенной для предварительной выборки как данных, так и инструкций, и современные процессоры x86 достаточно умны, когда дело доходит до этого. Некоторые более тонкие архитектуры, такие как ARM или GPU, могут быть уязвимы для этого. Но это действительно сильно зависит как от компилятора, так и от целевой системы.
Я бы сказал, что оптимизация порядка веток довольно хрупкая и эфемерная. Делайте это только как действительно точный шаг настройки.
Код:
#include <chrono>
#include <iostream>
#include <random>
#include <algorithm>
#include <iterator>
#include <functional>
using namespace std;
int main()
{
//Generate a vector of random integers from 1 to 100
random_device rnd_device;
mt19937 rnd_engine(rnd_device());
uniform_int_distribution<int> rnd_dist(1, 100);
auto gen = std::bind(rnd_dist, rnd_engine);
vector<int> rand_vec(5000);
generate(begin(rand_vec), end(rand_vec), gen);
volatile int nLow, nMid, nHigh;
//Count the number of values in each of three different ranges
//Run the test a few times
for (int n = 0; n != 10; ++n) {
//Run the test again, but now sort the conditional statements in reverse-order of likelyhood
{
nLow = nMid = nHigh = 0;
auto start = chrono::high_resolution_clock::now();
for (int& i : rand_vec) {
if (i >= 95) ++nHigh; //Least likely branch
else if (i < 20) ++nLow;
else if (i >= 20 && i < 95) ++nMid; //Most likely branch
}
auto end = chrono::high_resolution_clock::now();
cout << "Reverse-sorted: \t" << chrono::duration_cast<chrono::nanoseconds>(end-start).count() << "ns" << endl;
}
{
//Sort the conditional statements in order of likelyhood
nLow = nMid = nHigh = 0;
auto start = chrono::high_resolution_clock::now();
for (int& i : rand_vec) {
if (i >= 20 && i < 95) ++nMid; //Most likely branch
else if (i < 20) ++nLow;
else if (i >= 95) ++nHigh; //Least likely branch
}
auto end = chrono::high_resolution_clock::now();
cout << "Sorted:\t\t\t" << chrono::duration_cast<chrono::nanoseconds>(end-start).count() << "ns" << endl;
}
cout << endl;
}
}
Основываясь на некоторых других ответах здесь, похоже, что единственный реальный ответ: это зависит. Это зависит как минимум от следующего (хотя и не обязательно в этом порядке важности):
- Относительная вероятность каждой ветви. Это оригинальный вопрос, который был задан. Основываясь на существующих ответах, кажется, существуют некоторые условия, при которых упорядочение по вероятности помогает, но, похоже, это не всегда так. Если относительные вероятности не очень разные, то вряд ли будет какая-либо разница в том, в каком порядке они находятся. Однако, если первое условие происходит в 99,999% времени, а следующее - это доля того, что осталось, то я бы Предположим, что наиболее вероятным является выбор наиболее вероятного из них во времени.
- Стоимость расчета истинного / ложного условия для каждой отрасли. Если временные затраты на тестирование условий действительно высоки для одной ветви по сравнению с другой, то это, вероятно, окажет значительное влияние на сроки и эффективность. Например, рассмотрим условие, для расчета которого требуется 1 единица времени (например, проверка состояния булевой переменной), в сравнении с другим условием, для расчета которого требуются десятки, сотни, тысячи или даже миллионы единиц времени (например, проверка содержимого файл на диске или выполнение сложного SQL-запроса к большой базе данных). Предполагая, что код проверяет условия по порядку каждый раз, более быстрые условия, вероятно, должны быть первыми (если они не зависят от других условий, которые не выполняются первыми).
- Компилятор / Интерпретатор Некоторые компиляторы (или интерпретаторы) могут включать в себя оптимизации одного вида другого, которые могут повлиять на производительность (и некоторые из них присутствуют, только если определенные параметры выбраны во время компиляции и / или выполнения). Таким образом, если вы не проводите сравнение двух компиляций и исполнений идентичного кода в одной и той же системе с использованием одного и того же компилятора, где единственное различие заключается в порядке рассматриваемых веток, вам придется предоставить некоторую свободу действий для вариантов компилятора.
- Операционная система / аппаратное обеспечение Как упоминалось luk32 и Yakk, различные процессоры имеют свои собственные оптимизации (как и операционные системы). Таким образом, тесты снова подвержены изменениям здесь.
- Частота выполнения блока кода Если к блоку, который включает ветви, редко обращаются (например, только один раз во время запуска), то, вероятно, очень мало имеет значение, в каком порядке вы устанавливаете ветви. С другой стороны, если ваш код работает в этом блоке кода во время критической части кода, то порядок может иметь большое значение (в зависимости от тестов).
Единственный способ узнать наверняка - это сравнить ваш конкретный случай, предпочтительно в системе, идентичной (или очень похожей) на предполагаемую систему, в которой в конечном итоге будет выполняться код. Если он предназначен для работы на множестве разных систем с различным аппаратным обеспечением, операционной системой и т. Д., То рекомендуется сравнить несколько вариантов, чтобы определить, какой из них лучше. Это может быть даже хорошей идеей, чтобы код был скомпилирован с одним порядком в системе одного типа и другим порядком в системе другого типа.
Моё личное эмпирическое правило (в большинстве случаев при отсутствии эталона) это заказ на основе:
- Условия, которые основаны на результате предыдущих условий,
- Стоимость расчета условия, затем
- Относительная вероятность каждой ветви.
То, как я обычно это решаю для высокопроизводительного кода, - это поддерживать порядок, который наиболее читабелен, но предоставляя подсказки компилятору. Вот один пример из ядра Linux:
if (likely(access_ok(VERIFY_READ, from, n))) {
kasan_check_write(to, n);
res = raw_copy_from_user(to, from, n);
}
if (unlikely(res))
memset(to + (n - res), 0, res);
Здесь предполагается, что проверка доступа пройдет, и что ошибка не возвращается res, Попытка изменить порядок любого из этих предложений, если бы просто запутать код, но likely() а также unlikely() макросы на самом деле помогают удобочитаемости, указывая на то, что является нормальным случаем и что является исключением.
Реализация этих макросов в Linux использует специфические особенности GCC. Кажется, что clang и компилятор Intel C поддерживают один и тот же синтаксис, но MSVC не имеет такой возможности.
Также зависит от вашего компилятора и платформы, для которой вы компилируете.
Теоретически, наиболее вероятное условие должно сделать скачок управления как можно меньше.
Обычно наиболее вероятное условие должно быть первым:
if (most_likely) {
// most likely instructions
} else …
Самые популярные асмы основаны на условных ветвях, которые переходят, когда условие выполняется. Этот код на C, скорее всего, будет переведен в такую псевдо-асм:
jump to ELSE if not(most_likely)
// most likely instructions
jump to end
ELSE:
…
Это связано с тем, что переходы заставляют процессор отменять конвейер выполнения и останавливаться из-за изменения счетчика программы (для архитектур, которые поддерживают конвейеры, которые действительно распространены). Затем речь идет о компиляторе, который может применять или не применять некоторые сложные оптимизации, связанные с наличием статистически наиболее вероятного условия, чтобы элемент управления выполнял меньше переходов.
Я решил повторить тест на своей машине, используя код Lik32. Я должен был изменить это из-за моих окон или компилятора, думая, что высокое разрешение составляет 1 мс, используя
mingw32-g++.exe -O3 -Wall -std= C++ 11 -fexceptions -g
vector<int> rand_vec(10000000);
GCC произвел одинаковое преобразование в обоих исходных кодах.
Обратите внимание, что тестируются только два первых условия, так как третье всегда должно быть верным, GCC здесь является своего рода Шерлоком.
Задний ход
.L233:
mov DWORD PTR [rsp+104], 0
mov DWORD PTR [rsp+100], 0
mov DWORD PTR [rsp+96], 0
call std::chrono::_V2::system_clock::now()
mov rbp, rax
mov rax, QWORD PTR [rsp+8]
jmp .L219
.L293:
mov edx, DWORD PTR [rsp+104]
add edx, 1
mov DWORD PTR [rsp+104], edx
.L217:
add rax, 4
cmp r14, rax
je .L292
.L219:
mov edx, DWORD PTR [rax]
cmp edx, 94
jg .L293 // >= 95
cmp edx, 19
jg .L218 // >= 20
mov edx, DWORD PTR [rsp+96]
add rax, 4
add edx, 1 // < 20 Sherlock
mov DWORD PTR [rsp+96], edx
cmp r14, rax
jne .L219
.L292:
call std::chrono::_V2::system_clock::now()
.L218: // further down
mov edx, DWORD PTR [rsp+100]
add edx, 1
mov DWORD PTR [rsp+100], edx
jmp .L217
And sorted
mov DWORD PTR [rsp+104], 0
mov DWORD PTR [rsp+100], 0
mov DWORD PTR [rsp+96], 0
call std::chrono::_V2::system_clock::now()
mov rbp, rax
mov rax, QWORD PTR [rsp+8]
jmp .L226
.L296:
mov edx, DWORD PTR [rsp+100]
add edx, 1
mov DWORD PTR [rsp+100], edx
.L224:
add rax, 4
cmp r14, rax
je .L295
.L226:
mov edx, DWORD PTR [rax]
lea ecx, [rdx-20]
cmp ecx, 74
jbe .L296
cmp edx, 19
jle .L297
mov edx, DWORD PTR [rsp+104]
add rax, 4
add edx, 1
mov DWORD PTR [rsp+104], edx
cmp r14, rax
jne .L226
.L295:
call std::chrono::_V2::system_clock::now()
.L297: // further down
mov edx, DWORD PTR [rsp+96]
add edx, 1
mov DWORD PTR [rsp+96], edx
jmp .L224
Так что это мало что нам говорит, за исключением того, что в последнем случае не требуется прогнозирование ветвления.
Сейчас я перепробовал все 6 комбинаций if, первые 2 - обратный и отсортированный. высокий>> 95, низкий < 20, средний 20-94 с 10000000 итераций каждая.
high, low, mid: 43000000ns
mid, low, high: 46000000ns
high, mid, low: 45000000ns
low, mid, high: 44000000ns
mid, high, low: 46000000ns
low, high, mid: 44000000ns
high, low, mid: 44000000ns
mid, low, high: 47000000ns
high, mid, low: 44000000ns
low, mid, high: 45000000ns
mid, high, low: 46000000ns
low, high, mid: 45000000ns
high, low, mid: 43000000ns
mid, low, high: 47000000ns
high, mid, low: 44000000ns
low, mid, high: 45000000ns
mid, high, low: 46000000ns
low, high, mid: 44000000ns
high, low, mid: 42000000ns
mid, low, high: 46000000ns
high, mid, low: 46000000ns
low, mid, high: 45000000ns
mid, high, low: 46000000ns
low, high, mid: 43000000ns
high, low, mid: 43000000ns
mid, low, high: 47000000ns
high, mid, low: 44000000ns
low, mid, high: 44000000ns
mid, high, low: 46000000ns
low, high, mid: 44000000ns
high, low, mid: 43000000ns
mid, low, high: 48000000ns
high, mid, low: 44000000ns
low, mid, high: 44000000ns
mid, high, low: 45000000ns
low, high, mid: 45000000ns
high, low, mid: 43000000ns
mid, low, high: 47000000ns
high, mid, low: 45000000ns
low, mid, high: 45000000ns
mid, high, low: 46000000ns
low, high, mid: 44000000ns
high, low, mid: 43000000ns
mid, low, high: 47000000ns
high, mid, low: 45000000ns
low, mid, high: 45000000ns
mid, high, low: 46000000ns
low, high, mid: 44000000ns
high, low, mid: 43000000ns
mid, low, high: 46000000ns
high, mid, low: 45000000ns
low, mid, high: 45000000ns
mid, high, low: 45000000ns
low, high, mid: 44000000ns
high, low, mid: 42000000ns
mid, low, high: 46000000ns
high, mid, low: 44000000ns
low, mid, high: 45000000ns
mid, high, low: 45000000ns
low, high, mid: 44000000ns
1900020, 7498968, 601012
Process returned 0 (0x0) execution time : 2.899 s
Press any key to continue.
Так почему порядок выше, ниже, меньше, чем медленнее (незначительно)
Потому что самый непредсказуемый является последним и поэтому никогда не запускается через предиктор ветвления.
if (i >= 95) ++nHigh; // most predictable with 94% taken
else if (i < 20) ++nLow; // (94-19)/94% taken ~80% taken
else if (i >= 20 && i < 95) ++nMid; // never taken as this is the remainder of the outfalls.
Таким образом, ветви будут предсказаны, взяты, взяты и оставлены с
6%+(0,94*)20% неверно предсказывает.
"Сортировка"
if (i >= 20 && i < 95) ++nMid; // 75% not taken
else if (i < 20) ++nLow; // 19/25 76% not taken
else if (i >= 95) ++nHigh; //Least likely branch
Ветви будут предсказаны с не взятым, не взятым и Шерлоком.
25% + (0,75*)24% ошибочно прогнозируют
Разница составляет 18-23% (измеренная разница ~9%), но нам нужно вычислять циклы вместо того, чтобы неправильно прогнозировать%.
Давайте предположим, что 17 циклов неверно предсказывают штраф на моем процессоре Nehalem, и что каждая проверка занимает 1 цикл для выдачи (4-5 инструкций), а цикл также занимает один цикл. Зависимости данных - это счетчики и переменные цикла, но как только неправильные прогнозы исчезнут, это не должно влиять на время.
Таким образом, для "обратного" мы получаем время (это должна быть формула, используемая в компьютерной архитектуре: количественный подход IIRC).
mispredict*penalty+count+loop
0.06*17+1+1+ (=3.02)
(propability)*(first check+mispredict*penalty+count+loop)
(0.19)*(1+0.20*17+1+1)+ (= 0.19*6.4=1.22)
(propability)*(first check+second check+count+loop)
(0.75)*(1+1+1+1) (=3)
= 7.24 cycles per iteration
и то же самое для "отсортировано"
0.25*17+1+1+ (=6.25)
(1-0.75)*(1+0.24*17+1+1)+ (=.25*7.08=1.77)
(1-0.75-0.19)*(1+1+1+1) (= 0.06*4=0.24)
= 8.26
(8.26-7.24) /8.26 = 13,8% против ~ 9% измеренных (близко к измеренным!?!).
Так что очевидное из ОП не очевидно.
С этими тестами другие тесты с более сложным кодом или большим количеством зависимостей от данных, безусловно, будут отличаться, поэтому оцените ваш случай.
Изменение порядка тестирования изменило результаты, но это могло быть из-за различных выравниваний начала цикла, которые в идеале должны быть выровнены на 16 байтов на всех более новых процессорах Intel, но не в этом случае.
Разместите их в любом логическом порядке. Конечно, ветвление может быть медленнее, но ветвление не должно быть основной работой вашего компьютера.
Если вы работаете над критичной для производительности частью кода, то, конечно, используйте логический порядок, оптимизацию по профилю и другие методы, но для общего кода я думаю, что это действительно скорее стилистический выбор.
Если вы уже знаете относительную вероятность оператора if-else, то для повышения производительности было бы лучше использовать отсортированный способ, поскольку он будет проверять только одно условие (истинное).
Несортированным способом компилятор проверит все условия без необходимости и займет время.