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

avatar
GManNickG
27 июня 2012 в 13:51
1651749
29
25946

Вот фрагмент кода 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)
    {
        for (unsigned c = 0; c < arraySize; ++c)
        {   // Primary loop
            if (data[c] >= 128)
                sum += data[c];
        }
    }

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

    std::cout << elapsedTime << '\n';
    std::cout << "sum = " << sum << '\n';
}
  • Без 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)
        {
            for (int c = 0; c < arraySize; ++c)
            {   // Primary loop
                if (data[c] >= 128)
                    sum += data[c];
            }
        }

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

С аналогичным, но менее экстремальным результатом.


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

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

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


Связанные / дополнительные вопросы и ответы о том же эффекте с разными / более поздними компиляторами и параметрами:

Источник
screwnut
3 мая 2018 в 23:12
102

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

Šimon Hrabec
11 мая 2018 в 12:45
48

Еще одно наблюдение состоит в том, что вам не нужно сортировать массив, вам просто нужно разделить его со значением 128. Сортировка n * log (n), тогда как разделение просто линейное. По сути, это всего лишь один запуск шага быстрой сортировки по разделу с выбранным значением поворота 128. К сожалению, в C ++ есть только функция nth_element, которая выполняет разделение по позиции, а не по значению.

Jonas Kölker
5 октября 2020 в 08:26
11

@screwnut вот эксперимент, который покажет, что разделения достаточно: создайте несортированный, но разделенный массив со случайным содержимым. Измерьте время. Сортировать. Снова измерить время. Эти два измерения должны быть в основном неразличимы. (Эксперимент 2: создайте случайный массив. Измерьте время. Разделите его. Измерьте время еще раз. Вы должны увидеть такое же ускорение, как и сортировка. Вы можете объединить два эксперимента в один.)

Piotr Czapla
31 марта 2021 в 09:07
6

Кстати. на Apple M1 код выполняется за 17 секунд без сортировки и за 7 секунд после сортировки, так что штраф за предсказание ветвления не так уж плох для рисковой архитектуры.

Peter Cordes
15 апреля 2021 в 06:31
6

@RomanYavorskyi: Это зависит от компилятора. Если они сделают asm без ответвлений для этого конкретного теста (например, как часть векторизации с помощью SIMD, как в ) Почему обработка несортированного массива такая же скорость, как и обработка отсортированного массива с помощью современных x86-64 clang? или просто с скаляр cmov (флаг оптимизации gcc -O3 делает код медленнее, чем -O2), то отсортированный или нет не имеет значения. Но непредсказуемые ветви все еще очень реальны, когда это не так просто, как подсчет, так что было бы безумием удалять этот вопрос.

Peter Cordes
15 апреля 2021 в 06:46
3

@screwnut: Однако, честно говоря, все равно не стоит сначала размечать разделы, потому что разделение требует условного копирования или подкачки на основе того же сравнения array[i] > 128. (Если вы не собираетесь считать несколько раз и хотите разделить большую часть массива, чтобы он оставался быстрым, только неверное предсказание в неразмеченной части после некоторых добавлений или модификаций). Если вы можете заставить компилятор сделать это, в идеале просто векторизуйте с помощью SIMD или, по крайней мере, используйте скаляр без ветвей, если данные непредсказуемы. (Ссылки см. В предыдущем комментарии.)

Ответы (29)

avatar
Mysticial
27 июня 2012 в 13:56
33554

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


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

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

Image showing a railroad junction Изображение от Mecanismo, через Wikimedia Commons. Используется по лицензии CC-By-SA 3.0.

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

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

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

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

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

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


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

Screenshot of compiled code containing an if statement

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

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

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

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

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


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

Как вы стратегически догадались бы минимизировать количество раз, когда поезд должен возвращаться назад и спускаться по другому пути? Вы посмотрите на прошлую историю! Если поезд идет налево в 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, ...
branch =   T,   T,   N,   T,   T,   T,   T,  N,   T,   N,   N,   T,   T,   T  ...

       = TTNTTTTNTNNTTT ...   (completely random - impossible 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

Сценарий Время (секунды)
Ветвление - случайные данные 11,777
Ветвление - Сортированные данные 2,352
Без филиалов - случайные данные 2,564
Без филиалов - Сортированные данные 2,587

Java - NetBeans 7.1.1 JDK 7 - x64

Сценарий Время (секунды)
Ветвление - случайные данные 10.93293813
Ветвление - Сортированные данные 5.643797077
Без филиалов - случайные данные 3,113581453
Без филиалов - Сортированные данные 3,186068823

Наблюдения:

  • С веткой: Между отсортированными и несортированными данными существует огромная разница.
  • С помощью взлома: ​​Нет разницы между отсортированными и несортированными данными.
  • В случае 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 код без ветвей, он просто векторизует его ... и будет так же быстро, как и с ветвлением (с заменой цикла).

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

Hanna Mcquaig
1 июля 2020 в 00:11
47

это все C ++?

Clijsters
1 июля 2020 в 10:02
201

@HannaMcquaig Я бы предположил, что та часть, где написано "Java", не является C ++, но я могу ошибаться.

Matias Chara
12 июля 2020 в 23:52
22

подождите секунду, разве смещение отрицательных значений вправо не приводит к значениям, определяемым реализацией? int t = (данные [c] - 128) >> 31; сумма + = ~ t & данные [c];

Agoston Horvath
6 октября 2020 в 08:37
4

@MatiasChara это действительно скрыто, см. en.wikipedia.org/wiki/…; «однако большинство компиляторов выполнят арифметический сдвиг, в результате чего пробел будет заполнен знаковым битом левого операнда». Я полагаю, что к настоящему времени это стандарт де-факто.

mins
16 октября 2020 в 14:04
32

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

Max
26 ноября 2020 в 23:32
6

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

Mycotina
8 декабря 2020 в 09:26
5

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

Ibnelaiq
9 декабря 2020 в 07:05
4

@HannaMcquaig Всегда был

Raphael
5 января 2021 в 15:51
22

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

WhozCraig
8 января 2021 в 02:03
7

@Mycotina Это легче понять, если вы подумаете о кэше конвейера инструкций как о путях, о поезде (с вагонами) как о инструкциях и индикаторе того, идете ли вы влево или вправо каким-то чуваком в КОНЦЕ поезда; не начало. К тому времени, когда вы увидите его, чтобы понять, что вы угадали, уже слишком поздно что-то менять, конвейер впереди уже заполнен, но идет в неправильном направлении. Если вы ошиблись, предсказанный трубопровод нужно выбросить (сходить с рельсов; перетащить его обратно перед стрелочным переводом, поставить обратно на рельсы и отправить в обратном направлении).

C. Binair
3 марта 2021 в 16:21
4

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

Tom
10 марта 2021 в 14:47
7

@ C.Binair В первую очередь это среда выполнения, т.е. процессор предсказывает переходы при выполнении кода. Процессор также запоминает предыдущие результаты и использует их для прогнозирования следующего прыжка. Однако компилятор может предоставить некоторые начальные подсказки для предсказания ветвления во время компиляции - поиск «вероятных» и «маловероятных» атрибутов. Таким образом, можно сказать, что и то, и другое, но во время выполнения это происходит на самом деле.

Bhanuday Sharma
6 июня 2021 в 17:26
8

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

Peter Cordes
12 июня 2021 в 00:53
3

@Tom: Не совсем так. Большинство ISA не имеют какого-либо механизма, позволяющего компилятору фактически предоставлять ЦП подсказки ветвлений. Макросы likely / unlikely в основном просто влияют на решение использовать cmov (без ветвлений) вместо фактического ветвления и размещать asm так, чтобы в ожидаемом случае было меньше ветвей. (т. е. быстрый путь может быть получен конвейером непрерывно большими фрагментами.) Есть ли подсказка компилятора для GCC, чтобы заставить предсказание ветвления всегда идти определенным путем? И это пример фактического генератора кода x86.

Kuba hasn't forgotten Monica
21 августа 2021 в 04:24
1

@ C.Binair Прогноз делается во время выполнения, и его реализация обходится в миллионы транзисторов на ядро. И несколько докторов наук. диссертаций стоит потрудиться :) Современные предсказатели ветвления - это чудо инженерной мысли, вплоть до того, что Эйфелева башня начинает выглядеть крохотной. Они скрыты от глаз, но во многом отвечают за производительность современных процессоров. Отключите предсказание ветвлений (например, написав код, который захлопывает предсказатель и делает его бесполезным), и ядро ​​i7 3 ГГц похоже на дешевую ARM Arduino ...

tonnoz
25 августа 2021 в 14:51
2

Вероятно, один из лучших ответов на платформе, спасибо!

avatar
Geek26
5 ноября 2021 в 10:05
17

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

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

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

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

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

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

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

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

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

Peter Cordes
5 ноября 2021 в 10:50
2

Изменение должно быть ближе к середине отсортированного пути/пути выполнения, так как ветвь внутри цикла берется за первую половину, а не за последнюю половину элементов. (Или наоборот.) Кроме того, что означают 5 различных уровней в несортированном случае? Это двусторонняя ветвь.

GManNickG
5 ноября 2021 в 18:23
4

Что добавляет этот ответ, чего не хватает в существующих ответах?

avatar
MuhammadAliDEV
26 октября 2021 в 09:25
0

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

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

// 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;
}

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

timing of execution

Заключение:

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

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

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

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

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

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

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

Peter Cordes
26 октября 2021 в 09:33
1

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

Peter Cordes
26 октября 2021 в 09:45
1

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

MuhammadAliDEV
27 октября 2021 в 01:41
0

@PeterCordes проверьте сейчас. исправил проблему.

avatar
Bart Mensfort
27 июня 2021 в 13:49
-3

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

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

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

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

Peter Cordes
27 июня 2021 в 15:36
5

Вопрос был не в этом. Вопрос был в следующем: , если данные уже отсортированы, почему этот конкретный цикл условного приращения выполняется быстрее. Но да, если вы хотите ответить на вопрос «как оптимизировать этот запрос по отношению к массиву»: гистограмма действительно поместит ваши данные в форму, которая могла бы гораздо быстрее отвечать на запросы с произвольным порогом. Но если вы просто хотите ответить на один запрос для заданного порога с этими данными, предварительная обработка данных не ускорится. (По крайней мере, если вы можете убедить компилятор выполнить безветвленную сумму результатов сравнения логических значений 0/1.)

avatar
Numan Gillani
14 апреля 2021 в 08:08
16

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

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

data[c] >= 128

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

Peter Cordes
14 апреля 2021 в 08:15
1

Кеши инструкций и данных ЦП отделены от предсказания ветвления. (Сам BPU можно рассматривать как кэш направлений ветвления, но если это вы имеете в виду, вам следует быть более конкретным.) Весь код будет оставаться горячим в кэше L1i независимо от неверного предсказания ветвления; Проблема в самом конвейере. ЦП (или код) ничего не «ищет», поэтому я не уверен, что вы пытаетесь донести, когда говорите о «времени поиска».

Numan Gillani
14 апреля 2021 в 08:19
0

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

Peter Cordes
14 апреля 2021 в 08:25
1

Да, это правильно. Если вы замените свой текущий ответ этим комментарием, я бы изменил свой голос против! Но ваш ответ объясняет это не так. Вместо этого ваш ответ гласит: «В следующий раз кэш-память будет использоваться для поиска», что даже не имеет смысла и, конечно же, не является точным описанием соответствующей части внутреннего устройства ЦП.

Peter Cordes
14 апреля 2021 в 08:33
1

Кроме того, несортированный массив «имеет стоимость ветвления» только в том случае, если у вашего asm-файла изначально есть ветки. Счетчик без ответвлений (например, Почему обработка несортированного массива такая же скорость, как и обработка отсортированного массива с помощью современных x86-64 clang?) не заботится о шаблонах в данных.

avatar
Selcuk
10 января 2021 в 16:02
89

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

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

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

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

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

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

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

Peter Cordes
14 апреля 2021 в 22:29
0

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

avatar
hatirlatici
23 октября 2019 в 21:35
81

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

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

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

Peter Cordes
13 декабря 2019 в 14:29
1

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

avatar
user2297550
9 декабря 2018 в 06:18
103

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

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

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

Luke Hutchison
28 февраля 2019 в 12:18
4

Я действительно не понимаю, как это что-то доказывает? Единственное, что вы показали, это то, что «не выполнение всей работы по сортировке всего массива занимает меньше времени, чем сортировка всего массива». Ваше заявление о том, что он «работает быстрее всех», очень зависит от архитектуры. См. Мой ответ о том, как это работает на ARM. PS вы можете ускорить свой код на архитектурах без ARM, поместив суммирование в цикл блока из 200 элементов, сортировку в обратном порядке, а затем используя предложение Йохая Тиммера о взломе, как только вы получите значение вне диапазона. Таким образом, суммирование каждого 200-элементного блока может быть завершено досрочно.

Peter Cordes
13 декабря 2019 в 14:44
0

Если вы просто хотите эффективно реализовать алгоритм для несортированных данных, вы должны выполнить эту операцию без ответвлений (и с помощью SIMD, например, с x86 pcmpgtb, чтобы найти элементы с их старшим битом, затем И для обнуления меньших элементов). Тратить время на сортировку кусков будет медленнее. Безотказная версия будет иметь независимую от данных производительность, что также доказывает, что цена связана с неверным прогнозом ветвления. Или просто используйте счетчики производительности, чтобы наблюдать это напрямую, например, Skylake int_misc.clear_resteer_cycles или int_misc.recovery_cycles для подсчета циклов простоя внешнего интерфейса из неверных прогнозов.

user2297550
3 апреля 2020 в 06:44
1

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

user2297550
19 июня 2021 в 17:50
0

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

avatar
Luke Hutchison
22 декабря 2017 в 13:13
229

В 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 года, Стива Фербера и Роджера (ныне Софи) Уилсона.

Luke Hutchison
15 мая 2018 в 17:06
3

Другим нововведением в ARM является добавление суффикса инструкции S, который также является необязательным для (почти) всех инструкций, который, если он отсутствует, не позволяет инструкциям изменять биты состояния (за исключением инструкции CMP, задача которой заключается в установке битов состояния, поэтому суффикс S не нужен). Это позволяет вам избегать команд CMP во многих случаях, пока выполняется сравнение с нулем или аналогичным (например, SUBS R0, R0, # 1 установит бит Z (ноль), когда R0 достигнет нуля). Условные выражения и суффикс S не требуют накладных расходов. Довольно красивая ISA.

Luke Hutchison
15 мая 2018 в 17:08
3

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

Peter Cordes
21 февраля 2020 в 11:34
1

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

Peter Cordes
21 февраля 2020 в 11:36
2

Кстати, вы можете сохранить инструкцию в цикле, индексируя ее относительно конца массива. Перед циклом установите R2 = data + arraySize, затем начните с R1 = -arraySize. Нижняя часть цикла становится adds r1, r1, #1 / bnz inner_loop. Компиляторы по какой-то причине не используют эту оптимизацию: / Но в любом случае, предиктивное выполнение добавления в этом случае принципиально не отличается от того, что вы можете делать с кодом без ответвлений на других ISA, например x86 cmov. Хотя это не так хорошо: флаг оптимизации gcc -O3 делает код медленнее, чем -O2

Peter Cordes
21 февраля 2020 в 11:40
2

(Выполнение с предиктором ARM действительно не выполняет команду, поэтому вы даже можете использовать его при загрузке или сохранении, которые могут вызвать сбой, в отличие от x86 cmov с операндом источника памяти. Большинство ISA, включая AArch64, имеют только операции выбора ALU. Таким образом, предикация ARM может быть мощным и более эффективным, чем код без ветвей на большинстве ISA.)

avatar
omkaartg
7 декабря 2017 в 17:28
181

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

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

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

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

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

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

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

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

______   ________
|     |__|

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

___________________________________________ Straight road
 |_________________________________________|Longer road

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


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

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

avatar
Yochai Timmer
23 ноября 2017 в 14:28
197

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

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

 // 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];               
 }
Luke Hutchison
6 ноября 2018 в 12:28
2

Верно, но стоимость настройки сортировки массива составляет O (N log N), поэтому раннее прерывание не поможет вам, если единственная причина, по которой вы сортируете массив, - это возможность преждевременного прерывания. Если, однако, у вас есть другие причины для предварительной сортировки массива, тогда да, это полезно.

Yochai Timmer
27 февраля 2019 в 12:23
1

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

Luke Hutchison
28 февраля 2019 в 12:28
3

Да, именно об этом я сказал в своем первом комментарии :-) Вы говорите: «Прогноз ветвления будет пропущен только один раз». Но вы не учитываете промахи предсказания ветвления O (N log N) внутри алгоритма сортировки, что на самом деле больше, чем промахи предсказания ветвления O (N) в несортированном случае. Таким образом, вам нужно будет использовать все отсортированные данные O (log N) раз, чтобы достичь безубыточности (вероятно, фактически ближе к O (10 log N), в зависимости от алгоритма сортировки, например, для быстрой сортировки, из-за промахов в кеше - mergesort является более согласованным с кешем, поэтому вам понадобится около O (2 log N), чтобы выйти на безубыточность.)

Luke Hutchison
28 февраля 2019 в 12:34
1

Однако одной из значительных оптимизаций было бы выполнение только «быстрой сортировки наполовину», сортировка только элементов, меньших целевого значения поворота 127 (при условии, что все меньше или равно , точка поворота сортируется после поворота). Достигнув точки поворота, просуммируйте элементы перед точкой поворота. Это будет выполняться за время запуска O (N), а не за O (N log N), хотя по-прежнему будет много промахов предсказания ветвления, вероятно порядка O (5 N) на основе чисел, которые я дал ранее, поскольку это половина быстрой сортировки.

avatar
Eugene
6 ноября 2017 в 16:15
350

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

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

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

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

figure 1

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

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

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

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

without branch predictor

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

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

enter image description here

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

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

enter image description here

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

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

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

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

mckenzm
29 июля 2019 в 05:14
5

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

Peter Cordes
10 февраля 2020 в 04:03
4

@mckenzm: спекулятивный exec вне очереди делает предсказание ветвлений еще более ценным; а также скрытие пузырей выборки / декодирования, прогнозирование ветвлений + спекулятивное выполнение удаляет зависимости управления от задержки критического пути. Код внутри или после блока if() может выполнить до , когда станет известно условие перехода. Или для цикла поиска, такого как strlen или memchr, взаимодействия могут перекрываться. Если бы вам пришлось ждать, пока не станет известен результат «совпадение или нет», прежде чем запускать любую из следующих итераций, у вас возникнет узкое место по загрузке кеша + задержка ALU вместо пропускной способности.

Hanna Mcquaig
1 июля 2020 в 00:19
2

Вы создали пример приложения на JavaFX?

Eugene
1 июля 2020 в 01:14
2

@HannaMcquaig Нет, это сделано Swing. Код доступен по адресу github.com/Eugene-Mark/branch-predictor-demo.

avatar
Farhad
3 октября 2017 в 09:47
204

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

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

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

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

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

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

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

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

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

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

Ссылки:

avatar
Tony Tannous
4 августа 2017 в 10:07
265

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

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

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

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

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

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

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

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

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

 O      Route 1  /-------------------------------
/|\             /
 |  ---------##/
/ \            \
                \
        Route 2  \--------------------------------
Peter Cordes
10 февраля 2020 в 04:07
1

Хотя промывка трубопроводов происходит очень быстро Не совсем. Это быстро по сравнению с отсутствием кэша вплоть до DRAM, но на современной высокопроизводительной x86 (например, в семействе Intel Sandybridge) это около десятка циклов. Хотя быстрое восстановление позволяет избежать ожидания выхода всех старых независимых инструкций на пенсию, прежде чем начинать восстановление, вы все равно теряете много клиентских циклов из-за неверного прогноза. Что именно происходит, когда процессор Skylake неверно предсказывает ветвь?. (И в каждом цикле может быть около 4 рабочих инструкций.) Плохо для высокопроизводительного кода.

avatar
Alireza
18 июня 2017 в 11:40
420

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

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

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

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

Branch Prediction

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

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

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

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

Branch Prediction

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

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

avatar
ForeverLearning
12 января 2017 в 01:50
383

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

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

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

Peter Mortensen
16 марта 2018 в 12:47
5

Это очень интересная статья (на самом деле, я ее только что прочитал), но как она отвечает на вопрос?

ForeverLearning
16 марта 2018 в 15:37
4

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

avatar
Surt
11 октября 2015 в 21:05
812

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

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

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

2-bit state diagram

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

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

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

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


avatar
Maciej
10 октября 2015 в 00:30
767

Часто используемые логические операции в 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;

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

avatar
rkachach
23 сентября 2015 в 14:57
781

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

avatar
Harsh Sharma
3 июля 2015 в 15:35
918

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

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

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

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

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

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

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

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

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

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

если условие возвращает истину: enter image description here

Если условие возвращает false: enter image description here

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

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

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

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

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

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

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

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

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

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

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

M.kazem Akhgary
11 октября 2017 в 14:49
4

как две инструкции выполняются вместе? Это делается с помощью отдельных ядер процессора или инструкции конвейера интегрированы в одно ядро ​​процессора?

Sergey.quixoticaxis.Ivanov
3 ноября 2017 в 07:45
4

@ M.kazemAkhgary Все это внутри одного логического ядра. Если вам интересно, это хорошо описано, например, в Руководстве разработчика программного обеспечения Intel

avatar
Yves Daoust
24 июля 2013 в 07:57
1123

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

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

sehe
24 июля 2013 в 16:31
35

sum= 3137536 - умно. Очевидно, вопрос не в этом. Вопрос явно в объяснении удивительных характеристик производительности. Я склонен сказать, что добавление выполнения std::partition вместо std::sort полезно. Хотя на самом деле вопрос касается не только приведенного синтетического теста.

Yves Daoust
24 июля 2013 в 20:37
19

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

avatar
steveha
22 июля 2013 в 08:29
1248

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

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

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

atlaste
29 июля 2013 в 12:05
43

Правильно, вы также можете просто использовать бит напрямую и умножать (data[c]>>7 - это тоже где-то обсуждается); Я намеренно исключил это решение, но, конечно, вы правы. Небольшое примечание: эмпирическое правило для таблиц поиска заключается в том, что если он умещается в 4 КБ (из-за кеширования), он будет работать - желательно сделать таблицу как можно меньше. Для управляемых языков я бы увеличил объем до 64 КБ, для низкоуровневых языков, таких как C ++ и C, я бы, вероятно, пересмотрел (это только мой опыт). Начиная с typeof(int) = 4, я бы попытался придерживаться максимум 10 бит.

steveha
29 июля 2013 в 22:02
31

Я думаю, что индексирование со значением 0/1, вероятно, будет быстрее, чем целочисленное умножение, но я думаю, если производительность действительно критична, вы должны ее профилировать. Я согласен с тем, что небольшие таблицы поиска необходимы, чтобы избежать нагрузки на кеш, но очевидно, что если у вас больший кеш, вы можете обойтись более крупной таблицей поиска, поэтому 4 КБ - это скорее практическое правило, чем жесткое правило. Я думаю, вы имели в виду sizeof(int) == 4? Это было бы верно для 32-битной версии. У моего двухлетнего сотового телефона кэш L1 32 КБ, поэтому даже таблица поиска 4K может работать, особенно если значения поиска были байтами, а не int.

Richard Tingle
4 марта 2014 в 15:38
24

Возможно, мне что-то не хватает, но в вашем методе j, равном 0 или 1, почему бы вам просто не умножить свое значение на j перед его добавлением, а не использовать индексирование массива (возможно, следует умножить на 1-j, а не j)

atlaste
18 марта 2014 в 08:45
15

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

atlaste
18 марта 2014 в 08:52
21

@steveha P.S .: другой возможный ответ - int c = data[j]; sum += c & -(c >> 7);, который вообще не требует умножения.

Falco
2 апреля 2014 в 15:15
2

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

Petter
4 июля 2014 в 14:56
2

Заин прав. «Если» просто скрыто в таблице поиска. Код выполняется быстрее, потому что таблица поиска скрыта ВНЕ 100000 итераций. Использование таблицы поиска для решения этой проблемы не дает никаких преимуществ.

Logan Pickup
27 октября 2014 в 21:01
2

i = (x < node->value); node = node->link[i]; не имеет явной ветки, но по-прежнему содержит сравнение; от целевой архитектуры во многом зависит, можно ли решить эту проблему без ветки или нет. Поскольку это можно сделать на x86 (с использованием CMOV или LAHF) и ARM (условное добавление или перемещение), которые являются единственными архитектурами, которые я использую, возможно, это не важно!

steveha
27 октября 2014 в 23:05
2

В какой архитектуре для выражения типа (x < node->value) потребуется ветвь для оценки? Все архитектуры, с которыми я знаком, имеют регистр «флагов», и его просто извлечь желаемое значение флага. Я предполагаю, что на Pentium 4 извлечение битов флагов может быть медленным, поскольку IIRC этот чип не имеет специального оборудования для сдвига адресов, но заимствует ALU для сдвига битов. Но я не знаю, где может понадобиться настоящая ветка. Хм, ваши примеры были условными ... Идея в том, что, как только вы извлечете бит из флагов, вы можете просто использовать индексацию без ветки.

Luke Hutchison
28 февраля 2019 в 12:37
2

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

Peter Mortensen
27 мая 2019 в 13:07
2

А как насчет размеров кеша, L1, L2 и т. Д.? Необходимость обращаться к основной памяти для поиска в таблице была бы убийственной. Можете ли вы указать на это в своем ответе?

avatar
atlaste
24 апреля 2013 в 06:26
1471

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

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

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

  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();
avatar
Saqlain
15 февраля 2013 в 07:24
1315

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

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

cst1992
28 марта 2016 в 12:58
43

@MooingDuck 'Потому что это не имеет значения - это значение может быть любым, но оно все равно будет в пределах этих пороговых значений. Так зачем показывать случайное значение, если вы уже знаете пределы? Хотя я согласен с тем, что вы могли бы показать его для полноты картины и «просто так».

Mooing Duck
28 марта 2016 в 18:27
45

@ cst1992: Сейчас его самый медленный тайминг - TTFFTTFFTTFF, что на мой взгляд кажется вполне предсказуемым. Random по своей сути непредсказуем, поэтому вполне возможно, что он будет еще медленнее и, следовательно, выходит за пределы, указанные здесь. OTOH, может быть, TTFFTTFF отлично подходит для патологического случая. Не могу сказать, так как он не показывал время для случайного.

steveha
20 июля 2016 в 21:07
41

@MooingDuck Для человеческого глаза «TTFFTTFFTTFF» - это предсказуемая последовательность, но здесь мы говорим о поведении предиктора ветвления, встроенного в ЦП. Предсказатель ветвления - это не распознавание образов на уровне AI; это очень просто. Когда вы просто чередуете ветки, это плохо предсказывает. В большинстве случаев ветки почти всегда выполняются одинаково; рассмотрим цикл, который выполняется тысячу раз. Ветвь в конце цикла возвращается к началу цикла 999 раз, а затем в тысячный раз делает что-то другое. Обычно хорошо работает очень простой предсказатель ветвления.

Mooing Duck
20 июля 2016 в 21:10
37

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

steveha
26 июля 2016 в 03:49
6

@MooingDuck Это правда, что я не эксперт в проектировании процессоров. Но я предлагаю вам прочитать страницу Википедии о предикторах ветвления. Ни один из обсуждаемых проектов не мог привязаться к шаблону TTFFTTFF ... и правильно предсказать. (За исключением, может быть, нейронной сети с достаточно развитой нейронной сетью, и я готов поспорить, что вы обналичиваете деньги, что у вас нет вычислительного устройства с таким предсказателем ветвления в своем процессоре.) ru.wikipedia .org / wiki / Branch_predictor

Mooing Duck
26 июля 2016 в 04:33
21

@steveha: Двухуровневый адаптивный предсказатель может без проблем зафиксироваться на шаблоне TTFFTTFF. «Варианты этого метода прогнозирования используются в большинстве современных микропроцессоров». Прогнозирование локального ветвления и глобальное предсказание ветвления основаны на двухуровневом адаптивном предсказателе, они также могут. «Глобальное предсказание ветвлений используется в процессорах AMD, а также в процессорах Intel Pentium M, Core, Core 2 и Atom на базе Silvermont». Также добавьте в этот список предиктор Согласен, Гибридный предиктор, Прогнозирование косвенных переходов. Предиктор цикла не фиксируется, но достигает 75%. Остается только 2, которые нельзя заблокировать.

Warren K
23 декабря 2016 в 22:32
7

@MooingDuck: Диаграмма в ответе Сурта ниже, я думаю, объясняет, почему TTFFTTFF на самом деле является «патологическим случаем» в примере Saqlain.

avatar
Shan
30 декабря 2012 в 16:16
166

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

ysap
17 мая 2013 в 19:53
9

Просто для полноты картины, вероятно, это не то, как вы бы реализовали это в Matlab. Бьюсь об заклад, это было бы намного быстрее, если бы это было сделано после векторизации проблемы.

Shan
17 мая 2013 в 23:50
2

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

Thorbjørn Ravn Andersen
24 августа 2013 в 16:34
2

Использует ли Matlab собственные числа или конкретную реализацию matlab (бесконечное количество цифр или около того?)

avatar
caf
12 октября 2012 в 05:53
2022

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

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

TallBrian
9 декабря 2013 в 04:00
92

Это страшно, в несортированном списке должна быть 50% вероятность попадания в доп. Почему-то предсказание ветвления имеет только 25% промахов, как оно может быть лучше, чем 50% промахов?

caf
9 декабря 2013 в 04:29
149

@ tall.b.lo: 25% от всех ветвей - в цикле две ветки , одна для data[c] >= 128 (которая имеет коэффициент пропусков 50%, как вы предлагаете) и одна для условие цикла c < arraySize, которое имеет коэффициент промахов ~ 0%.

avatar
vulcan raven
3 июля 2012 в 02:25
2463

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

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

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

avatar
WiSaGaN
28 июня 2012 в 02:14
3581

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

Сценарий Время (секунды)
Ветвление - случайные данные 8,885
Ветвление - Сортированные данные 1,528
Без филиалов - случайные данные 3,716
Без филиалов - Сортированные данные 3,71

x64

Сценарий Время (секунды)
Ветвление - случайные данные 11.302
Ветвление - Сортированные данные 1,830
Без филиалов - случайные данные 2,736
Без филиалов - Сортированные данные 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 для специальной обработки для Прогнозирование ветвления и <4777495 4725825 штрафов. >.

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

fernal73
3 декабря 2020 в 05:32
4

coderhelper.com/questions/9745389/…

avatar
Daniel Fischer
27 июня 2012 в 13:54
4406

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

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

Adam Freeman
23 сентября 2014 в 18:58
144

Работает ли предсказание ветвления лучше для отсортированных массивов по сравнению с массивами с разными шаблонами? Например, для массива -> {10, 5, 20, 10, 40, 20, ...} следующий элемент в массиве из шаблона - 80. Будет ли этот тип массива ускорен за счет предсказания ветвления в какой следующий элемент здесь 80, если следовать шаблону? Или это обычно помогает только с отсортированными массивами?

Agrim Pathak
30 октября 2014 в 07:51
187

То есть все, что я обычно узнал о Big-O, выпало из окна? Лучше нести затраты на сортировку, чем затраты на разветвление?

Daniel Fischer
30 октября 2014 в 10:14
175

@AgrimPathak Это зависит от обстоятельств. Для не слишком больших входных данных алгоритм с более высокой сложностью работает быстрее, чем алгоритм с меньшей сложностью, когда константы меньше для алгоритма с более высокой сложностью. Трудно предсказать, где находится точка безубыточности. Кроме того, сравните этот, местонахождение важно. Big-O важен, но это не единственный критерий производительности.

Filip Bartuzi
9 ноября 2014 в 13:37
95

Когда происходит предсказание ветвления? Когда язык узнает, что массив отсортирован? Я думаю о ситуации с массивом, который выглядит так: [1,2,3,4,5, ... 998,999,1000, 3, 10001, 10002]? увеличит ли этот неясный 3 время работы? Это будет столько же, сколько несортированный массив?

Daniel Fischer
9 ноября 2014 в 13:49
91

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

Peter Wone
1 мая 2015 в 04:02
5

@AdamFreeman - Сортировка здесь актуальна только постольку, поскольку в этом коде увеличивает предсказание ветвления до 100% успеха.

Dr t
25 мая 2017 в 17:51
6

Я бы порекомендовал взглянуть на: en.wikibooks.org/wiki/Optimizing_C%2B%2B/Writing_efficient_code/…, который обеспечивает хорошее обсуждение с примерами этой темы, включая те, которые не упоминаются в каких-либо комментариях, которые я видел по этому вопросу.

आनंद
15 сентября 2017 в 14:16
5

@DanielFischer знает ли компилятор, какой массив отсортирован, а какой нет?

knickum
13 октября 2017 в 21:43
6

@AnandTyagi Как заметил Питер Вон, компилятор не знает, какой массив отсортирован или нет. Представьте себе чрезвычайно простой предсказатель ветвления, который принимает тот же путь, что и предыдущая итерация, например поезд, поворачивающий налево, если последний раз ехал налево, и наоборот. Для отсортированного массива из 256 целых чисел (игнорируя неопределенную первую итерацию) прогноз будет правильным от 2 до 128, неправильным при 129, а затем правильным из 130–256. Это ужасный предсказатель ветвления, который будет работать только в этой конкретной ситуации, но действительно хороший предсказатель должен с этим справиться.

Omer
27 июня 2020 в 05:57
3

Прогнозы ветвления в основном происходят на уровне компилятора или обрабатываются процессором? И почему java или c ++ не могут с этим справиться? Я имею в виду, почему это не сложно предсказать, верно?