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

Введение

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

Пример кода

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

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

int main()
{
    // Генерация данных
    const unsigned arraySize = 32768;
    int data[arraySize];

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

    // Сортируем массив для повышения производительности
    std::sort(data, data + arraySize);

    // Тест производительности
    clock_t start = clock();
    long long sum = 0;
    for (unsigned i = 0; i < 100000; ++i)
    {
        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 << '\n';
    std::cout << "sum = " << sum << '\n';
}

Временные результаты

• Без сортировки: ~11.54 секунд.
• С сортировкой: ~1.93 секунд.

Почему сортировка улучшает производительность?

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

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

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

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

Пример с разными массивами

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

Вот графическая иллюстрация:

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

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

Избегание зависимостей от ветвлений

Один из способов минимизировать влияние ветвлений — это сделать код «безветвленным». Например, вместо использования конструкции if можно использовать побитовые операции:

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

Это удаляет ветвление, поскольку условие превращается в умножение на 0 или 1, в зависимости от истинности условия.

Использование таблиц поиска

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

int lookup[256] = {0};
for (int i = 128; i < 256; ++i) {
    lookup[i] = i;
}

sum += lookup[data[c]];

Заключение

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

Источник