Why is processing a sorted array faster than processing an unsorted array?

В этом коде на C ++ сортировка данных (перед временной областью) ускоряет выполнение основного цикла примерно в 6 раз:

#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);
    }
}

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

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

• Что происходит?


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

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

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

• Почему обработка несортированного массива выполняется с той же скоростью, что и обработка отсортированного массива с помощью современного x86-64 clang?


• флаг оптимизации gcc -O3 делает код медленнее, чем -O2

You are a victim of branch prediction fail.

What is Branch Prediction?

Consider a railroad junction:

_{Image by Mecanismo, via Wikimedia Commons. Used under the CC-By-SA 3.0 license.}

Now for the sake of argument, suppose this is back in the 1800s - before long-distance or radio communication.

You are a blind operator of a junction and you hear a train coming. You have no idea which way it is supposed to go. You stop the train to ask the driver which direction they want. And then you set the switch appropriately.

Trains are heavy and have a lot of inertia, so they take forever to start up and slow down.

Is there a better way? You guess which direction the train will go!

• If you guessed right, it continues on.


• If you guessed wrong, the driver will stop, back up, and yell at you to flip the switch. Then it can restart down the other path.

If you guess right every time, the train will never have to stop.

If you guess wrong too often, the train will spend a lot of time stopping, backing up, and restarting.

Consider an if-statement: At the processor level, it is a branch instruction:

You are a processor and you see a branch. You have no idea which way it will go. What do you do? You halt execution and wait until the previous instructions are complete. Then you continue down the correct path.

Modern processors are complicated and have long pipelines. This means they take forever to "warm up" and "slow down".

Is there a better way? You guess which direction the branch will go!

• If you guessed right, you continue executing.


• If you guessed wrong, you need to flush the pipeline and roll back to the branch. Then you can restart down the other path.

If you guess right every time, the execution will never have to stop.

If you guess wrong too often, you spend a lot of time stalling, rolling back, and restarting.

This is branch prediction. I admit it's not the best analogy since the train could just signal the direction with a flag. But in computers, the processor doesn't know which direction a branch will go until the last moment.

How would you strategically guess to minimize the number of times that the train must back up and go down the other path? You look at the past history! If the train goes left 99% of the time, then you guess left. If it alternates, then you alternate your guesses. If it goes one way every three times, you guess the same...

In other words, you try to identify a pattern and follow it. This is more or less how branch predictors work.

Most applications have well-behaved branches. Therefore, modern branch predictors will typically achieve >90% hit rates. But when faced with unpredictable branches with no recognizable patterns, branch predictors are virtually useless.

Further reading: "Branch predictor" article on Wikipedia.

As hinted from above, the culprit is this if-statement:

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

Notice that the data is evenly distributed between 0 and 255. When the data is sorted, roughly the first half of the iterations will not enter the if-statement. After that, they will all enter the if-statement.

This is very friendly to the branch predictor since the branch consecutively goes the same direction many times. Even a simple saturating counter will correctly predict the branch except for the few iterations after it switches direction.

Quick visualization:

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)

However, when the data is completely random, the branch predictor is rendered useless, because it can't predict random data. Thus there will probably be around 50% misprediction (no better than random guessing).

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)

What can be done?

If the compiler isn't able to optimize the branch into a conditional move, you can try some hacks if you are willing to sacrifice readability for performance.

Replace:

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

Java - NetBeans 7.1.1 JDK 7 - x64

Наблюдения:

• С веткой: Существует огромная разница между отсортированными и несортированными данными.


• С помощью взлома: нет разницы между отсортированными и несортированными данными.


• В случае с C ++ взлом происходит на самом деле немного медленнее, чем в случае с веткой, когда данные отсортированы.

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

Обновить:

• GCC 4.6.1 с -O3 или -ftree-vectorize на x64 способен генерировать условное перемещение, поэтому нет разницы между отсортированными и несортированными данными - и то, и другое выполняется быстро. Это называется "if-преобразованием" (в безветвление) и необходимо для векторизации, но иногда полезно и для скалярного преобразования.

  
  

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

  
  



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

  
  



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

  
  



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

  
  

• Clang также векторизирует if() версию, как и GCC 5 и более поздние версии с -O3, хотя требуется довольно много инструкций для подписи-расширения до 64-битной суммы на x86 без SSE4 или AVX2. (-march=x86-64-v2 или v3). Смотрите Почему обработка несортированного массива выполняется с той же скоростью, что и обработка отсортированного массива с помощью современного x86-64 clang?

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

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

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

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

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

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

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

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

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

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

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

x86

x64

The result is robust in multiple tests. We get a great speedup when the branch result is unpredictable, but we suffer a little bit when it is predictable. In fact, when using a conditional move, the performance is the same regardless of the data pattern.

Now let's look more closely by investigating the x86 assembly they generate. For simplicity, we use two functions max1 and max2.

max1 uses the conditional branch if... else ...:

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

max2 uses the ternary operator ... ? ... : ...:

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

On an x86-64 machine, GCC -S generates the assembly below.

: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 uses much less code due to the usage of instruction cmovge. But the real gain is that max2 does not involve branch jumps, jmp, which would have a significant performance penalty if the predicted result is not right.

So why does a conditional move perform better?

In a typical x86 processor, the execution of an instruction is divided into several stages. Roughly, we have different hardware to deal with different stages. So we do not have to wait for one instruction to finish to start a new one. This is called pipelining.

In a branch case, the following instruction is determined by the preceding one, so we cannot do pipelining. We have to either wait or predict.

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

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

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

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

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

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

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

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