В частности, если у меня есть серия если
...иначе если
заявления, и я почему-то знаю заранее относительную вероятность того, что каждое выступление будет оценено как "истина", сколько разница по времени выполнения он делает, чтобы отсортировать их в порядке вероятности? Например, я предпочитаю этот:
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
Кажется очевидным, что отсортированный вариант будет быстрее, однако для удобства чтения или наличие побочных эффектов, мы, возможно, захотите, чтобы заказать их не оптимально. Это's также трудно сказать, насколько хорошо процессор будет делать с предсказанием ветвлений, пока вы на самом деле запустить код.
Так, в ходе экспериментов с этим, я в конечном итоге отвечая на свой собственный вопрос для конкретного случая, но я'd хотелось услышать другие мнения/выводы, а также.
Важно: этот вопрос предполагает, что если
заявления можно произвольно изменить без каких-либо других влияний на поведение программы. На мой ответ, три условных тестов являются взаимоисключающими и не производят никаких побочных эффектов. Конечно, если заявления должны быть оценены в определенном порядке для достижения определенного желаемого поведения, то вопрос об эффективности спорный.
Как правило, большинство, если не все процессоры Intel предположим, вперед ветки не взял в первый раз видят их. См. Godbolt's работы.
После этого ветвь идет в филиал кэша предсказание, и прошлое поведение используется для информирования будущего предсказания ветвлений.
Так в непрерывном цикле, эффект misordering будет относительно небольшой. Предиктор филиал будет узнать, что набор отраслей, скорее всего, и если у вас есть нетривиальный объем работы в цикле небольшие различия выиграл'т добавить до много.
В общем код, Большинство компиляторов по умолчанию (не хватает другой причине) буду заказывать произведенный машинный код примерно так, как вы заказали его в свой код. Таким образом, если заявления являются заявлениями филиалы, когда они терпят неудачу.
Так что вы должны заказать свои филиалы в порядке убывания вероятности, чтобы получить лучшие предсказания ветвлений от А "первая встреча" по.
В микротестов производительности, что петли плотно многократно набором условий и не тривиальная работа преобладают крошечные эффекты графа инструкция и тому подобное, и мало относительно ветке Проблемы прогнозирования. Поэтому в данном случае вы профиль, в качестве правила большого пальца выиграл'т быть надежным.
Кроме того, векторизация и многих других оптимизаций применить к крошечной петле.
Так что в целом код, ставить скорее всего кода внутри блока 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 с /О2, результаты показывают, что отсортированный версия стабильно около 28% быстрее, чем несортированный версия. В luk32'ы комментарий, я тоже поменяли порядок двух тестов, что дает заметную разницу (22% против 28%). Код был работать под Windows 7 на Intel процессор Xeon серии E5-2697 V2 с. Это, конечно, очень конкретных проблем, и не следует рассматривать как окончательный ответ.
Нет, вы не должны, если вы действительно уверены, что пострадавших целевой системы. По умолчанию идут на читаемость.
Я сильно сомневаюсь в ваших результатах. Я'вэ изменен ваш пример немного, так что задним ходом выполнения легче. Ideone, а последовательно показывает, что обратный порядок быстрее, хотя и не намного. На некоторых работает даже это иногда переворачивается. Я'd не сказать, результаты не являются окончательными. coliru сообщает никакой реальной разницы, а также. Я могу проверить процессор Exynos5422 на мой о ODROID xu4 позже.
Дело в том, что современные процессоры имеют предикторы филиала. Есть много-много логики, посвященный предварительной выборки данных и инструкций, а также современных x86 процессоров достаточно умный, когда дело доходит до этого. Некоторые стройнее архитектур типа оружия или 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;
}
}
Просто мои 5 копеек. Кажется, эффект заказ, если отчетность должна зависеть от:
Вероятность каждой инструкции if.
Количество итераций, поэтому предиктора власть может окочуриться.
Вероятно/маловероятно компилятором подсказок, т. е. макет кода.
Для изучения этих факторов, я аттестованы следующие функции:
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;
}
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;
}
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;
}
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 (т. е. вероятность в %% к высоко вероятным, если заявление), второй аргумент-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
Для 4К итераций и (почти) 100% вероятность очень понравилось выступление разница огромная 223%:
ordered_ifs/100/4 1673 НС НС 1673 417073 reversed_ifs/100/4 3738 НС 188087 3738 НС
Для 4К итераций и 50% вероятность очень понравилось выступление разница составляет около 14%:
---------------------------------------------------------------------
Benchmark Time CPU Iterations
---------------------------------------------------------------------
ordered_ifs/50/4 4660 ns 4658 ns 150948
reversed_ifs/50/4 5342 ns 5341 ns 126800
Разница между 4K и 8K итераций для (почти) 100% вероятность очень понравилось высказывание примерно в два раза (как и ожидалось):
ordered_ifs/100/4 1673 НС НС 1673 417073 ordered_ifs/100/8 3381 НС НС 3381 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
Так что на мой и5 предиктора филиал не впечатляюще для не-так-вероятно, ветками и большими наборами данных.
Для 4К итераций результаты несколько хуже для 50% вероятности, и несколько лучше, почти 100% вероятность:
ordered_ifs/50/4 4660 НС НС 4658 150948 ordered_ifs/100/4 1673 НС НС 1673 417073 ordered_ifs_with_hints/50/4 5551 НС НС 5551 125160 ordered_ifs_with_hints/100/4 1575 НС НС 1575 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
Итак, советы тоже помогают, но только немного.
Общий вывод: всегда тестируйте код, потому что результаты могут удивить.
Надеюсь, что помогает.
Опираясь на некоторые другие ответы здесь, похоже, единственный реальный ответ: зависит. Это зависит от того, по крайней мере следующее (но не обязательно в этом порядке важности):
Единственный способ узнать наверняка, является эталоном вашем конкретном случае, желательно на системы, идентичные (или очень похожие) в системе, на которой код будет, в конце концов. Если он предназначен для работы на множестве различных систем с различным аппаратным обеспечением, операционной системой и т. д. тогда это хорошая идея, чтобы тест в нескольких вариациях, чтобы увидеть, какая из них лучше. Это может быть даже хорошая идея, чтобы код был скомпилирован с один заказ на один тип системы, и другой заказ на другой тип системы.
Мое личное правило (в большинстве случаев, в отсутствии эталона) на основе:
Так, как я обычно это решается для высокопроизводительного кода является сохранение того, что является наиболее читаемым, но обеспечивают подсказки для компилятора. Вот один пример из ядре 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);
Здесь предполагается, что проверка пройдет, а ошибка не вернулась в "Рес". Насторожил какой-либо из этих пунктов, если бы только запутать код макросов, но вероятно ()
и вряд ли()
на самом деле помочь удобочитаемости, указывая на то, что это обычный случай и что является исключением.
В реализации Linux эти макросы используются особенности ССЗ. Кажется, что Clang и компилятора Intel c поддержкой тот же синтаксис, но индекса MSVC не'Т есть такая функция.
Также зависит от вашего компилятора и платформы вы компилируете для.
В теории, скорее всего, условие должно сделать управление прыгнуть как можно меньше.
Как правило, скорее всего, условие должно быть первым:
if (most_likely) {
// most likely instructions
} else …
Наиболее популярные АСМ основаны на условных ветвей, которые прыгают, когда состояние правда. Что код на Си будет скорее всего переведен на таких псевдо АСМ:
jump to ELSE if not(most_likely)
// most likely instructions
jump to end
ELSE:
…
Это потому, что прыжки сделать процессор прервать выполнение трубопровода и заглохнет, потому что программа счетчик меняли (для архитектур, поддерживающих трубопроводы, которые действительно распространен). Тогда речь идет о компиляторе, который может или не может применить некоторые сложные оптимизации, о том, статистически наиболее вероятно состояние, чтобы получить контроль сделает меньше прыжков.
Я решил повторно проверить на моей собственной машине, используя код Lik32. Пришлось менять его из-за моей Windows или компилятор думает высокое разрешение 1мс, используя
mingw32-G++и.ехе -О3 -стены -с std=с++11 -fexceptions -г
vector<int> rand_vec(10000000);
ССЗ сделал такое же преобразование на исходные коды.
Обратите внимание, что проверены в качестве третьего только первые два условия всегда должны быть истинными, 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 комбинаций, если'ы, топ-2 являются оригинальными обратного и сортируют. высокая >= 95, низкий < 20, Mid-это 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% mispredicts.
на "сортировка"и
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% mispredicts
Давая 18-23% разницы (измеряется разница ~9%), но нужно посчитать циклы вместо mispredicting %.
Позвольте'ы предполагаем 17 циклов mispredict штраф на мой процессор Nehalem и что каждая проверка занимает 1 цикл проблемы (4-5 инструкции) и цикл занимает один цикл слишком. Зависимости данных счетчиков и петли переменные, но как только mispredicts находятся вне пути, он должен'т повлиять на сроки.
Так что для "от обратного" Мы вам тайминги (это должна быть формула, используемая в компьютерная архитектура: количественный подход МСИО).
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, но это'т в этом случае.
Поместить их в любом логическом порядке. Конечно, власть может быть медленнее, но ветвления не следует большинство работы делает ваш компьютер.
Если вы работаете на критическое для производительности части кода, то, конечно, использовать логический порядок, профильная оптимизация и другие методы, но для общего кода, я думаю, что его действительно больше стилистический выбор.
Если вы уже знаете относительная вероятность, если-else оператор,то для целей исполнения было бы лучше использовать отсортированный так, как он будет проверять только одно условие(истинный).
В неразобравшись, как компилятор будет проверять без надобности все условия и потребует времени.