Spiiin's blog | Agner Fog's Optimization manuals

Agner Fog's Optimization manuals

2024/02/20

https://www.agner.org/optimize/#manuals - отличные мануалы по оптимизациям от датского эволюционного биолога (программирует, наверное, для души).

C++

Optimizing software in C++: An optimization guide for Windows, Linux and Mac platforms — стоимость абстракций в C++ коде.

ISO/IEC TR 18015, “Technical Report on C++ Performance”

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

Многие знают также способ борьбы с виртуальными функциями с помощью CRTP+static_cast.

Runtime-полиморфизм в C++ - еще про способы реифицировать полиморфизм

A Journey Into Non-Virtual Polymorphism in C++ - Rudyard Merriam - C++23 способ провернуть то же самое через deducing this, немного менее сuriously

Deducing this Patterns - Ben Deane - более детально.
Один из прикольных паттернов оттуда:

struct my_vector : vector<int> {
    using vector<int>::vector;
    auto sorted_by(this my_vector self, auto comp)->my_vector {
        sort(self.begin(), self.end(), comp);
        return self;
    }
}
//прокидывается в функцию как rvalue
my_vector{3,1,4,1,5,9,2}.sorted_by(less_than);

Asm

The microarchitecture of Intel, AMD, and VIA CPUs - позиционируется как гайд для ассемблерщиков и компиляторщиков. Но всё еще понятно для gamedev программистов и любителей почитать дизассемблированный листинг сгенерированного компилятором C++-кода.

Для меня мануал оказался интересен объяснением архитектуры современных процессоров языком, всё еще понятным программистам, а не железячникам. Плюс в универе когда-то был курс по архитектуре компьютеров, который начинался с 8086 и заканчивался очень беглым описанием первых Pentium, а тут как раз продолжение ровно с того места, на котором он заканчивался.

Для примера, многие C++-программисты могут ответить, что ++i лучше чем i+=1, так как у процессора есть специальная инструкция inc, оптимизированная для прибавления единицы. Однако можно проверить, что современные компиляторы вставляют вместо этого add eax, 1 (а с оптимизациями и вообще lea eax, [rdi + 1]). Почему же они не используют “быстрый” inc?

современные процессоры умеют Out-of-order execution. Инструкции разбиваются на микро-операции.

Какой-нибудь push eax может разделяться на операцию вычисления нового адреса верхушки стека (для чего есть отдельный пайплайн stack engine), и операцию перемещения из регистра по этому адресу. Выполнить первую микро-операцию можно отдельно от второй и даже раньше, чем предыдущию инструкцию, которая записывает значение в этот регистр. Соответственно, процессор “знает” о том, какие микрооперации можно выполнять независимо от других, а какие должны дождаться выполнения предыдущих

Забавно, что микро-операции затем снова могут склеиваться в одну макро-операцию(instruction fusion), для экономии памяти. Существует кеш декодированных инструкций, чтобы не тратить время на повторное декодирование для коротких циклов. Интересно, если ли в каких-нибудь процессорах регистры, в которые можно загрузить инструкции (хотя бы в архитектурах, где инструкции одинакового размера)

еще одна фича процессоров — вместо прямого использования указанного регистра, может использоваться временный невидимый регистр.

mov eax, [mem1] # допустим, что mem1 в кеше
mov ebx, [mem2] #     а mem2 нет
add ebx, eax    # нужно дождаться чтения mem2
imul eax, 6     # можно начинать выполнять умножение раньше сложения, так как копия eax
                #    необходимая для выполнения сложения сохранится
                #    для предыдущей операции во временном регистре
mov [mem3], eax
mov [mem4], ebx

многие инструкции меняют значения флагов. Флаги хранятся в регистре, который тоже может быть заменён на временный. Некоторые операции требуют синхронизации временного регистра с обычным (retirement).
по историческим причинам inc не меняет значения carry-флага процессора, в отличие от add. Из-за этого следующие за ней инструкции, использующие значения регистра флагов, должны собрать актуальное значение этого регистра флагов (дополнительная микро-операция). lea же хороша тем, что вообще не трогает флаги.

Еще один ненормальный факт из мира асма, непонятный C++ программистам: у некоторых процессоров с несколькими декодировщиками инструкций эти декодировщики обладают неодинаковыми возможностями - например, первый может декодировать инструкции, которые генерируют от 1 до 4 микроопераций, а второй и третий - только инструкции с 1 микрооперацией. В этом случае для достижения максимальной скорости выполнения инструкции должны быть расставлены “в стихотворной форме”, по паттерну 4-1-1, чтобы занять одновременно все 3 декодировщика (генерация одновременно по 6 микроопераций за цикл, а при ритме 2-2-2 - по 2 микрооперации за цикл).

Инструкции могут декодироваться заранее, если следующие стадии заняты вычислениями. Корректному декодированию могут мешать инструкции условных переходов (if/loop) и indirect jump с несколькими вариантами перехода(switch/function pointers/virtual). Аппаратный способ борьбы с неправильным декодированием — предсказания переходов.

Простейший “предсказатель” логического перехода — таблица из адреса перехода и соотвествующего ему двухбитного saturating-счётчика (“почти точно правда/скорее правда/скорее ложь/почти точно ложь”). Другой вариант трактовки бит в счётчике — вместо “переход произойдёт/не произойдёт” - “будет ли как в прошлый раз/будет не так, как прошлый раз” (позволяет предсказывать flip-flop переходы). Более сложные варианты могут содержать “память” на несколько предыдущих значений, например, 4 saturating-счётчика, каждый из которых показывает, какая вероятность перехода в следующее состояние в зависимости от 2х предыдущих состояний. Для indirect jump также необходимы несколько saturating-счётчиков для каждого из вариантов перехода. Предсказатели циклов могут запоминать количество повторов цикла. Различные варианты могут объединяться в гибридные предсказатели.

Если отойти от магии инструкций и их предсказаний — важными являются также предсказуемые паттерны доступа к данным. Чтобы данные эффективно попадали в кеши, они должны лежать в памяти последовательно. Кеш-строк много, так что удобная тактика для циклов — за первый проход захватить все нужные для последующих проходов данные в кеш-строки, чтобы второй и последующий проходы использовали данные из этих кеш-строк.
Array of structures of arrays - Array of structures of arrays - способ раскладывания в памяти данных, чтобы и в кеш побольше попало, и чтобы обрабатывать пачками. В плане возможностей описания данных в памяти, си не очень далеко ушёл от ассемблера.

Оптимизации компиляторов

Chandler Carruth, но в ту же тему:
Optimizing the Emergent Structures of C++ — про возможности в оптимизации инструкций и данных компилятором.
Efficiency with Algorithms, Performance with Data Structures — как обычно, векторы и хеш-таблицы без списков внутри эффективные, списки и графы (и структуры в которых они неявно спрятаны) — нет.