#books

Обзор книги "Modern Parallel Programming with C++ and Assembly Language" (2022 г.) 📚

(можно скачать PDF тут)

Как можно понять, книга посвящена "параллельному программированию".
Но тут имеется в виду не та параллельность когда есть много CPU (и используются мьютексы, etc.), а параллельность внутри одного CPU, а если точнее, то вся книга про SIMD (single instruction, multiple data) 🏃

Сейчас стандартные типы данных имеют размер 8/16/32/64 бит (соответственно это byte/word/dword/qword), они "нативно" поддерживаются потому что сами регистры общего назначения у процессора имеют размер 64 бита 🤡

Но в процессорах часто есть регистры на 128, 256 и даже 512 бит (соответственно это xmmword/ymmword/zmmword в x86) 😎 В эти регистры "упаковываются" значения стандартного размера и над ними затем делаются групповые операции.

Проще показать на примере - пусть мы суммируем float'ы:

// float* z, const float* x, const float* y, size_t n
for (size_t i = 0; i < n; i++)
    z[i] = x[i] + y[i];

То SIMD-версия на 256-битных регистрах могла бы выглядеть так (с поправкой на конкретный компилятор, т.к. эти интринсики не специфицированы в Стандарте С++):

// представим что `n` делится на 8
for (size_t i = 0; i < n; i += 8) {
    __m256 x_vals = _mm256_loadu_ps(&x[i]); // грузим x[i..i+8] в один регистр
    __m256 y_vals = _mm256_loadu_ps(&y[i]); // грузим y[i..i+8] в другой регистр
    __m256 z_vals = _mm256_add_ps(x_vals, y_vals); // вычисляем z[i..i+8] в третьем
    _mm256_storeu_ps(&z[i], z_vals); // выгружаем z[i..i+8] в память
}

Код выше работает быстро, решительно, в разы быстрее "наивного" варианта.
Общий flow такой - в "длинный" регистр выгружается мини-массив чисел (в примере выше массив из 8 float'ов), и ускорение достигается за счет того, что процессор не тратит время на чтение одних и те же опкодов, а сразу делает нужную операцию.

Так как процессоры сейчас гига сложные (я наклал кирпичей даже когда делал эмулятор m68k 45-летней давности!), то таких "групповых операций" наделали много. Можно, например, вычислять еще z[i] = min(x[i], y[i]), или y[i] = x[2*i] + x[2*i+1], или даже быстро переставить элементы z[i] = x[y[i]], и так далее.

Книга посвящена только архитектуре x86 (архитектуры как ARM не рассматриваются).
SIMD-расширений в x86 есть несколько. Сначала в 1997 году появился MMX от Intel, потом в 1998 году 3DNow от AMD, и так далее, многие давно устарели и не выпускаются.
Книга посвящена только сравнительно новым SIMD-расширениям AVX (2011 год), AVX2 (2013 год) и AVX-512 (2017 год).

Глава 1️⃣ описывает базу SIMD.
В главах 2️⃣➖8️⃣ по одному шаблону описываются фичи AVX / AVX2 / AVX-512:
1️⃣ Описывается какая-нибудь платиновая задача - найти минимум/среднее в массиве, перемножить матрицы, применить свёртку, etc.
2️⃣ Приводится портянка кода на C++: "наивная реализация" vs "реализация на SIMD", с нудным описанием что откуда идёт.
3️⃣ Приводится бенчмарк, наивная реализация проигрывает SIMD в среднем в 10-15 раз.
В главе 9️⃣ описывается как можно было бы сделать портабельную SIMD-программу - для этого в x86 есть опкод cpuid, по которому можно узнать поддерживаемые SIMD-расширения и еще много что.
В главе 1️⃣0️⃣ неплохо описывается боян архитектура процессора x86-64 вместе с этими SIMD-регистрами в 256/512 бит.
В главах 1️⃣1️⃣➖1️⃣8️⃣ описывается то же, что в главах 2-8, но на ассемблере... Я это не читал 😁
В главе 1️⃣9️⃣ описывается здравый смысл, то есть гайд по SIMD-оптимизациям, общая тема - оптимизировать надо не всё подряд, а только то что видно в профайлере, потому что SIMD-код понимать трудно и легко ошибиться.
В аппендиксах есть инфа как ставить вижуэл студио и ссылки на доки... 🔍

В целом полезная книга, можно почитать для общего развития. Только нужно иметь в виду:
1️⃣ Некоторые задачи лучше решаются через GPU, а не через SIMD на CPU (который ускорит лишь в единицы раз, а не в сотни).
2️⃣ Современный компилятор может сам сгенерировать SIMD-код (но это бабка надвое сказала).
3️⃣ Сначала профайлер, потом оптимизации.

#jostik

Обзор жостиков C++ 😱 (номер sizeof(char))

(Предисловие)
Эту картинку я сделал месяц назад, и хотел отправить в WG21 (Working Group 21, он же Комитет C++) как предложение для логотипа 🎨 Это буква "С" и два плюса.

Но вспомнив комитетские приколы, решил не делать 🦆
Какой-нибудь товарищ комиссар Рабочей Группы по многообразию не принял бы ее, аргументировав что для репрезентации нужна широкая цветовая палитра, а вместо одного из крестов, например, символ зороастризма 🤲 Зачем это делать, если он сам не живет так, как говорил Заратустра - непонятно. Слишком многим людям форма важнее содержания.

Поэтому это будет новая ава 😐

1️⃣ Strong-типы 🙂

Теория о них тут, реализация на гитхабе.
Strong-типы это обертки над базовыми типами (int, double и пр.), которые не могут конвертироваться в другие типы. Это полезно, чтобы не путать аргументы и понимать цель значения из имени типа.

Например, вместо такого конструктора:

Rectangle(double width, double height);

Можно сделать такой:

Rectangle(Width width, Height height);

Где Width и Height - обертки над double, и их нельзя перепутать ✋

Strong-типам можно придавать разные "скиллы" - например Addable, Comparable, Hashable и прочие, чтобы соответственно работали операции сложения, сравнения или можно было положить тип в хэшмапу.

Эти типы "бесплатные" для рантайма - компилятор выбрасывает шелуху и работает с базовым типом 🕶

Раньше я их не принимал (если ты путаешься в параметрах, то вместо 15 параметров нужен builder pattern 🛑), но сейчас наоборот, без них жить сложнее - это неплохая вещь.

2️⃣ Упакованные типы 📦

Как известно, у типов есть выравнивание:

struct Biba {
    uint16_t a; /* 2 bytes */
    /* padding 6 bytes */
    uint64_t b; /* 8 bytes */
};
static_assert(sizeof(Biba) == 16);
static_assert(alignof(Biba) == 8);

Но во время парсинга пакетов всяких протоколов это может мешать, потому что никаких padding'ов между полями не предусмотрено. Также во время работы с сетью супер важно оптимизировать память. Тогда надо убирать выравнивание (alignment) 🎩

Это можно сделать разными способами, самый удобный такой:

#pragma pack(push, 1)
struct Boba {
    uint16_t a; /* 2 bytes */
    uint64_t b; /* 8 bytes */
};
#pragma pack(pop)
static_assert(sizeof(Boba) == 10);
static_assert(alignof(Boba) == 1);

(Этот pragma pack выглядит странно, потому что у него есть типа внутренний стек)
Команда pack(push, N) значит что все типы будут иметь alignment максимум N байт, а pack(pop) убирает это.

Менее удобный способ (потому что надо ставить каждому классу вручную) это вешать на структуру __attribute__((packed)).
Это немного по-другому работает внутри компилятора, но итог один - alignment равный единице.

Способ, который не работает - спецификатор alignas, он может только увеличить дефолтный alignment. Оно используется для подгона структуры под кэш-линию (64 байта) или SIMD-инструкции (16/32/64 байта).

А как это работает на уровне ассемблера? 🤔 Компилятор не будет генерировать дичь с переносами байтов (как для bitfield), там формируется честный unaligned access.
Как оказывается, на x86 никаких сюрпризов нет. Оно всегда поддерживало unaligned access (работающий медленнее чем aligned).
А на других архитектурах может произойти треш - надо беречься 🤔

ПРОДОЛЖЕНИЕ В КОММЕНТАРИЯХ 👀

#compiler

День, когда умер CRTP 🫡

По исходникам проектов на C++ можно определять, примерно в какое время был написан код 👨‍🦳 В истории C++ был революционный стандарт C++11, еще чуть менее революционный C++20 (по убыванию используемости - concepts, ranges, coroutines, modules), и проходные между ними (C++14, C++17).

В C++23 есть единственная крупная фича, ради которой стоило его ждать - deducing this 😳 Единственное место, где нужно про него читать - пропозал в стандарт, там есть всё - мотивация, обоснование всех тонкостей дизайна, примеры использования, разбор всех корнер кейсов, и прочее. Все другие объяснения из интернета принципиально менее полны 📖 Я сюда не буду копипастить примеры, они есть в пропозале.

Long story short, в каждом методе используется неявный "нулевой" параметр this, эта фича добавляет возможность явно указать этот параметр, причем необязательно с исходным типом (можно заиспользовать шаблон). Это оказалось очень нужным - уменьшает дублирование методов, убирает необходимость в CRTP, позволяет удобнее рекурсивные лямбды, и прочее 😎

Конечно, у deducing this есть ряд drawbacks 🤷‍♂️
1️⃣Есть ряд спецэффектов по типу shadowing'а переменной базового класса (в пропозале они разобраны)
2️⃣ Методы становятся шаблонными со всеми вытекающими - Clang известен тем, что в отличие от MSVC не особо проверяет код шаблона до инстанциации
3️⃣ В коде начинается треш с категориями значений, нужно понимать разницу между auto, auto&&, decltype(auto), и специально добавили срань как std::forward_like.

Реализация deducing this наконец-то появилась в LLVM/Clang 18, который зарелизился 6 марта 😮 К сожалению, релиз получился всратым, и баги не пофикшены до сих пор 🚬 Поэтому его пока никто не использует.

Но уже сейчас можно изучать вопрос - как лучше всего подготовиться к использованию этой фичи и гарантировать, что все перестанут писать "по-старому"? 👦
В этом нам поможет libclang! Мы можем написать простые python-тесты на исходный код (о них писал тут🔍), и отлавливать устаревший код.

Первым делом нужно, чтобы в проекте генерировался compile_commands.json. Это простой список команд для компилятора, его описание тут, он нужен для многих вещей, например для автокомплита.
Его создание поддерживается в CMake, для этого в корневом CMakeLists.txt надо добавить:

set(CMAKE_EXPORT_COMPILE_COMMANDS ON)

Потом надо поставить пакеты из этого поста🔍 Код всего теста можно посмотреть тут, дальше я опишу что он делает.

ПРОДОЛЖЕНИЕ В КОММЕНТАРИЯХ 🏃

#jostik #compiler

Обзор жостиков C++ 😎 (номер 0x00000002)

1️⃣ Сделай сам requires-clause для полей класса 😶

Шаблоны C++ развиваются в сторону упрощения - многое было сделано, чтобы избавиться от enable_if и ручной специализации шаблонов.

Одна из фичей - сейчас можно наложить trailing requires-clause на класс и на метод, чтобы ограничить их использование:

template<typename T>
  requires std::copyable<T> && std::movable<T>
struct Blow {
  void make_job()
    requires (sizeof(T) > 100)
  { /* ... */ }
};

Логичным следующим шагом должно стать ограничение на поле класса.

Такое опциональное наличие поля было бы полезно везде, где из-за свойств шаблонной сущности меняется размер класса. Например делетеры в умных указателях (как std::unique_ptr). Или отсутствие поля "size", если он указан в шаблоне (как std::span).

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

template<typename T, std::size_t N = 0>
class JanusVector {
private:
  // static vector, N is fixed
  std::array<T, N> arr_ requires (N > 0);

  // dynamic vector, N is not fixed
  std::size_t size_ requires (N == 0);
  T* data_ requires (N == 0);
};

// ...

int main() {
  JanusVector<int, 228> vec1;
  static_assert(sizeof(vec1) == 4 * 228);

  JanusVector<int> vec2;
  static_assert(sizeof(vec2) == 16);
}

Недавно мной была вкинута идея в разнорабочую группу по C++, пока без эффекта 🥱

Решил для прикола сделать реализацию этой фичи на Clang 👀
(Ссылки: как настроить сетап для clang, как создать свой keyword)

Дифф за пару вечеров получился не очень большим (он на gist.github.com), состоит из таких кусков:
1️⃣ В парсере разрешить парсить выражение trailing requires-clause после полей класса.
2️⃣ Сохранять это выражение в класс FieldDecl, вычислять его значение в методе isRequiresClauseSatisfied.
3️⃣ Добавить проверки в LayoutBuilder'е, чтобы не вкомпилировать storage под неудовлетворяющие поля.
4️⃣ Диагностировать обращения к неудовлетворяющим полям (создается ошибка компиляции).
5️⃣ Осторожно проинстанцировать выражение во время инстанциации шаблона 😠 Непроинстанцированные зависимые константные выражения невычисляемы!

Вот так можно делать proof of concept фичи 🥂 Это самый базовый пример, еще не рассмотрено несколько концептуальных вопросов, например:
1️⃣ Разрешить ли одинаковые имена у полей, если они никогда не скомпилируются вместе в одном классе?
2️⃣ Нужно ли помещать поле в скоуп выражения, для такого:

    // типа поле `kek_` скомпилится если у него будет метод `foo()`
    T kek_ requires requires { kek_.foo(); };

3️⃣ Всякие мелкие баги, наподобии того что в реализации не запрещено брать адрес &Foo::kek у нескомпилировавшегося поля kek.

В КОММЕНТАРИЯХ ЕЩЕ ТРИ ЖОСТИКА C++ 🏃

#story

Обзор на работу в большой компании 💼

В начале этого года я покинул Яндекс, где проработал чуть больше 4 лет 👨‍🦳
Хотя там была ровная братва среди коллег и «интересные проекты»™️, я внял мудрости современного философа - «за деньги да» 😃 Но обо всем по порядку...

Часть1️⃣ Рассказ бывалого балабола

Я накидал субъективный обзор 😀 на плюсы и минусы
➕1️⃣ Hard skills
За несколько первых месяцев реальной работы в мощном темпе выучиваешь в разы больше, чем за годы «саморазвития» до этого 👦
За долгий срок работы можно порешать задачи из широкого спектра, испытать все виды инцидентов, и в целом это интересный опыт 🤡 Можно смотреть курсы ШАД, код крутых коллег, внутренние ресурсы.
Нельзя сказать, чтобы у каждого было супер крутое знание какого-либо языка - это не самоценность, а просто инструмент выполнения задачи. Нередко встречаются ржаки по типу как на этом скрине, что чела закинули в команду где пишут на Х и он тоже выучил Х за 21 день (можно догадываться про уровень понимания)👶
Компании не нужно, чтобы ты был rockstar - большие проекты делаются сотнями людей, и адекватный менеджмент ориентируется на их средний уровень, а также резервирует время под возможные переделки ⏰
Если же менеджмент неадекватный, то будут требовать сделать космолет за неделю, что будет не под силу даже Леннарту Поттерингу 😐
К вопросу о том - можно ли считать себя "ылитой", если ты работаешь в FAANG или под них косящих 😀 - имхо это звучит неуместно, когда речь идет о супер формализованном процессе найма workforce (результат каждого собеса это буквально true или false) с "good enough" компетенцией, чтобы закрывать стандартные таски. Так вижу.

➕2️⃣ Soft skills
Если есть желание, софт скиллы тоже неплохо прокачиваются. Хотя их можно качать бесконечно - если какой-то алгоритм или фичу можно выучить раз и навсегда, то взаимодействие с людьми это то, чему можно учиться всю жизнь 🤗
Обычный "работяга" - низшее звено пищевой цепочки. То, что он делает какие-то таски - это значит что топы определили направление, менеджеры поборолись за скоуп, а тимлид нарезал таски из глубокого знания codebase.

И достаточно скоро надо будет самому быстро наводить связи и эффективно общаться по рабочим вопросам. Не могу посчитать, со сколькими коллегами была переписка, но это цифра порядка нескольких сотен 📝 Поэтому если есть когнитивные баги, которые мешают нормально общаться - будет трудно работать и расти, я это видел на примере нескольких супер-крутых технически коллег, у которых были сложности (плохо считывали эмоции и социальные ситуации).

Это тот случай, когда "негативный опыт - тоже опыт". Так как многое завязано на человеческий фактор, комфортное пребывание во многом зависит от твоих коллег и еще намного больше от рукля.
За все время у меня было 5 руклей, со всеми я супер ровно сработался, кроме одного. Так оно работает - чтобы у тебя были задачи с высоким импактом и рост, необходимое условие чтобы рукль (и дальше по цепочке вверх) этого тоже хотели. Некоторое время я с ним промучался, но ничего не помогало и все было настолько плохо, что мне даже ставили встречу с HR с неприятным разговором 😵 Так что совет - лучше сразу уходить, если есть негатив с руклем, а не пытаться это исправить.
Я чуть не перешел к кенту в стартап, но по итогу просто ротировался в другой под-отдел и неплохо поработал в компании еще 1.5 года 💼

ПРОДОЛЖЕНИЕ В КОММЕНТАРИЯХ 📖

#books #compiler

На фотокарточках 6-летней давности - админ готовится к сессии.
Подготовка происходила в виде 12-часового чтения учебников 🎮 Во время бота физических предметов включал на фоне "Ансамбль Христа Спасителя", чтобы было веселее читать 🎧
Когда информация больше не лезла - прогуливался по Тушино, где тогда жил (его достопримечательности можно увидеть в снимавшемся там фильме "Россия 88") 🔍
По случаю успешной сдачи экзамена обычно приобретался Rheinwein и устраивался вечер просмотра старых фильмов (таких как "Metropolis", 1927), а назавтра наступал бот нового предмета 🚬

Это давно позади - теперь я читаю что хочу 😐 На этот раз сделал обзор на 4️⃣ книги.

1️⃣ "Clang Compiler Frontend" (2024 г.) 📚
(PDF тут)
Совсем новая книга от активного разработчика Clang/LLVM 💼
Очень полезная, если хочется разобраться, что происходит внутри компилятора. Легко читается, есть теория (про AST, SourceLocation, матчеры, etc.), красивые графики, многие концепции автор иллюстрирует через брейкпоинты и показ стека в дебаггере ⌨️
Описаны многие фичи кодовой базы - указатели с флагами, самописный rtti, структуры данных как llvm::Twine, TableGen, система тестов, и тд.

Каждая крупная тулза тоже подробно разобрана - clang-tidy (линтер), clang-format (форматтер), clangd (предыдущие два + автокомплит в IDE).
Есть не только теория - описано как сделать свой чекер в clang-tidy 🖥
Про clangd больше понравилось описание оптимизаций 💨 Например, когда меняешь что-то в редакторе, clangd перекомпилирует кусок AST только .cpp-файла, а хедеры из #include не трогает (так как их не меняли). А при парсинге хедеров (когда это требуется) не парсятся тела функций, так как автокомплиту это не нужно. Из-за этих оптимизаций автокомплит быстро летает 😎

Для тех, кто уже давно шарился в исходниках Clang/LLVM (и патчил что-то), будет мало нового, но для остальных - must have, круто знать свой компилятор 👦

2️⃣ "C++ Move Semantics - The Complete Guide" (2022 г.) 📚
(PDF тут)
Да, это целая книга про мув семантику 🚬 По мотивам книги про C++ лямбды.
Самая муторная и скучная для чтения книга из списка - когда видишь название параграфа по типу:

10.3.2 Conflicting Template Parameter Deduction with Universal References

Книгу хочется закрыть и не открывать.

Эта семантика рассматривается с разных сторон - затрагиваются и колхозинг мува до C++11, и noexcept-guarantee в контейнерах, и в какой момент в стандарте rvalue разделилось на prvalue+xvalue, и так далее.
Можно узнать какие-то мелкие приколы, например что автор предпочел бы чтобы универсальные ссылки не смешивались с rvalue-ссылками (оба записываются через &&), то есть можно было бы сделать хотя бы так:

    template<typename Coll>
    void foo(Coll&&& arg) { ... }

Или что функции в шаблонном классе называются temploid - типа это шаблонный код, но он как бы для обычной функции, поэтому свойства шаблонных функций на нее не распространяются - так что вот такой термин есть 😐

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

ПРОДОЛЖЕНИЕ В КОММЕНТАРИИ 👇

#jostik #compiler

Обзор жостиков C++ 😔 (номер 0b11)

На этот раз будет аж семь жостиков - три про DIY в Clang, одно про устройство Wireshark, одно с видео, и пара про идиомы C++ 📈 7️⃣ В данный момент это самый плотный набор жостиков.

1️⃣ [Clang] Сделай сам наследование в enum 🍷
У enum'ов в C++ нет наследования. Но это могло бы быть полезным в редких случаях, когда есть общий enum для всех кейсов, но в каких-то окружениях есть мелкие различия, которыми не хочется засорять общее место.

Пусть программа работает с большими ресторанами, куда отправляем запросы на доставку. С нашей стороны можно запросить новую доставку или отмену доставки (статус становится Adding/Cancelling и ждется ответ от сервера), после ответов от сервера статус становится Added/Cancelled/Delivered.
Большинство ресторанов не имеет возможности изменить адрес доставки (только отменять и создавать новую), но пусть какое-нибудь "Кафе Пушкинъ" 😬 так умеет, тогда неплохо бы иметь enum-наследник:

enum class DeliveryStatus : uint8_t {
  Adding,
  Added,
  Cancelling,
  Cancelled,
  Delivered,
};
enum class CafePushkinDeliveryStatus : DeliveryStatus {
  Moving,
};

(Планируется, что при изменении заказа статус меняется Added -> Moving -> Added)

Я попробовал придумать дизайн для наследования 🤔 Придумал такие правила:
1️⃣ У enum-наследника нумерация первой константы как будто она следует за последней константой родителя:

enum class First : short {
  None,            /* = 0 */
  MovedPermanently    = 301, 
  Found,           /* = 302 */
  SeeOther,        /* = 303 */
};
enum class Second : First {
  NotModified,     /* = 304 */
  UseProxy,        /* = 305 */
  BadRequest          = 400,
  Unauthorized,    /* = 401 */
};
enum class Third : Second {
  PaymentRequired, /* = 402 */
  Forbidden,       /* = 403 */
  InternalServerError = 500,
};

2️⃣ enum-наследник наследует родительский underlying type транзитивно

static_assert(sizeof(First) == 2);
static_assert(sizeof(Second) == 2);
static_assert(sizeof(Third) == 2);
static_assert(std::is_same_v<std::underlying_type_t<First>, short>);
static_assert(std::is_same_v<std::underlying_type_t<Second>, First>);
static_assert(std::is_same_v<std::underlying_type_t<Third>, Second>);

3️⃣ enum-родитель может неявно кастоваться к своему enum-наследнику:

inline constexpr Third kFound = First::Found;

4️⃣ Скоуп enum-наследника включает в себя все символы enum-родителей - этот пример аналогичен прошлому:

inline constexpr Third kFound = Third::Found;

То есть lookup по Third::Found находит enum constant First::Found (имеет тип First), потом на нем делается implicit cast к типу Third 🪄

Сделал proof of concept в Clang - ссылка на дифф 😐
(Это базовый вариант - нет тестов, не супер красивый код, не рассмотрена возможность множественного наследования, и так далее...)

Код компилятора жесткий, есть много хаков чтобы например различать a ? new enum E : int{} от foo(a, enum E : int{}).
Также под флагами поддерживается нестандартный синтаксис, например можно писать enum E : int *p; что равносильно enum E : int; E *p; (прикол от microsoft)

ПРОДОЛЖЕНИЕ В КОММЕНТАРИЯХ 🏃

#quiz

Дикий тест по C++ с рофлами 😁

Давно ничего не писал, решил выкатить тест по 🅰️➕➕

Сделал его не баянистым и не мега жестким, а именно по своему личному рабочему опыту 💼
Он состоит из 50 вопросов, покрыты разные темы, но главное что почти везде за вопросом стоит реальная польза от знания ответов 🤔 Но это не точно

Проходите тест! https://news.1rj.ru/str/QuizBot?start=WsPQdlYE 🔍 🤔

#offtop #essay

Löcherdämmerung (Гибель лохов) ⚰️

Решил написать небольшой обзор на современное общество 😉 Это не про C++, но тоже имеет отношение к делу. Уверен, что получилось достаточно злободневно

Все совпадения случайны, я не несу ответственность если вы узнали в чем-то себя 🤪 Посоветовал бы не принимать это всерьез, так как присутствует ржака

Читайте, может быть будет интересно 🧐
https://telegra.ph/L%C3%B6cherd%C3%A4mmerung-Gibel-lohov-10-20

#longread #retro

Написал новую статью 📖 Это продолжение постов про m68k и про сегу.

Создаем эмулятор Sega Mega Drive на C++

В этой статье описано создание эмулятора 16-битной приставки Sega Mega Drive на C++ 🏃

Будет много интересного: эмуляция процессора Motorola 68000, реверсинг игр, графика на OpenGL, шейдеры, и многое другое. И все это на современном C++. В статье много картинок, можно хоть на них посмотреть 🔍

#books #compiler

Обзор книги "Оптимизирующие компиляторы. Структура и алгоритмы" (2024 г.) 📚

Я вас категорически приветствую! Третьего дня, по совету проверенных камрадов, приобрел новую мегакнигу "Оптимизирующие компиляторы". Сразу же, задыхаясь от интереса, схватил книгу цепкими лапами и принялся читать.
Контент - мое почтение. Настоящей глыбой является Константин Владимиров. Даже моя, привыкшая к суровым алгоритмам башка, отказывалась принимать с первого захода. Совместными с ChatGPT усилиями дочитали книгу.
Ощущения - атас! С "dragonbook" не идет ни в какое сравнение. Кроме того, задания в конце глав заставляют сильно думать. Проходил так всю неделю. Решительно готов к новым контрибам в Clang/LLVM.
Многие дети тут увидят ненужные академические материалы. Тупым детям невдомек, что абстрактная математика и прикладные алгоритмы это разные вещи.
Книга отличная. Всем рекомендую к приобретению.
Все это, как водится, рецензия.

❌ ❌ ❌

Работа компилятора разделяется на несколько больших кусков - условно "фронтенд" и "бэкенд" (но и внутри них своя иерархия 🖥)
95% того, о чем я писал (по хештегу #compiler и т.д.) относится именно к фронтенду компилятора.
На этом же уровне работают почти весь набор стандартных тулзов для C++ погромиста: clang-tidy (по AST), clangd (тоже по AST), clang-format (по аннотированным токенам) и т. д.
Во фронтенды компиляторов порог входа сравнительно низкий - без предварительной подготовки любой студент может почитать/покоммитить или даже создать свой фронтенд 👦

Другое дело - бэкенд компиляторов, там требуется более серьезная подготовка - с графами, линейной алгеброй, теорией алгоритмов, и прочим. Книга как раз сфокусирована на бэкенде, в основном высокоуровневом (в отрыве от инструкций конкретной машины).

Главы:
1️⃣ Тулчейны. Спидран по всем компонентам от грамматик до линкеров 🏃‍♂️
2️⃣ Введение в оптимизации. Древние алгосы про "анализ потока данных" и решение многих задач через "решетки", нужны для ввода в контекст.
3️⃣ Построение SSA. Что такое SSA и как его построить через "дерево доминаторов".
4️⃣ Базовые оптимизации для SSA. Крутые алгоритмы для "глобальной нумерации значений" и "устранения избыточных вычислений".
5️⃣ Цикловые оптимизации. Много алгоритмов для оптимизации циклов (как for и while).
6️⃣ Межпроцедурные оптимизации. Инлайн и де-инлайн функций, хвостовая рекурсия, девиртуализация, и т. д.
7️⃣ Разрушение SSA. Саморазрушение - вот что действительно важно. Перевод SSA в ассемблер, и лютое количество NP-полных задач чтобы это нормально сделать 😔

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

К алгоритмам есть информация - какие применяются в LLVM и/или GCC, есть много примеров на LLVM IR. Активно используется "динамическое программирование", "жадные алгоритмы", "union-find множества" и прочие дорогие сердцу.

Для каждого термина дается перевод на английский, тоже с мета-информацией. В частности есть доходчивое пояснение почему "graph cycle" переводится как "цикл" (и от него производные слова как "зациклиться" и т.д.), а "loop" тоже как "цикл" а не "луп" 🤔

Многие факты узнал впервые - например какие задачи компилятора решаемы (хотя бы за квадратичное время) а какие NP-полные, и компилятор их не делает решает приближенно 🚬

После прочтения книги в очередной раз понял, что не могу быть 100% уверенным, какой ассемблер сгенерирует компилятор 🤪 На эту тему есть крутой сборник фактов Common Misconceptions about Compilers.