Branch Prediction: Как ваш процессор уже как 35 лет предсказывает будущее.

🧙🏻‍♂️ Современные процессоры уже давно получили свои экстрасенсорные способности. С помощью Branch Prediction они способны заглядывать в будущее и предугадывать, какой путь выполнится в вашем коде. Это как если бы ваш компьютер знал, что вам нужно сделать следующее, еще до того, как вы это сами осознаете!

Branch Prediction — это технология в процессорах, которая помогает предсказать, какой путь выберет программа, когда встречается условный переход (например, if или switch) и в условиях неопределённости. При выполнении условных инструкций (ветвлений) процессор должен решить, какой из возможных путей будет выбран, чтобы минимизировать задержки и улучшить производительность.

🙉 Почему это важно?
Когда процессор сталкивается с условным переходом, он должен решить, какой путь выполнить. Если процессор не знает, какой путь выбрать, он может просто сидеть и ждать, что замедляет работу. Branch Prediction помогает процессору заранее выбрать путь и продолжить выполнение инструкций, что значительно ускоряет работу.

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

👨🏻‍💻 Факт для IT
90% точность прогнозирования ветвлений выдают современные процессоры.
3 ns нужно процессору для обработки неверного предсказания ветвления и да это аппаратная и программная функция.

🔎 Проверим это всё кодом
Один и тот же метод, который обрабатывает каждый элемент массива одинаково. Возьмём: массив с рандомными числами, тот же но отсортированный массив, массив с только чётными числами и массив с чередующимися числами чёт/нечёт

👨‍💻 Код

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Columns;
using BenchmarkDotNet.Running;

BenchmarkRunner.Run<BranchPrediction>();

[HideColumns(Column.Error, Column.StdDev), MemoryDiagnoser]
public class BranchPrediction
{
    private const int N = 12_09_2024;
    
    private int[] _unorderedArray = new int[N];
    private int[] _ordered = new int[N];
    private int[] _allAreOdd = new int[N];
    private int[] _alternating = new int[N];
 
    [GlobalSetup]
    public void Setup()
    {
        _unorderedArray = Enumerable.Range(0, N).Select(_ => Random.Shared.Next()).ToArray();
        _ordered = _unorderedArray.OrderBy(x => x % 2).ToArray();
        _allAreOdd = Enumerable.Repeat(42, N).ToArray();
        _alternating = Enumerable.Range(0, N).Select(i => i % 2 == 0 ? 42 : 777).ToArray();
    }
 
    [Benchmark]
    public int Ordered() => GetEvensCount(_ordered);

    [Benchmark]
    public int Unordered() => GetEvensCount(_unorderedArray);

    [Benchmark]
    public int AllAreOdd() => GetEvensCount(_allAreOdd);
    
    [Benchmark]
    public int Alternating() => GetEvensCount(_alternating);

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

😮 Benchmark
Остортированный массив становится в 6 раз быстрее чем массив с неотсортированными числами 👨‍💻

| Method      | Mean      |
|------------ |----------:|
| Ordered     |  7.897 ms |
| Unordered   | 47.648 ms |
| AllAreOdd   |  7.985 ms |
| Alternating |  9.585 ms |

🗿 Так что в следующий раз, когда ваш ноут/пк начнёт тупить, не переживайте — он просто пытается угадать, когда вы наконец закончите свою работу и перестанете его нагружать.

#computerscience #dotnet

💡 Channel | ✏ Chat