Вопрос: Почему быстрее обрабатывать отсортированный массив, чем несортированный массив?


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

21451


источник


Ответы:


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


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

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

Licensed Image Образ by Mecanismo, через Википедия. Используется под CC-By-SA 3.0 лицензия.

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

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

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

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

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

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


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

image2

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

Современные процессоры сложны и имеют длинные конвейеры. Поэтому они навсегда навсегда «разогреваются» и «замедляются».

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

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

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


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

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

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

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

Дальнейшее чтение: Статья «Отраслевой предсказатель» в Википедии ,


Как намекнул сверху, виновником является это утверждение if:

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

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

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

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

T = branch taken
N = branch not taken

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

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

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

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

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

Итак, что может быть сделано?

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

Заменить:

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

с:

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

Это устраняет ветвь и заменяет ее некоторыми побитовыми операциями.

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

Контрольные показатели: Core i7 920 @ 3,5 ГГц

C ++ - Visual Studio 2010 - версия для x64

//  Branch - Random
seconds = 11.777

//  Branch - Sorted
seconds = 2.352

//  Branchless - Random
seconds = 2.564

//  Branchless - Sorted
seconds = 2.587

Java - Netbeans 7.1.1 JDK 7 - x64

//  Branch - Random
seconds = 10.93293813

//  Branch - Sorted
seconds = 5.643797077

//  Branchless - Random
seconds = 3.113581453

//  Branchless - Sorted
seconds = 3.186068823

Замечания:

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

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


Обновить:

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

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

  • Intel Compiler 11 делает что-то чудесное. Это развязывает две петли , тем самым поднимая непредсказуемую ветвь во внешний контур. Таким образом, он не только защищает ошибочные предсказания, но и в два раза быстрее, чем любые VC ++ и GCC могут генерировать! Другими словами, ICC воспользовался тестовым циклом, чтобы победить эталон ...

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

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


28313



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

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


3595



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

x86

//  Branch - Random
seconds = 8.885

//  Branch - Sorted
seconds = 1.528

//  Branchless - Random
seconds = 3.716

//  Branchless - Sorted
seconds = 3.71

x64

//  Branch - Random
seconds = 11.302

//  Branch - Sorted
 seconds = 1.830

//  Branchless - Random
seconds = 2.736

//  Branchless - Sorted
seconds = 2.737

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

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

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

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

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

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

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

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

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

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

Так почему же условный ход работает лучше?

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

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

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

Книга Компьютерные системы: перспектива программиста, второе издание подробно объясняет это. Вы можете проверить раздел 3.6.6 для Инструкции условного перемещения , целая глава 4 для Архитектура процессора , и Раздел 5.11.2 для специального лечения для Штрафное предсказание и штрафные санкции ,

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


2917



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

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

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


1999



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

Сортировка:

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

Unsorted:

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

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

Сортировка:

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

Unsorted:

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

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


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

perf stat ./sumtest_sorted

Сортировка:

 Performance counter stats for './sumtest_sorted':

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

  11.827228330 seconds time elapsed

Unsorted:

 Performance counter stats for './sumtest_unsorted':

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

  28.935500947 seconds time elapsed

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

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

Видеть учебник по производительности Больше подробностей.


1667



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

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

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

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

Предыстория и почему

Пфье, так что, черт возьми, это должно означать?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

// 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.Next(256);

//To keep the spirit of the code in-tact 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();

1138



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

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

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

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

Производительность if-statement зависит от того, имеет ли его состояние предсказуемую структуру. Если условие всегда истинно или всегда ложно, логика предсказания ветвления в процессоре будет забирать шаблон. С другой стороны, если шаблон непредсказуем, 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

A " Плохо «True-false pattern может сделать if-statement до шести раз медленнее, чем " хорошо " шаблон! Конечно, какой шаблон хорош, а что плохой, зависит от точных инструкций, генерируемых компилятором и конкретным процессором.

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


1016



One way to avoid branch prediction errors is to build a lookup table, and index it using the data. Stefan de Bruijn discussed that in his answer.

But in this case, we know values are in the range [0, 255] and we only care about values >= 128. That means we can easily extract a single bit that will tell us whether we want a value or not: by shifting the data to the right 7 bits, we are left with a 0 bit or a 1 bit, and we only want to add the value when we have a 1 bit. Let's call this bit the "decision bit".

By using the 0/1 value of the decision bit as an index into an array, we can make code that will be equally fast whether the data is sorted or not sorted. Our code will always add a value, but when the decision bit is 0, we will add the value somewhere we don't care about. Here's the code:

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

This code wastes half of the adds, but never has a branch prediction failure. It's tremendously faster on random data than the version with an actual if statement.

But in my testing, an explicit lookup table was slightly faster than this, probably because indexing into a lookup table was slightly faster than bit shifting. This shows how my code sets up and uses the lookup table (unimaginatively called lut for "LookUp Table" in the code). Here's the C++ code:

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

In this case the lookup table was only 256 bytes, so it fit nicely in cache and all was fast. This technique wouldn't work well if the data was 24-bit values and we only wanted half of them... the lookup table would be far too big to be practical. On the other hand, we can combine the two techniques shown above: first shift the bits over, then index a lookup table. For a 24-bit value that we only want the top half value, we could potentially shift the data right by 12 bits, and be left with a 12-bit value for a table index. A 12-bit table index implies a table of 4096 values, which might be practical.

EDIT: One thing I forgot to put in.

The technique of indexing into an array, instead of using an if statement, can be used for deciding which pointer to use. I saw a library that implemented binary trees, and instead of having two named pointers (pLeft and pRight or whatever) had a length-2 array of pointers, and used the "decision bit" technique to decide which one to follow. For example, instead of:

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

this library would do something like:

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

Here's a link to this code: Red Black Trees, Eternally Confuzzled


944



In the sorted case, you can do better than relying on successful branch prediction or any branchless comparison trick: completely remove the branch.

Indeed, the array is partitioned in a contiguous zone with data < 128 and another with data >= 128. So you should find the partition point with a dichotomic search (using Lg(arraySize) = 15 comparisons), then do a straight accumulation from that point.

Something like (unchecked)

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

or, slightly more obfuscated

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

A yet faster approach, that gives an approximate solution for both sorted or unsorted is: sum= 3137536; (assuming a truly uniform distribution, 16384 samples with expected value 191.5) :-)


871



The above behavior is happening because of Branch prediction.

To understand branch prediction one must first understand Instruction Pipeline:

Any instruction is broken into a sequence of steps so that different steps can be executed concurrently in parallel. This technique is known as instruction pipeline and this is used to increase throughput in modern processors. To understand this better please see this example on Wikipedia.

Generally, modern processors have quite long pipelines, but for ease let's consider these 4 steps only.

  1. IF -- Fetch the instruction from memory
  2. ID -- Decode the instruction
  3. EX -- Execute the instruction
  4. WB -- Write back to CPU register

4-stage pipeline in general for 2 instructions. 4-stage pipeline in general

Moving back to the above question let's consider the following instructions:

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

Without branch prediction, the following would occur:

To execute instruction B or instruction C the processor will have to wait till the instruction A doesn't reach till EX stage in the pipeline, as the decision to go to instruction B or instruction C depends on the result of instruction A. So the pipeline will look like this.

when if condition returns true: enter image description here

When if condition returns false: enter image description here

As a result of waiting for the result of instruction A, the total CPU cycles spent in the above case (without branch prediction; for both true and false) is 7.

So what is branch prediction?

Branch predictor will try to guess which way a branch (an if-then-else structure) will go before this is known for sure. It will not wait for the instruction A to reach the EX stage of the pipeline, but it will guess the decision and go to that instruction (B or C in case of our example).

In case of a correct guess, the pipeline looks something like this: enter image description here

If it is later detected that the guess was wrong then the partially executed instructions are discarded and the pipeline starts over with the correct branch, incurring a delay. The time that is wasted in case of a branch misprediction is equal to the number of stages in the pipeline from the fetch stage to the execute stage. Modern microprocessors tend to have quite long pipelines so that the misprediction delay is between 10 and 20 clock cycles. The longer the pipeline the greater the need for a good branch predictor.

In the OP's code, the first time when the conditional, the branch predictor does not have any information to base up prediction, so the first time it will randomly choose the next instruction. Later in the for loop, it can base the prediction on the history. For an array sorted in ascending order, there are three possibilities:

  1. All the elements are less than 128
  2. All the elements are greater than 128
  3. Some starting new elements are less than 128 and later it become greater than 128

Let us assume that the predictor will always assume the true branch on the first run.

So in the first case, it will always take the true branch since historically all its predictions are correct. In the 2nd case, initially it will predict wrong, but after a few iterations, it will predict correctly. In the 3rd case, it will initially predict correctly till the elements are less than 128. After which it will fail for some time and the correct itself when it sees branch prediction failure in history.

In all these cases the failure will be too less in number and as a result, only a few times it will need to discard the partially executed instructions and start over with the correct branch, resulting in fewer CPU cycles.

But in case of a random unsorted array, the prediction will need to discard the partially executed instructions and start over with the correct branch most of the time and result in more CPU cycles compared to the sorted array.


682



An official answer would be from

  1. Intel - Avoiding the Cost of Branch Misprediction
  2. Intel - Branch and Loop Reorganization to Prevent Mispredicts
  3. Scientific papers - branch prediction computer architecture
  4. Books: J.L. Hennessy, D.A. Patterson: Computer architecture: a quantitative approach
  5. Articles in scientific publications: T.Y. Yeh, Y.N. Patt made a lot of these on branch predictions.

You can also see from this lovely diagram why the branch predictor gets confused.

2-bit state diagram

Each element in the original code is a random value

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

so the predictor will change sides as the std::rand() blow.

On the other hand, once it's sorted, the predictor will first move into a state of strongly not taken and when the values change to the high value the predictor will in three runs through change all the way from strongly not taken to strongly taken.



603