C++95

#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.

#longread #retro

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

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

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

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

#offtop #essay

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

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

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

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

#quiz

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

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

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

Проходите тест! https://t.me/QuizBot?start=WsPQdlYE 🔍 🤔

#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)

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

#story

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

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

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

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

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

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

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

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

#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++ 🏃

#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)

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

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

Channel photo updated

#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).
А на других архитектурах может произойти треш - надо беречься 🤔

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

Channel photo updated

#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️⃣ Сначала профайлер, потом оптимизации.

#opensource

Обзор опенсорсных программ и конкурсов Google 🕸

Я в Google никогда не работал, но имел честь поучаствовать во многих его программах. В этом плане Google уникален, потому что единственный из компаний своего уровня тратит так много на фактически благотворительность для повышения своего престижа.
Это может быть актуально для других крупных компаний. Я перечислю только те программы, где участвовал сам, а так их разных несколько десятков.

1️⃣ Google Code-In 👦
Это уже закрытая программа, она проходила каждый год с 2010 до 2019.
Суть была такова - с одной стороны заявлялись разные опенсорсные организации (как KDE, Fedora, Tensorflow и прочие), которые готовили кучу задачек чуть сложнее чем "добавить виджет в панель", то есть довольно лайтовые.
С другой стороны заявлялись микрочелики 13-17 лет (включительно), которые их выполняли в течении нескольких недель. Бесплатно, за опыт 😁 Но в конце каждая организация выбирала двух жостиков, и они на халяву езжали в США 🇺🇸

Я поучаствовал пару раз, во второй мне подфартило и я на пару недель на халяву съездил в Bay Area (несколько "официальных" дней полностью за счет Google, остальные дни оплачивали отель на свои 💳)
Примерно как это было можно посмотреть в более древнем фотоотчете этого хлопца.
В целом, было интересно после глубинки белгородской области, побывал во многих местах, которые потом снял пизДудь в своей рекламе. Из минусов были конские цены на всё и засилье бомжей сидящих на крэке, но это общеизвестные факты насчет Bay Area.

2️⃣ Google Summer of Code 🏝
Тоже программа про опенсорс как предыдущая, есть разница:
1️⃣ Длится три месяца
2️⃣ Участвуют только студенты
3️⃣ Опенсорсных организаций намного больше - практически все известные там есть
4️⃣ Сделать надо какую-то серьезную задачу для организации, вот список для LLVM. Студент должен предоставить план ("пропозал"), как он собирается делать эту задачу. Некоторые организации требуют наличие коммитов в проекте, или сдать тест на C++, или еще как-то доказать достойность. Но многие организации "легкие" и там проекты полная халява.

Последний 5️⃣ факт - Google платит за работу студентам. Раньше всем за лето платили 5000$ независимо от страны, расы, гендера и прочая, и прочая 💰
Потом решили, что слишком много участников из бантустанов, им такое бабло будет жирно. Поэтому ввели какой-то индекс гамбургера. Студенты из России и ее любимых соседей получают по 3000$ (минимум по шкале), из США по 6000$ (почти максимум) и так далее 💸

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

3️⃣ Google Code Jam 🍯
Легендарный контест по решению задачек, с лайв-стримами и прочим ⌨️
К сожалению, уже закрытый, проходил каждый год с 2003 до 2020 года.

Там была "воронка" из нескольких раундов: Qualification, Round 1, Round 2, Round 3, Final - с возрастающей сложностью.
На квалификацию записывались десятки тысяч людей, до финала доходило по ~26 человек из топа Round 3 (стата по годам).

Я до финала никогда не доходил - пик был в 2019, когда в Round 3 получил 171 место 🧐 И потом мне на почте не отдали футболку за участие в 3м раунде, потому что паспорт находился на замене по причине наступления 20 лет 🕺
А мой подписчик @bminaiev был в финалах неоднократно 😎 Подписывайтесь на его блог - @bminaiev_blog 😉

4️⃣ Google Hash Code #️⃣
Самый бомжацкий из конкурсов (тоже отменен, с 2023) - надо зарегистрировать команду из 2-4 человек и решать задачу оптимизации чего-нибудь несколько часов онлайн.

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

#story

Психоакустика и Bluetooth 🎧

(Вступление)

Heute treff ich einen Herrn,
Сегодня встречаюсь с одним господином,
Der hat mich zum Fressen gern.
Который охотно меня съест.
Weiche Teile und auch Harte,
Нежное филе, да и твердые куски
Stehen auf der Speisekarte.
Входят в меню!

На фото господин, чей голос я почти каждый день слушаю уже давно.
Особенно круто было в 12-13 лет. Представьте - на улице среди панелек мрак и холод, в дворовой школе безвкусно одетые учителя талдонят про деепричастия, на перемене порамсил с иностранным специалистом (и его 100500 братьев хотят с тобой поговорить), на обед вчерашние макароны.
Но вот ты за компьютером, включаешь эту музыку, и все проблемы тают как майский снег, ты становишься "Богом, входящим в Вальгаллу". Всегда есть что посмотреть - например клип из 1995 (вдохновленный романом "Парфюмер"), клип из 1998 (нарезанный из фильма "Олимпия" 1938 года), запись концерта 1998 года Live Aus Berlin (море огня) 🔥

Самый базовый формат цифрового звука это PCM, он представляет собой просто значения амплитуд (это громкость звука).
Например, формат WAV это заголовок из 44 байт, после которого идут байты PCM.
Несжатый звук длительностью в 1 секунду, с частотой 48kHz, стерео (то есть два канала), с двумя байтами на каждое значение амплитуды занимает примерно 1.5 Мбит.

Звук передается мне через Bluetooth 🤙 Но в таком случае его приходится сжимать.
Рекламируется, что пропускная способность Bluetooth составляет 3 Мбит/с, но по факту доступно в разы меньше и вышеуказанный звук нельзя передать несжатым.
Например, под "3 Мбит/с" подразумевается, что идут две одновременные передачи битов от девайса A к девайсу Б, и наоборот от девайса Б к девайсу А, обе 1.5 Мбит/c (направление меняется каждые 625 микросекунд). Кроме этого, много места занимают служебные заголовки, и бывает снижение битрейта из-за расстояния и интерференции 😔

Звук можно сжимать без потерь (lossless кодеки), там применяется много приколов и есть много кодеков (например FLAC), но толку мало - сжатие получается примерно в два раза. Этого недостаточно, чтобы нормально передавать звук по Bluetooth. Еще такие алгоритмы обычно вычислительно сложные 👎

Звук можно сжимать с потерями (lossy кодеки). Всего кодеков в Bluetooth с десяток, но единственный, который должен поддерживаться каждым девайсом это SBC (sub-band coding) 🤷‍♂️
Этот кодек сжимает по отдельности небольшие куски стрима. Например, для 16-битного стерео это 512 байт, то есть 128 значений амплитуд, что при частоте 44.1kHz соответствует 2.9мс. В кодеке можно поставить разные настройки (о них "договариваются" девайсы при коннекте через специальные пакеты), при High Quality на такой кусок выходит пакет в 119 байт, что соответствует битрейту 328 Кбит/с.

Чтобы так сильно сжать звук, используются познания психоакустики 👁 Эта наука изучает обработку звука мозгом. Если есть какой-то громкий звук в определенной частоте, то остальные звуки в других частотах мозг как бы "не слышит".
В SBC используется примитивная психоакустическая модель. Частоты разделяется на несколько равных диапазонов (называются "band", в SBC их максимум 8 штук, а в MP3 аж 32), и чем "громче" диапазон, тем больше битов выделяется на его кодировку, а информацию о "тихих" диапазонах можно и вовсе выбросить.
Информация упаковывается в фрейм, получателю остается вычислительно куда менее трудоемкая задача - распаковать фрейм, восстановить подпорченный сжатием звук и воспроизвести его 🎧

За мощность сжатия в SBC отвечает параметр bitpool. Чем он больше, тем меньше сжимается аудио. К сожалению, абсолютное большинство производителей девайсов и софта (даже Windows и Linux) ограничили его сверху значением 53, что дает этот самый битрейт 328 кбит/с.

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

#compiler

На фото типичная задняя обложка журнала или тетради в нулевые годы. Сейчас такого не увидишь (закон не позволяет или устарело?), но в то время я выбирал тетради с самым забитым задником, чтобы было на что посмотреть в школе 🔍

На кнопочном телефоне у меня было не так много Java-игр, плюс товарищи могли что-то передать по ИК-порту. Но однажды мне купили ШНУР по которому можно было с компа перекинуть все, и я стал "устанавливать все игры" 🖥

Ломая глаза об экран 240x320, я прошел все популярные игры, а для Gravity Defied я прошел все моды и даже пытался менять в .jar-файле что-то сам, получилось поставить картинку на фон и поменять окраску мотыка ⌨️

Обзор байткода Java 👩‍💻

Язык 👩‍💻Java появился в 1995 году и прошел большую эволюцию. Сначала он использовался для апплетов, выполняющихся в браузере. Потом для приложений Nokia и прочих кнопочников (подмножество J2ME).

Эти направления давно умерли, но язык живет - он популярен для разработки в Android, в финтехе и бэкенде (лучший в мире фреймворк для бэкенда 👩‍💻 Spring), есть много проектов (Kafka, ZooKeeper, etc.), появились интероперабельные языки - 👩‍💻Kotlin, 👩‍💻Scala, Closure.
Есть несколько реализаций компилятора Java и виртуальных машин.

Язык довольно простой, потому что на него наложена куча ограничений:
Весь код должен находиться внутри классов.
Тело функции надо писать сразу (нельзя как в C++ только "объявить" функцию).
Принцип "1 класс = 1файл" - в файле Foo.java должно находиться определение ровно одного класса с именем Foo.
Все типы, кроме примитивных (int, double, и пр.), неявно наследуются от класса java.lang.Object. Все методы виртуальные (кроме статических методов).

Генерики в языке - просто развод, их по факту нет. Они добавлены аж в 2004 году как синтаксический сахар 🍫
Все ссылки на объекты указывают на java.lang.Object, а в коде делается неявное приведение к типу.
То есть запись ArrayList<Foo> это самообман - в действительности хранятся ссылки не на Foo, а на java.lang.Object, просто есть неявное приведение к Foo и компилятор чекнет что в твоем коде нигде нет некорректных приведений 🔍

Чтобы примитивные типы можно было использовать в контейнерах, для них сделаны типы-"обертки", наследующиеся от java.lang.Object. Для int это Integer, для double это Double, и так далее.
Нельзя сделать ArrayList<int>, можно сделать ArrayList<Integer>.
Можно оценить оверхед - если std::vector<int> из 128 элементов это 4*128 последовательных байт в памяти, то ArrayList<Integer> из тех же элементов это 128 объектов (которые находятся хрен знает где в куче), каждый является оберткой над int-ом 🍔
Хотя в Java это нормально - он не задумывался как супер вычислительный язык.

После компиляции каждый Foo.java преобразуется в Foo.class, потом они все попадают в "исполняемый" .jar-файл, который является просто zip-архивом 📦
В начале .class-файла находится "constant pool", это константы (строки, длинные числа, и прочее).
Потом в файле находятся функции класса, скомпилированные в байткод.

В супер понятной официальной спеке можно увидеть примерный вывод компилятора в разных случаях, формат .class-файла, что должна делать виртуальная машина, и прочее.
Байткод очень простой - каждая команда состоит из 1 байта, называется "опкод", после него может быть 1-2 байта дополнительной инфы, если надо.
Команды разбиты на ~20 групп из почти одинаковых опкодов, список тут. Многие высокоуровневые, например опкод arraylength который положит на стек размер массива.

Компилятор (который переводит язык в .class-файлы) не делает никаких предположений о memory layout объекта, поэтому вызов метода выглядит так:

    invokevirtual #4 // каждый метод (кроме статических) является виртуальным

Где #4 это 4-й объект в "constant pool", являет собой "символическую ссылку", то есть тупо строку 😁
Если это метод int addtwo(int a, int b) в классе Example, то ссылка такая: Example.addtwo(II)I
Виртуальная машина должна сама все отрезольвить и подставить адрес метода.

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