Каков эффект упорядочения, если ... еще, если утверждения по вероятности?

187

В частности, если у меня есть ряд 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операторы могут быть произвольно переупорядочены без каких-либо других последствий для поведения программы. В моем ответе три условных теста являются взаимоисключающими и не дают побочных эффектов. Конечно, если утверждения должны оцениваться в определенном порядке для достижения желаемого поведения, тогда вопрос эффективности является спорным.

Carlton
источник
35
Вы можете добавить примечание, что условия являются взаимоисключающими, в противном случае две версии не эквивалентны
idclev 463035818
28
Довольно интересно, как вопрос с самоответом за час получил более 20 голосов с довольно плохим ответом. Ничего не вызывая на OP, но начинающие должны остерегаться прыжков на повозке. Вопрос может быть интересным, но результаты сомнительны.
luk32
3
Я полагаю, что это можно описать как форму оценки короткого замыкания, поскольку попадание в одно сравнение отрицает попадание в другое сравнение. Я лично предпочитаю реализацию, подобную этой, когда одно быстрое сравнение, скажем, логическое, может помешать мне перейти к другому сравнению, которое может включать ресурсоемкие манипуляции со строками, регулярное выражение или взаимодействие с базой данных.
MonkeyZeus
11
Некоторые компиляторы предлагают возможность собирать статистику по взятым ветвям и передавать их обратно в компилятор, чтобы он мог лучше оптимизировать.
11
Если для вас
Джастин,

Ответы:

96

Как правило, большинство, если не все процессоры Intel, предполагают, что прямые ветви не берутся с первого раза, когда они их видят. Смотрите работу Годболта .

После этого ветвь переходит в кэш предсказания ветвления, и для информирования о будущем предсказании ветвления используется прошлое поведение.

Таким образом, в тесном цикле, эффект неправильного порядка будет относительно небольшим. Предиктор ветвей собирается узнать, какой набор веток наиболее вероятен, и если у вас нет нетривиального объема работы в цикле, небольшие различия не будут сильно складываться.

В общем коде большинство компиляторов по умолчанию (без другой причины) упорядочивают полученный машинный код примерно так, как вы его упорядочили в своем коде. Таким образом, если заявления являются прямыми ветвями, когда они терпят неудачу

Таким образом, вы должны упорядочить свои ветви в порядке уменьшения вероятности, чтобы получить лучший прогноз ветвления из «первого столкновения».

Микробенчмарк, который многократно зацикливается на множестве условий и выполняет тривиальную работу, будет зависеть от крошечных эффектов подсчета команд и тому подобного, а также от проблем, связанных с предсказанием относительных переходов. Так что в этом случае вы должны зарегистрироваться , так как практические правила не будут надежными.

Кроме того, векторизация и многие другие оптимизации применяются к крошечным узким циклам.

Итак, в общем коде, поместите наиболее вероятный код в ifблок, и это приведет к наименьшему количеству пропущенных некэшируемых предсказаний ветвления. В тесных циклах следуйте общему правилу, чтобы начать, и если вам нужно знать больше, у вас нет другого выбора, кроме как профилировать.

Естественно, все это выходит за рамки, если некоторые тесты намного дешевле, чем другие.

Якк - Адам Невраумонт
источник
19
Также стоит подумать о том, насколько дороги сами тесты: если один тест только немного более вероятен, но намного дороже, то, возможно, стоит поставить другой тест первым, потому что экономия от не дорогого теста, вероятно, перевесит сбережения от отраслевого прогноза и т. д.
psmears
Ссылка вы предоставили не поддерживают свой вывод , как правило, большинство , если не все процессоры Intel считать , передние ветви не будет принята в первый раз , они видят их . Фактически, это справедливо только для относительно непонятного процессора Arrendale, результаты которого показаны первыми. Основные результаты Ivy Bridge и Haswell вообще не подтверждают это. Haswell выглядит очень близко, чтобы «всегда предсказывать провал» для невидимых ветвей, а Ivy Bridge не совсем ясен.
BeeOnRope
Обычно считается, что процессоры на самом деле не используют статические предсказания, как это было в прошлом. Действительно, современная Intel, вероятно, использует нечто вроде вероятностного предиктора TAGE. Вы просто хешируете историю веток в различные таблицы истории и берете одну, которая соответствует самой длинной истории. Он использует «тег», чтобы избежать псевдонимов, но у тега есть только несколько битов. Если вы пропустите всю длину истории, вероятно, будет сделан некоторый прогноз по умолчанию, который не обязательно зависит от направления ветвления (в Haswell мы можем сказать, что это явно не так).
BeeOnRope
44

Я составил следующий тест, чтобы рассчитать время выполнения двух разных 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. Это, конечно, очень специфично для проблемы и не должно интерпретироваться как окончательный ответ.

Carlton
источник
9
OP следует соблюдать осторожность, так как изменение if... else ifоператора может существенно повлиять на то, как логика протекает через код. unlikelyПроверка не может прийти часто, но не может быть бизнес - необходимость для проверки unlikelyсостояния первого перед проверкой для других.
Люк Т Брукс
21
На 30% быстрее? Ты имеешь в виду, что это было быстрее, примерно на% от дополнительных утверждений, которые не нужно было выполнять? Кажется, довольно разумный результат.
UKMonkey
5
Как вы это сделали? Какой компилятор, процессор и т. Д.? Я уверен, что этот результат не является переносимым.
luk32
12
Проблема с этим микробенчмарком заключается в том, что ЦП определит, какая из ветвей наиболее вероятна, и кеширует его, когда вы неоднократно зацикливаетесь на нем. Если ветвления не проверялись в небольшом замкнутом цикле, кэш предсказания ветвления мог бы не содержать их в нем, и затраты могли бы быть намного выше, если ЦП угадал неправильное руководство по кэшу предсказания нулевого ветвления.
Якк - Адам Невраумонт
6
Этот тест не слишком надежен. Компиляция с gcc 6.3.0 : g++ -O2 -march=native -std=c++14дает небольшое преимущество отсортированным условным операторам, но в большинстве случаев разница в процентах между двумя запусками составляла ~ 5%. Несколько раз это было на самом деле медленнее (из-за различий). Я вполне уверен, что заказывая ifs не стоит беспокоиться; PGO, вероятно, полностью
Джастин
30

Нет, вы не должны, если вы действительно не уверены, что целевая система затронута. По умолчанию идут по читабельности.

Я очень сомневаюсь в ваших результатах. Я немного изменил ваш пример, чтобы отменить выполнение стало проще. 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;
    }
}
luk32
источник
При переключении порядка отсортированных и обратно отсортированных if-блоков я получаю такую ​​же разницу в производительности ~ 30%, как это было сделано в вашем коде. Я не уверен, почему Ideone и колиру не показывают никакой разницы.
Карлтон
Конечно интересно. Я попытаюсь получить некоторые данные для других систем, но это может занять целый день, пока мне не придется поиграться с этим. Вопрос интересный, особенно в свете ваших результатов, но они настолько впечатляющие, что мне пришлось перепроверить его.
luk32
Если вопрос, каков эффект? ответ не может быть нет !
PJTraill
Ага. Но я не получаю уведомления об обновлениях исходного вопроса. Они сделали формулировку ответа устаревшей. Сожалею. Я отредактирую содержание позже, чтобы указать, что он ответил на оригинальный вопрос и показал некоторые результаты, которые подтвердили исходную точку.
luk32
Это стоит повторить: «По умолчанию идем по удобочитаемости». Написание читаемого кода часто дает вам лучшие результаты, чем попытка получить крошечное повышение производительности (в абсолютном выражении), усложняя анализ вашего кода для людей.
Андрей Бреза
26

Просто мои 5 центов. Кажется, эффект упорядочения, если заявления должны зависеть от:

  1. Вероятность каждого оператора if.

  2. Количество итераций, чтобы можно было использовать предсказатель ветвления.

  3. Вероятные / маловероятные подсказки компилятора, то есть расположение кода.

Чтобы изучить эти факторы, я проверил следующие функции:

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

Но для итераций 8K результаты всегда немного лучше:

---------------------------------------------------------------------
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

Так что подсказки тоже помогают, но чуть-чуть.

Общий вывод: всегда проверяйте код, потому что результаты могут удивить.

Надеюсь, это поможет.

Андрей Берестовский
источник
1
i5 Nehalem? i5 Skylake? Просто сказать «i5» не очень конкретно. Кроме того, я полагаю, вы использовали g++ -O2или -O3 -fno-tree-vectorize, но вы должны сказать так.
Питер Кордес
Интересно, что with_hints по-прежнему отличается для упорядоченного и обратного. Было бы хорошо, если бы вы ссылались на источник где-нибудь. (например, ссылка Godbolt, предпочтительно полная ссылка, чтобы укорочение ссылки не могло сгнить.)
Питер Кордес
1
Тот факт, что предсказатель ветвления способен хорошо предсказывать даже при размере входных данных 4K, т. Е. Способен «сломать» эталон, запоминая результаты ветвления в цикле с периодом в тысячи, является свидетельством силы современного предсказатели ветвей. Имейте в виду, что предикторы в некоторых случаях весьма чувствительны к таким вещам, как выравнивание, поэтому трудно сделать убедительные выводы о некоторых изменениях. Например, вы заметили противоположное поведение для подсказки в разных случаях, но это можно объяснить подсказкой, случайно изменяющей компоновку кода, которая повлияла на предиктор.
BeeOnRope
1
@PeterCordes моя главная мысль: пока мы можем попытаться предсказать результаты изменения, все же мы лучше измерим производительность до и после изменения ... И вы правы, я должен был упомянуть, что он был оптимизирован с -O3 и процессором i5-4460 @ 3.20 ГГц
Андрей Берестовский,
19

Основываясь на некоторых других ответах здесь, похоже, что единственный реальный ответ: это зависит . Это зависит как минимум от следующего (хотя и не обязательно в этом порядке важности):

  • Относительная вероятность каждой ветви. Это оригинальный вопрос, который был задан. Основываясь на существующих ответах, кажется, что существуют некоторые условия, при которых упорядочение по вероятности помогает, но, похоже, это не всегда так. Если относительные вероятности не очень разные, то вряд ли будет какая-либо разница в том, в каком порядке они находятся. Однако, если первое условие происходит в 99,999% времени, а следующее - это доля того, что осталось, то я бы Предположим, что наиболее вероятным является выбор наиболее вероятного из них в плане времени.
  • Стоимость расчета истинного / ложного условия для каждой отрасли. Если временные затраты на тестирование условий действительно высоки для одной ветви по сравнению с другой, то это, вероятно, окажет значительное влияние на сроки и эффективность. Например, рассмотрим условие, для расчета которого требуется 1 единица времени (например, проверка состояния булевой переменной), в сравнении с другим условием, для расчета которого требуются десятки, сотни, тысячи или даже миллионы единиц времени (например, проверка содержимого файл на диске или выполнение сложного SQL-запроса к большой базе данных). Предполагая, что код проверяет условия по порядку каждый раз, более быстрые условия, вероятно, должны быть первыми (если они не зависят от других условий, которые не выполняются первыми).
  • Компилятор / Интерпретатор Некоторые компиляторы (или интерпретаторы) могут включать в себя оптимизации одного вида другого, которые могут повлиять на производительность (и некоторые из них присутствуют, только если определенные параметры выбраны во время компиляции и / или выполнения). Таким образом, если вы не проводите сравнение двух компиляций и исполнений идентичного кода в одной и той же системе с использованием одного и того же компилятора, где единственное различие заключается в порядке рассматриваемых веток, вам придется предоставить некоторую свободу действий для вариантов компилятора.
  • Операционная система / аппаратное обеспечение Как упоминали luk32 и Yakk, различные процессоры имеют свои собственные оптимизации (как и операционные системы). Таким образом, тесты снова подвержены изменениям здесь.
  • Частота выполнения блока кода Если к блоку, который включает ветви, редко обращаются (например, только один раз во время запуска), то, вероятно, очень мало имеет значение, в каком порядке вы устанавливаете ветви. С другой стороны, если ваш код работает с этим блоком кода во время критической части кода, то порядок может иметь большое значение (в зависимости от тестов).

Единственный способ узнать наверняка - это сравнить ваш конкретный случай, предпочтительно в системе, идентичной (или очень похожей) на предполагаемую систему, в которой в конечном итоге будет выполняться код. Если он предназначен для работы на множестве разных систем с различным аппаратным обеспечением, операционной системой и т. Д., То рекомендуется сравнить несколько вариантов, чтобы определить, какой из них лучше. Может быть даже хорошей идеей, чтобы код был скомпилирован с одним порядком в системе одного типа и другим порядком в системе другого типа.

Моё личное эмпирическое правило (в большинстве случаев при отсутствии эталона) это заказ на основе:

  1. Условия, которые основаны на результате предыдущих условий,
  2. Стоимость вычисления условия, затем
  3. Относительная вероятность каждой ветви.
Ampersat
источник
13

То, как я обычно это решаю для высокопроизводительного кода, заключается в поддержании порядка, который наиболее читабелен, но дает подсказки компилятору. Вот один пример из ядра 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 не имеет такой возможности .

JPA
источник
4
Это было бы более полезно , если вы могли бы объяснить , как likely()и unlikely()макросы определены, и включают в себя некоторую информацию о соответствующей функции компилятора.
Нейт
1
AFAIK, эти подсказки «только» изменяют структуру памяти блоков кода и приводят к переходу «да» или «нет». Это может иметь преимущества в производительности, например, для необходимости (или отсутствия таковой) чтения страниц памяти. Но это не меняет порядок, в котором оцениваются условия в длинном списке else-ifs
Hagen von Eitzen
@HagenvonEitzen Хм, да, это хороший момент, это не может повлиять на порядок, else ifесли компилятор не достаточно умен, чтобы знать, что условия являются взаимоисключающими.
jpa
7

Также зависит от вашего компилятора и платформы, для которой вы компилируете.

Теоретически, наиболее вероятное условие должно сделать скачок управления как можно меньше.

Обычно наиболее вероятное условие должно быть первым:

if (most_likely) {
     // most likely instructions
} else 

Самые популярные ASM основаны на условных ветвлений , которые прыгают , когда условие истинно . Этот код на C, скорее всего, будет переведен в такую ​​псевдо-асм:

jump to ELSE if not(most_likely)
// most likely instructions
jump to end
ELSE:

Это связано с тем, что переходы заставляют процессор отменять конвейер выполнения и останавливаться из-за изменения счетчика программы (для архитектур, которые поддерживают конвейеры, которые действительно распространены). Затем речь идет о компиляторе, который может применять, а может и не применять некоторые сложные оптимизации, касающиеся наличия статистически наиболее вероятного условия, чтобы элемент управления выполнял меньше переходов.

NoImaginationGuy
источник
2
Вы заявили, что условное ветвление возникает, когда условие истинно, но пример «псевдоасм» показывает обратное. Кроме того, нельзя сказать, что условные переходы (а тем более все переходы) задерживают конвейер, потому что современные процессоры обычно имеют прогноз ветвления. Фактически, если прогнозируется, что ветвь будет взята, но не взята, конвейер будет остановлен. Я бы все же попытался отсортировать условия в порядке убывания вероятности, но то, что компилятор и процессор делают из него, сильно зависит от реализации.
Арне Фогель
1
Я поставил «not (most_likely)», поэтому, если most_likely имеет значение true, управление будет продолжаться без прыжков.
NoImaginationGuy
1
«Самые популярные асмы основаны на условных ветвях, которые прыгают, когда условие выполняется». Какими ISA это будет? Это точно не относится ни к x86, ни к ARM. Ад для базовых процессоров ARM (и очень древних x86, даже для сложных бит / с они обычно все еще начинают с этого предположения, а затем адаптируются) предиктор ветвлений предполагает, что прямая ветвь не берется, а обратные ветвления всегда есть, так что противоположность утверждению правда.
Voo
1
Компиляторы, которые я пробовал в основном, использовали упомянутый выше подход для простого теста. Обратите внимание, что на clangсамом деле использовался другой подход для test2и test3: из-за эвристики, которая указывает на то, что тест < 0или, == 0вероятно, будет ложным, он решил клонировать оставшуюся часть функции на обоих путях, чтобы он мог выполнить condition == falseпуть сквозного падения. Это возможно только потому, что оставшаяся часть функции короткая: test4я добавил еще одну операцию, и она вернулась к подходу, описанному выше.
BeeOnRope
1
@ArneVogel - правильно спрогнозированные выбранные ветви не полностью тормозят конвейер на современных процессорах, но они все еще часто значительно хуже, чем не взятые: (1) они означают, что поток управления не является смежным, поэтому остальные инструкции после jmpне являются полезно, так что пропускная способность выборки / декодирования теряется (2) даже при прогнозировании современные большие ядра делают только одну выборку за цикл, поэтому он устанавливает жесткий предел в 1 взятый переход / цикл (OTOH современный Intel может сделать 2 не взятых / цикл) (3 ) предсказанию ветвлений сложнее иметь дело с взятыми последовательными ветвлениями, а в случае быстрых + медленных предикторов ...
BeeOnRope
6

Я решил повторить тест на своей машине, используя код 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, но не в этом случае.

Surt
источник
4

Разместите их в любом логическом порядке. Конечно, ветвление может быть медленнее, но ветвление не должно быть основной работой вашего компьютера.

Если вы работаете над критичной для производительности частью кода, то, конечно, используйте логический порядок, оптимизацию по профилю и другие методы, но для общего кода, я думаю, это действительно скорее стилистический выбор.

разъем
источник
6
Ошибки прогнозирования ветвления дороги. В microbenchmarks, они под стоило , потому что x86s имеют большую таблицу отраслевых предсказателей. Тесный цикл в тех же условиях приводит к тому, что процессор знает лучше, чем вы, какой из них наиболее вероятен. Но если у вас есть ветки по всему коду, у вашего кеша предсказания ветвлений не будет слотов, и процессор принимает все, что установлено по умолчанию. Знание того, что такое предположение по умолчанию, может сэкономить циклы по всей базе кода
Якк - Адам Невраумонт
@ Якк Джек - единственный правильный ответ. Не делайте оптимизаций, которые снижают читабельность, если ваш компилятор может выполнить эту оптимизацию. Вы бы не делали постоянное свертывание, удаление мертвого кода, развертывание цикла или любую другую оптимизацию, если бы ваш компилятор сделал это для вас, не так ли? Напишите свой код, используйте оптимизированную по профилю оптимизацию (которая предназначена для решения этой проблемы, потому что кодеры отстали в догадках), а затем посмотрите, оптимизирует это ваш компилятор или нет. В конце концов, в любом случае вы не хотите иметь ничего общего с критичным по производительности кодом.
Кристоф Дигельманн
@ Кристоф Я бы не стал включать код, который, как я знал, мертв. Я бы не использовал, i++когда ++iэто сделало бы, потому что я знаю, что i++для некоторых итераторов трудно оптимизировать, ++iи разница (для меня) не имеет значения. Речь идет об избежании пессимизации; размещение наиболее вероятного блока первым в качестве привычки по умолчанию не приведет к заметному снижению читабельности (и может даже помочь!), в то время как в результате получится код, дружественный к предсказанию ветвлений (и, таким образом, обеспечивающий равномерное небольшое повышение производительности, которое невозможно восстановить более поздней
микрооптимизацией
3

Если вы уже знаете относительную вероятность оператора if-else, то для повышения производительности было бы лучше использовать отсортированный способ, поскольку он будет проверять только одно условие (истинное).

Несортированным способом компилятор проверит все условия без необходимости и займет время.

адитья рават
источник