Сказка про Branch prediction

Конвейер трудится изо всех сил, чтобы повысить производительность твоей программы. А злобные «if»'ы нагло врываются посреди его работы и всё портят!

Насколько полезен конвейер в современных ЭВМ? Как сильно мешаются ветвления в коде, которые ты написал? И как архитекторы процессоров сглаживают ущерб, который «if»'ы наносят по производительности программ?

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

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

Про предсказание переходов, или branch prediction, написано очень много статей. А ещё, написано и всё ещё продолжают писать очень много научных работ. А архитекторы процессоров до сих пор умудряются его улучшать на практике. Поэтому, перед тем как продемонстрировать что-то своё и весёлое, я просто обязан отправить вас прочитать какую-нибудь готовую и хорошую статью, подробно рассказывающую, как работают предсказатели переходов. Я счел вот эту достаточно старую статью на Хабре простой и понятной для любого программирующего человека, достаточно качественной и полной, чтобы хорошенько погрузиться в эту тему, красивой и весёлой, с хорошими картинками. Это не полная суровая научная статья. Это так, чтобы ознакомиться «на пальцах».

А в этой статье давайте просто убедимся, что конвейер и предсказатель переходов существуют, и что они реально полезны. А ещё, внезапно, рассмотрим, как можно извлекать практическую пользу из branch prediction'а!

А теперь давайте сделаем что-нибудь весёлое

В коде, который мы пишем, обязательно присутствуют условия. Самый популярный вид этой операции в большинстве ЯП, наверное, такой: if ... else ....

А в ЭВМ, на которых исполняются наши программы, есть конвейер. Дак вот, конвейер и if друг с другом не дружат. If частенько вставляет палки в колёса конвейеру. И архитекторы ЭВМ изощрятся очень интересными способами, чтобы как можно сильнее подружить if'ы с конвейером.

Вы думаете, что это шутки? Что в вашем прикладном коде это «всё равно не заметно»? Что настолько низкоуровневый механизм, как предсказатель переходов, невозможно отследить в прикладных приложениях? Или что это какая-то очередная малополезная фигня на эпсилон производительности программ? Ха. Сейчас я вам покажу всю мощь конвейера!

Пусть у нас есть массив случайных чисел. И мы хотим посчитать, сколько в нём чётных. Код, который это делает, можно написать так:

public static int GetEvensCount(int[] arr)
{
    var evens = 0;
    for (var i = 0; i < arr.Length; i++)
        if (arr[i] % 2 == 0)
            evens++;
 
    return evens;
}

А что, если предварительно просто отсортировать тот же массив чисел по критерию чётности, и выполнить точно такой же код? Да, в рамках задачи «посчитать число четных чисел» достаточно глупо сортировать массив по критерию четности. Но мы не решаем эту задачу, мы пытаемся нащупать предсказатель переходов!

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

private int[] orderedArray = new int[N];
private int[] unorderedArray = new int[N];
private const int N = 100_000;
 
[GlobalSetup]
public void Setup()
{
    var random = new Random();
    for (var i = 0; i < N; i++)
    {
        unorderedArray[i] = random.Next();
    }
 
    orderedArray = unorderedArray.OrderBy(x => x % 2).ToArray();
}
 
[Benchmark]
public int Ordered()
{
    return GetEvensCount(orderedArray);
}
 
[Benchmark]
public int Unordered()
{
    return GetEvensCount(unorderedArray);
}
 
public static int GetEvensCount(int[] arr)
{
    var evens = 0;
    for (var i = 0; i < arr.Length; i++)
        if (arr[i] % 2 == 0)
            evens++;
 
    return evens;
}

И вот такой результат:

|        Method |      Mean |
|-------------- |----------:|
|       Ordered |  56.08 us |
|     Unordered | 403.58 us |

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

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

Проморгали? Давайте разбираться.

Как выглядит цепочка «прохождения или непрохождения» if'а в случае отсортированного массива? Как-то так (T — true, F — false):

TTTTTTT....TTTFFF...FFFFFFF

А как она выглядит в случае неотсортированного массива? Совершенно случайно. Ну, например так:

TFFTFTTFTTFFT...TFFTFTFTFTT

В первом случае, в случае отсортированного массива, уже на второй-третьей итерации цикла предсказатель переходов делает предположение, что всегда будет побеждать ветка, которая следует за результатом True, то есть конвейер готовится выполнять код под if'ом и всё, что пойдёт дальше. Потом пару раз ошибётся, когда начнутся F (False), снова переобучится, и теперь всегда будет готовить конвейер для ветки False, то есть сразу под следующую итерацию цикла.

Во втором случае у него нет никаких шансов что-то предсказать. Наверное, примерно с вероятностью 50% он будет выбирать «неправильную» ветку для конвейера. А спотыкаясь об неправильный выбор процессору придётся сбрасывать состояние конвейера, начинать накапливать его сначала, теряя десятки тактов за каждый такой раз!

И, как мы уже отметили ранее, отношение скорости этих методов чуть менее, чем на порядок. И это притом, что помимо if'а в коде есть ещё переходы в цикле, сложения и обращения к памяти.

Кстати, вы можете самостоятельно поиграться с разными комбинациями и посмотреть, насколько мощен предсказатель переходов:

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

• Поискать не чётные, а нечётные числа. Или инвертировать if. Или попробовать if с else веткой.

• Посмотреть, как будет отличаться результат в зависимости от размера массива чисел и его попаданиянепопадания в L1L2 кеш.

• Проверить соотношение производительности алгоритма на отсортированном и не отсортированном массиве по остатку от деления на других числах. Например, если хочется поискать все числа, дающие остаток 3 при делении на 5.

Думаю, что существует ещё куча всяких интересных паттернов, на которые интересно испытать предсказатель переходов в вашем процессоре. Ведь от его архитектуры и реализации branch prediction'а в нём многое зависит. Быть может ваш процессор лучше справится с какими-то случаями, чем мой или вашего соседа.

Про извлечение практической пользы

Логично задаться вопросом, а можно ли извлекать практическую пользу из знания о существовании предсказателя переходов и его проблем с ветвлениями в коде? О да, и ещё как!

Арифметика

Например, как на счёт того, чтобы не писать if'ы там, где мы можем так сделать? Чаще всего такое возможно где-то вокруг арифметики и работы с числами. Например, наш с вами код про четные числа можно переписать таким образом (сначала предыдущая реализация, чтобы была перед глазами, затем новая):

//Первая реализация с if
public static int GetEvensCount(int[] arr)
{
    var evens = 0;
    for (var i = 0; i < arr.Length; i++)
        if (arr[i] % 2 == 0)
            evens++;
 
    return evens;
}
 
//Новая реализация без if
public static int GetEvensCountNoIf(int[] arr)
{
    var evens = 0;
    for (var i = 0; i < arr.Length; i++)
        evens += 1 ^ (arr[i] % 2);
 
    return evens;
}

Давайте запустим бенчмарк и сравним новую и старую версию кода на отсортированном и не отсортированном массиве:

|        Method |      Mean |
|-------------- |----------:|
|       Ordered |  56.08 us |
|     Unordered | 403.58 us |
|   OrderedNoIf |  86.82 us |
| UnorderedNoIf |  86.85 us |

Отлично видно, что версия кода без if'ов работает одинаково и на отсортированном, и на не отсортированном массиве. В случае, когда мы не контролируем источник данных, когда элементы в массиве не отсортированы, версия кода без if'ов почти в 5 раз быстрее! И это не потому, что сам if медленный, а XOR быстрый. Как видно на отсортированных массивах, реализация без if всё-таки чуть-чуть медленнее, чем с if'ами. Это ещё одно подтверждение, на сколько необходим и как крут branch prediction!

Не арифметика

Хотите чего-то более «натурального», чем магия с арифметикой? Сортировать пузырьком умеете? Спорим, что мой пузырёк быстрее? (признаюсь, я подсмотрел этот пример в интернете):

[Benchmark]
public void Sort1()
{
    for (var i = 0; i < N; i++)
    for (var j = 0; j < N - (i + 1); j++)
        if (array[j] > array[j + 1])
            Swap(j, j + 1);
}
 
[Benchmark]
public void Sort2()
{
    for (var i = 0; i < N - 1; i++)
    for (var j = i; j >= 0; j--)
        if (array[j] > array[j + 1])
            Swap(j, j + 1);
}
 
public void Swap(int x, int y)
{
    var z = array[x];
    array[x] = array[y];
    array[y] = z;
}

В чём разница? Да так, ничего особенного (N = 100_000):

| Method |     Mean |
|------- |---------:|
|  Sort1 | 14.545 s |
|  Sort2 |  5.846 s |

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

Здесь тоже постарался branch prediction.

В первом случае, особенно на первых итерациях по внешнему циклу, элементы «всплывают» преимущественно через «неотсортированную» часть массива, а значит выполнится ветка if или нет — достаточно случайное явление, не поддающееся предсказанию.

Во втором случае элементы «тонут» к началу массива, где он уже отсортирован. А значит, сначала постоянно выполняется условие «true», пока элемент не встанет на «своё место», а потом постоянно случается условие «false», ведь массив уже отсортирован на этом участке. А последовательность TTT…TTTFFF…FFF очень даже хорошо предсказывается.

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

Пусть будет такой плохой код, зато всё понятно:

public void Sort1CountTransitions()
{
    var prev = false;
    long transitions = 0;
 
    for (var i = 0; i < N; i++)
    for (var j = 0; j < N - (i + 1); j++)
        if (array[j] > array[j + 1])
        {
            Swap(j, j + 1);
            if (prev == false)
            {
                prev = true;
                transitions++;
            }
        }
        else
        {
            if (prev == true)
            {
                prev = false;
                transitions++;
            }
        }
 
    Console.WriteLine(transitions);
}
 
public void Sort2CountTransitions()
{
    var prev = false;
    long transitions = 0;
 
    for (var i = 0; i < N - 1; i++)
    for (var j = i; j >= 0; j--)
        if (array[j] > array[j + 1])
        {
            Swap(j, j + 1);
            if (prev == false)
            {
                prev = true;
                transitions++;
            }
        }
        else
        {
            if (prev == true)
            {
                prev = false;
                transitions++;
            }
        }
 
    Console.WriteLine(transitions);
}

Я вызвал два этих метода на одинаковом случайном массиве размера 100_000 и получил такие числа: 1659142346 и 199942. То есть 1.6 миллиарда шансов ошибиться предсказателю переходов в первом случае против 199 тысяч во втором случае. Оттуда и разница в три раза в эффективности второго пузырька относительно первого.

Вместо выводов

• Не используйте if'ы! (шутка)

• Не сортируйте пузырьком!

• Уважайте конвейер и его труды!

• Branch prediction работает вне зависимости от вашего языка программирования. Хоть на ассемблере пишите, работать будет одинаково!

• Знайте, как работают ЭВМ и извлекайте из этих знаний пользу. Ну или хотя бы удовольствие!

• Обязательно прочитайте нормальную статью про предсказатель переходов. Например, я рекомендовал в самом начале вот эту.

P.S.

А в видеокартах проблема branch prediction'а стоит ещё острее. Их скалярность и требовательность к производительности накладывают куда более жёсткие требования к линейности и предсказуемости. На видеокартах даже специально ради этого присутствует куча встроенных инструкций типа min, max, и арифметической магии, которые минимизируют число if'ов. Ведь на видеокарте проще сделать кучу лишней арифметики, чем сделать один if и сбросить конвейер.