Это самый популярный вопрос о переполнении стека.

Введение

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

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

int main()
{
    // Generate an array of integers with a size of 32768
    const unsigned arraySize = 32768;
    int data[arraySize];

    // Assign each array item with a random number between 1 and 256
    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = std::rand() % 256;

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

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

Запуск этого кода без сортировки массива занимает около 11,54 секунды. Но если вы отсортируете массив, код запустится за 1,93 секунды. Первичный цикл почти в шесть раз быстрее.

Что ж, я решил попробовать ту же концепцию в Javascript.

Вот версия того же кода на Javascript.

// Generate an array of integers with a size of 32768
const arraySize = 32768;
const data = new Array(arraySize);

// Assign each array item with a random number between 1 and 256
for (let c = 0; c < arraySize; ++c)
  data[c] = Math.floor(Math.random() * 256);

// !!! With this, the next loop runs faster

//data.sort();

// // Duration Test
const start = new Date().getTime()

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

console.log((new Date().getTime() - start) / 1000);
console.log("sum = " + sum);

Несортированный массив занимает около 45,674 секунд, а отсортированный массив занимает около 32,953 секунд. Разница во времени здесь не такая существенная, как в коде на C++, но тем не менее даже в Javascript отсортированный массив работает быстрее, чем несортированный. Какова основная причина этого?

Предиктор ветвления

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

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

Заключение

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