Это 15-я статья в серии, посвящённая оптимизации подсистем памяти. Остальные доступны здесь (англ.).

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

Предсказание ветвлений и подсистема памяти

▍ Краткое введение в предсказание ветвлений и спекулятивное выполнение

Схема предсказания переходов (ветвлений) является частью многих современных процессоров и используется для ускорения вычислений, когда у процессора недостаточно данных для продолжения работы. По сути, согласно ей процессор пытается спрогнозировать результат выполнения условной ветки кода до его фактического вычисления. Это событие мы называем спекуляцией в отношении результата ветвления, и последующие инструкции выполняются спекулятивно, то есть в случае ошибочного прогноза их результаты будут отменены. Разберём пример:

for (size_t i = 0; i < n; i++) {
   if (a[i] >= 0) {
       positive++;
   } else {
       negative++;
   }
}

В этом примере, если операнд a[i] недоступен, результат условной ветки if (a[i] >= 0) можно предугадать. Допустим, процессор спрогнозировал, что результатом её выполнения будет true. В этом случае он начинает выполнять positive++. Позднее значение a[i] становится доступным, и если результат ветвления был спрогнозирован верно, тогда процессор проделал полезную работу, и лишних затрат не возникнет. Тем не менее, если прогноз ветвления окажется ошибочным, процессору придётся отменить спекулятивно выполненные инструкции и начать выполнять ветку else.

В качестве альтернативы такому решению можно подождать, пока операнд a[i] станет доступен, и только затем решать, какие инструкции выполнять – из ветки if или else. Однако в большинстве случаев по очевидным причинам этот подход окажется медленнее.

▍ Предсказание ветвлений в деталях

При успешном прогнозировании ветвления этот процесс обеспечивает общее повышение быстродействия. Поэтому в случае веток, чей результат предугадать легко¹, мы больше ничего не можем предпринять для повышения эффективности ПО или подсистемы памяти. Но что произойдёт, если ветвление спрогнозировано ошибочно?

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

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

▍ Взаимодействие между прогнозированием и подсистемой памяти

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

• Обычно спекуляция оказывается полезна, поскольку позволяет процессору выполнять потенциально полезную работу. Очень часто потребность в прогнозировании возникает из-за того, что операнд не был считан из подсистемы памяти – в этом случае спекуляция оказывается вариантом продвинуться вперёд, минуя узкое место в схеме работы памяти.
• Если ветвление предсказывается ошибочно, за это приходится платить – результаты спекулятивно выполненных инструкций отменяются. Итоговые затраты зависят от используемого процессора, но оказываются не слишком высоки и обычно составляют 10-20 тактов.
• Спекуляция может повысить требуемую пропускную способность памяти, поскольку некоторые запрошенные данные не будут использованы. С положительной стороны это позволяет заранее выполнять некоторые операции загрузки/сохранения, что очень важно для загрузок, имеющих длительную задержку (поступающих из памяти или более масштабных кэшей данных).
• Альтернативой для кода с ветвлениями выступает код без них. В нём вычисляется как тело инструкции if, так и тело инструкции else, а корректный результат выбирается на основе заданного условия. Такой подход исключает возможный штраф за ошибочное предсказание ветвления, но имеет ряд недостатков:
  
  • Вычисление инструкций if и else оказывается более затратным.
  • Процессор лишён возможности предугадывать результаты ветвлений. На практике это означает, что некоторые инструкции будут выполнены позднее, чем в случае с прогнозированием ветвлений.

Теперь становится более очевидно, что вопрос производительности и предсказания ветвлений является непростым, поскольку представляет компромисс между тремя факторами: штрафом за ошибочный прогноз, задержкой загрузки/сохранения и пропускной способностью памяти. Тем не менее на практике производительность ПО при наличии ветвлений выглядит так:

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

Техники

Для ускорения ПО вам потребуется выбрать реализацию алгоритма с ветвлением или без. Тем не менее реализовать код без ветвлений на C/C++ оказывается не так просто.

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

▍ Написание кода без ветвлений с помощью ассемблера или внутренних механизмов компилятора

Единственный 100% способ написать код без ветвлений – это использовать ассемблер или внутренние механизмы компилятора. Подробный разбор написания кода на ассемблере выходит за рамки этой статьи, но в качестве рекомендации приведу две версии двоичного поиска, который мы использовали в ходе тестирования: изначальный код с ветвлением и версия без ветвлений с условными переходами.

На системах x86-64, если ваш код обрабатывает числа с плавающей запятой или двойной точности, вы можете использовать механизмы компилятора, которые типично используете для векторизации. Механизмы обработки чисел с плавающей запятой или чисел двойной точности также существуют для невекторизованного кода, поскольку обработка чисел с плавающей запятой на современных процессорах x86-64 выполняется в векторных регистрах. Вот написанный таким образом пример быстрой сортировки без ветвления, которую мы использовали при тестировании: изначальный код, версия без ветвлений.

▍ Написание кода без ветвлений с помощью арифметического приёма

Для избежания ветвлений можно воспользоваться арифметикой. Возьмём в качестве примера следующий фрагмент кода:

if (a[i] > 0) {
   cnt++;
}

Его переписывание с использованием арифметического приёма опирается на тот факт, что выражение a[i] > 0 имеет значение 1, если оказывается true, и 0, если – false. В итоге всё выражение можно записать так:

cnt += (a[i] > 0);

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

Эксперименты

Здесь мы приведём два эксперимента по анализу взаимодействия подсистемы памяти и модуля прогнозирования ветвлений. Оба эксперимента выполнялись на системе Intel® Core(TM) i5-10210U, каждый по пять раз, на основе чего был выведен средний результат. Стандартное отклонение было небольшим. Исходный код для обоих экспериментов доступен здесь.

▍ Двоичный поиск без ветвлений

В качестве первого эксперимента мы измерим быстродействие трёх версий алгоритма двоичного поиска: простой (с ветвлением), без ветвлений с условными переходами и без ветвлений с использованием арифметики. Вот исходный код этого алгоритма:

int binary_search(int* array, int number_of_elements, int key) {
    int low = 0, high = number_of_elements-1, mid;
    while(low <= high) {
        mid = (low + high)/2;

        if(array[mid] < key)
            low = mid + 1; 
        else if(array[mid] == key)
            return mid;
        else
            high = mid-1;
    }
    return -1;
}

В версии с ветвлением значения для low и high вычисляются спекулятивно, ещё до получения array[mid] из подсистемы памяти. Но эти вычисления оказываются верны лишь в 50% случаев, то есть данный код подвержен ошибочным предсказаниям ветвлений.

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

Просматривая приведённую таблицу, можно отметить, что:

• Версия с условными переходами оказывается быстрее версии с ветвлением, пока размер массива не достигает 256К элементов. При размере массива в 1М элементов версия с ветвлениями работает ощутимо быстрее.
• Версия с условными переходами выполняет примерно вдвое больше инструкций, чем версия с ветвлением.
• Версия с использованием арифметики выполняет примерно в 2,5 раза больше инструкций, чем версия с ветвлением.
• Версия с ветвлением загружает больше данных из памяти, чем две другие версии. При максимальном размере массива она передаёт в 2,5 раза больше данных, чем другие версии.

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

▍ Алгоритмы быстрой и пирамидальной сортировки без ветвлений

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

static int partition(std::vector<float>& vector, int low, int high) {
    float pivot = vector[high];

    int i = (low - 1);

    for (int j = low; j < high; j++) {
        if (vector[j] <= pivot) {
            i++;
            std::swap(vector[i], vector[j]);
        }
    }
    i = i + 1;
    std::swap(vector[i], vector[high]);
    return i;
}

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

Тот же алгоритм мы реализовали с использованием внутренних механизмов компилятора, чтобы исключить из него ветвления. Ниже приведена таблица времени выполнения быстрой сортировки для массива из 32 М чисел с плавающей запятой:Исключение ветвлений ускорило выполнение алгоритма, хотя в итоге выполнялось почти вдвое больше инструкций. Алгоритм обращается к данным последовательно. Это означает, что устройство предвыборки может быстро доставлять данные в процессор.

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

Сопоставим полученные результаты с реализацией пирамидальной сортировки. Этот вид сортировки выстраивает внутри массива кучу. Её алгоритм выглядит так:

static void heapify(std::vector<float>& vec, int n, int i) {
    int largest = i;

    int start = 2 * i + 1;
    int end = std::min(start + 2, n);

    for (int j = start; j < end; j++) {
        if (vec[j] > vec[largest]) {
            largest = j;
        }
    }

    if (largest != i) {
        std::swap(vec[i], vec[largest]);

        heapify_k(vec, n, largest);
    }
}

Цикл на строках 7-11 короткий и выполняет не более двух итераций. Затем функция heapify вызывает сама себя. Этот алгоритм создаёт кучу, выстраивая внутри массива дерево. Если текущий узел дерева является i, левый его потомок находится в позиции 2 * i + 1, а правый – в позиции 2 * i + 2. Выполнение поиска по подобному дереву с аппаратной точки зрения приводит к большому числу случайных доступов к памяти.

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

1. Многие ветвления предугадать легко, поскольку они в основном сводятся к true, false или какому-то предсказуемому паттерну. ↪
2. Это измерение уже проводилось в статье «Why is quicksort faster than heapsort? And how to make them faster?» ↪

Помоги спутнику бороться с космическим мусором в нашей новой игре! ????