java - Почему быстрее обрабатывать отсортированный массив, чем несортированный массив?




10 Answers

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

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

java c++ performance optimization branch-prediction

Вот фрагмент кода на 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);
    }
}

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

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

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



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

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

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




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

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

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

  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();



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

Но в этом случае мы знаем, что значения находятся в диапазоне [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«LookUp Table» в коде). Вот код 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, что может быть практичным.

EDIT: Одна вещь, которую я забыл положить.

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

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

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

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

Вот ссылка на этот код: Red Black Trees , Eternally Confuzzled




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

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

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

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

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

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

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

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

Без предсказания ветвления, следующее:

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

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

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

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

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

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

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

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

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

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

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

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

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

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




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

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

или аналогичным образом:

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

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

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




Это уж точно!...

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

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

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

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

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

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

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

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

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




Усиление прогноза прибыли!

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

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

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

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

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

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

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

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

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



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

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

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

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

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

Там действительно три разных типа ветвей:

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

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

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

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

Рекомендации:




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

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

 // sort backwards (higher values first)
 std::sort(data, data + arraySize, std::greater<int>());

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



Related


Tags

java   c++   performance   optimization   branch-prediction