- PVSM.RU - https://www.pvsm.ru -
В ней мы изучим взаимодействие механизма предсказания ветвлений с подсистемой памяти. В повествовании мы будем исходить из предположения, что вам знаком принцип предсказания ветвлений и работы подсистем памяти в современных процессорах.
Схема предсказания переходов (ветвлений) является частью многих современных процессоров и используется для ускорения вычислений, когда у процессора недостаточно данных для продолжения работы. По сути, согласно ей процессор пытается спрогнозировать результат выполнения условной ветки кода до его фактического вычисления. Это событие мы называем спекуляцией в отношении результата ветвления, и последующие инструкции выполняются спекулятивно, то есть в случае ошибочного прогноза их результаты будут отменены. Разберём пример:
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
. Однако в большинстве случаев по очевидным причинам этот подход окажется медленнее.
1 [2], мы больше ничего не можем предпринять для повышения эффективности ПО или подсистемы памяти. Но что произойдёт, если ветвление спрогнозировано ошибочно?
В случае ошибочного прогноза спекулятивно выполненные инструкции оказываются ненужными, и их результаты приходится отбросить. При этом стоит выделить инструкции load
и store
, которые даже при спекулятивном выполнении затрачивают ресурсы подсистемы памяти. Получается, что в результате ошибочного предсказания эти ресурсы тратятся впустую.
Если нашей целью является уменьшение нагрузки на память, тогда решением этой проблемы станет написание кода без ветвлений. Тем не менее нашей первостепенной задачей является создание более быстрого ПО, а не такого, которое будет экономить память. При этом для его ускорения нам нужно понимать принципы взаимодействия модуля предсказания ветвлений и подсистемы памяти.
При анализе производительности прогнозирования ветвлений нужно учитывать три аспекта:
if
, так и тело инструкции else
, а корректный результат выбирается на основе заданного условия. Такой подход исключает возможный штраф за ошибочное предсказание ветвления, но имеет ряд недостатков:
if
и else
оказывается более затратным.Теперь становится более очевидно, что вопрос производительности и предсказания ветвлений является непростым, поскольку представляет компромисс между тремя факторами: штрафом за ошибочный прогноз, задержкой загрузки/сохранения и пропускной способностью памяти. Тем не менее на практике производительность ПО при наличии ветвлений выглядит так:
Для ускорения ПО вам потребуется выбрать реализацию алгоритма с ветвлением или без. Тем не менее реализовать код без ветвлений на C/C++ оказывается не так просто.
Когда дело доходит до ветвлений компилятор может свободно генерировать или не генерировать их в соответствии с внутренней эвристикой. На практике чаще всего он будет генерировать код с ветвлениями, но вам потребуется проверять это в его отчёте о сборке, чтобы знать наверняка. С учётом этого реализация версии без ветвлений может оказаться проблематичной. В текущем разделе мы представим две техники написания алгоритмов без ветвлений.
Единственный 100% способ написать код без ветвлений – это использовать ассемблер или внутренние механизмы компилятора. Подробный разбор написания кода на ассемблере выходит за рамки этой статьи, но в качестве рекомендации приведу две версии двоичного поиска, который мы использовали в ходе тестирования: изначальный код с ветвлением [3] и версия без ветвлений с условными переходами [4].
На системах x86-64, если ваш код обрабатывает числа с плавающей запятой или двойной точности, вы можете использовать механизмы компилятора, которые типично используете для векторизации. Механизмы обработки чисел с плавающей запятой или чисел двойной точности также существуют для невекторизованного кода, поскольку обработка чисел с плавающей запятой на современных процессорах x86-64 выполняется в векторных регистрах. Вот написанный таким образом пример быстрой сортировки без ветвления, которую мы использовали при тестировании: изначальный код [5], версия без ветвлений [6].
Для избежания ветвлений можно воспользоваться арифметикой. Возьмём в качестве примера следующий фрагмент кода:
if (a[i] > 0) {
cnt++;
}
Его переписывание с использованием арифметического приёма опирается на тот факт, что выражение a[i] > 0
имеет значение 1
, если оказывается true
, и 0
, если – false
. В итоге всё выражение можно записать так:
cnt += (a[i] > 0);
В качестве более сложного примера реализации двоичного поиска без ветвлений с использованием арифметики можете рассмотреть такое решение: изначальный код [3], версия без ветвлений [7].
Здесь мы приведём два эксперимента по анализу взаимодействия подсистемы памяти и модуля прогнозирования ветвлений. Оба эксперимента выполнялись на системе Intel® Core(TM) i5-10210U, каждый по пять раз, на основе чего был выведен средний результат. Стандартное отклонение было небольшим. Исходный код для обоих экспериментов доступен здесь [8].
В качестве первого эксперимента мы измерим быстродействие трёх версий алгоритма двоичного поиска: простой (с ветвлением), без ветвлений с условными переходами и без ветвлений с использованием арифметики. Вот исходный код этого алгоритма:
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М поисков.
Размер массива (в элементах) | Исходная версия | Версия с условными переходами | Версия с арифметическим приёмом |
4 К | Время выполнения: 0,22 с Инструкций: 434 M CPI: 1,96 Получение данных из памяти: 0,45 ГБ |
Время выполнения: 0.14 с Инструкций: 785 M CPI: 0.728 Получение данных из памяти: 0,25 ГБ |
Время выполнения: 0,19 с Инструкций: 1,102 M CPI: 0,69 Получение данных из памяти: 0,32 ГБ |
16 К | Время выполнения: 0,26 с Инструкций: 511 M CPI: 2,01 Получение данных из памяти: 0,49 ГБ |
Время выполнения: 0,19 с Инструкций: 928 M CPI: 0,77 Получение данных из памяти: 0,39 ГБ |
Время выполнения: 0,24 с Инструкций: 1,308 M CPI: 0.72 Получение данных из памяти: 0,46 ГБ |
64 К | Время выполнения: 0,32 с Инструкций: 584 M CPI: 2,143 Получение данных из памяти: 0,48 ГБ |
Время выполнения: 0,24 с Инструкций: 1,064 M CPI: 0,90 Получение данных из памяти: 0,25 ГБ |
Время выполнения: 0,31 с Инструкций: 1,504 CPI: 0,82 Получение данных из памяти: 0,26 ГБ |
256 К | Время выполнения: 0,43 с Инструкций: 646 M CPI: 2,59 Получение данных из памяти: 0,36 ГБ |
Время выполнения: 0,39 с Инструкций: 1,199 M CPI: 1,28 Получение данных из памяти: 0,32 ГБ |
Время выполнения: 0,47 с Инструкций: 1,698 M CPI: 1,09 Получение данных из памяти: 0,36 ГБ |
1 М | Время выполнения: 0,56 с Инструкций: 727 M CPI: 3,05 Получение данных из памяти: 0,67 ГБ |
Время выполнения: 0,59 с Инструкций: 1,333 M CPI: 1,72 Получение данных из памяти: 0,59 ГБ |
Время выполнения: 0,70 с Инструкций: 1,891 M CPI: 1,42 Получение данных из памяти: 0,68 ГБ |
4 М | Время выполнения: 1,127 с Инструкций: 798 M CPI: 4,65 Получение данных из памяти: 9,94 ГБ |
Время выполнения: 1,48 с Инструкций: 1,467 M CPI: 3,1 Получение данных из памяти: 3,75 ГБ |
Время выполнения: 1,59 с Инструкций: 2,084 M CPI: 2,45 Получение данных из памяти: 3,9 ГБ |
16 М | Время выполнения: 1,65 с Инструкций: 870 M CPI: 6,26 Получение данных из памяти: 18,48 ГБ |
Время выполнения: 2,75 с Инструкций: 1,601 CPI: 4,16 Получение данных из памяти: 6,95 ГБ |
Время выполнения: 2,90 с Инструкций: 2,277 M CPI: 3,18 Получение данных из памяти: 7,05 ГБ |
Просматривая приведённую таблицу, можно отметить, что:
За ошибочный прогноз ветвлений приходится платить, но платить приходится и в случае задержки выполнения загрузки. При небольших размерах массива версия без ветвлений работает быстрее в то время, как при значительном его размере быстрее оказывается версия с ветвлением.
В качестве второго эксперимента мы проанализируем алгоритм быстрой сортировки2 [9]. Его ключевым механизмом является разделение данных относительно выбранной точки. В качестве такой точки разделения мы будем случайным образом выбирать элемент из массива. После этого данные массива будут делиться на две половины: левую, где все элементы меньше точки разделения, и правую со всеми остальными элементами. В целом этот алгоритм выглядит так:
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 М чисел с плавающей запятой:
Метрика | Быстрая сортировка с ветвлением | Быстрая сортировка без ветвлений |
Время выполнения | 2,94 с | 1,69 с |
Инструкций | 8,81 миллиарда | 14,7 миллиарда |
Тактов | 11,4 миллиарда | 6,5 миллиарда |
CPI | 1,3 | 0,44 |
Получение данных из памяти | 5,23 ГБ | 4,21 ГБ |
Исключение ветвлений ускорило выполнение алгоритма, хотя в итоге выполнялось почти вдвое больше инструкций. Алгоритм обращается к данным последовательно. Это означает, что устройство предвыборки может быстро доставлять данные в процессор.
В этом случае штраф за ошибочное прогнозирование высок по сравнению с задержкой операций загрузки, поэтому версия без ветвлений оказывается быстрее. В этой версии также получается меньше данных из подсистемы памяти.
Сопоставим полученные результаты с реализацией пирамидальной сортировки. Этот вид сортировки выстраивает внутри массива кучу. Её алгоритм выглядит так:
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 М чисел с плавающей запятой:
Метрика | Пирамидальная сортировка с ветвлением | Пирамидальная сортировка без ветвлений |
Время выполнения | 12,6 с | 29,1 с |
Инструкций | 8,94 миллиарда | 35,5 миллиарда |
Тактов | 41,6 миллиарда | 73,5 миллиарда |
CPI | 1,06 | 2,07 |
Получение данных из памяти | 69,3 ГБ | 79,3 ГБ |
Полученные результаты полностью противоположны результатам алгоритма быстрой сортировки. Здесь версия с ветвлением оказалась вдвое быстрее версии без него. По своей природе пирамидальная сортировка выполняет много произвольных обращений к памяти, которые при столь большом массиве обслуживаются именно из основной памяти, а не из кэша. В итоге эти обращения имеют высокую задержку и в идеале должны выполняться как можно раньше.
↪ [10]
Why is quicksort faster than heapsort? And how to make them faster? [11]» ↪ [12]
Помоги спутнику бороться с космическим мусором в нашей новой игре! 🛸 [13]
Автор: Дмитрий Брайт
Источник [14]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/algoritmy/389330
Ссылки в тексте:
[1] здесь: https://johnnysswlab.com/category/performance/low-level-performance/memory-performance/
[2] 1: #anchorid1
[3] изначальный код с ветвлением: https://github.com/ibogosavljevic/johnysswlab/blob/master/2023-12-branches-memory/binary_search.cpp#L26
[4] версия без ветвлений с условными переходами: https://github.com/ibogosavljevic/johnysswlab/blob/master/2023-12-branches-memory/binary_search.cpp#L35
[5] изначальный код: https://github.com/ibogosavljevic/johnysswlab/blob/master/2022-01-sort/quicksort.h#L22
[6] версия без ветвлений: https://github.com/ibogosavljevic/johnysswlab/blob/master/2022-01-sort/quicksort.h#L43
[7] версия без ветвлений: https://github.com/ibogosavljevic/johnysswlab/blob/master/2023-12-branches-memory/binary_search.cpp#L53
[8] здесь: https://github.com/ibogosavljevic/johnysswlab/tree/master/2023-12-branches-memory
[9] 2: #anchorid2
[10] ↪: #anchorid3
[11] Why is quicksort faster than heapsort? And how to make them faster?: https://johnnysswlab.com/why-is-quicksort-faster-than-heapsort-and-how-to-make-them-faster/
[12] ↪: #anchorid4
[13] Помоги спутнику бороться с космическим мусором в нашей новой игре! 🛸: https://t.me/ruvds_community/641
[14] Источник: https://habr.com/ru/companies/ruvds/articles/784596/?utm_source=habrahabr&utm_medium=rss&utm_campaign=784596
Нажмите здесь для печати.