C++95 – Telegram
C++95
1.52K subscribers
3 photos
21 files
115 links
640K ought to be enough for anybody

Author: @cloudy_district aka izaron.github.io
Download Telegram
C++95
Компилятор_языка_Си_для_микроЭВМ_Хендрикс_Д_z_lib_org.pdf
#retro #books #compiler

Обзор книги "Компилятор языка Си для микроЭВМ" (1989 г.) 📚

Эта книга - перевод на русский язык "The Small-C Handbook" 1984 года.

Я прочитал эту книгу, чтобы понять, как сильно изменились компиляторы за многие годы. Книга имеет историческую ценность как окно в реалии разработки 30-40 лет назад.

Как "микроЭВМ" рассматривается популярный тогда микропроцессор Intel 8080. Он имеет 8-разрядную архитектуру, семь 8-битных регистров, и 16-разрядную адресацию памяти (что дает адресацию 64 Кбайт = 65 536 байт памяти).

В странах Организации Варшавского Договора многие технологии копировались. Функциональным аналогом Intel 8080 была микросхема КР580ВМ80А, разработанная Киевским НИИ микроприборов, поэтому советские программисты могли успешно читать книги про Intel 8080.

Микропроцессор - вещь полезная, ее можно использовать в компьютерах, светофорах, принтерах, игровых автоматах, синтезаторах, измерительных приборах...

Под "Small C" понимается подмножество языка Си, которое самописный компилятор может скомпилировать. Small C слабо отличается от "полного" Си.
Доступны все основные конструкции, но например типов всего два - char (1 байт) и int (2 байта). Intel 8080 в базовой комплектации не умел работать с float-числами, для них нужен отдельный сопроцессор Intel 8231/8232.

Книга состоит из нескольких частей.
В ч.1 описан микропроцессор 8080, система его команд, обзор ассемблеров, загрузчиков и компоновщиков программ. Базовые вещи за несколько десятилетий не изменились.
В ч.2 описан язык Small C, который как по мне почти ничем не отличается от "полного" C.
В ч.3 самое интересное - описывается компилятор и все что с ним связано, как разные конструкции должны выглядеть в ассемблере, всякие мелочи (кросскомпиляция, etc.).

Прямо в книге приводится исходник компилятора - портянка на половину книги. Я нашел эти исходники на гитхабе, лучше смотреть там (файлы от cc.def до cc42.c).

Какие есть особенности у компиляторов того времени / такого типа:

🚀 Всего за ~3000 строк кода можно сделать свой компилятор Си на коленке, кому не лень. А сейчас LLVM занимает не меньше 11mln строк кода на C/C++.
Когда технология простая, то каждый может ее скопировать/сделать, но с развитием технологии выживают всего несколько реализаций.
Компиляторы C/C++, веб-браузеры, операционные системы - раньше их было значительно больше, но сейчас это единичные программы.

🚀 Компилятор однопроходный - парсит файл один раз сверху вниз. Компиляция очень быстрая.
Компилятор языка C++ уже не может быть однопроходным. Например, из-за шаблонов или constexpr-кода. Самый простой пример - парсинг класса: сначала парсятся сигнатуры всех методов и полей, только потом тела методов.
class TSomeClass {
public:
int GetValue() const {
return Value_; // C++ "видит" Value_, хотя он определен "позже"
}
private:
int Value_;
};

🚀 Нет никаких оптимизаций кода (кроме самых элементарных как сжатия выражения 2+3 в константу 5).
В книге есть глава о том, как писать "оптимальный код", там дикие советы наподобии:
🤯 "глобальные переменные лучше локальных"
🤯 "лучше всего сравнивать выражения с константной равной 0"
🤯 "++i лучше чем i++"
Потому что компилятор сгенерирует меньше ассемблерных команд, если им следовать!

🚀 Вместе с предыдущим пунктом - нет промежуточного представления кода (например AST) для анализа - компилятор генерирует ассемблер не отходя от кассы. Например, во время парсинга if-выражения создаются метки и команды условного перехода на метку.

🚀 Есть разнообразные ограничения с расчетом того, что компилятор сам работает на не то чтобы мощной машине.
Например нельзя иметь в файле больше 130 штук #define, названия переменных длиннее 9 символов, больше 200 глобальных переменных...
Сам код изобилует обращениями к глобальным переменным.
👍5🔥1😁1
#books

Обзор книги "C++ Lambda Story" 📚

(можно посмотреть тут - https://leanpub.com/cpplambda)

Как известно, язык C++ очень простой, всего лишь за 157 страниц можно понять, как работают лямбды в C++
Перед прочтением можно пересмотреть видеоприкол C++ Lambda Ace Attorney 😃

В книге есть исследование по всей сфере вопроса: как без лямбд обходились до C++11, и как возможности лямбд расширялись от стандарта к стандарту (C++14/17/20).

Изначальная идея лямбд простая - запись
    auto lam = [](double param) { /* do something */ };
...функционально должна работать примерно как
    struct {
void operator()(double param) const { /* do something */ }
} lam;
...то есть быть более простой записью для функтора (объект класса с operator()), которые широко использовались в C++98/03.

Все дальнейшие изменения в дизайне лямбд связаны с общим развитием языка, чтобы приспособить к функтору новые фичи.
Книга дает представление, как лямбды выглядят "внутри", поэтому многие рассмотренные вопросы становятся самоочевидными:
🤔 почему capture нужно делать только для автоматических переменных;
🤔 как делать capture для this;
🤔 серьезная разница между лямбдами которые ничего не capture-ят, и которые делают это; и многое другое...

Многое я уже знал заранее (даже лазил в части компилятора, который генерирует лямбды), поэтому мне было интересно, найдутся ли неизвестные мне интересные факты? Оказалось, что такое есть:

🚀 Начиная с C++20 можно создавать объект лямбды (раньше было нельзя)
auto foo = [](int a, int b) { return a + b; };
decltype(foo) bar;
// ^ (до C++20) error: no matching constructor for initialization of 'decltype(foo)'
это нужно для передачи типа лямбды, например как параметра в std::set - пример на godbolt

🚀 Начиная с C++17 можно использовать std::invoke для улучшения читабельности в немедленных вызовах лямбд:
auto v1 = [&]{ /* .../ }();
auto v2 = std::invoke([&]{ /* .../ });
пример на godbolt

🚀 Если лямбда ничего не capture-ит, то она может быть сконвертирована в указатель на функцию.
Если написать + перед лямбдой, то мы получим указатель на функцию, а не объект лямбды (потому что + можно применять на указатель, а на объект лямбды нельзя).
Это самый простой способ без static_cast-ов. Тред на stackoverflow.

🚀 От лямбды (точнее от ее класса) можно унаследоваться разными способами.
В таком случае получившийся класс будет представлять из себя класс с несколькими operator()(...) (с разными аргументами). Есть несколько паттернов, где это применимо, но выглядит это довольно жутко и редко где нужно.
Например, есть такой паттерн из доки для std::visit:
std::visit(overloaded{
[](A a) { std::cout << a.name << std::endl; },
[](B b) { std::cout << b.type << std::endl; },
[](C c) { std::cout << c.age << std::endl; }
}, something);

Остальные "приколы" меня не очень удивили: лямбды в контейнере, особенности лямбд в многопоточке, capture объекта [*this], шаблонные лямбды... Они выглядели самоочевидными, но кому-то может быть интересным 🙂
👍71🤯1
#compiler #cringe

Колхозное компиляторостроение 🌾🚜🐄

Мсье PG выложил критический пост про "компилятор Python в C++" с реддита.

Не стоит заниматься такими вещами, как компилирование (точнее, транслирование) Python в C++, потому что это совершенно разные языки.
При всем желании перевести получится только базовый минимум языка, без кода как val = 1; val = 'hello' (где меняется тип переменной).
Но это мелочи - посмотрим, чем является компилятор.

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

Там используется встроенный лексер питона (библиотека tokenize), чтобы получить лексемы (токены), а потом по этим токенам итерируются один за другим и просто транслируют слово на Python в слово на C++: compiler.py.
Таким образом малореально "скомпилировать" более-менее сложную программу на Python, транслятор очень негибкий.

Для таких задач лучше подходит встроенный лексер+парсер питона (библиотека ast).
Для AST используется идиома "visitor": можно "посещать" ноды дерева и генерировать код. Почти все тулзы для исходного кода (в том числе для трансляции кода) используют визиторы.
Примерно в таком стиле может выглядеть транслятор кода - gist.github.com

C++ по задумке нужен как "промежуточное представление", чтобы в конечном счете из Python получить оптимизированный бинарник.
Это тоже неудачная идея - лучше переводить Python в LLVM IR, потому что он более универсальный чем C++.
По запросу python llvm находятся какие-то проекты на эту тему.

В целом переводить Python "для оптимизации" в какое-то другое представление не имеет смысла - многие Python-библиотеки написаны на C/C++ и из Python у них только наружный интерфейс.
👍7
#library

Классическая механика на C++ - обзор движка Box2D 🚀

Box2D это физический движок, используется в основном в играх. Игры с Box2D можно посмотреть на YouTube. Самой популярной игрой является, наверное, Angry Birds.

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

✏️ "Фигура" в Box2D это круг, многоугольник (не больше 8 углов), или отрезок.
✏️ "Тело" состоит из 1+ фигур, можно придать свою плотность, коэффициент трения и упругость.
✏️ Телу можно придавать "ограничения", например запрещать вращение или движение по оси X/Y.
✏️ Между телами могут быть "связи", которые будут держать тела вместе, разных типов.
✏️ У "связей" также могут быть разные ограничения, например в эмуляции человеческого локтя ограничен возможный угол между частями руки.
✏️ "Мир" содержит в себе эти объекты и управляет памятью и эмуляцией движения.
✏️ В любой момент можно добавлять/удалять тела, применять силу, вращение, импульс... Также можно проверять коллизии тел, делать raycast, вычислять расстояние между телами и многое другое.

Эти понятия можно комбинировать в самые сложные конфигурации - пример транспорта на YouTube.

Константа time step определяет, сколько времени "прошло" с предыдущего перерасчета мира. Обычно мир пересчитывают 60 раз в секунду (time step = 1.0f / 60.0f).

В алгоритмах используется простая математика. Из старших классов школы - вычисление нормалей, матрицы вращения, произведение векторов, тригонометрия. Из первого курса вуза - метод Эйлера.

Box2D можно сбилдить всего за 5 секунд, даже вместе с тестовым приложением.
Он написан на суржике C и C++: не используются namespace, константы через enum, есть самодельные списки объектов и т.д.
Например, если объект должен находиться в списке, то указатель на следующий объект списка находится прямо в классе, а не "снаружи":
for (b2Body* b = myWorld->GetBodyList(); b; b = b->GetNext())
b->... // do something with the body

В Box2D используется реализация двух популярных типов аллокаторов:
💾 Аллокатор маленьких объектов (b2BlockAllocator) - вместо того, чтобы постоянно вызывать malloc/free для маленьких объектов, этот аллокатор сразу запрашивает 16kb памяти и создает объекты там (пока есть место).
💾 Аллокатор на стеке (b2StackAllocator) - на стеке лежит 100kb памяти, объекты создаются там.
Это позволяет во время "перерасчета мира" обходиться без аллокаций памяти.

Все объекты нужно создавать через "мир" (b2World):
b2Body* b = myWorld->CreateBody(&bodyDef);
Удалять тоже нужно через "мир", хотя деструктор b2World::~b2World() очистит всё что не удалено вручную.

Движок использует разные техники, чтобы быстрее делать перерасчет мира.
Если перемещение (угол/импульс/...) объектов считается быстро, то для быстрого расчета коллизий нужно использовать структуры данных.
Можно подробно почитать об этой проблеме на wikipedia. Целью оптимизаций является получение алгоритма за O(N) вместо O(N^2), где N-количество объектов.
Box2D использует "динамическое дерево" (b2DynamicTree) - весь мир делится на две части, каждая часть тоже делится на две, и так далее.

🐷 Можно на примере свинок из Angry Birds придумать игровую логику.
Если вы играли в Angry Birds, то помните, что свинки довольно хрупкие, но они могут остаться в живых (потеряв "здоровье"), если упадут с небольшой высоты, или на них упадет некрупная балка.
Мерой урона для свинки может считаться импульс коллизии с другим предметом.
strength = M_свинка * V_свинка + M_предмет * V_предмет

Можно итерироваться по всем "контактам" между телами, чтобы поймать начало коллизии:
for (b2Contact* contact = world->GetContactList(); contact; contact = contact->GetNext())
contact->... //do something with the contact

Но это неэффективно и некрасиво. Лучше использовать коллбек на коллизию через b2ContactListener
👍9🤔2
#compiler

[Часть 1/2]
Как работает статический анализ кода? Обзор clang-tidy 🧹🧹🧹

clang-tidy нужен, чтобы поправлять исходники C++ (или хотя бы выводить warning-и). В других языках такой инструмент называется "linter" и часто встроен в сам язык и/или стандартизирован (например PEP8 в Python).

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

Несмотря на то, что проверок уже почти 300 штук, все равно можно придумать идею для своих проверок.

✏️ Описание проверки
Я придумал свою проверку. Как до C++17 объявлялись константные переменные? По-правильному примерно так:
// в .h-файле:
extern const std::string DVCC_DVVC_BLOCK_TYPE_NAME;
// в .cpp-файле:
const std::string DVCC_DVVC_BLOCK_TYPE_NAME = "Dolby Vision configuration";

Вообще можно в .h-файле определить константную переменную, и это скомпилируется, но будет плохо, потому что const-переменные по умолчанию static. Это значит что каждый .cpp-файл будет иметь дело с локальной копией одной и той же переменной 👻
// так плохо! в .h-файле:
const std::string DVCC_DVVC_BLOCK_TYPE_NAME = "Dolby Vision configuration";

Начиная с C++17 можно записывать значения подобных переменных не отходя от кассы:
// в .h-файле
inline const std::string DVCC_DVVC_BLOCK_TYPE_NAME = "Dolby Vision configuration";

И вот моя проверка должна находить первые два плохие случая и предлагать писать по-новому, как в третьем случае.

✏️ Как это работает в коде
Я это сделал в феврале (тут pull request), но до прода не дотащил, так как ревью медленно проходит (примерно раз в три месяца).

Посмотрим по коду, как эта вещь работает ⚙️ Сначала надо ограничить возможные языки - нужен C++17 или выше:
  bool isLanguageVersionSupported(const LangOptions &LangOpts) const override {
return LangOpts.CPlusPlus17;
}

Clang переводит исходники в AST (Absract Syntax Tree). Проверки работают исключительно на AST Matchers - это конструкция для нахождения нужных нод дерева. AST Matchers пишутся легко, но из-за сложности стандарта они постоянно патчатся, чтобы покрыть крайние случаи 🐸

Надо придумать и "зарегистрировать" AST Matcher для интересующих нас нод. Это должны быть объявления переменных, причем глобальные константные не-inline переменные на уровне файла (т.е. не внутри класса).

Достаточно ли этого? Нет... Если посмотреть Стандарт, то окажется, что из рассмотрения нужно выкинуть переменные внутри анонимного namespace (их точно бесполезно исправлять), шаблонные переменные (они неявно inline), volatile переменные (тут не помню почему), а также переменные внутри extern "C" на всякий случай:
  auto NonInlineConstVarDecl =
varDecl(hasGlobalStorage(),
hasDeclContext(anyOf(translationUnitDecl(),
namespaceDecl())), // is at file scope
hasType(isConstQualified()), // const-qualified
unless(anyOf(
isInAnonymousNamespace(), // not within an anonymous namespace
isTemplateVariable(), // non-template
isInline(), // non-inline
hasType(isVolatileQualified()), // non-volatile
isExternC() // not "extern C" variable
)));

Регистрируем матчер для поиска extern объявлений (AST Matchers можно смешивать):
    Finder->addMatcher(varDecl(NonInlineConstVarDecl, isExternallyVisible())
.bind("extern-var-declaration"),
this);

Регистрируем матчер для поиска не-inline определений:
    Finder->addMatcher(varDecl(NonInlineConstVarDecl, isDefinition(),
unless(isExternallyVisible()))
.bind("non-inline-var-definition"),
this);
👍3👏2
#compiler

[Часть 2/2]
Как работает статический анализ кода? Обзор clang-tidy 🧹🧹🧹

В коде, который реагирует на найденную ноду, нужно определить текст warning-a:

  const VarDecl *D = nullptr;
StringRef Msg;
bool InsertInlineKeyword = false;

if ((D = Result.Nodes.getNodeAs<VarDecl>("non-inline-var-definition"))) {
Msg = "global constant %0 should be marked as 'inline'";
InsertInlineKeyword = true;
} else {
D = Result.Nodes.getNodeAs<VarDecl>("extern-var-declaration");
Msg = "global constant %0 should be converted to C++17 'inline variable'";
}

Если мы увидели, что переменная объявлена не в хидере, то ничего не делаем, возвращаем из функции (на уровне AST Matchers это пока нельзя ловить).

Теперь можно вывести красивый warning в месте объявления переменной.
Если у нас случай с определением не-inline переменной, то заодно можно поправить исходник, приписав "inline " перед объявлением переменной (во время работы clang-tidy поправит исходник):

  DiagnosticBuilder Diag = diag(D->getLocation(), Msg) << D;
if (InsertInlineKeyword)
Diag << FixItHint::CreateInsertion(D->getBeginLoc(), "inline ");

Теперь вы знаете, как примерно работает статический анализ кода 🙂
👍3🔥3
#story

Эмуляция физических процессов с использованием численных методов 🌊

Программы для всевозможных симуляций реальных объектов (вода, огонь, дым, стекло, ткань, теплообмен и пр.) занимают большой пласт в мире C++. Кроме академических исследований, это нужно в фильмах и играх.
Во время учебы в вузе я кое-что подобное делал на практикуме (с использованием суперкомпьютера и GPU NVIDIA)

Сначала физический процесс нужно описать математической моделью. Это теория, которую шаг за шагом проходят в вузах:
📚 Общая теория дифференциальных уравнений и всего что с ними связано (обычно 1-годовой курс в вузе)
📚 Векторный анализ, который впрочем у нас не являлся отдельным предметом, а изучался в рамках математического анализа ближе к концу 1.5-годового курса
📚 От физики обычно берут уже некие давно известные формулы - достаточно несколько месяцев изучать материалы по нужной сфере (гидродинамика/электромагнетизм/...)
📚 Предмет уравнения математической физики комбинируют прошлые шаги и досконально изучают некоторые уравнения за 0.5-годовой курс.

Как выглядят одни из простейших уравнений (без "источников тепла" и пр. влияний):
🔬 Уравнение теплопроводности (там есть гифка с симуляцией)
🔬 Волновое уравнение (симуляция на ютубе)

Что вообще нужно для компьютерной симуляции физического явления, кроме математической модели?
Моделирование происходит на конечной области (по пространству и по времени), поэтому нужны правильно заданные начальные и/или граничные условия - то есть состояние в области в момент t = 0 и, возможно, состояние на границах области в каждый момент t.

Этого достаточно для симуляции - то есть компьютеру не нужно искать аналитическое решение математической модели.
В некоторых случаях это даже невозможно сделать - до сих пор не найдено аналитическое решение уравнений Навье-Стокса (для симуляции жидкости)!

Область симулируемого явления представляется в виде сетки.
Представим, что мы в двухмерной модели имеем область NxM сантиметров. Тогда нам нужно выбрать "шаг" h см, так чтобы мы получили массив из (N/h)x(M/h) точек.
Теперь все функции модели дискретизируются, то есть вычисляются в данных точках.

Это нужно по простой причине - теперь производные можно вычислять на базе соседних точек. Вот что можно подставить вместо f'(x), т.е. производной от f(x):
(f(x+h) - f(x-h)) / 2h
а так можно представить производную второго порядка f''(x):
(f(x + h) - 2f(x) + f(x-h)) / 4h^2

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

Многие симуляции хорошо распараллеливаются, приводятся к матричному виду, и могут успешно вычисляться на суперкомпьютерах или на GPU - это еще один скилл, которым нужно овладеть 📚

А для красивой графики можно заиспользовать библиотеку по типу SFML. Правда, если планируется трехмерная графика, то нужно выучить такой же объем знаний в сфере Computer Graphics.

Вот так выглядит путь, чтобы научиться эмулировать физические процессы, понимая что происходит внутри 🙂

Бонус: симуляция аэродинамики разных предметов на ютубе 🎥
👍3🤯1
#madskillz

Итераторы с неопределенным концом 🏁

Итераторы это одна из главных концепций C++. У каждого класса контейнера (set/vector/list/...) в C++ есть свой соответствующий класс итератора (для доступа к своим данным).

Класс, для которого определен итератор, должен иметь методы begin() и end(), по вызову которых отдаются объекты итератора.
Класс итератора должен иметь методы operator++() и operator*().
Наличия этих методов достаточно для использования итератора в разных стандартных методах и в range-based for loop.

Обычно итераторы итерируются по всем объектам от begin() до end():
    const std::vector<int> vec{1, 3, 5, 7, 9};
// внизу аналог выражения `for (int value : vec) { /* ... */ }`
auto __begin = vec.begin();
auto __end = vec.end();
for ( ; __begin != __end; ++__begin) {
int value = *__begin;
/* do something with `value`... */
}

Однако бывают случаи, когда end() нельзя вычислить заранее и нужно делать на каждом шагу проверку, не пора ли выходить из цикла. В стандарте C++20 встречается такой костыль:
1️⃣ Завести пустой мусорный класс std::default_sentinel_t
2️⃣ Метод end() класса-"контейнера" должен отдавать объект мусорного класса
    std::default_sentinel_t end() { 
return {};
}
(а метод begin() продолжает отдавать объект итератора)
3️⃣ Класс итератора должен определить оператор сравнения с объектом мусорного класса:
    bool operator==(std::default_sentinel_t) const { 
return /* какое-то условие */;
}

В итоге старый код с итераторами работает как прежде, но завершается только когда оператор сравнения вернет true.

Какие есть реально используемые use cases:
🎯 std::counted_iterator - обертка над каким-нибудь другим итератором, итерируется по не более чем N элементам
🎯 Поддержка range-based for для корутин - чтобы можно было в цикле забирать новые значения от корутины, пока она активна (класс итератора - class Iter)
👍7
#compiler

Как компилятор замеряет скорость компиляции? 🕰

В C++ легко сделать так, чтобы проект собирался очень долго. В моем личном топе - юнит-тест (в виде одного .cpp-файла) компилировался 4.5 минуты.

К счастью, скорость компиляции можно дебажить. Во время компиляции одного файла нужно указать настройку -ftime-trace:
-ftime-trace
Turn on time profiler. Generates JSON file based on output filename. Results can be analyzed with chrome://tracing or Speedscope App for flamegraph visualization.
-ftime-trace-granularity=<arg>
Minimum time granularity (in microseconds) traced by time profiler

Команда может выглядеть так:
clang++ main.cpp -c -ftime-trace -ftime-trace-granularity=50

Получившийся json-файл main.json можно визуализовать на 🔬SpeedScope. (На гитхабе есть гифка, как это примерно выглядит)

Что делает компилятор:
⚙️ Перед началом компиляции, если задана настройка -ftime-trace, clang вызовет метод llvm::timeTraceProfilerInitialize.
⚙️ В этом методе проинициализируется объект структуры llvm::TimeTraceProfiler.
⚙️ Когда начинается какое-то событие, нужно вызвать метод llvm::TimeTraceProfiler::begin, чтобы запомнить время начала.
⚙️ Когда событие заканчивается, нужно вызвать метод llvm::TimeTraceProfiler::end, чтобы добавить запись о событии.
⚙️ Как видно по коду, используется стек, потому что события вложены друг в друга (например внутри события "компиляция файла" есть событие "распарсить класс").
⚙️ После компиляции файла вызывается метод llvm::TimeTraceProfiler::write для записи в json-файл.

По умолчанию параметр -ftime-trace-granularity равен 500 (500 микросекунд). Записываются не все события, а только достаточно "долгие", которые длились дольше чем 500μs - участок кода.

В коде нужные методы не вызывают "вручную" - используется стандартная идиома RAII в виде структуры llvm::TimeTraceScope.
Как видно, в момент вызова конструктора "событие начинается", вызова деструктора "событие заканчивается".
(если компиляция вызывалась без флага -ftime-trace, то этот объект не делает ничего)

Можно привести примеры - вот так засекается время на инстанциацию шаблонов (которая происходит после парсинга файла): PerformPendingInstantiations.
Пока происходит инстанциация шаблонов, засекаются всякие "вложенные" события, например InstantiateFunction.

Вот так компилятор нехитрым образом делает нужный flame graph 🙂
По моему опыту наблюдений за скоростью компиляции, "фронтенд" компилятора (парсинг файла в AST) занимает в 3-20 раз больше времени чем "бэкенд" (перевод AST в LLVM IR, оптимизация и перевод в бинарник).
Основная причина этого дисбаланса - огромный объем исходного файла после того, как раскроются все #include (в почти всех современных проектах на C++).

На основе этих данных становится видно, что нужно поправить, чтобы ускорить компиляцию. А впрочем, это уже совсем другая история...
👍81🔥1😁1
#compiler #advice

Не компилируйте шаблонный код каждый раз ⌨️

У меня есть травма детства, я не очень люблю шаблоны - считаю, что лучше их использовать в исключительных случаях. Есть не так много случаев, когда классы/методы должны быть шаблонными.

Я использую собственный индикатор: если параметры шаблона в теории заранее неизвестны, то он нужен (например std::vector<T>).
Если все параметры известны (например void make_sound<TAnimalCat/TAnimalDog/TAnimalBird>()), то лучше сделать виртуальный класс IAnimal.

Но часто приходится работать с устоявшейся архитектурой, поэтому представим, что у нас есть шаблоны для конечного числа параметров.

Сам шаблонный код еще ничего не делает. Только когда вызывается метод/класс с некоторыми параметрами шаблона, шаблон "инстанцируется", то есть генерируется уникальный метод/класс под эти параметры.
При компилировании каждого .cpp-файла (которых может быть сотни) мы часто вынуждены компилировать один и тот же участок кода - пример на godbolt.

Инстанцированные шаблонные методы имеют linkage type linkonce_odr, подробнее про него тут - https://news.1rj.ru/str/cxx95/38

Чтобы избежать компиляции одного и того же кода в каждом .cpp-файле, можно под шаблоном "объявить инстанциации" для всех известных параметров через extern template - пример на godbolt.
В таком случае где-то нужно "определить инстанциации" - для примера выше нужно в условном some_header.cpp написать:
    template int calc<float>();
template int calc<double>();
Теперь код в шаблоне будет компилироваться всего один раз.

Однако можно и весь шаблонный код держать в своем .cpp-файле, часто это упрощает читаемость - пример на godbolt.

Можно оценить полезность разных подходов:
🚬 Подход с extern template является полумерой, потому что обычно выигрыш в скорости компиляции абсолютно незначительный
🤤 Подход с шаблонным кодом полностью в своем .cpp-файле неплох, улучшает читаемость кода
Please open Telegram to view this post
VIEW IN TELEGRAM
👍6
#story

Корутины для чайников (таких как я) 🫖

Когда я пытался постигнуть, как работают добавленные в C++20 корутины, я лицезрел невеликое количество понятных объяснений в интернете.
Авторы начинают вспоминать, в каком году впервые появился термин, или впутывать в дело goroutines (из языка Go), или Boost.Fiber, или подсчитывать во сколько квинтиллионов раз корутины быстрее потоков... 😑

Базовую понятную теорию о корутинах я нашел тут: Coroutine Theory. С первой строки понятно, что корутина - это функция, которая может приостанавливать и продолжать (с момента остановки) свое выполнение пример на godbolt:
TGenerator<int> fibonacci() {
int a = 0, b = 1;
while (true) {
co_yield a;
a = std::exchange(b, a + b);
}
}
Место для переменных a и b не возникнет из ниоткуда (а стек использовать нельзя), поэтому память под локальные переменные должна аллоцироваться в куче (компилятор должен это поддержать). После этой теории два главных факта:
✍️ Корутины - синтаксический сахар (по типу лямбд), который иногда может упрощать код. Аналог фибоначчи без корутины.
✍️ Корутины как "функции с состояниями" перпендикулярны многопоточности, они никак ее не заменяют и никак ей не мешают.

Теперь настало время узнать задачи, которые решаются корутинами лучше чем другими средствами. Можно приводить в пример http-серверы, но это слишком неочевидный пример.
На мой взгляд, один из лучших постов: How to implement action sequences and cutscenes про сложную логику в играх.
Это не на C++, а на простом скриптовом языке Lua, но не меняет концепции (и корутины там легче выглядят).

C++ как обычно пошел хардкорно-укуренным путем 🚬 Он определяет только интерфейсы для корутин, а программист должен абсолютно сам писать event loop-ы и классы для awaiter/promise.
По этой ссылке есть игрушечный event loop для задач. Без специализации в этой области ловить нечего - нужно использовать уже готовые библиотеки, например lewissbaker/cppcoro или YACLib.

Корутины - вещь неплохая, но подход к реализации в C++ (с поощрением радикального велосипедизма) меня удивил. Общее впечатление (с опытом корутин в Lua/Python) совпало с этим комментарием на Хабре.
Please open Telegram to view this post
VIEW IN TELEGRAM
👍61
#advice

std::unreachable - безопасная стрельба в ногу 🔫

В C++23 стандартизировали метод std::unreachable, у которого лютое описание: invokes undefined behavior.

(До C++23 на linux можно использовать __builtin_unreachable)

Бывают случаи, когда совершенно точно известно, что значения аргумента в функции - ограниченное множество, но от нас все равно требуется что-то вернуть из функции при "недостижимых" значениях.

Пусть совершенно точно известно, что метод magic_func принимает только значения 1 или 3:
int magic_func(int value) {
switch (value) {
case 1:
return 100;
case 3:
return 500;
default:
/* ???????????? */
}
}
Нужно написать бесполезный код - что делать при значении не равном 1 или 3. Обычно делают два варианта:
    return 0; // возврат мусорного значения
throw std::exception(); // бросание мусорного исключения

Лишний код генерирует лишние инструкции - ссылка на godbolt.

Инструкция unreachable никакой семантики не имеет, и нужна чтобы показать компилятору, что данный участок кода "недостижим". Компилятор может как-то оптимизировать этот участок кода.
undefined behaviour значит, что в этом участке кода может происходить всё что захочет компилятор.

В нашем случае, если написать unreachable (ссылка на godbolt), компилятор выкинет лишнюю проверку и код станет таким:
int magic_func(int value) {
if (value == 1) {
return 100;
}
return 500;
}
Please open Telegram to view this post
VIEW IN TELEGRAM
👍8🔥2
#story

Обзор языка HolyC для TempleOS ✝️

TempleOS - операционная система, которую в течении многих лет в одиночку создавал программист Терри Дэвис. Разработка началась после психиатрической госпитализации, в ходе которой у Терри была диагностирована шизофрения. По его словам, Бог приказал ему разработать операционную систему, которая должна стать "Третьим Храмом". 🚬

Почти всю жизнь Терри был безработным, поэтому разрабатывал свою систему целыми днями, в свободное время на различных форумах толкая телеги про ЦРУ, "ниггеров", и богохульников.

Данный мусье распиарен, поклонники писали его биографию, делали ролики на ютубе. Он сам написал свой загрузчик, ядро, менеджер окон, графическую библиотеку, игры - это все на своем языке Holy C (С†) со своим компилятором.

Дизайн С† есть тут, а также тут можно увидеть примерные программы. Он похож на C с добавлением многих фичей.

Исходники компилятора читаются тяжело, но что-то понять можно.

Лексер, который разбирает исходники в токен, делает это с изменением текущего состояния в CCmpCtrl *cc, потому что разбор токенов происходит одновременно с разбором выражений.

Парсер, который разбирает выражения, сделан в виде простого рекурсивного спуска, например так выглядит парсинг if-выражения. Парсер создает блоки "промежуточного кода".

"Промежуточный код" оптимизируется многими способами, например есть свертка констант (описание на вики) и оптимизированное распределение регистров (описание на вики). Потом промежуточный код транслируется в ассемблер.

Из минусов компилятора можно назвать его однопроходность (из-за этого язык ближе к C, чем к C++), а также поддержка всего одной архитектуры.
А в остальном компилятор неплох, видно что автор был неординарным программистом, чтобы в одиночку писать все программы такого уровня (включая операционку).
Please open Telegram to view this post
VIEW IN TELEGRAM
👍61🔥1😁1
В последнее время я ничего не писал - решил написать на тему разработки в тонком клиенте 😎

#story

Тонкий клиент для разработки на C++ - с картинками! 😱

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

На примере Clang/LLVM: по воспоминаниям старожилов, ~5 лет назад его весь можно было построить в Debug-режиме на стандартном компьютере. Сейчас это невозможно, так как объем занимаемой памяти при линковке бинарника часто пробивает порог в 16гб RAM.
Приходится иметь билд в режиме Release или RelWithDebInfo - с этими режимами почти нереально дебажить, приходится ставить много дебажных выводов (как cerr() << Expr->size()), и сложно что-либо серьезное сделать. 😏

Можно иметь мощный домашний компьютер, но это неудобно (если нравится работать лежа) и его нельзя быстро перевезти.

Я уже много лет не разрабатываю что-то серьезное на самом ноутбуке. На работе использую рабочий виртуальный сервер, а в свободное время свой личный виртуальный сервер.

Личный виртуальный сервер можно создать много где - Yandex Cloud, Google Cloud, AWS, Microsoft Azure; в зависимости от преимуществ, средств (,и санкционного режима). Сейчас у меня машина на Yandex Cloud, с такими ресурсами:
🔍 ресурсы виртуальной машины
Там процессор Intel Cascade Lake, 32 ядра, 32гб RAM, 200гб SSD.
Сейчас это стоит ~11 540 рублей в месяц (на сайтах есть калькуляторы)

Этих ресурсов достаточно для всего - например весь Clang с нуля можно сбилдить за 13 минут (это во много раз быстрее чем на локальном ноутбуке), и дебажить через gdb/lldb.
Для системы можно выбрать любую ОС любой версии, это тоже в сотни раз быстрее, чем обновлять/ставить их вручную
🔍 список ОС

Зайти с локального ноутбука на виртуалку можно через SSH
🔍 кусок .ssh/config и вход в виртуалку
в моем случае по команде ssh -A mango

Конечно, тем кто не работал много времени с виртуалкой, будет сложно эффективно в ней работать. Я опишу используемые мной много лет программы.
Для эффективной работы я использую byobu, это терминальный оконный менеджер.
🔍 оконный менеджер byobu внутри виртуалки

Для написания кода я использую Neovim (форк Vim) - но это дело привычки. Многие коллеги используют Visual Studio Code, он умеет подключаться к виртуалкам по SSH, и просто более привычен для большинства.
🔍 neovim (у меня включены контекстные подсказки и автокомплит)

Для дебага я использую LLDB (аналог дебаггера GDB)
🔍 lldb в процессе

Система контроля версий тоже только изнутри виртуалки
🔍 git в виртуалке

Таким образом можно в процессе работы совсем не вылезать за пределы мощной виртуалки, а ноутбук иметь средней мощности. Я оптимизирую параметры ноутбука по легкости, чтобы он почти не чувствовался в рюкзаке.
Please open Telegram to view this post
VIEW IN TELEGRAM
👍13
#compiler

clang-format: царь-костыль 🩼

Я раньше писал про clang-tidy в этом блоге. Он нужен для проверки кода на качество. У него модульный вид - каждый может написать свою проверку и использовать множество независимых друг от друга проверок. Он работает на уровне AST, то есть код проходит лексический и синтаксический анализ до тулзы.

А clang-format это еще одна тулза, нужная для форматирования исходного кода - чтобы было нужное количество пробелов, отсортированные #include и прочее. Он работает на уровне токенов, то есть код проходит только лексический анализ до тулзы.

То есть clang-format очень приблизительно понимает, что перед ним за токен и что нужно сделать. Например, текст
class A: B {
ему это видится как последовательность токенов
(kw_class) (identifier) (colon) (identifier) (l_brace)

И clang-format применяет серию захардкоженных правил поверх этих токенов, с поддержкой разной фигни как стека вложенности для скобок. Никакой модульности нет, то есть все правила написаны прямо в глубине тулзы.

Например, в какой-то момент в середине работы вызывается метод WhitespaceManager::generateReplacements, который поправляет пробелы, и в нем внутри метод WhitespaceManager::alignArrayInitializers, чтобы поправить пробелы в массивах.

Совсем без семантики форматировать сложно, поэтому clang-format перед форматированием "аннотирует" токены дополнительными данными: сопоставляет каждому Token структуру FormatToken.
Там есть всякие поля, как bool IsArrayInitializer (то что этот токен - начало array initialization);
или FormatToken *MatchingParen (ссылка на закрывающую скобку).

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

Есть куча issue про clang-format, а чинить их значительно сложнее чем issue для clang-tidy.
Если в clang-tidy область потенциальных правок - код отдельной проверки (максимум несколько сотен строк), то в clang-format это весь clang-format.

Например, очень сложно починить такой пустяк как неработающее форматированое во вложенном внутри скобок array initializer. Дело в том, что форматирование полагается на "аннотацию" токенов, а оно именно такое для вложенных скобок, какое есть. Надо править "аннотатор", но это сложно и есть риск сломать что-то еще.

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

Поэтому старайтесь делать модульные программы, чтобы уменьшить область потенциальных правок при починке бага 😎
Please open Telegram to view this post
VIEW IN TELEGRAM
👍4😢4
#madskillz

Простой switch для строк 🎲

В C++ в switch-выражении в case не могут находиться строки или строковые литералы.

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

Такое жесткое ограничение сделано из практических соображений - switch-выражения в бинарнике могут трансформироваться в супер-оптимизированный вид с помощью branch table, когда по целочисленному значению аргумента просто вычисляется адрес кода, куда надо прыгнуть.

Понятно, что для строк branch table сделать нельзя, и эффективность switch-а не будет отличаться от кучи if-ов.

В других языках строки в switch возможны - Java 7, C# 6, но там нет упора на максимальную производительность.

Но можно сделать самописный простой "switch", чтобы упростить такой код:
    Color color = UnknownColor;
if (argv[i] == "red") {
color = Red;
} else if (argv[i] == "orange") {
color = Orange;
} else if (argv[i] == "yellow") {
color = Yellow;
} else if (argv[i] == "green") {
color = Green;
} else if (argv[i] == "violet" || argv[i] == "purple") {
color = Violet;
}
В такой:
    Color color = StringSwitch<Color>(argv[i])
.Case("red", Red)
.Case("orange", Orange)
.Case("yellow", Yellow)
.Case("green", Green)
.Cases("violet", "purple", Violet)
.Default(UnknownColor);

Реализация StringSwitch есть в llvm: StringSwitch.h

Внутри этого класса всего два поля:
1️⃣ std::string_view str - сравниваемая строка (в нашем примере argv[i])
2️⃣ std::optional<T> value - итоговое значение (в нашем случае T = Color)

При вызове метода Case, если value еще не заполнено и строка равна нужной, то value заполняется.
Есть методы EndsWith и StartsWith, которые заполнят value, если часть строки равна нужной.
Есть аналогичные case-insensitive методы, а также методы Cases для нескольких значений.
Наконец есть оператор приведения к нужному типу (в нашем случае к Color).

На мой взгляд, можно еще сделать класс LambdaSwitch, который в отличие от StringSwitch мог бы принимать лямбды, и ставить значение, если лямбда возвращает true. 😐
Please open Telegram to view this post
VIEW IN TELEGRAM
👍8
#retro #books #compiler

Рассказ "Редкая профессия" (1997 г.) 📖

Этот рассказ был опубликован в далеком 1997 году. Исходный PDF не сохранился, поэтому почитать можно здесь.

Рассказ о том, как команда из двух программистов занималась уникальной работой - созданием компилятора C++ в конце 90-х годов по заказу иностранной компании.

Читается легко - произведение передает дух времени, описывает трудности взаимодействия с забугорной конторой, денежный вопрос, проблемы менеджмента, общие вопросы разработки компиляторов и языка C++.

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

В сегодняшних условиях повторить этот подвиг не выйдет - поздно. Стандарт C++ с тех пор многократно усложнился, и работоспособных компиляторов единицы.

С компиляторами произошла та же история, что с веб-браузерами, операционными системами, игровыми консолями - раньше их было десятки и их мог сделать кто угодно на коленке, но усложнение сферы оставило лишь единицы выживших.
Please open Telegram to view this post
VIEW IN TELEGRAM
👍3🖕1
#books

Обзор книги "Team Geek" (2014 г.) 📚

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

Эту книгу мне подарили в сан-францисском офисе Google 5.5 лет назад, с тех пор она лежала без дела до недавнего времени. Но это хорошо - без длинного рабочего опыта я бы ее просто не понял.

Это книга не про C++ и даже не совсем про разработку, но она может помочь работать в команде более эффективно. Она разбирает типичные поведенческие особенности программистов, правила и принципы успешных команд, и многое другое в корпоративном мире. 😔

Книга толковая, нет инфоцыганщины. Она разбита на микро-главы, некоторые из них оказались лютой жизой, с которой я сам сталкивался 😱

✏️ Efficient Meetings
Чтобы митинги (как "необходимое зло" для многих программистов) не были бесполезными, лучше соблюдать написанные кровью законы:
1) На встрече для дизайна чего-то нового желательно иметь не более 5 человек, с бОльшим числом людей проводить ее сложно.
2) Если есть ежедневные митинги (стендапы), где выступает каждый член команды, они должны быть не длиннее 15 минут.
3) Митинг выбивает контекст работы, поэтому их желательно ставить возле interrupt point: до/после обеда, под конец дня и т.д.

✏️ Working in a “Geographically Challenged” Team
Цитата: "If the discussion didn’t happen on the email list, then it never really happened."

✏️ Code Comments
Цитата: "Comments should be focused on WHY the code is doing what it’s doing, not WHAT the code is doing."

✏️ Be a Catalyst
Цитата: "In many cases, knowing the right people is more valuable than knowing the right answer" - про контакты, которые разработчик должен иметь с другими разработчиками в корпорации.

✏️ Be Honest
Глава про важность конструктивного и понятного фидбека, в том числе про бесполезность сэндвича с говном. Многие люди просто не понимают или не так хорошо читают между строк, поэтому нужна прямота, если в коллеге что-то нужно изменить.

✏️ The Office Politician
Глава про офисных кидал среди коллег, которым нельзя доверяться, чтобы они не выезжали за твой счет и присваивали твои достижения.

✏️ The Bad Organization
Во многих компаниях главный продукт не софт, а что-то другое (банки, еда, одежда...), и программисты там просто вспомогательный персонал. В таких случаях резко выше риск, что с процессами в компании жопа - в главе есть общие признаки.

А топ-менеджеры просто не знают зачем ты здесь нужен как класс и зачем тебе платить в несколько раз больше чем уборщику.

✏️ Learn to Manage Upward
Самая лучшая глава - про визибилити. Чтобы расти вверх, нужно показывать ощутимые всеми вокруг результаты в виде графиков, запусков проектов в прод, и так далее.

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

Хотя без defensive работы не обойтись никак, она не дает никаких очков во время ревью. Цитата:
A team should never spend more than one-third to one-half of its time and energy on defensive work, no matter how much technical debt there is. Any more time spent is a recipe for political suicide.
Я бы дописал в главу это: Если вы все время занимаетесь только defensive работой, которая очевидно никого не впечатлит на ревью, то поздравляю - вас назначили лохом!
Please open Telegram to view this post
VIEW IN TELEGRAM
👍8🖕1
#story

Ускорение компиляции на C++ 🏃

Очень боянистая тема "ускорение компиляции" - это специальный вид спорта, в котором принимали участие многие разработчики на C++, которым не нравится медленная сборка. Я перечислю основные направления этого спорта.😃

Основным источником проблем является "N*M problem", почти все подходы стараются избежать именно его. Это значит, что если в проекте есть N хидеров и M не-хидеров, то суммарное количество распарсенных файлов в процессе компиляции будет стремиться к N*M, потому что каждый не-хидер компилируется отдельно и транзитивно подключает почти все хидеры, если за этим не следить.
Суммарный размер всех подключенных хидеров может достигать сотен тысяч строк.

Это актуально не только при билде с нуля. Если изменить какой-нибудь важный хидер, который включается почти везде, то это почти равносильно билду с нуля. В запущенных случаях изменения в почти всех хидерах триггерят пересборку с нуля.
В идеале надо стремиться к N+M, как это сделано во многих языках.

💪💪 PImpl
PImpl это супер боянистая идиома (почитать можно тут), чья цель изначально скрыть API класса, но от ее использования есть хороший побочный эффект - API может не подключать хидеры нужного класса, если там используется только указатель на класс!

Минусы:
Объект нужного класса придется хранить в куче. Но есть сильное колдунство Fast PImpl (https://news.1rj.ru/str/cxx95/27), которое впрочем имеет свои минусы.
Сложно поддерживать, нужна сила воли.

💪💪 Jumbo build (он же Unity build, он же Single Translation Unit)
Можно почитать тут. Unity-билд это подход, когда все файлы модуля строятся за один присест. Это значит что если у нас есть файлы "aaa.cpp", "bbb.cpp", ..., "zzz.cpp", то создается (желательно автоматически) файл который их всех подключает:
/* all.cpp */
#include "aaa.cpp"
#include "bbb.cpp"
// ...
#include "zzz.cpp"
И билдится только файл "all.cpp". Смысл в том, что если 90%+ времени компиляции занимает не сам файл, а хидеры которые их подключают, то такой подход почти линейно ускорит компиляцию.

Минусы:
Будут конфликтовать имена статических методов и переменных
Вообще это какая-то дичь и лечит симптомы, а не причины

💪💪 Precompiled headers
Можно почитать тут. Если у нас есть какие-то очень редко меняющиеся хидеры, то их можно "прекомпилировать".
Компилятор Clang делает это так - читает хидеры (например test.h), анализирует и сохраняет в типа уже "распарсенном" формате (например в test.h.pch).
Смысл в том, что если в коде где-то есть инклюд хидера test.h, то компилятор не будет его парсить с нуля, а прочитает test.h.pch, что будет типа быстрее, так как там уже готовое синтаксическое дерево файла.

Минусы:
Как я ни пробовал, у меня это нифига не работает значительно быстрее. В интернете много споров с этим подходом.

💪💪 Include What You Use
Это тулза для удаления лишних инклюдов. Есть хорошая документация. Иногда бывают баги связанные с тем что математически доказать ненужность инклюда нельзя - они все неявно влияют друг на друга.

💪💪 Быстрая виртуалка
Ускорять компиляцию можно не только руками. Здесь я описал, как можно использовать виртуалки с большими ресурсами для разработки - https://news.1rj.ru/str/cxx95/60

💪💪 Распределенная сборка
В крупных компаниях с крупными проектами используется распределенная сборка - что-нибудь готовое (distcc) или даже свое (недавняя статья от VK).
Эта большая тема, в статье круто описано как выглядит распределенная сборка 😃 Кроме того, чтобы не собирать всякие объектники по многу раз, можно использовать кэши - если твой коллега уже запускал сборку и ждал результатов, то тебе ждать не придется.

💪💪 Новый модный линкер mold
С линкерами в принципе проблем нет, но если у вас бинарь с Debug-символами в несколько гигабайт, то он может линковать вечность, по 2-3-10 минут.
Сейчас разрабатывается новый линкер mold, который типа быстрее других линкеров, но про него нет внятной документации и кое-кто жалуется на нестабильность и поломанные бинари.
Please open Telegram to view this post
VIEW IN TELEGRAM
🔥4👍3🤯1🖕1
#compiler #books

Обзор книги "Language Implementation Patterns" (2010 г.) 📚

(можно посмотреть тут - https://pragprog.com/noscripts/tpdsl/language-implementation-patterns/)

После прохождения в университете стандартных условно "компиляторских" курсов ("формальные языки и грамматики" и "конструирование компиляторов"), я увидел что они слабо относятся к реальному дело.

Реальные компиляторы написаны не совсем так, как сказано в кондовых теоретических учебниках. Мне как будто не хватало какой-то информации - например, ни одна грамматика не разберет сходу, что означает запись T(i) в C++, так как для этого нужно знать что такое T и i, а грамматики так не смогут. 😟

Книга Language Implementation Patterns супер информативная и содержит real-life теорию с кодом для реализации языковых тулз.
В ней разбираются всякие примеры как: интерпретатор байткода, статический анализатор кода, компилятор C/C++ (урезанный) и многое другое.

В книге есть 31 "паттерн" от простых к сложным, каждый паттерн описывает структуру данных, алгоритм, или типичную архитектуру для языковых тулз.

Паттерны разделены на 4 части: чтение ввода (I), анализ ввода (II), интерпретация ввода (III), генерация вывода (IV).
Самые простые приложения используют только I, сложные используют I+II+III или I+II+IV.
Для примера с моего старого поста (https://news.1rj.ru/str/cxx95/40): часть I объясняет "лексический анализ", часть II "синтаксический анализ", часть IV "кодогенерацию".

В книге не изобретаются велосипеды, а сразу дается правильная архитектура или вспомогательная тулза 🙂
Например, вся часть I может быть покрыта ANTLR - генератором парсеров (а автор книги - разработчик ANTLR), и свой парсер не придется писать.

Это экономит много времени, потому что у человекочитаемой грамматики (например в форме БНФ) могут быть супер неочевидные правила разбора, и надо самому вычислять множества FIRST и FOLLOW, а этому посвящается университетский курс... Генератор парсеров все делает за программиста по описанию грамматики.

Казалось бы - разве так много людей часто делают компилятор чего-либо? Но эта книга все равно будет полезна всем, кто делает свой DSL, тулзы для рефакторинга кода, форматирования, статического анализа, метрик.

Какие есть комментарии к книге:
🤔 Надо помнить, что разрабатываемый в книге примерный "компилятор для C++" делается для урезанного языка. В реальном мире анализатор для C++ это не LL(1) или LL(*), а скорее LL(k), где k - размер файла...
🤔 Весь код в книге написан на Java (ANTLR тоже на нем), возможно кому-то не понравится этот язык.
🤔 В одном из паттернов есть крохоборство для "буфера токенов" - прочитанные из файла токены выкидываются из памяти. Но даже в C++, где после препроцессора файлы могут быть в миллионы строк (и в N раз больше токенов) всё хранится в памяти.
🤔 В книге часто рекламируется генератор парсеров ANTLR, но для ряда сложных задач он выглядит трешово и намного более непонятным чем если бы это делалось в коде. Пример - когда "оптимизируем" код в языке для записи операция с векторами:
4 * [0, 5*0, 3] -> [4*0, 4*5*0, 4*3] -> [0, 0, 4*3]
предлагается сделать это прямо в конфиге ANTLR:
scalarVectorMult : ^('*' INT ^(VEC (e+=.)+)) -> ^(VEC ^('*' INT $e)+) ;
zeroX : ^('*' a=INT b=INT {$a.int==0}?) -> $a ; // 0*x -> 0
xZero : ^('*' a=INT b=INT {$b.int==0}?) -> $b ; // x*0 -> 0
🤔 В книге совсем не описана генерация в машинный код и сложные оптимизации. Это отдельная наука и большинству людей никогда не пригодятся эти знания. Но надо иметь в виду, что книга грубо говоря показывает как код на С++ переводится в LLVM IR.
Буквально на последней странице упоминается LLVM и рекомендуется его использование для компилируемых языков, так как там уже есть все для этого.
Please open Telegram to view this post
VIEW IN TELEGRAM
👍7🔥2🖕1
#creepy

Миф о виртуальных деструкторах 🍅

На собеседованиях и в реальной жизни часто встречается вопрос: "Зачем нужен виртуальный деструктор?"

В очень достоверном источнике знаний (то есть в интернете) практически везде написано в таком ключе:
Если у вас в классе присутствует хотя бы один виртуальный метод, деструктор также следует сделать виртуальным. При этом не следует забывать, что деструктор по умолчанию виртуальным не будет, поэтому следует объявить его явно. Если этого не сделать, у вас в программе почти наверняка будут UB (скорее всего в виде утечек памяти).

Но есть логичный вопрос: почему бы тогда компилятору не генерировать виртуальный деструктор автоматически (для классов с виртуальными методами)? 🤔
Ведь он кучу всего генерирует сам (например move- и copy-конструкторы, move- и copy-операторы присваивания).

Ответ: Потому что утверждение выше неправильное! 😱 Виртуальный деструктор нужен только тогда, когда есть риск, что объект класса-наследника могут разрушить по указателю на класс-предок.

Пусть есть базовый виртуальный класс DrinkMachine и его наследник класс CoffeeMachine.
Каждый объект программы рано или поздно надо разрушить, это делается в 2х разных случаях:
1️⃣ Объект создан на стеке, тогда программа сама вызовет деструктор
{
CoffeeMachine cm;
// перед выходом из scope сам вызывается cm.~CoffeeMachine()
}
В этом случае неважно какой деструктор (виртуальный или нет), потому что в обоих случаях вызовется то что нужно - деструктор реального объекта.

2️⃣ Объект создан в куче, тогда программист сам делает разрушение объекта, обычно так:
DrinkMachine* dm = ...; // возможно вместо `...` здесь был `new CoffeeMachine()`
// ...
delete dm;
(или если у нас объект по типу std::unique_ptr<DrinkMachine> - происходит то же самое)

Оператор delete обычно делает две вещи: вызывает деструктор и освобождает память:
dm->~DrinkMachine();
std::free(dm);

В этом случае важно чтобы вызвался именно деструктор реального объекта, т.е. возможно мы на самом деле хотели бы вызвать ~CoffeeMachine(). В этом случае нужен виртуальный деструктор - он будет лежать во vtable, и как метод будет находиться динамически.

Если второго случая в программе не бывает, то виртуальный деструктор не нужен - например в этой программе все работает без ошибок:
void MakeDrink(DrinkMachine& dm) {
dm.MakeDrink(); // вызов виртуального метода
}
void MakeCoffee() {
CoffeeMachine cm;
MakeDrink(cm);
// cm удалится сам через `cm.~CoffeeMachine()`
}

Это может быть важно для программ, которых нужно оптимизировать, потому что вызов виртуального метода (в т.ч. виртуального деструктора) дает оверхед в виде двух memory load.

P. S. Есть такой прикол как девиртуализация - когда компилятор сразу понимает какой метод нужно вызвать (не глядя во vtable). Но для этого компилятор должен доказать, что он точно знает, какой метод нужно вызвать. Хорошая статья на эту тему.

Девиртуализация не стандартизирована, поэтому нужно проверять на своем компиляторе самому - оптимизируется ли вызов виртуального деструктора в примере с MakeCoffee выше или нет. Если да - то можно забить и всегда делать виртуальный деструктор.
Please open Telegram to view this post
VIEW IN TELEGRAM
👍7🔥3🖕1