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

24456

Вот фрагмент кода C ++, который демонстрирует очень своеобразное поведение. По какой-то странной причине сортировка данных чудесным образом делает код почти в шесть раз быстрее:

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

int main()
{
    // Generate data
    const unsigned arraySize = 32768;
    int data[arraySize];

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

    // !!! With this, the next loop runs faster.
    std::sort(data, data + arraySize);

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

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

    double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;

    std::cout << elapsedTime << std::endl;
    std::cout << "sum = " << sum << std::endl;
}
  • Без std::sort(data, data + arraySize);кода выполняется за 11,54 секунды.
  • С отсортированными данными код запускается за 1,93 секунды.

Сначала я думал, что это может быть просто аномалией языка или компилятора, поэтому я попробовал Java:

import java.util.Arrays;
import java.util.Random;

public class Main
{
    public static void main(String[] args)
    {
        // Generate data
        int arraySize = 32768;
        int data[] = new int[arraySize];

        Random rnd = new Random(0);
        for (int c = 0; c < arraySize; ++c)
            data[c] = rnd.nextInt() % 256;

        // !!! With this, the next loop runs faster
        Arrays.sort(data);

        // Test
        long start = System.nanoTime();
        long sum = 0;

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

        System.out.println((System.nanoTime() - start) / 1000000000.0);
        System.out.println("sum = " + sum);
    }
}

С похожим, но менее экстремальным результатом.


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

  • Что здесь происходит?
  • Почему обработка отсортированного массива быстрее, чем обработка несортированного массива?

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

GManNickG
источник
170
Woops ... re:
Обвал
16
@SachinVerma Не в моей голове: 1) JVM может быть достаточно умным, чтобы использовать условные движения. 2) Код связан с памятью. 200M слишком велик, чтобы поместиться в кэш процессора. Таким образом, производительность будет ограничена пропускной способностью памяти вместо ветвления.
Мистика
12
@ Мистик, около 2). Я думал, что таблица прогнозирования отслеживает шаблоны (независимо от фактических переменных, которые были проверены для этого шаблона) и изменяет вывод прогноза на основе истории. Не могли бы вы дать мне причину, почему сверхбольший массив не выиграл бы от предсказания ветвления?
Сачин Верма
15
@SachinVerma Да, но когда массив такой большой, в игру вступает еще больший фактор - пропускная способность памяти. Память не плоская . Доступ к памяти очень медленный, и пропускная способность ограничена. Чтобы упростить вещи, существует только так много байтов, которые могут быть переданы между процессором и памятью за фиксированное время. Простой код, подобный приведенному в этом вопросе, вероятно, достигнет этого предела, даже если он замедлен из-за неправильных прогнозов. Этого не происходит с массивом 32768 (128 КБ), потому что он помещается в кэш L2 ЦП.
Мистик
13
Существует новый недостаток безопасности называется BranchScope: cs.ucr.edu/~nael/pubs/asplos18.pdf
Veve

Ответы:

31805

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


Что такое предсказание отрасли?

Рассмотрим железнодорожный узел:

Изображение, показывающее железнодорожный узел Изображение Mecanismo, через Wikimedia Commons. Используется по лицензии CC-By-SA 3.0 .

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

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

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

Есть ли способ лучше? Вы угадываете, в каком направлении будет идти поезд!

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

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


Рассмотрим оператор if: на уровне процессора это инструкция перехода:

Снимок экрана скомпилированного кода, содержащего оператор if

Вы процессор, и вы видите ветку. Вы понятия не имеете, по какому пути это пойдет. Чем ты занимаешься? Вы останавливаете выполнение и ждете, пока предыдущие инструкции не будут выполнены. Затем вы продолжаете идти по правильному пути.

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

Есть ли способ лучше? Вы угадываете, в каком направлении пойдет филиал!

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

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


Это прогноз отрасли. Я признаю, что это не лучшая аналогия, так как поезд мог просто сигнализировать направление с флагом. Но в компьютерах процессор не знает, в каком направлении пойдет ветка, до последнего момента.

Итак, как вы могли бы стратегически угадать, сколько раз поезд должен вернуться и пойти по другому пути? Вы смотрите на прошлую историю! Если поезд идет влево 99% времени, значит, вы уехали. Если это чередуется, то вы чередуете свои догадки. Если это происходит в одну сторону каждые три раза, вы догадаетесь, то же самое ...

Другими словами, вы пытаетесь определить шаблон и следовать ему. Это более или менее то, как работают предсказатели ветвлений.

Большинство приложений имеют хорошо управляемые ветви. Таким образом, современные отраслевые предикторы, как правило, достигают> 90% показателей успеха. Но когда они сталкиваются с непредсказуемыми ветвями без распознаваемых шаблонов, предикторы ветвей практически бесполезны.

Дальнейшее чтение: статья "Ветка предиктора" в Википедии .


Как указывалось выше, виновником является следующее if-утверждение:

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

Обратите внимание, что данные равномерно распределены между 0 и 255. Когда данные отсортированы, примерно первая половина итераций не войдет в оператор if. После этого все они введут оператор if.

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

Быстрая визуализация:

T = branch taken
N = branch not taken

data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
branch = N  N  N  N  N  ...   N    N    T    T    T  ...   T    T    T  ...

       = NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT  (easy to predict)

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

data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118,  14, 150, 177, 182, 133, ...
branch =   T,   T,   N,   T,   T,   T,   T,  N,   T,   N,   N,   T,   T,   T,   N  ...

       = TTNTTTTNTNNTTTN ...   (completely random - hard to predict)

Так что же можно сделать?

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

Заменить:

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

с:

int t = (data[c] - 128) >> 31;
sum += ~t & data[c];

Это исключает ветвление и заменяет его на некоторые побитовые операции.

(Обратите внимание, что этот хак не является строго эквивалентным исходному оператору if. Но в этом случае он действителен для всех входных значений data[].)

Тесты: Core i7 920 @ 3,5 ГГц

C ++ - Visual Studio 2010 - выпуск x64

//  Branch - Random
seconds = 11.777

//  Branch - Sorted
seconds = 2.352

//  Branchless - Random
seconds = 2.564

//  Branchless - Sorted
seconds = 2.587

Java - NetBeans 7.1.1 JDK 7 - x64

//  Branch - Random
seconds = 10.93293813

//  Branch - Sorted
seconds = 5.643797077

//  Branchless - Random
seconds = 3.113581453

//  Branchless - Sorted
seconds = 3.186068823

Замечания:

  • В ветке: между отсортированными и несортированными данными существует огромная разница.
  • С помощью Hack: нет разницы между отсортированными и несортированными данными.
  • В случае C ++ хак на самом деле медленнее, чем с веткой, когда данные сортируются.

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


Обновить:

  • GCC 4.6.1 с -O3или -ftree-vectorizeна x64 может генерировать условный ход. Таким образом, нет никакой разницы между отсортированными и несортированными данными - оба быстры.

    (Или несколько быстро: для уже отсортированного случая cmovможет быть медленнее, особенно если GCC ставит его на критический путь, а не просто add, особенно на Intel до Broadwell, где cmovимеет 2 цикла задержки: флаг оптимизации gcc -O3 делает код медленнее, чем -O2 )

  • VC ++ 2010 не может генерировать условные перемещения для этой ветви даже в /Ox.

  • Компилятор Intel C ++ (ICC) 11 совершает чудеса. Он чередует две петли , тем самым поднимая непредсказуемую ветвь на внешнюю петлю. Таким образом, он не только защищен от неправильных прогнозов, но также в два раза быстрее, чем то, что могут генерировать VC ++ и GCC! Другими словами, ICC воспользовалась тестовым циклом, чтобы победить тест ...

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

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

Mysticial
источник
256
Взгляните на следующий вопрос: stackoverflow.com/questions/11276291/… Компилятор Intel приблизился к полному избавлению от внешнего цикла.
Мистик
24
@Mysticial Как поезд / компилятор знает, что он ввел неправильный путь?
onmyway133
26
@obe: Учитывая иерархические структуры памяти, невозможно сказать, сколько будет стоить промах кеша. Он может отсутствовать в L1 и разрешаться в более медленном L2, или пропускаться в L3 и разрешаться в системной памяти. Однако, если по какой-то странной причине эта ошибка в кеше не приводит к загрузке памяти на нерезидентной странице с диска, у вас есть хорошая точка зрения ... у памяти не было времени доступа в диапазоне миллисекунд примерно за 25-30 лет ;)
Andon M. Coleman
21
Практическое правило для написания кода, который эффективен на современном процессоре: все, что делает выполнение вашей программы более регулярным (менее неравномерным), будет стремиться сделать его более эффективным. Сортировка в этом примере имеет этот эффект из-за предсказания перехода. Локальный доступ (а не случайные удаленные доступы) имеет этот эффект из-за кэшей.
Лутц Пречелт
22
@ Сандип Да. Процессоры все еще имеют прогноз ветвления. Если что-то изменилось, это компиляторы. В настоящее время я держу пари, что они с большей вероятностью будут делать то, что ICC и GCC (ниже -O3) сделали здесь, то есть удалить ветку. Учитывая, насколько серьезным является этот вопрос, вполне возможно, что компиляторы были обновлены для конкретной обработки случая в этом вопросе. Обязательно обратите внимание на SO. И это произошло по этому вопросу, где GCC был обновлен в течение 3 недель. Я не понимаю, почему это не произошло бы и здесь.
Мистик
4087

Отраслевой прогноз.

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

Даниэль Фишер
источник
105
Предсказание ветвей работает лучше на отсортированных массивах по сравнению с массивами с разными шаблонами? Например, для массива -> {10, 5, 20, 10, 40, 20, ...} следующий элемент в массиве из шаблона - 80. Будет ли ускорен этот тип массива с помощью предсказания перехода в какой следующий элемент 80 здесь, если шаблон следует? Или это обычно помогает только с отсортированными массивами?
Адам Фриман
133
Таким образом, в основном все, что я обычно узнал о биг-о, находится за окном? Лучше понести стоимость сортировки, чем стоимость ветвления?
Агрим Патхак
133
@AgrimPathak Это зависит. Для не слишком больших входных данных алгоритм с более высокой сложностью быстрее, чем алгоритм с более низкой сложностью, когда константы меньше для алгоритма с более высокой сложностью. Где точка безубыточности может быть трудно предсказать. Кроме того, сравните это , местность важна. Big-O важен, но это не единственный критерий эффективности.
Даниэль Фишер
65
Когда происходит предсказание ветвления? Когда язык узнает, что массив отсортирован? Я думаю о ситуации с массивом, который выглядит следующим образом: [1,2,3,4,5, ... 998,999,1000, 3, 10001, 10002]? это неясное 3 увеличит время работы? Это будет так же долго, как несортированный массив?
Филипп Бартузи
63
@FilipBartuzi Предсказание ветвлений происходит в процессоре ниже уровня языка (но язык может предлагать способы сообщить компилятору о том, что вероятно, поэтому компилятор может генерировать код, подходящий для этого). В вашем примере отклонение 3 приведет к ошибочному прогнозированию ветвлений (для соответствующих условий, когда 3 дает результат, отличный от 1000), и, следовательно, обработка этого массива, вероятно, займет пару десятков или сотен наносекунд дольше, чем отсортированный массив, вряд ли когда-нибудь заметный. То, что стоит времени, - это высокий уровень неверных прогнозов, одно неправильное прогнозирование на 1000 не так уж много.
Даниэль Фишер
3312

Причина, по которой производительность резко улучшается при сортировке данных, заключается в том, что штраф за предсказание ветвлений снят, как прекрасно объясняется в ответе 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 эталонный тест (формат скопирован из Mysticial):

x86

//  Branch - Random
seconds = 8.885

//  Branch - Sorted
seconds = 1.528

//  Branchless - Random
seconds = 3.716

//  Branchless - Sorted
seconds = 3.71

x64

//  Branch - Random
seconds = 11.302

//  Branch - Sorted
 seconds = 1.830

//  Branchless - Random
seconds = 2.736

//  Branchless - Sorted
seconds = 2.737

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

Теперь давайте более подробно рассмотрим 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 для специальной обработки для Штрафов Предсказания и Ошибочного предсказания .

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

WiSaGaN
источник
7
@ BlueRaja-DannyPflughoeft Это неоптимизированная версия. Компилятор НЕ оптимизировал троичный оператор, он просто перевел его. GCC может оптимизировать, если-тогда, если дан достаточный уровень оптимизации, тем не менее, этот показывает силу условного перемещения, и ручная оптимизация имеет значение.
WiSaGaN
100
@WiSaGaN Код ничего не демонстрирует, потому что ваши две части кода компилируются в один и тот же машинный код. Чрезвычайно важно, чтобы люди не понимали, что выражение if в вашем примере отличается от terenary в вашем примере. Это правда, что вы признаете сходство в своем последнем абзаце, но это не стирает тот факт, что остальная часть примера вредна.
Джастин Л.
55
@WiSaGaN Мое отрицательное голосование определенно превратится в повышательное, если вы измените свой ответ, чтобы удалить вводящий в заблуждение -O0пример и показать разницу в оптимизированном asm на двух ваших тестовых примерах.
Джастин Л.
56
@UpAndAdam На момент тестирования VS2010 не может оптимизировать исходную ветку в условное перемещение даже при указании высокого уровня оптимизации, в то время как gcc может.
WiSaGaN
9
Этот троичный операторный трюк прекрасно работает на Java. Прочитав ответ Mystical, я подумал, что можно сделать для Java, чтобы избежать ложного предсказания ветвления, поскольку в Java нет ничего эквивалентного -O3. троичный оператор: 2.1943 с и оригинал: 6.0303 с.
Кин Чунг
2272

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

Начиная с оригинального цикла:

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цикла, поэтому вы можете поднять ifout:

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 раз быстрее, чем раньше.

вулкан ворон
источник
276
Если вы хотите обмануть, вы можете также вывести умножение за пределы цикла и выполнить sum * = 100000 после цикла.
Jyaif
78
@Michael - Я считаю, что этот пример на самом деле является примером оптимизации циклически-инвариантного подъема (LIH), а НЕ цикла подкачки . В этом случае весь внутренний цикл не зависит от внешнего цикла и поэтому может быть выведен из внешнего цикла, после чего результат просто умножается на сумму iв одну единицу = 1e5. Это не имеет никакого значения для конечного результата, но я просто хотел установить рекорд, так как это такая часто посещаемая страница.
Яир Альтман
54
Хотя и не в простом духе обмена циклами, внутреннее ifв этой точке может быть преобразовано в: sum += (data[j] >= 128) ? data[j] * 100000 : 0;которое компилятор может уменьшить cmovgeили эквивалентно.
Алекс Норт-Киз
43
Внешний цикл должен сделать время, затрачиваемое внутренним циклом, достаточно большим для профиля Так почему бы вам не поменять местами. В конце эта петля будет удалена в любом случае.
saurabheights
34
@saurabheights: Неправильный вопрос: почему бы компилятору НЕ поменять цикл. Микробенчмарки это сложно;)
Матье М.
1885

Несомненно, некоторые из нас будут заинтересованы в способах идентификации кода, который является проблематичным для предсказателя ветвления ЦП. Инструмент 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%   )

Unsorted:

==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];
           .      .  .   .          }
           .      .  .   .      }

Unsorted:

          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

Unsorted:

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

Смотрите руководство по производительности для более подробной информации.

кафе
источник
74
Это страшно, в несортированном списке должна быть 50% вероятность попадания в адд. Каким-то образом предсказание ветвлений имеет только 25% промахов, как это может быть лучше, чем промах 50%?
TallBrian
128
@ tall.b.lo: 25% от всех ветвей - в цикле есть две ветви: одна для data[c] >= 128(которая, как вы предлагаете, имеет промах 50%), а другая для условия цикла, c < arraySizeкоторая имеет промах ~ 0%. ,
Кафе
1341

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

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

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

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

Фон и почему

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

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

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

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

Построение стола

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

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

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

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

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

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

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();
atlaste
источник
57
Вы хотите обойти ветвь-предиктор, почему? Это оптимизация.
Дастин Опря
108
Потому что ни одна ветка не лучше, чем ветка :-) Во многих ситуациях это просто намного быстрее ... если вы оптимизируете, это определенно стоит попробовать. Они также используют его в f.ex. graphics.stanford.edu/~seander/bithacks.html
atlaste
36
Как правило, таблицы поиска могут быть быстрыми, но запускали ли вы тесты для этого конкретного условия? Вы по-прежнему будете иметь условие ветвления в своем коде, только теперь оно перемещено в часть генерации справочной таблицы. Вы все еще не получили бы свой перфоманс
Зейн Ризви
38
@ Зейн, если вы действительно хотите знать ... Да: 15 секунд с веткой и 10 секунд с моей версией. В любом случае, это полезная техника, которую нужно знать в любом случае.
Атлас
42
Почему не sum += lookup[data[j]]где lookupмассив с 256 записей, первые из них равно нулю , а последние, будучи равен индексу?
Крис Вандермоттен,
1200

Поскольку данные распределяются между 0 и 255 при сортировке массива, около первой половины итераций не будет входить в if-statement ( 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утверждение в шесть раз медленнее, чем « хороший » паттерн! Конечно, какой шаблон хорош, а какой плох, зависит от точных инструкций, сгенерированных компилятором, и от конкретного процессора.

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

Saqlain
источник
23
@MooingDuck 'Потому что это не будет иметь значения - это значение может быть чем угодно, но оно все равно будет в пределах этих порогов. Так зачем показывать случайное значение, когда вы уже знаете пределы? Хотя я согласен с тем, что вы могли бы показать один из них для полноты и «просто так».
cst1992
24
@ cst1992: Сейчас его самый медленный выбор времени - TTFFTTFFTTFF, что, на мой взгляд, вполне предсказуемо. Случайность по своей природе непредсказуема, поэтому вполне возможно, что она будет еще медленнее и, таким образом, выходит за пределы, показанные здесь. OTOH, это может быть, что TTFFTTFF отлично попадает в патологический случай. Не могу сказать, так как он не показывал время наугад.
Mooing Duck
21
@MooingDuck Для человеческого глаза «TTFFTTFFTTFF» - это предсказуемая последовательность, но мы говорим здесь о поведении предиктора ветвления, встроенного в CPU. Предиктором ветвления является не распознавание образов на уровне AI; это очень просто Когда вы просто чередуете ветви, это не очень хорошо предсказывает. В большинстве кода ветки идут одинаково почти все время; рассмотрим цикл, который выполняется тысячу раз. Ветвь в конце цикла возвращается к началу цикла 999 раз, а затем в тысячный раз происходит нечто иное. Обычно очень хорошо работает предсказатель ветвлений.
Steveha
18
@steveha: Я думаю, что вы делаете предположения о том, как работает предсказатель ветви ЦП, и я не согласен с этой методологией. Я не знаю, насколько продвинут этот предсказатель ветвления, но мне кажется, что он гораздо более продвинут, чем вы. Вы, вероятно, правы, но измерения определенно были бы хорошими.
Мычанка
5
@steveha: Двухуровневый адаптивный предиктор может без проблем использовать шаблон TTFFTTFF. «Варианты этого метода прогнозирования используются в большинстве современных микропроцессоров». Локальное предсказание ветвления и глобальное предсказание ветвления основаны на двухуровневом адаптивном предикторе, они также могут. «Глобальное предсказание ветвлений используется в процессорах AMD, а также в процессорах Intel Pentium M, Core, Core 2 и Silvermont на основе Atom». Также добавьте в этот список предиктор Соглашения, Гибридный предиктор, Прогнозирование косвенных переходов. Предиктор цикла не блокируется, но достигает 75%. Это оставляет только 2, которые не могут закрепиться
Mooing Duck
1126

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

Но в этом случае мы знаем, что значения находятся в диапазоне [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];

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

steveha
источник
29
Правильно, вы также можете просто использовать бит напрямую и умножить ( data[c]>>7- что также обсуждается где-то здесь); Я намеренно оставил это решение, но, конечно, вы правы. Небольшое примечание: практическое правило для справочных таблиц заключается в том, что если он умещается в 4 КБ (из-за кэширования), он будет работать - желательно, чтобы таблица была как можно меньше. Для управляемых языков я бы увеличил это до 64 КБ, для низкоуровневых языков, таких как C ++ и C, я бы, вероятно, пересмотрел (это только мой опыт). С тех пор typeof(int) = 4я бы попробовал придерживаться до 10 бит.
Атлас
17
Я думаю, что индексирование со значением 0/1, вероятно, будет быстрее, чем целочисленное умножение, но я думаю, что если производительность действительно критична, вы должны ее профилировать. Я согласен с тем, что маленькие таблицы поиска необходимы, чтобы избежать нагрузки на кэш, но, очевидно, если у вас больший кэш, вы можете справиться с большей таблицей поиска, поэтому 4 КБ - это скорее практическое правило, чем жесткое правило. Я думаю ты имел ввиду sizeof(int) == 4? Это было бы верно для 32-разрядных. Мой двухлетний сотовый телефон имеет кэш-память L1 объемом 32 КБ, поэтому даже таблица поиска 4K может работать, особенно если значения поиска были байтами, а не целыми.
Steveha
12
Возможно, я что-то упускаю, но в вашем jметоде равно 0 или 1, почему бы вам просто не умножить свое значение, jпрежде чем добавлять его, а не использовать индексирование массива (возможно, следует умножить на, 1-jа не на j)
Ричард Тингл
6
@steveha Умножение должно быть быстрее, я пытался найти его в книгах Intel, но не смог его найти ... в любом случае, сравнительный анализ также дает мне этот результат здесь.
Атлас
10
@steveha PS: еще один возможный ответ, int c = data[j]; sum += c & -(c >> 7);который не требует умножения вообще.
Атлас
1022

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

Действительно, массив разделен на смежные зоны с, 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) :-)

Ив Дауст
источник
23
sum= 3137536- умная. Это явно не в этом вопрос. Вопрос в том, чтобы объяснить удивительные характеристики производительности. Я склонен сказать, что добавление делать std::partitionвместо того, чтобы std::sortценно. Хотя актуальный вопрос распространяется не только на синтетический тест.
Сехе
12
@DeadMG: это действительно не стандартный дихотомический поиск по заданному ключу, а поиск по индексу разделения; требуется одно сравнение на одну итерацию. Но не полагайтесь на этот код, я не проверял его. Если вы заинтересованы в гарантированно правильной реализации, дайте мне знать.
Ив Дауст
832

Вышеупомянутое поведение происходит из-за предсказания Ветви.

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

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

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

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

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

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

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

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

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

когда условие возвращает true: введите описание изображения здесь

Когда условие возвращает ложное: введите описание изображения здесь

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

Так что же такое прогноз отрасли?

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

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

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

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

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

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

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

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

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

Суровая Шарма
источник
1
как две инструкции выполняются вместе? это сделано с отдельными ядрами процессора, или инструкция конвейера интегрирована в одно ядро ​​процессора?
М.Казем Ахгари
1
@ M.kazemAkhgary Это все внутри одного логического ядра. Если вам интересно, это хорошо описано, например, в Руководстве разработчика программного обеспечения Intel
Sergey.quixoticaxis.Ivanov
728

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

  1. Intel - предотвращение ошибочных прогнозов отрасли
  2. Intel - реорганизация ветвей и циклов для предотвращения ошибочных прогнозов
  3. Научные труды - отраслевое прогнозирование компьютерной архитектуры
  4. Книги: Дж. Л. Хеннесси, Д. А. Паттерсон: Компьютерная архитектура: количественный подход
  5. Статьи в научных публикациях: TY Yeh, YN Patt сделал много из них по отраслевым прогнозам.

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

2-битная диаграмма состояний

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

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

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

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


Surt
источник
697

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

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

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

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

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

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

rkachach
источник
679

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

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

bool a, b;
b = !a;

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

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

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

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

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

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

Маца
источник
342

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

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

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

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

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

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

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

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

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

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

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

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

Алиреза
источник
304

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

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

Ссылка находится здесь: http://www.geoffchappell.com/studies/windows/km/ntoskrnl/api/ex/profile/demo.htm

ForeverLearning
источник
3
Это очень интересная статья (на самом деле, я только что все прочитал), но как она отвечает на вопрос?
Питер Мортенсен,
2
@PeterMortensen Я немного озадачен вашим вопросом. Например, вот одна соответствующая строка из этого фрагмента: When the input is unsorted, all the rest of the loop takes substantial time. But with sorted input, the processor is somehow able to spend not just less time in the body of the loop, meaning the buckets at offsets 0x18 and 0x1C, but vanishingly little time on the mechanism of looping. автор пытается обсудить профилирование в контексте кода, размещенного здесь, и в процессе пытается объяснить, почему отсортированный случай намного быстрее.
ForeverLearning
261

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

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

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

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

фигура 1

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

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

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

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

без предсказателя ветвлений

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

  1. Используйте Branch Predictor и не делайте условный переход. Давайте предположим, что прогноз не принимает условный переход.

введите описание изображения здесь

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

  1. Используйте Branch Predictor и сделайте условный прыжок. Давайте предположим, что прогноз не принимает условный переход.

введите описание изображения здесь

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

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

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

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

Евгений
источник
1
Почти так же хорошо, как маркетинговые анимации Intel, и они были одержимы не только предсказанием переходов, но и неисполнением заказа, обе стратегии были "спекулятивными". Чтение вперед в памяти и хранилище (последовательная предварительная выборка в буфер) также является спекулятивным. Все это складывается.
Маккензм
@mckenzm: нестандартный спекулятивный исполнитель делает предсказание ветвления еще более ценным; Помимо скрытия пузырей извлечения / декодирования, прогнозирование ветвлений + умозрительный exec удаляет управляющие зависимости из задержки критического пути. Код внутри или после if()блока может выполняться до того, как станет известно условие ветвления. Или для цикла поиска, подобного strlenили memchr, взаимодействия могут перекрываться. Если бы вам пришлось ждать, пока результат совпадения или не будет известен, прежде чем выполнять какую-либо следующую итерацию, вы бы столкнулись с узким местом в нагрузке на кэш + задержка ALU вместо пропускной способности.
Питер Кордес
210

Выгода предсказания ветвлений!

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

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

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

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

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

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

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

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

 O      Route 1  /-------------------------------
/|\             /
 |  ---------##/
/ \            \
                \
        Route 2  \--------------------------------
Тони Танноус
источник
Пока промывка трубопроводов супер быстрая Не совсем. Это быстро по сравнению с отсутствием кэша вплоть до DRAM, но на современном высокопроизводительном x86 (например, семейство Intel Sandybridge) это около десятка циклов. Хотя быстрое восстановление позволяет избежать ожидания выхода всех устаревших независимых инструкций до начала восстановления, вы все равно теряете много циклов внешнего интерфейса из-за неправильного прогноза. Что именно происходит, когда процессор Skylake неправильно предсказывает ветку? , (И в каждом цикле может быть около 4 инструкций работы.) Плохо для высокопроизводительного кода.
Питер Кордес
153

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

Поле проверки состояния и необязательное поле «set status bit» можно комбинировать, например:

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

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

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

Люк Хатчисон
источник
1
Другим нововведением в ARM является добавление суффикса инструкции S, также необязательного для (почти) всех команд, который, если он отсутствует, не позволяет командам изменять биты состояния (за исключением команды CMP, задачей которой является установка битов состояния, так что ему не нужен суффикс S). Это позволяет вам избегать команд CMP во многих случаях, если сравнение выполняется с нулем или подобным (например, SUBS R0, R0, # 1 установит бит Z (Ноль), когда R0 достигнет нуля). Условные выражения и суффикс S не требуют дополнительных затрат. Это довольно красивый ISA.
Люк Хатчисон
2
Отсутствие добавления суффикса S позволяет вам иметь несколько условных инструкций подряд, не беспокоясь о том, что одна из них может изменить биты состояния, что в противном случае может иметь побочный эффект при пропуске остальных условных инструкций.
Люк Хатчисон
Обратите внимание, что ОП не включает время сортировки при их измерении. Вероятно, перед выполнением цикла ветки x86 ветвь сортировки является общей потерей, хотя несортированный случай делает цикл намного медленнее. Но сортировка большого массива требует много работы.
Питер Кордес
Кстати, вы можете сохранить инструкцию в цикле путем индексации относительно конца массива. Перед циклом настройте R2 = data + arraySize, затем начните с R1 = -arraySize. Нижняя часть цикла становится adds r1, r1, #1/ bnz inner_loop. Компиляторы не используют эту оптимизацию по какой-то причине: / В любом случае, предикатное выполнение добавления в этом случае принципиально не отличается от того, что вы можете делать с кодом без ветвей на других ISA, таких как x86 cmov. Хотя это не так приятно: флаг оптимизации gcc -O3 делает код медленнее, чем -O2
Питер Кордес
1
(Выполнение с предикатом ARM действительно не выполняет инструкции, так что вы даже можете использовать ее при загрузке или cmovхранении, которые могут привести к сбою, в отличие от x86 с операндом источника памяти. Большинство ISA, включая AArch64, имеют только операции выбора ALU. Так что предопределение ARM может быть мощным и может использоваться более эффективно, чем код без ответвлений на большинстве ISA.)
Питер Кордес
147

Это про предсказание ветвлений. Что это?

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

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

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

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

На самом деле существует три вида ветвей:

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

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

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

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

Ссылки:

Фархад
источник
146

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

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

 // 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];               
 }
Йохай Тиммер
источник
1
Правильно, но стоимость установки для сортировки массива составляет O (N log N), поэтому раннее прерывание не поможет вам, если единственная причина, по которой вы сортируете массив, заключается в возможности преждевременного сбоя. Однако если у вас есть другие причины для предварительной сортировки массива, то да, это ценно.
Люк Хатчисон
Зависит от того, сколько раз вы сортируете данные по сравнению с тем, сколько раз вы зациклились на них. Сортировка в этом примере - только пример, это не должно быть только перед циклом
Yochai Timmer
2
Да, именно это я и сделал в своем первом комментарии :-) Вы говорите: «Прогноз ветвления будет пропущен только один раз». Но вы не учитываете пропуски ветвления O (N log N) внутри алгоритма сортировки, которые на самом деле больше, чем пропуски ветвления O (N) в несортированном случае. Таким образом, вам нужно было бы использовать всю совокупность отсортированных данных O (log N) раз для безубыточности (вероятно, на самом деле ближе к O (10 log N), в зависимости от алгоритма сортировки, например, для быстрой сортировки, из-за пропадания кэша - mergesort более кэш-когерентен, так что вам нужно приблизиться к O (2 log N) использования, чтобы
Люк Хатчисон
Одной из важных оптимизаций, однако, было бы сделать только «половину быстрой сортировки», сортируя только элементы, меньшие, чем целевое значение поворота 127 (предполагая, что все, меньше или равное сводке, сортируется после сводки). Как только вы достигнете точки, суммируйте элементы перед точкой. Это будет выполняться во время запуска O (N), а не O (N log N), хотя все еще будет много ошибок прогнозирования ветвлений, вероятно, порядка O (5 N) на основе чисел, которые я дал ранее, так как это половина быстрой сортировки.
Люк Хатчисон
132

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

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

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

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

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

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

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

______   ________
|     |__|

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

___________________________________________ Straight road
 |_________________________________________|Longer road

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


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

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

Omkaar.K
источник
124

Я попробовал тот же код с 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.

Shan
источник
7
Просто ради полноты, это, вероятно, не то, как вы бы реализовали это в Matlab. Могу поспорить, что это будет намного быстрее, если сделать это после векторизации проблемы.
ysap
1
Matlab выполняет автоматическое распараллеливание / векторизацию во многих ситуациях, но проблема здесь в том, чтобы проверить эффект предсказания ветвлений. Матлаб в любом случае не застрахован!
Шань
1
Использует ли matlab собственные числа или конкретную лабораторную реализацию (бесконечное количество цифр или около того?)
Торбьерн Равн Андерсен
55

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

Следующий код не сортирует весь массив, а только 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;
}

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

user2297550
источник
4
Я действительно не вижу, как это доказывает что-нибудь? Единственное, что вы показали, это то, что «не вся работа по сортировке всего массива занимает меньше времени, чем сортировка всего массива». Ваше утверждение, что это «также работает быстрее», очень зависит от архитектуры. Смотрите мой ответ о том, как это работает на ARM. PS вы могли бы ускорить свой код на архитектурах без ARM, поместив суммирование внутри цикла из 200 элементов, отсортировав его в обратном порядке, а затем воспользовавшись предложением Йохая Тиммера о разрыве при получении значения вне диапазона. Таким образом, каждое суммирование блока из 200 элементов может быть прекращено досрочно.
Люк Хатчисон
Если вы просто хотите эффективно реализовать алгоритм для несортированных данных, вы должны выполнить эту операцию без ответвлений (и с SIMD, например, с x86, pcmpgtbчтобы найти элементы с установленным старшим битом, а затем AND, чтобы обнулить меньшие элементы). Тратить любое время на сортировку кусков будет медленнее. Версия без ответвлений будет иметь независимую от данных производительность, что также будет свидетельствовать о том, что затраты обусловлены неправильным прогнозом переходов. Или просто используйте счетчики производительности, чтобы наблюдать это напрямую, как Skylake int_misc.clear_resteer_cyclesили int_misc.recovery_cyclesподсчитывать циклы простоя внешнего интерфейса от неправильных прогнозов
Питер Кордес
Оба комментария выше, кажется, игнорируют общие алгоритмические проблемы и сложности, в пользу защиты специализированного оборудования со специальными машинными инструкциями. Я нахожу первое, особенно мелкое, в том, что оно безрассудно отвергает важные общие идеи в этом ответе в слепой пользу специализированных машинных инструкций.
user2297550
36

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

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

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

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]) …”или эквивалентной. Для отсортированной последовательности этот тест всегда верен, тогда как для случайной последовательности выбранная ветвь изменяется случайным образом.

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

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

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

Сельчук
источник
28

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

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

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

hatirlatici
источник
Инструкции остаются горячими в кэше инструкций L1 ЦП независимо от их неправильных прогнозов. Проблема заключается в извлечении их в конвейер в правильном порядке, прежде чем непосредственно предыдущие инструкции будут декодированы и завершены.
Питер Кордес
15

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

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

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

// Тестовое задание

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

// Объявляем и затем заполняем таблицу поиска

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;
this library would do something like:

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

это хорошее решение, может быть, оно будет работать

Манодж Кашьям
источник
С каким компилятором / оборудованием C ++ вы это тестировали и с какими опциями компилятора? Я удивлен, что оригинальная версия не автоматически векторизовалась в хороший SIMD-код без ответвлений. Вы включили полную оптимизацию?
Питер Кордес
Таблица поиска 4096 записей звучит безумно. Если вы выходите любые биты, вам нужно не только использовать результат LUT , если вы хотите добавить оригинальный номер. Все это звучит как глупые трюки, чтобы обойти ваш компилятор не так просто, используя методы без ветвей. Более простым будет mask = tmp < 128 : 0 : -1UL;/total += tmp & mask;
Питер Кордес