Почему обработка отсортированного массива выполняется быстрее, чем обработка несортированного массива?

Ответ для быстрого и простого понимания (подробности читайте в других)

Эта концепция называется предсказанием ветвления

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

Проблема возникает при условном переходе, когда есть два возможных пути или части кода, которые могут быть выполнены.

Когда предсказание оказалось верным, метод оптимизации сработал.

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

Здравый смысл подсказывает, что прогнозы для чего-то отсортированного намного точнее, чем прогнозы для чего-то несортированного.

визуализация предсказания ветвления:

отсортировано
несортированный

Почему обработка отсортированного массива выполняется быстрее, чем обработка несортированного массива?

Пример из кода:

// CPP program to demonstrate processing
// time of sorted and unsorted array
#include <iostream>
#include <algorithm>
#include <ctime>
using namespace std;

const int N = 100001;

int main()
{
    int arr[N];

    // Assign random values to array
    for (int i=0; i<N; i++)
        arr[i] = rand()%N;

    // for loop for unsorted array
    int count = 0;
    double start = clock();
    for (int i=0; i<N; i++)
        if (arr[i] < N/2)
            count++;

    double end = clock();
    cout << "Time for unsorted array :: "
        << ((end - start)/CLOCKS_PER_SEC)
        << endl;
    sort(arr, arr+N);

    // for loop for sorted array
    count = 0;
    start = clock();

    for (int i=0; i<N; i++)
        if (arr[i] < N/2)
            count++;

    end = clock();
    cout << "Time for sorted array :: "
        << ((end - start)/CLOCKS_PER_SEC)
        << endl;

    return 0;
}

Время выполнения:

Заключение:

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

Что такое прогнозирование переходов?

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

Как предсказание ветвления неприменимо в приведенном выше случае?

Условие if проверяет, что arr [i] <5000, но если вы наблюдаете в случае отсортированного массива, после передачи числа 5000 условие всегда ложно, а до этого всегда истинно. ЦП распознает этот шаблон и сможет правильно предсказать, какая инструкция будет выполняться следующей после условного перехода, вместо того, чтобы иногда перематывать назад после неправильного предположения.

Работа алгоритма прогнозирования ветвления:

Прогнозирование ветвлений работает по шаблону, которому следует алгоритм, или, в основном, по истории, как оно было выполнено на предыдущих шагах. Если предположение верное, то ЦП продолжает выполнение, а если что-то пойдет не так, ЦП должен очистить конвейер, откатиться к ветви и перезапустить с начала.

Возможно, вам не стоит сортировать данные, поскольку диапазон выходных значений ограничен. Намного быстрее вычислить, сколько раз встречается каждое значение.

например у вас есть 20 данных между 0..3, тогда вы можете зарезервировать 3 счетчика. В итоге у вас может быть: {0: 10x, 1: 8x, 2: 2x}

Чтобы преобразовать этот массив обратно в линейный массив, просто выведите 10x 0, 8x 1, 2x 2.

Если значения не равны 0..2, но все еще ограничены, вы все равно можете рассмотреть этот метод. Сортировка всегда идет медленно! Другое преимущество: это небольшой код, его легко читать и тестировать, меньше ошибок.

ПРОГНОЗ ОТРАСЛИ

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

data[c] >= 128

Получите дополнительную помощь по этой ссылке: Прогнозирование множественных ветвлений для суперскалярных задач с широкими проблемами

Ответ Бьярна Страуструпа на этот вопрос:

Это похоже на вопрос для интервью. Это правда? Как бы вы узнали? Плохая идея - отвечать на вопросы об эффективности без предварительного измерения, поэтому важно знать, как это делать.

Итак, я попробовал с вектором из миллиона целых чисел и получил:

Already sorted    32995 milliseconds
Shuffled          125944 milliseconds

Already sorted    18610 milliseconds
Shuffled          133304 milliseconds

Already sorted    17942 milliseconds
Shuffled          107858 milliseconds

Я запускал это несколько раз, чтобы убедиться. Да, феномен реальный. Мой ключевой код был:

void run(vector<int>& v, const string& label)
{
    auto t0 = system_clock::now();
    sort(v.begin(), v.end());
    auto t1 = system_clock::now();
    cout << label
         << duration_cast<microseconds>(t1 — t0).count()
         << " milliseconds\n";
}

void tst()
{
    vector<int> v(1'000'000);
    iota(v.begin(), v.end(), 0);
    run(v, "already sorted ");
    std::shuffle(v.begin(), v.end(), std::mt19937{ std::random_device{}() });
    run(v, "shuffled    ");
}

По крайней мере, такое явление реально с этим компилятором, стандартной библиотекой и настройками оптимизатора. Различные реализации могут давать и дают разные ответы. Фактически, кто-то провел более систематическое исследование (его можно найти при быстром поиске в Интернете), и большинство реализаций показывают этот эффект.

Одна из причин - предсказание ветвления: ключевая операция в алгоритме сортировки - “if(v[i] < pivot]) …” или эквивалентная. Для отсортированной последовательности этот тест всегда верен, тогда как для случайной последовательности выбранная ветвь изменяется случайным образом.

Другая причина в том, что когда вектор уже отсортирован, нам никогда не нужно перемещать элементы в их правильное положение. Эффект от этих мелких деталей равен пяти или шести, которые мы видели.

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

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

Этот вопрос коренится в моделях прогнозирования ветвлений на ЦП. Я бы рекомендовал прочитать эту статью:

Увеличение скорости выборки инструкций с помощью прогнозирования нескольких переходов и кеширования адресов переходов

Когда вы отсортировали элементы, IR может не беспокоиться о том, чтобы получать все инструкции ЦП снова и снова. Он извлекает их из кеша.

Предположение других ответов о необходимости сортировки данных неверно.

Следующий код сортирует не весь массив, а только его 200-элементные сегменты, и поэтому выполняется быстрее всего.

Сортировка только k-элементных секций завершает предварительную обработку за линейное время, O(n), а не за O(n.log(n)) время, необходимое для сортировки всего массива.

#include <algorithm>
#include <ctime>
#include <iostream>

int main() {
    int data[32768]; const int l = sizeof data / sizeof data[0];

    for (unsigned c = 0; c < l; ++c)
        data[c] = std::rand() % 256;

    // sort 200-element segments, not the whole array
    for (unsigned c = 0; c + 200 <= l; c += 200)
        std::sort(&data[c], &data[c + 200]);

    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i) {
        for (unsigned c = 0; c < sizeof data / sizeof(int); ++c) {
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    std::cout << static_cast<double>(clock() - start) / CLOCKS_PER_SEC << std::endl;
    std::cout << "sum = " << sum << std::endl;
}

Это также «доказывает», что это не имеет ничего общего с какой-либо алгоритмической проблемой, такой как порядок сортировки, и это действительно предсказание ветвления.

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

Внутренний цикл этого алгоритма на языке ассемблера ARM будет выглядеть примерно так:

MOV R0, #0   // R0 = sum = 0
MOV R1, #0   // R1 = c = 0
ADR R2, data // R2 = addr of data array (put this instruction outside outer loop)
.inner_loop  // Inner loop branch label
    LDRB R3, [R2, R1]   // R3 = data[c]
    CMP R3, #128        // compare R3 to 128
    ADDGE R0, R0, R3    // if R3 >= 128, then sum += data[c] -- no branch needed!
    ADD R1, R1, #1      // c++
    CMP R1, #arraySize  // compare c to arraySize
    BLT inner_loop      // Branch to inner_loop if c < arraySize

Но на самом деле это часть более широкой картины:

CMP коды операций всегда обновляют биты состояния в регистре состояния процессора (PSR), потому что это их цель, но большинство других инструкций не затрагивают PSR, если вы не добавите к инструкции дополнительный суффикс S, указав что PSR должен быть обновлен на основе результата инструкции. Так же, как 4-битный суффикс условия, возможность выполнять инструкции без влияния на PSR - это механизм, который снижает потребность в ветвях на ARM, а также облегчает отправку не по порядку на аппаратном уровне , потому что после выполняя некоторую операцию X, которая обновляет биты состояния, впоследствии (или параллельно) вы можете выполнить кучу другой работы, которая явно не должна влиять (или быть затронутой) битами состояния, затем вы можете проверить состояние установленных битов состояния ранее X.

Поле проверки условий и дополнительное поле «установить бит состояния» можно комбинировать, например:

• ADD R1, R2, R3 выполняет R1 = R2 + R3 без обновления каких-либо битов состояния.
• ADDGE R1, R2, R3 выполняет ту же операцию, только если предыдущая инструкция, которая повлияла на биты состояния, привела к условию «Больше чем» или «Равно».
• ADDS R1, R2, R3 выполняет добавление, а затем обновляет флаги N, Z, C и V в регистре состояния процессора в зависимости от того, был ли результат отрицательным, нулевым, перенесенным (для добавления без знака) или переполнен (для подписанного дополнения).
• ADDSGE R1, R2, R3 выполняет добавление только в том случае, если проверка GE истинна, а затем обновляет биты состояния на основе результата сложения.

Большинство архитектур процессоров не имеют этой возможности указать, следует ли обновлять биты состояния для данной операции, что может потребовать написания дополнительного кода для сохранения и последующего восстановления битов состояния, или может потребовать дополнительных ветвей, или может ограничить эффективность неупорядоченного выполнения процессора: одним из побочных эффектов большинства архитектур наборов команд ЦП, принудительно обновляющих биты состояния после большинства инструкций, является то, что гораздо сложнее определить, какие инструкции могут выполняться параллельно, не мешая друг другу. Обновление битов состояния имеет побочные эффекты, поэтому имеет линеаризирующий эффект на код. Способность ARM смешивать и сопоставлять тестирование условий без ветвлений для любой инструкции с возможностью обновлять или не обновлять биты состояния после любой инструкции является чрезвычайно мощной как для программистов на ассемблере, так и для компиляторов, и дает очень эффективный код.

Когда вам не нужно разветвляться, вы можете избежать временных затрат на промывку конвейера для того, что в противном случае было бы короткими ветвями, и вы можете избежать сложности дизайна многих форм спекулятивной оценки. Влияние на производительность первоначальной наивной реализации средств защиты от многих недавно обнаруженных уязвимостей процессора (Spectre и т. Д.) Показывает, насколько производительность современных процессоров зависит от сложной логики умозрительной оценки. Благодаря короткому конвейеру и значительному снижению потребности в ветвлении ARM не нужно полагаться на умозрительные оценки так же, как на процессоры CISC. (Конечно, высокопроизводительные реализации ARM включают в себя умозрительную оценку, но это меньшая часть истории производительности.)

Если вы когда-нибудь задавались вопросом, почему ARM оказалась настолько феноменально успешной, насколько блестящей эффективностью и взаимодействием этих двух механизмов (в сочетании с другим механизмом, который позволяет вам «сдвинуть ствол» влево или вправо один из двух аргументов любого арифметического оператора или смещения оператора доступа к памяти без дополнительных затрат) являются важной частью истории, потому что они являются одними из величайших источников эффективности архитектуры ARM. Невозможно переоценить великолепие оригинальных дизайнеров ARM ISA 1983 года, Стива Фербера и Роджера (ныне Софи) Уилсона.

Сортированные массивы обрабатываются быстрее, чем несортированный массив, из-за явления, называемого предсказанием ветвления.

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

Выполнение неверного прогноза приводит к возврату к предыдущему шагу и выполнению с другим прогнозом. Если прогноз верен, код перейдет к следующему шагу. Неправильный прогноз приводит к повторению того же шага до тех пор, пока не будет получен правильный прогноз.

Ответ на ваш вопрос очень прост.

В несортированном массиве компьютер делает несколько прогнозов, что увеличивает вероятность ошибок. В то время как в отсортированном массиве компьютер делает меньше прогнозов, что снижает вероятность ошибок. Чтобы сделать больше прогнозов, потребуется больше времени.

Сортированный массив: прямая дорога

____________________________________________________________________________________
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT

Несортированный массив: изогнутая дорога

______   ________
|     |__|

Прогнозирование ответвления: угадывание / прогнозирование прямой дороги и следование по ней без проверки

___________________________________________ Straight road
 |_________________________________________|Longer road

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

Также хочу процитировать @Simon_Weaver из комментариев:

Он не делает меньше прогнозов - он делает меньше неверных прогнозов. Он по-прежнему должен прогнозировать каждый раз в цикле ...

​​Помимо того факта, что прогнозирование ветвлений может замедлить вас, у отсортированного массива есть еще одно преимущество:

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

 // sort backwards (higher values first), may be in some other part of the code
 std::sort(data, data + arraySize, std::greater<int>());

 for (unsigned c = 0; c < arraySize; ++c) {
       if (data[c] < 128) {
              break;
       }
       sum += data[c];               
 }

Как уже упоминалось другими, за загадкой скрывается Branch Predictor.

Я не пытаюсь что-то добавить, а объясняю концепцию по-другому. В вики есть краткое введение, содержащее текст и диаграммы. Мне нравится приведенное ниже объяснение, в котором используется диаграмма для интуитивной разработки предсказателя ветвлений.

В компьютерной архитектуре предсказателем ветвления является цифровая схема, которая пытается угадать, в каком направлении ветвь (например, if-then-else структура) пойдет до того, как это станет известно наверняка. В цель предсказателя ветвления - улучшить поток в конвейер команд. Предикторы ветвления играют решающую роль в достижение высокой эффективности во многих современных конвейерных архитектуры микропроцессоров, такие как x86.

Двустороннее ветвление обычно реализуется с помощью условного перехода. инструкция. Условный переход можно либо «не выполнять», либо продолжить. выполнение с первой ветвью кода, которая следует сразу за после условного перехода, или его можно "взять" и перейти к другое место в программной памяти, где находится вторая ветвь кода. хранится. Доподлинно неизвестно, будет ли условный переход приняты или не приняты до тех пор, пока условие не будет рассчитано и условный переход в инструкции прошел стадию исполнения трубопровод (см. рис.1).

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

1. Без предиктора ветвления.

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

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

Для выполнения 3 инструкций потребуется 9 тактов.

2. Используйте предсказатель ветвления и не выполняйте условный переход. Предположим, что прогноз , а не с условным переходом.

Для выполнения 3 инструкций потребуется 7 тактов.

3. Используйте предсказатель ветвления и выполните условный переход. Предположим, что прогноз , а не с условным переходом.

Для выполнения 3 инструкций потребуется 9 тактов.

Время, потраченное впустую в случае неверного предсказания перехода, равно количество этапов в конвейере от этапа выборки до выполнить этап. Современные микропроцессоры, как правило, имеют довольно длинные конвейеры, так что задержка неверного предсказания составляет от 10 до 20 часов циклы. В результате увеличение длины трубопровода увеличивает потребность в более продвинутый предсказатель ветвлений.

Как видите, похоже, у нас нет причин не использовать Branch Predictor.

Это довольно простая демонстрация, которая разъясняет самую основную часть Branch Predictor. Если эти гифки раздражают, пожалуйста, удалите их из ответа, и посетители также могут получить исходный код живой демонстрации из BranchPredictorDemo

Речь идет о предсказании переходов. Что это?

• Предиктор ветвления - это один из древних методов повышения производительности, который до сих пор находит применение в современных архитектурах. Хотя простые методы прогнозирования обеспечивают быстрый поиск и энергоэффективность, они страдают от высокого уровня ошибочного прогнозирования.

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

• В дополнение к этому, в сложных методах прогнозирования время, необходимое для прогнозирования ветвей, само по себе очень велико - от 2 до 5 циклов - что сопоставимо со временем выполнения фактических ветвей.

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

На самом деле существует три разных типа ветвей:

Условные переходы вперед - в зависимости от условия выполнения ПК (счетчик программ) изменяется так, чтобы указывать на адрес вперед в потоке команд.

Обратные условные переходы - ПК изменен так, чтобы указывать назад в потоке команд. Ветвление основано на некотором условии, например, обратном переходе к началу программного цикла, когда тест в конце цикла утверждает, что цикл должен быть выполнен снова.

Безусловные переходы - сюда входят переходы, вызовы процедур и возвраты, не имеющие определенного условия. Например, инструкция безусловного перехода может быть закодирована на языке ассемблера как просто «jmp», и поток инструкций должен быть немедленно направлен в целевое местоположение, на которое указывает инструкция перехода, тогда как условный переход может быть закодирован как «jmpne» перенаправит поток инструкций только в том случае, если результат сравнения двух значений в предыдущих инструкциях «сравнения» показывает, что значения не равны. (Сегментированная схема адресации, используемая архитектурой x86, добавляет дополнительную сложность, поскольку переходы могут быть либо «близкими» (внутри сегмента), либо «далекими» (вне сегмента). Каждый тип по-разному влияет на алгоритмы прогнозирования ветвлений.)

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

Ссылки:

• Предиктор ветвления

• Демонстрация самопрофилирования

• Обзор прогнозирования ветвления

• Прогнозирование ветвления (с использованием машины обратного пути)

Прирост предсказания ветвления!

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

if (expression)
{
    // Run 1
} else {
    // Run 2
}

Всякий раз, когда есть оператор if-else \ switch, выражение должно быть вычислено, чтобы определить, какой блок должен быть выполнен. В ассемблерном коде, сгенерированном компилятором, вставляются условные инструкции ветки.

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

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

Визуализация:

Допустим, вам нужно выбрать маршрут 1 или маршрут 2. Ожидая, пока ваш партнер проверит карту, вы остановились в ## и подождали, или вы можете просто выбрать маршрут 1, и, если вам повезет (маршрут 1 правильный маршрут), тогда отлично, вам не пришлось ждать, пока ваш партнер проверит карту (вы сэкономили время, которое потребовалось бы ему, чтобы проверить карту), иначе вы просто повернете назад.

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

 O      Route 1  /-------------------------------
/|\             /
 |  ---------##/
/ \            \
                \
        Route 2  \--------------------------------

Это точно! ...

Прогнозирование переходов замедляет выполнение логики из-за переключения, которое происходит в вашем коде! Это как если бы вы идете по прямой улице или по улице с большим количеством поворотов, наверняка прямой будет быстрее! ...

Если массив отсортирован, ваше условие ложно на первом шаге: data[c] >= 128, затем становится истинным значением на всем пути до конца улицы. Так вы быстрее доберетесь до конца логики. С другой стороны, используя несортированный массив, вам нужно много поворачивать и обрабатывать, что наверняка заставит ваш код работать медленнее ...

Посмотрите на изображение, которое я создал для вас ниже. Какая улица будет закончена быстрее?

Таким образом, программно предсказание ветвления замедляет процесс ...

Также в конце приятно знать, что у нас есть два типа предсказаний ветвлений, каждый из которых по-разному повлияет на ваш код:

1. Статический

2. Динамический

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

Чтобы эффективно написать код, чтобы воспользоваться этими правила, при написании операторов if-else или switch проверяйте наиболее Сначала распространенные случаи, а затем постепенно снижайте их до наименее распространенных. Циклы не обязательно требуют особого упорядочивания кода для статическое предсказание ветвления, так как только условие итератора цикла обычно используется.

На этот вопрос уже много раз были даны превосходные ответы. Тем не менее, я хотел бы обратить внимание группы на еще один интересный анализ.

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

Ссылка здесь: Демонстрация самопрофилирования

Официальный ответ будет от

1. Intel - предотвращение затрат на неверное прогнозирование филиалов
2. Intel - реорганизация ветвей и циклов для предотвращения неверных прогнозов
3. Научные статьи - архитектура компьютера прогнозирования отрасли
4. Книги: J.L. Hennessy, D.A. Паттерсон: Компьютерная архитектура: количественный подход
5. Статьи в научных изданиях: Т.Ю. Ага, Ю.Н. Патт сделал много таких предсказаний ветвлений.

На этой прекрасной диаграмме вы также можете увидеть, почему предсказатель ветвления запутался.

Каждый элемент в исходном коде представляет собой случайное значение

data[c] = std::rand() % 256;

, поэтому предсказатель будет менять сторону при ударе std::rand().

С другой стороны, после сортировки предиктор сначала перейдет в состояние "строго не принято", а когда значения изменятся на высокое значение, предиктор за три прогона полностью изменится от "строго непринято" до "строго". принято.

Часто используемые логические операции в C ++ приводят к появлению множества ветвей в скомпилированной программе. Если эти ветви находятся внутри циклов и их трудно предсказать, они могут значительно замедлить выполнение. Логические переменные хранятся как 8-битные целые числа со значением 0 для false и 1 для true.

Логические переменные переопределены в том смысле, что все операторы, которые имеют логические переменные в качестве входных данных, проверяют, имеют ли входные данные любое другое значение, кроме 0 или 1, но операторы, которые имеют логические значения в качестве выходных данных, не могут давать никакого другого значения, кроме 0 или 1. Это делает операции с логическими переменными в качестве входных данных менее эффективными, чем необходимо. Рассмотрим пример:

bool a, b, c, d;
c = a && b;
d = a || b;

Обычно это реализуется компилятором следующим образом:

bool a, b, c, d;
if (a != 0) {
    if (b != 0) {
        c = 1;
    }
    else {
        goto CFALSE;
    }
}
else {
    CFALSE:
    c = 0;
}
if (a == 0) {
    if (b == 0) {
        d = 0;
    }
    else {
        goto DTRUE;
    }
}
else {
    DTRUE:
    d = 1;
}

Этот код далек от оптимального. Ветвления могут занять много времени в случае ошибочных прогнозов. Логические операции можно сделать намного более эффективными, если точно известно, что операнды не имеют других значений, кроме 0 и 1. Причина, по которой компилятор не делает такого предположения, заключается в том, что переменные могут иметь другие значения, если они не инициализированы или получены из неизвестных источников. Приведенный выше код можно оптимизировать, если a и b были инициализированы допустимыми значениями или если они поступают от операторов, производящих логический вывод. Оптимизированный код выглядит так:

char a = 0, b = 1, c, d;
c = a & b;
d = a | b;

char используется вместо bool, чтобы можно было использовать побитовые операторы (& и |) вместо логических операторов (&& и ||). Поразрядные операторы - это отдельные инструкции, которые занимают только один такт. Оператор ИЛИ (|) работает, даже если a и b имеют значения, отличные от 0 или 1. Операторы AND (&) и EXCLUSIVE OR (^) могут давать противоречивые результаты, если операнды имеют значения, отличные от 0 и 1.

~ нельзя использовать для НЕ. Вместо этого вы можете создать логическое НЕ для переменной, которая известна как 0 или 1, с помощью XOR с помощью 1:

bool a, b;
b = !a;

можно оптимизировать до:

char a = 0, b;
b = a ^ 1;

a && b нельзя заменить на a & b, если b - это выражение, которое не следует вычислять, если a равно false (&& не будет оценивать b, <6699> будет Аналогично, a || b нельзя заменить на a | b, если b - это выражение, которое не следует вычислять, если a равно true.

Использование побитовых операторов более выгодно, если операнды являются переменными, чем если операнды являются сравнениями:

bool a; double x, y, z;
a = x > y && z < 5.0;

является оптимальным в большинстве случаев (если вы не ожидаете, что выражение && будет генерировать множество ошибочных прогнозов ветвлений).

В той же строке (я думаю, что это не было выделено ни одним ответом) полезно упомянуть, что иногда (особенно в программном обеспечении, где важна производительность - например, в ядре Linux) вы можете найти некоторые операторы if, подобные следующему:

if (likely( everything_is_ok ))
{
    /* Do something */
}

​​или аналогично:

if (unlikely(very_improbable_condition))
{
    /* Do something */    
}

И likely(), и unlikely() на самом деле являются макросами, которые определяются с помощью чего-то вроде __builtin_expect GCC, чтобы помочь компилятору вставить код прогноза в пользу условия с учетом информации, предоставленной пользователем. GCC поддерживает другие встроенные команды, которые могут изменять поведение выполняющейся программы или выдавать инструкции низкого уровня, такие как очистка кеша и т. Д. См. эту документацию, в которой рассматриваются доступные встроенные функции GCC.

Обычно такого рода оптимизации в основном встречаются в приложениях жесткого реального времени или встроенных системах, где время выполнения имеет значение и критично. Например, если вы проверяете состояние ошибки, которое происходит только 1/10000000 раз, то почему бы не сообщить об этом компилятору? Таким образом, по умолчанию прогноз ветвления будет предполагать, что условие ложно.

Указанное выше поведение происходит из-за предсказания ветвления.

Чтобы понять предсказание ветвления, нужно сначала понять Instruction Pipeline :

Любая инструкция разбита на последовательность шагов, так что разные шаги могут выполняться одновременно и параллельно. Этот метод известен как конвейер команд и используется для увеличения пропускной способности в современных процессорах. Чтобы лучше понять это, посмотрите этот пример в Википедии.

Как правило, современные процессоры имеют довольно длинные конвейеры, но для простоты рассмотрим только эти 4 шага.

1. IF - Получить инструкцию из памяти
2. ID - расшифровать инструкцию
3. EX - Выполнить инструкцию
4. WB - обратная запись в регистр ЦП

4-ступенчатый конвейер в целом для 2 инструкций.

Возвращаясь к вышеуказанному вопросу, давайте рассмотрим следующие инструкции:

                        A) if (data[c] >= 128)
                                /\
                               /  \
                              /    \
                        true /      \ false
                            /        \
                           /          \
                          /            \
                         /              \
              B) sum += data[c];          C) for loop or print().

Без прогнозирования ветвления произойдет следующее:

Для выполнения инструкции B или инструкции C процессору придется ждать, пока инструкция A не дойдет до стадии EX в конвейере, поскольку решение перейти к инструкции B или инструкции C зависит от результата инструкции A. Итак, конвейер будет выглядеть так.

если условие возвращает истину:

Если условие возвращает false:

В результате ожидания результата инструкции A общее количество циклов ЦП, потраченных в приведенном выше случае (без предсказания ветвления; как для истинного, так и для ложного), составляет 7.

Итак, что такое прогнозирование ветвлений?

Предиктор ветвления попытается угадать, в каком направлении пойдет ветвь (структура if-then-else), прежде чем это станет известно наверняка. Он не будет ждать, пока инструкция A достигнет стадии EX конвейера, но угадает решение и перейдет к этой инструкции (B или C в нашем примере).

В случае правильного предположения конвейер выглядит примерно так:

Если позже обнаруживается, что предположение было неверным, то частично выполненные инструкции отбрасываются, и конвейер запускается заново с правильной ветвью с задержкой. Время, которое тратится впустую в случае неверного предсказания перехода, равно количеству этапов в конвейере от этапа выборки до этапа выполнения. Современные микропроцессоры, как правило, имеют довольно длинные конвейеры, поэтому задержка неверного предсказания составляет от 10 до 20 тактов. Чем длиннее конвейер, тем больше потребность в хорошем предсказателе ветвления .

В коде OP в первый раз, когда условие, предсказатель ветвления не имеет никакой информации для обоснования предсказания, поэтому в первый раз он случайным образом выберет следующую инструкцию. Позже в цикле for он может основывать прогноз на истории. Для массива, отсортированного в порядке возрастания, есть три возможности:

1. Все элементы меньше 128
2. Все элементы больше 128
3. Некоторые начальные новые элементы меньше 128, а позже становятся больше 128

Предположим, что предсказатель всегда будет принимать истинную ветвь при первом запуске.

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

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

Но в случае случайного несортированного массива при прогнозировании необходимо будет отбросить частично выполненные инструкции и большую часть времени начинать с правильной ветви, что приведет к увеличению циклов ЦП по сравнению с отсортированным массивом.

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

Действительно, массив разделен на смежную зону с data < 128 и другую с data >= 128. Таким образом, вы должны найти точку разделения с помощью дихотомического поиска (используя Lg(arraySize) = 15 сравнения), а затем выполнить прямое накопление от этой точки.

Что-то вроде (не отмечено)

int i= 0, j, k= arraySize;
while (i < k)
{
  j= (i + k) >> 1;
  if (data[j] >= 128)
    k= j;
  else
    i= j;
}
sum= 0;
for (; i < arraySize; i++)
  sum+= data[i];

или, немного более запутанный

int i, k, j= (i + k) >> 1;
for (i= 0, k= arraySize; i < k; (data[j] >= 128 ? k : i)= j)
  j= (i + k) >> 1;
for (sum= 0; i < arraySize; i++)
  sum+= data[i];

Еще более быстрый подход, который дает приблизительное решение как для отсортированного, так и для несортированного: sum= 3137536; (при условии действительно равномерного распределения, 16384 выборки с ожидаемым значением 191,5) : -)

Один из способов избежать ошибок прогнозирования ветвления - создать таблицу поиска и проиндексировать ее с использованием данных. Стефан де Брейн обсудил это в своем ответе.

Но в этом случае мы знаем, что значения находятся в диапазоне [0, 255], и нас интересуют только значения> = 128. Это означает, что мы можем легко извлечь один бит, который скажет нам, хотим ли мы значение или нет. : сдвигая данные вправо на 7 бит, у нас остается 0 бит или 1 бит, и мы хотим добавить значение только тогда, когда у нас есть 1 бит. Назовем этот бит «бит решения».

Используя значение 0/1 бита решения в качестве индекса в массиве, мы можем создать код, который будет одинаково быстрым независимо от того, отсортированы данные или нет. Наш код всегда будет добавлять значение, но когда бит решения равен 0, мы добавим значение туда, где нас не интересует. Вот код:

// Test
clock_t start = clock();
long long a[] = {0, 0};
long long sum;

for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        int j = (data[c] >> 7);
        a[j] += data[c];
    }
}

double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
sum = a[1];

Этот код тратит впустую половину добавлений, но никогда не приводит к ошибке предсказания ветвления. Это намного быстрее для случайных данных, чем версия с фактическим оператором if.

Но в моем тестировании явная таблица поиска была немного быстрее, чем эта, вероятно, потому, что индексация в таблице поиска была немного быстрее, чем смещение битов. Это показывает, как мой код настраивает и использует таблицу поиска (в коде она называется lut вместо «Таблица поиска»). Вот код C ++:

// Declare and then fill in the lookup table
int lut[256];
for (unsigned c = 0; c < 256; ++c)
    lut[c] = (c >= 128) ? c : 0;

// Use the lookup table after it is built
for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        sum += lut[data[c]];
    }
}

В этом случае таблица поиска была всего 256 байтов, поэтому она хорошо помещается в кеш, и все было быстро. Этот метод не сработал бы, если бы данные были 24-битными значениями, а нам нужна была бы только половина из них ... таблица поиска была бы слишком большой, чтобы ее можно было использовать на практике. С другой стороны, мы можем комбинировать два показанных выше метода: сначала сдвинуть биты, а затем проиндексировать таблицу поиска. Для 24-битного значения, которое нам нужна только верхняя половина значения, мы потенциально можем сдвинуть данные вправо на 12 бит и оставить 12-битное значение для индекса таблицы. 12-битный табличный индекс подразумевает таблицу из 4096 значений, что может быть практичным.

Техника индексации в массиве вместо использования оператора if может использоваться для решения, какой указатель использовать. Я видел библиотеку, которая реализовывала двоичные деревья, и вместо двух именованных указателей (pLeft и pRight или что-то еще) имела массив указателей длиной 2 и использовал технику «бит решения», чтобы решить, какой из них следовать. Например, вместо:

if (x < node->value)
    node = node->pLeft;
else
    node = node->pRight;

эта библиотека будет делать что-то вроде:

i = (x < node->value);
node = node->link[i];

Вот ссылка на этот код: Красно-черные деревья, Вечно запутанные

Я только что прочитал этот вопрос и ответы на него и чувствую, что ответа нет.

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

Этот подход в целом работает, если:

1. это небольшая таблица, которая, вероятно, будет кэширована в процессоре, и
2. вы работаете в довольно плотном цикле и / или процессор может предварительно загрузить данные.

Предпосылки и почему

С точки зрения процессора, ваша память медленная. Чтобы компенсировать разницу в скорости, в ваш процессор встроено несколько кешей (кеш L1 / L2). Итак, представьте, что вы делаете свои красивые вычисления и понимаете, что вам нужен кусок памяти. Процессор выполняет операцию «загрузки» и загружает часть памяти в кеш, а затем использует кеш для выполнения остальных вычислений. Поскольку память относительно медленная, эта «загрузка» замедлит вашу программу.

Подобно предсказанию ветвлений, это было оптимизировано в процессорах Pentium: процессор предсказывает, что ему необходимо загрузить часть данных, и пытается загрузить ее в кеш до того, как операция действительно попадет в кеш. Как мы уже видели, предсказание ветвления иногда ужасно неверно - в худшем случае вам нужно вернуться и фактически дождаться загрузки памяти, которая займет вечность ( другими словами: предсказание неудачного ветвления - это плохо , загрузка памяти после неудачного предсказания ветвления просто ужасна! ).

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

Первое, что нам нужно знать, это что такое small ? Хотя меньше, как правило, лучше, практическое правило - использовать таблицы поиска размером <= 4096 байт. В качестве верхнего предела: если ваша таблица поиска больше 64 КБ, вероятно, стоит пересмотреть.

Построение таблицы

Итак, мы выяснили, что можем создать небольшую таблицу. Следующее, что нужно сделать, это создать функцию поиска. Функции поиска обычно представляют собой небольшие функции, которые используют пару основных целочисленных операций (и, или, xor, сдвиг, сложение, удаление и, возможно, умножение). Вы хотите, чтобы ваш ввод транслировался функцией поиска в какой-то «уникальный ключ» в вашей таблице, который затем просто дает вам ответ на всю работу, которую вы хотели выполнить.

В этом случае:> = 128 означает, что мы можем сохранить значение, <128 означает, что мы избавляемся от него. Самый простой способ сделать это - использовать «И»: если мы сохраним его, мы сделаем И с помощью 7FFFFFFF; если мы хотим избавиться от него, мы И его с 0. Заметьте также, что 128 - это степень двойки, поэтому мы можем пойти дальше и составить таблицу из 32768/128 целых чисел и заполнить ее одним нулем и множеством 7FFFFFFFF's.

Управляемые языки

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

Ну, не совсем ... :-)

Была проделана значительная работа по устранению этой ветви для управляемых языков. Например:

for (int i = 0; i < array.Length; ++i)
{
   // Use array[i]
}

В этом случае компилятору очевидно, что граничное условие никогда не будет выполнено. По крайней мере, компилятор Microsoft JIT (но я ожидаю, что Java делает аналогичные вещи) заметит это и полностью снимет проверку. ВАУ, это значит, что нет отделения. Аналогичным образом будут рассмотрены и другие очевидные случаи.

Если у вас возникнут проблемы с поиском на управляемых языках - ключ в том, чтобы добавить & 0x[something]FFF к вашей функции поиска, чтобы сделать проверку границ предсказуемой - и наблюдайте, как это происходит быстрее.

Результат этого случая

// Generate data
int arraySize = 32768;
int[] data = new int[arraySize];

Random random = new Random(0);
for (int c = 0; c < arraySize; ++c)
{
    data[c] = random.Next(256);
}

/*To keep the spirit of the code intact, I'll make a separate lookup table
(I assume we cannot modify 'data' or the number of loops)*/

int[] lookup = new int[256];

for (int c = 0; c < 256; ++c)
{
    lookup[c] = (c >= 128) ? c : 0;
}

// Test
DateTime startTime = System.DateTime.Now;
long sum = 0;

for (int i = 0; i < 100000; ++i)
{
    // Primary loop
    for (int j = 0; j < arraySize; ++j)
    {
        /* Here you basically want to use simple operations - so no
        random branches, but things like &  |, *, -, +, etc. are fine. */
        sum += lookup[data[j]];
    }
}

DateTime endTime = System.DateTime.Now;
Console.WriteLine(endTime - startTime);
Console.WriteLine("sum = " + sum);
Console.ReadLine();

Поскольку данные распределяются между 0 и 255 при сортировке массива, примерно в первой половине итераций не будет введено выражение if (оператор if используется ниже).

if (data[c] >= 128)
    sum += data[c];

Возникает вопрос: что заставляет вышеуказанный оператор не выполняться в определенных случаях, как в случае с отсортированными данными? А вот и «предсказатель ветвления». Предиктор ветвления - это цифровая схема, которая пытается угадать, в каком направлении пойдет ветвь (например, структура if-then-else), прежде чем это станет известно наверняка. Цель предсказателя ветвления - улучшить поток в конвейере команд. Предикторы ветвления играют решающую роль в достижении высокой эффективности!

Давайте проведем сравнительную оценку, чтобы лучше понять это

Производительность оператора if зависит от того, имеет ли его состояние предсказуемую структуру. Если условие всегда истинно или всегда ложно, логика предсказания ветвления в процессоре подберет шаблон. С другой стороны, если шаблон непредсказуем, выражение if будет намного дороже.

Давайте измерим производительность этого цикла при различных условиях:

for (int i = 0; i < max; i++)
    if (condition)
        sum++;

Вот тайминги цикла с различными шаблонами истинно-ложно:

Condition                Pattern             Time (ms)
-------------------------------------------------------
(i & 0×80000000) == 0    T repeated          322

(i & 0xffffffff) == 0    F repeated          276

(i & 1) == 0             TF alternating      760

(i & 3) == 0             TFFFTFFF…           513

(i & 2) == 0             TTFFTTFF…           1675

(i & 4) == 0             TTTTFFFFTTTTFFFF…   1275

(i & 8) == 0             8T 8F 8T 8F …       752

(i & 16) == 0            16T 16F 16T 16F …   490

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

Таким образом, нет никаких сомнений во влиянии предсказания переходов на производительность!

Я пробовал тот же код с MATLAB 2011b с моим MacBook Pro (Intel i7, 64 бит, 2,4 ГГц) для следующего кода MATLAB:

% Processing time with Sorted data vs unsorted data
%==========================================================================
% Generate data
arraySize = 32768
sum = 0;
% Generate random integer data from range 0 to 255
data = randi(256, arraySize, 1);


%Sort the data
data1= sort(data); % data1= data  when no sorting done


%Start a stopwatch timer to measure the execution time
tic;

for i=1:100000

    for j=1:arraySize

        if data1(j)>=128
            sum=sum + data1(j);
        end
    end
end

toc;

ExeTimeWithSorting = toc - tic;

Результаты для вышеуказанного кода MATLAB следующие:

  a: Elapsed time (without sorting) = 3479.880861 seconds.
  b: Elapsed time (with sorting ) = 2377.873098 seconds.

Результаты кода C, как в @GManNickG, я получаю:

  a: Elapsed time (without sorting) = 19.8761 sec.
  b: Elapsed time (with sorting ) = 7.37778 sec.

Исходя из этого, похоже, что MATLAB почти в в 175 раз медленнее, чем реализация C без сортировки, и в в 350 раз медленнее с сортировкой. Другими словами, эффект (предсказания ветвления) равен 1,46x для реализации MATLAB и 2,7x для реализации C.

Несомненно, некоторые из нас будут заинтересованы в способах идентификации кода, который проблематичен для предсказателя ветвления ЦП. Инструмент Valgrind cachegrind имеет имитатор предсказателя ветвления, включенный с помощью флага --branch-sim=yes. Выполнение его по примерам в этом вопросе с уменьшением количества внешних циклов до 10000 и компиляцией с g++ дает следующие результаты:

Сортировано:

==32551== Branches:        656,645,130  (  656,609,208 cond +    35,922 ind)
==32551== Mispredicts:         169,556  (      169,095 cond +       461 ind)
==32551== Mispred rate:            0.0% (          0.0%     +       1.2%   )

Несортированный:

==32555== Branches:        655,996,082  (  655,960,160 cond +  35,922 ind)
==32555== Mispredicts:     164,073,152  (  164,072,692 cond +     460 ind)
==32555== Mispred rate:           25.0% (         25.0%     +     1.2%   )

Переходя к построчному выводу, производимому cg_annotate, мы видим для рассматриваемого цикла:

Сортировка:

          Bc    Bcm Bi Bim
      10,001      4  0   0      for (unsigned i = 0; i < 10000; ++i)
           .      .  .   .      {
           .      .  .   .          // primary loop
 327,690,000 10,016  0   0          for (unsigned c = 0; c < arraySize; ++c)
           .      .  .   .          {
 327,680,000 10,006  0   0              if (data[c] >= 128)
           0      0  0   0                  sum += data[c];
           .      .  .   .          }
           .      .  .   .      }

Несортированный:

          Bc         Bcm Bi Bim
      10,001           4  0   0      for (unsigned i = 0; i < 10000; ++i)
           .           .  .   .      {
           .           .  .   .          // primary loop
 327,690,000      10,038  0   0          for (unsigned c = 0; c < arraySize; ++c)
           .           .  .   .          {
 327,680,000 164,050,007  0   0              if (data[c] >= 128)
           0           0  0   0                  sum += data[c];
           .           .  .   .          }
           .           .  .   .      }

Это позволяет легко идентифицировать проблемную строку - в несортированной версии строка if (data[c] >= 128) вызывает 164 050 007 неверно предсказанных условных переходов (Bcm) в модели предсказателя ветвления cachegrind, тогда как в отсортированной версии она вызывает только 10 006.

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

perf stat ./sumtest_sorted

Сортировано:

 Performance counter stats for './sumtest_sorted':

  11808.095776 task-clock                #    0.998 CPUs utilized          
         1,062 context-switches          #    0.090 K/sec                  
            14 CPU-migrations            #    0.001 K/sec                  
           337 page-faults               #    0.029 K/sec                  
26,487,882,764 cycles                    #    2.243 GHz                    
41,025,654,322 instructions              #    1.55  insns per cycle        
 6,558,871,379 branches                  #  555.455 M/sec                  
       567,204 branch-misses             #    0.01% of all branches        

  11.827228330 seconds time elapsed

Несортированный:

 Performance counter stats for './sumtest_unsorted':

  28877.954344 task-clock                #    0.998 CPUs utilized          
         2,584 context-switches          #    0.089 K/sec                  
            18 CPU-migrations            #    0.001 K/sec                  
           335 page-faults               #    0.012 K/sec                  
65,076,127,595 cycles                    #    2.253 GHz                    
41,032,528,741 instructions              #    0.63  insns per cycle        
 6,560,579,013 branches                  #  227.183 M/sec                  
 1,646,394,749 branch-misses             #   25.10% of all branches        

  28.935500947 seconds time elapsed

Он также может выполнять аннотацию исходного кода с разборкой.

perf record -e branch-misses ./sumtest_unsorted
perf annotate -d sumtest_unsorted

 Percent |      Source code & Disassembly of sumtest_unsorted
------------------------------------------------
...
         :                      sum += data[c];
    0.00 :        400a1a:       mov    -0x14(%rbp),%eax
   39.97 :        400a1d:       mov    %eax,%eax
    5.31 :        400a1f:       mov    -0x20040(%rbp,%rax,4),%eax
    4.60 :        400a26:       cltq   
    0.00 :        400a28:       add    %rax,-0x30(%rbp)
...

Подробнее см. в руководстве по производительности.

Если вам интересно узнать о дополнительных возможностях оптимизации этого кода, обратите внимание на следующее:

Начиная с исходного цикла:

for (unsigned i = 0; i < 100000; ++i)
{
    for (unsigned j = 0; j < arraySize; ++j)
    {
        if (data[j] >= 128)
            sum += data[j];
    }
}

С заменой петель мы можем безопасно изменить этот цикл на:

for (unsigned j = 0; j < arraySize; ++j)
{
    for (unsigned i = 0; i < 100000; ++i)
    {
        if (data[j] >= 128)
            sum += data[j];
    }
}

Затем вы можете видеть, что условное выражение if остается постоянным на протяжении всего выполнения цикла i, поэтому вы можете поднять if на выход:

for (unsigned j = 0; j < arraySize; ++j)
{
    if (data[j] >= 128)
    {
        for (unsigned i = 0; i < 100000; ++i)
        {
            sum += data[j];
        }
    }
}

Затем вы видите, что внутренний цикл может быть свернут в одно выражение, если модель с плавающей запятой позволяет это (например, выбрасывается /fp:fast)

for (unsigned j = 0; j < arraySize; ++j)
{
    if (data[j] >= 128)
    {
        sum += data[j] * 100000;
    }
}

Этот в 100 000 раз быстрее, чем раньше.

Причина, по которой производительность резко повышается при сортировке данных, заключается в том, что устраняется штраф за предсказание ветвления, как прекрасно объяснено в Ответе Mysticial.

Теперь, если мы посмотрим на код

if (data[c] >= 128)
    sum += data[c];

мы можем обнаружить, что значение этой конкретной ветви if... else... состоит в том, чтобы добавить что-то, когда выполняется условие. Этот тип ветвления может быть легко преобразован в оператор условного перемещения , который будет скомпилирован в инструкцию условного перемещения: cmovl в системе x86. Ветвление и, следовательно, потенциальный штраф за предсказание ветвления удаляются.

В C, таким образом, C++, оператор, который компилируется напрямую (без какой-либо оптимизации) в инструкцию условного перемещения в x86, является тернарным оператором ... ? ... : .... Поэтому мы перепишем приведенный выше оператор в эквивалентный:

sum += data[c] >=128 ? data[c] : 0;

Сохраняя читабельность, мы можем проверить коэффициент ускорения.

На процессоре Intel Core i7 -2600K при 3,4 ГГц и режиме выпуска Visual Studio 2010 эталонный тест:

x86

x64

Результат устойчив в нескольких тестах. Мы получаем большое ускорение, когда результат перехода непредсказуем, но мы немного страдаем, когда он предсказуем. Фактически, при использовании условного перемещения производительность одинакова независимо от шаблона данных.

Теперь давайте посмотрим более внимательно, исследуя сборку x86, которую они генерируют. Для простоты мы используем две функции max1 и max2.

max1 использует условную ветвь if... else ...:

int max1(int a, int b) {
    if (a > b)
        return a;
    else
        return b;
}

max2 использует тернарный оператор ... ? ... : ...:

int max2(int a, int b) {
    return a > b ? a : b;
}

На машине x86-64 GCC -S генерирует сборку ниже.

:max1
    movl    %edi, -4(%rbp)
    movl    %esi, -8(%rbp)
    movl    -4(%rbp), %eax
    cmpl    -8(%rbp), %eax
    jle     .L2
    movl    -4(%rbp), %eax
    movl    %eax, -12(%rbp)
    jmp     .L4
.L2:
    movl    -8(%rbp), %eax
    movl    %eax, -12(%rbp)
.L4:
    movl    -12(%rbp), %eax
    leave
    ret

:max2
    movl    %edi, -4(%rbp)
    movl    %esi, -8(%rbp)
    movl    -4(%rbp), %eax
    cmpl    %eax, -8(%rbp)
    cmovge  -8(%rbp), %eax
    leave
    ret

max2 использует гораздо меньше кода из-за использования инструкции cmovge. Но реальный выигрыш заключается в том, что max2 не включает переходов по ветвям, jmp, что значительно снижает производительность, если прогнозируемый результат неверен.

Так почему же условное перемещение работает лучше?

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

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

В случае условного перемещения команда условного перемещения выполнения делится на несколько этапов, но более ранние этапы, такие как Fetch и Decode, не зависят от результата предыдущей инструкции; результат нужен только на последних этапах. Таким образом, мы ждем долю времени выполнения одной инструкции. Вот почему версия с условным перемещением медленнее, чем ветвление, когда прогнозирование простое.

Книга Компьютерные системы: взгляд программиста, второе издание объясняет это подробно. Вы можете проверить Раздел 3.6.6 для Условных инструкций по перемещению , всю Главу 4 для Архитектура процессора и Раздел 5.11.2 для специальной обработки для Прогнозирование ветвления и <4777495 4725825 штрафов. >.

Прогнозирование ветвления.

Для отсортированного массива условие data[c] >= 128 сначала является false для серии значений, затем становится true для всех последующих значений. Это легко предсказать. При использовании несортированного массива вы платите за разветвление.