Reciprocal throughput30.05.2023 10:31

В предыдущих сериях

Современные процессоры очень круты. Они таят в себе великое множество секретов и невероятных возможностей. И просто восхитительно, что некоторые из способностей процессоров легко продемонстрировать даже из такого высокоуровневого языка, как C#, буквально за десять строчек кода!

Художественное отступление, шутка на текущую тему. Для того, чтобы узнать самое интересное, читать текст под катом совершенно не обязательно.

Представьте себе ресторан. А в нём цех по готовке пиццы. Только рабочие в нём тупенькие-тупенькие.

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

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

Ого, дак теперь можно печь одновременно много пицц! Пока первый рабочий разбирает корявый почерк официанта на бумажке со следующим заказом, второй уже раскатал тесто для предыдущей пиццы. А как только третий полил соусом предыдущий круг теста, ему уже подсунули следующий. И так далее. Круто!

Вот только это всё работает до тех пор, пока пиццы в заказах независимые друг от друга. Ведь оказывается, что вся работа конвейера зависит от кривых рук официанта! Представьте себе, что официант накалякал на бумажке «Приготовить пиццу A. Когда пицца А будет готова, начать готовить пиццу Б». Получается, что конвейер оказался заблокирован на результате выполнения всего конвейера для предыдущей пиццы! Пока пицца А не доготовится, пиццу Б даже не начнут раскатывать. Конвейер будет простаивать, а рабочие расслабятся и ничего не будут делать какое-то время.

Вот такой вот печальный официант-driven pizza development.


Как всегда, удобно погружаться в курс дела, начиная с какого-нибудь очень простого и жизненного примера. Пусть у нас есть список чеков. И мы хотим дать пользователю сервис «покажи, сколько мы заработали за сегодня». То есть надо просто просуммировать все числа из чеков. Ну и, пусть чеков будет много. Десятки тысяч. Гипермаркет у нас, Metro какой-нибудь. Иначе неинтересно.

Вот у нас есть набор того, сколько нам заплатили. Просто чиселки в массиве: 

private long[] array = new long[16_000];

Большинство, наверное, сходу напишет такой код подсчета суммы: 

public long EnumerableSum()
{
    return array.Sum();
}

И большинство будут правы, если мы не гонимся за эффективностью. Но для того, чтобы понять то, чему посвящена статья, давайте всё-таки попробуем написать этот код эффективнее. Мы намеренно будем оптимизировать этот алгоритм шаг за шагом, чтобы была понятна логика этих действий. Чтобы в самом конце прийти к тому, ради чего эта статья затевалась, без каких либо дополнительных вопросов.

Погнали оптимизировать 

Говорим НЕТ LINQ

Все слышали, что LINQ очень далёк от «производительности». Поэтому давайте напишем код вот так: 

public long SumNaive()
{
    long result = 0;
    var bound = array.Length;
    for (int i = 0; i < bound; i++)
    {
        result += array[i];
    }
 
    return result;
}

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

|                  Method |        Mean | Allocated |
|------------------------ |------------:|----------:|
|           EnumerableSum |   69.810 us |      32 B |
|                SumNaive |    9.387 us |         - |

Всё верно, LINQ медленный, ещё и объектами в хипе намусорил. В печь его, на дрова для пицц.

Говорим НЕТ safety checks

Давайте подумаем, что в реализации метода SumNaive может мешать нам посчитать сумму очень быстро? Если заглянуть в asm-код, то легко заметить, что из-за того, что это массив, мы на каждое обращение к каждому элементу массива по индексу проверяем, а не вышли ли мы за границы массива.

; Сначала всякая подготовительная работа, которая выполняется один раз
; А внимания достоен только наш основной цикл
M00_L00:
       mov       r9,rdx            ; берем указатель на массив, за ним идёт его длина
       cmp       r8d,[r9+8]        ; проверка i на границу массива
       jae       short M00_L02     ; идём кидать исключение, если вышли за границы
       movsxd    r10,r8d
       add       rax,[r9+r10*8+10] ; само сложение чисел в RAX, где будет результат
       inc       r8d               ; i++
       cmp       r8d,ecx           ; сравнение с границей массива
       jl        short M00_L00     ; возвращаемся в начала цикла, если i < length
 
M00_L02:
       call      CORINFO_HELP_RNGCHKFAIL ; кидаем исключение, вышли за границы массива
       int       3

Если писать код на unsafe, то этой валидации не будет.

public unsafe long SumNaiveUnsafe()
{
    long result = 0;
    var length = array.Length;
    fixed (long* ptr = array)        //Взяли указатель на начало массива
    {
        var pointer = ptr;            // Менять fixed переменную нельзя, поэтому копия
        var bound = pointer + length; // Вычислили правую границу
        while (pointer != bound)      // Пока не достигли правой границы
        {
            result += *pointer;       // Складываем со значением по адресу pointer
            pointer += 1;             // Сдвигаем указатель на 1 * sizeof(long)
        }
    }
 
    return result;
}

Такой C# код будет компилироваться вот в это: 

; Сначала всякая подготовительная работа, которая выполняется один раз
; А внимания достоен только наш основной цикл
M00_L03:
       add rax,[rdx]     ; Складываем в RAX значение из массива по адресу RDX
       add rdx,8         ; К смещению в массиве прибавляем 8 (sizeof(long))
       cmp rdx,rcx       ; В RCX лежит длина массива, проверяем границы
       jne short M00_L03 ; Продолжаем цикл, если не дошли до конца

Такой ASM код нам уже нравится. Он не делает абсолютно ничего лишнего. Забенчмаркаем и увидим, что это существенно помогло: 

|                  Method |        Mean | Allocated |
|------------------------ |------------:|----------:|
|           EnumerableSum |   69.810 us |      32 B |
|                SumNaive |    9.387 us |         - |
|          SumNaiveUnsafe |    5.761 us |         - |

Отлично. Дальше код будет только unsafe. Но самое главное — в таком ASM коде не осталось никакого мусора. На самом деле, цель была именно в этом :). Нам это будет необходимо для демонстрации того, ради чего это всё затевалось.

Говорим ДА некоторым хитростям

А теперь давайте добавим немного безумия. Как вам вот такая реализация? 

public unsafe long SumTrickyUnsafe()
{
    long x = 0;
 
    var length = array.Length;
    fixed (long* ptr = array)
    {
        var pointer = ptr;
        var bound = pointer + length;
        while (pointer != bound)
        {
            x += *pointer;
            x += *(pointer + 1);
            x += *(pointer + 2);
            x += *(pointer + 3);
            pointer += 4;
        }
    }
 
    return x;
}

Легко заметить, что алгоритм неверный. Да, если длина массива не делится на 4, мы посчитаем сумму чисел неверно (или, возможно, словим AccessViolation). И мы должны обработать хвостик в конце обычным способом. Давайте пока пренебрежем этим, ведь массивы огромные, и будем пользоваться массивами с длиной, делящейся на 4. Очевидно, что обработать хвостик, если длина не делится на 4, стоит эпсилон времени. А вот код из-за этого станет менее читабельный.

Также дотошный читатель может заметить, что в этом варианте сложений столько же, сколько и в предыдущем. Зачем тогда так извращаться? А давайте всё равно забенчмаркаем: 

|                  Method |      Mean | Allocated |
|------------------------ |----------:|----------:|
|           EnumerableSum | 69.810 us |      32 B |
|                SumNaive |  9.387 us |         - |
|          SumNaiveUnsafe |  5.761 us |         - |
|         SumTrickyUnsafe |  4.423 us |         - |

Ой! Неожиданно? Этот код на ~30% быстрее. В чем подвох? Давайте для начала посмотрим на ASM код: 

; Сначала всякая подготовительная работа, которая выполняется один раз
; А внимания достоен только наш основной цикл
M00_L03:
       add       rax,[rdx]    
       add       rax,[rdx+8]
       add       rax,[rdx+10]
       add       rax,[rdx+18]  ; Собственно сами 4 сложения
 
       add       rdx,20        ; К смещению в массиве прибавляем 20 (т.е. 32, хекс же)
                               ; 32 = 4 *(sizeof(long))
       cmp       rdx,rcx       ; В RCX лежит длина массива, проверяем границы
       jne       short M00_L03 ; Продолжаем цикл, если не дошли до конца

Заметим, что этот код очень похож на то, что мы видели в предыдущий раз. Вот прям в точности такой же, только сложений не 1 на итерацию цикла, а сразу 4. Можно было бы подумать «ну конечно, всяких лишних CMP и JNE стало меньше, вот и быстрее!». И в целом это правда. Но есть тут кое что более интересное, осталось совсем чуть-чуть.

Кстати, почему бы компилятору тогда самому не написать очень-очень много строчек ADD?

Действительно, обошлись бы вообще без всяких сравнений и прыжков по меткам.

Так делать в общем случае нельзя. Всё потому, что размер кода на самом деле очень важен. Чем он меньше, тем лучше. И код уж точно не должен быть размера O (N) от размера input’а. Впрочем, такое преобразование кода, которое мы сделали руками, очень умные компиляторы (например, для C++) иногда проворачивают.

Говорим ДА знаниям* устройства процессоров

Приколы на этом не заканчивается. Как вам вот такое? 

public unsafe long SumTrickyAndSmartUnsafe()
{
    long w = 0;
    long x = 0;
    long y = 0;
    long z = 0;
 
    var length = array.Length;
    fixed (long* ptr = array)
    {
        var pointer = ptr;
        var bound = pointer + length;
        while (pointer != bound)
        {
            w += *pointer;
            x += *(pointer + 1);
            y += *(pointer + 2);
            z += *(pointer + 3);
            pointer += 4;
        }
    }
 
    w += x;
    y += z;
    return w + y;
}

Да, складывать будем не в одну переменную X, а в четыре. А потом в конце будем вынуждены ещё и просуммировать их. Казалось бы, мы лишь добавили дополнительных вычислений, лишних переменных. Но раз это здесь, видимо, это ещё быстрее. Вот бенчмарк: 

|                  Method |      Mean | Allocated |
|------------------------ |----------:|----------:|
|           EnumerableSum | 69.810 us |      32 B |
|                SumNaive |  9.387 us |         - |
|          SumNaiveUnsafe |  5.761 us |         - |
|         SumTrickyUnsafe |  4.423 us |         - |
| SumTrickyAndSmartUnsafe |  3.595 us |         - |

Catched!

Вот оно! Мы устроили всё это здесь ради того, чтобы добраться до вот этой разницы в ~23% между двумя последними вариантами кода. Давайте изучать ситуацию пристальнее, как обычно, с помощью ASM кода: 

; Сначала всякая подготовительная работа, которая выполняется один раз
; А внимания достоен только наш основной цикл
M00_L03:
       add       rax,[rcx]
       add       rdx,[rcx+8]
       add       r8,[rcx+10]
       add       r9,[rcx+18]
 
       add       rcx,20
       cmp       rcx,r10
       jne       short M00_L03

Код снова очень похож на предыдущий, где мы складывали всё в один регистр RAX. Только сейчас мы складываем это в 4 регистра: RAX, RDX, R8, R9. Это все регистры в x64, кто не знаком с R8 и R9 — это простые целочисленные регистры. А потом, вне цикла, мы вынуждены будем ещё и сложить друг с другом эти 4 регистра.

Погружаемся в устройство процессоров

Что за трюк? Почему складывать в 4 разных регистра быстрее, чем складывать в один регистр? Тут самое время вспомнить про архитектуру современных процессоров.

Вы думаете, что мы написали последовательную, «однопоточную» (если можно так выразиться) программу? Процессор так не думает.

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

Процессор конвейерит и параллелит исполнение инструкций

Есть, например, инструкция MUL, умножение. Её latency = 3. То есть, чтобы выполнить умножение, нужно затратить 3 цикла процессора. Но давайте представим, что мы умножаем три раза 6 совершенно независимых чисел. A = A*B,  C = C*D, E = E*F.

  1. На первом цикле начнется выполнение A*B.

  2. На втором цикле начнется выполнение C*D, а A*B будет на втором шаге.

  3. На третьем цикле начнется выполнение E*F,  C*D будет на втором шаге, а A*B будет на завершающем третьем.

  4. На четвертом цикле E*F будет на втором шаге умножения,  C*D на завершающем.

  5. На пятом цикле E*F будет на завершающем шаге.

Итого, мы на 3 умножения потратили не 9 циклов, а всего 5. Потому что все 3 операции были в цепочке независимых инструкций. Но как только мы свяжем их друг с другом через какую-нибудь переменную (регистр), так возможность pipelining’а мгновенно исчезает. Так, умножения вида A = A*B,  A = A*C и A = A*D образуют цепочку зависимых операций. Из-за того, что для выполнения каждого следующего умножения надо знать значение регистра A. А значение регистра A как раз в предыдущей инструкции и считается. И потому каждое умножение будет занимать 3 цикла не пуская никого в pipeline.

А сложения исполняются буквально одновременно

Вернёмся к нашим сложениям. Они чуть интереснее. Если для умножения у каждого ядра есть свой единственный mul-capable unit, то для сложения их, обычно, четыре! А latency одного сложения = 1. Это значит, что если все 4 сложения независимы и образуют independent chain, то все 4 сложения могут выполниться за 1 цикл!

Именно потому наш первый вариант с реализацией четырех сложений подряд оказался медленнее, чем второй. Потому что в первом варианте мы всё складывали в одну и ту же переменную. И в ASM коде соответственно было так же — мы складывали всё в один регистр RAX. А значит на 4 последовательных сложения потратили 4 процессорных цикла. А во втором варианте 4 сложения делались в разные переменные. И в ASM коде 4 сложения делались в 4 разных регистра соответственно. И все 4 сложения выполнились за 1 цикл.

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

Вот мы и вывели Reciprocal throughput

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

Reciprocal throughput: the maximum number of instructions of the same kind that can be executed per clock cycle when the operands of each instruction are independent of the preceding instructions.

То есть для инструкции ADD latency = 1, а reciprocal throughput = 0.25. Это значит, что 1 / 0.25 инструкции могут работать «параллельно». То есть 4. А для инструкции MUL latency = 3, а reciprocal throughput = 1. Это значит, что мы можем исполнять 3 операции MUL одновременно, вот только каждая следующая будет начинать исполняться через 1 цикл после предыдущей.

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

Бонус

Если что, складывать числа в массиве нужно всё-таки не так. Для этого есть векторные инструкции (SIMD).

Без всяких заморочек, какая-то реализация в лоб. 

public unsafe long SumSimd()
{
    var vectorSum = Vector.Zero;
    var vectorSize = Vector.Count;
   
    var length = array.Length;
    fixed (long* ptr = array)
    {
        var pointer = ptr;
        var bound = pointer + length;
        while (pointer != bound)
        {
            vectorSum += Unsafe.Read>(pointer);
            pointer += vectorSize;
        }
    }
      return Vector.Dot(vectorSum, Vector.One);
}

По-хорошему, тут ещё нужно обрабатывать хвостик, если массив не делится на размер вектора. Но для простоты я опустил это, в нашем бенчмарке размер массива = 16000 long’ов, что делится нацело даже на 512-битный регистр. В предыдущих реализациях, где производилось по 4 сложения на одну итерацию цикла, мы тоже опирались на то, что размер массива делится на 4. В настоящем коде там тоже пришлось бы обрабатывать хвостики.

Вот результат бенчмарка: 

|                  Method |      Mean | Allocated |
|------------------------ |----------:|----------:|
|           EnumerableSum | 69.810 us |      32 B |
|                SumNaive |  9.387 us |         - |
|          SumNaiveUnsafe |  5.761 us |         - |
|         SumTrickyUnsafe |  4.423 us |         - |
| SumTrickyAndSmartUnsafe |  3.595 us |         - |
|                 SumSimd |  1.998 us |         - |

И для полноты картины, скриншот полного бенчмарка. Важно отметить, что мы бенчмаркали на размере массива 16000 long’ов, что легко умещается в кеш-линию процессора. Если взять массив на сотни мегабайт, пропорции длительности работы методов будут немного отличаться, но смысл останется тот же самый. Можете попробовать сделать это сами ;)

5bd06dab719318d7aac15bacfc72bcaa.png

Заключение

Где могут применяться знания о reciprocal throughput? Действительно, тема довольно узкая. Ну, как минимум, эта способность процессоров вовсю эксплуатируется компиляторами. И иногда вы пользуетесь этой возможностью процессоров, даже не подозревая этого. Также, очевидно, изредка можно встретить ситуации, когда нужно выжать максимум производительности из каких-то алгоритмов. Например, когда такие вычисления составляют существенную часть всей работы приложения. Чаще такое встречается где-нибудь в геометрии, географии, машинном обучении (там, правда, есть и видеокарты для такого), научных и статистических вычислениях, различных моделированиях каких-нибудь процессов.

А вообще, я считаю, что в принципе очень полезно знать, как оно устроено внутри. Понимать, почему те или иные манипуляции с кодом, пусть и очень высокоуровневым (как C#), влияют на итоговый результат и качество работы программы.

А ещё, смотрите как красиво вышло. Тривиальной программой на таком языке, как C#, можно демонстрировать буквально самые низлежащие принципы работы современных процессоров. Это был отдельный небольшой вызов лично для меня.

© Habrahabr.ru