#video

Марсианские ужасы 👽

Как программист я часто имею дело с "воздушными замками": пишу код который работает с абстрактными в вакууме понятиями.

Неожиданно я наткнулся на видео, где разбирают софт для марсохода NASA (nasa/fprime). Сразу же, задыхаясь от интереса, открыл видео и принялся смотреть. Настоящей глыбой является мегадевайс, для которого писался этот код.

Первые 15 минут видео составляет унылое обозрение CI и велопарка .bash-скриптов для билда. Оттуда мы узнаем, что по авторитетной оценке анализатора lgtm.com репозиторий является редкой годнотой с качеством C/C++ кода A+.

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

В полном ужасе я обнаружил обзор на ядреную дедову смесь C89 и C++11, а от количества code smell у меня отклеились обои. Я стал свидетелем такого преступного программирования как:

Свои кривые реализации строки и вектора (буфера)

ObjBase::~ObjBase() {} // не делают ~ObjBase() = default
void resetSer(void);
ExternalSerializeBuffer(ExternalSerializeBuffer& other);
ExternalSerializeBuffer(ExternalSerializeBuffer* other);
const char* operator=(const char* src);
(void)snprintf(buffer, size, ...

В коде использование reinterpret_cast в 169 местах
Константы задаются через enum

Я думаю, надо сделать аудит NASA на предмет коррупционного сговора с lgtm.com о качестве кода. А также можно не бояться восстания машин, потому что Терминатор скорее будет страдать деменцией и стрелять себе в ноги, чем в Сару Коннор.

Комментарии к видео интереснее самого видео - работники разных European Space Agency подтверждают экстремистский уровень программирования в "научной" и "государственной" сфере.

#advice

Избыточный const снижает перфоманс ⏱

Правильное использование const это большая тема в C++. Самое крутое объяснение я видел на Const Correctness, C++ FAQ, но там не показан один из минусов "избыточного" const.

Пусть у нас есть структура, которая представляет собой API-объект. Содержимое этой структуры не планируется как-то изменять после создания, поэтому с первого взгляда логично, чтобы все поля были объявлены константными:

struct Widget {
    const std::size_t radius;
    const std::vector<Event> events;
    const Element element;
};

Но это плохо, если в коде объекты этого типа перемещаются, хранятся в векторе, и так далее.
Дело в том, что const-поля нельзя мувнуть, поэтому в записи Widget w2{std::move(w1)} поля events и element скопируются.
(пример на godbolt с логами)

Также константность полей часто просто не нужна - для нашей цели достаточно, чтобы константным был сам объект (или ссылка на него), а не его поля.

void Do(const Widget& widget);

#madskillz и #video

Успех применения идиомы Read-Copy-Update в C++

В видео За полгода - C++ Погода разработчик Яндекс.Погоды Дмитрий Старков рассказывает о переезде погодных микросервисов на C++ 🌤

До переезда Погода разрабатывалась на Node.JS + Memcached и отвечала за 300мс в 99 перцентиле. Это было медленно даже с кэшем, а после улучшения погодных предсказаний кэш стал сильно разъезжаться с реальными данными 👎🏻

Чтобы ускориться и улучшить утилизацию CPU, решили переписать на C++.
Для быстроты данные держатся in-memory, не в СУБД.

В памяти программа держит погодное состояние, которое регулярно читается (по GET-запросам от пользователей) и обновляется (по POST-запросам от поставщиков данных).

Обычный подход - shared_ptr:

std::shared_ptr<State> state;

И использование std::mutex с std::lock_guard для безопасного чтения/записи.

Более быстрый подход - использование std::shared_mutex и std::shared_lock (для читателей) и std::unique_lock (для писателей)

Однако такой подход все равно был недостаточно быстрым (в видео есть графики со "спайками"). Поэтому применили lock-free идиому Read-Copy-Update. Состояние живет тут:

std::atomic<std::shared_ptr<State>> state;

И читатель атомарно копирует объект, лежащий внутри std::atomic, прежде чем как-то с ним работать. Писатель также атомарно изменяет объект.

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

Переписывание обернулось успехом - при возросшем (за время переписывания) в 1.5 раза RPS Погода отказалась от рассинхронизирующих кэшей и стала отвечать за 30мс на 99 перцентиле! ⏱

#creepy

Двуликий inline для функций

Так вышло, что сейчас в C++ ключевое слово inline для функций (точнее, само понятие inline-функции) наделяет их двумя абсолютно ортогональными друг другу effective смыслами. Понятно, что один смысл вытек из другого, но все равно это раздельные сущности. Это:

(1) [dcl.inline].2: Подсказка компилятору о том, что более предпочтительна подстановка кода из функции в место вызова, чем сам вызов функции. (В компиляторе Clang в LLVM IR этот атрибут у функции называется inlinehint)

(2) [dcl.inline].6: Правило, что у функции может быть несколько определений (definition) за программу. Для отсутствия UB это должны быть одинаковые определения - что естественным образом соблюдается, т.к. обычно метод определен в хидере. (В компиляторе атрибут у функции называется linkonce_odr)

Получается, что у функции есть два атрибута - inlinehint и linkonce.

Прикол в том, что:
Стандарт написан так, что inlinehint подразумевается только у функций, где явно написан спецификатор inline.

Clang выполняет именно это, т.е. inlinehint ставится тогда и только тогда, когда есть спецификатор inline.

То есть получается вот что: inline int random() { return 4; } будет И inlinehint, И linkonce.

А вот методы, которые по Стандарту являются implicit inline functions, например:
(*) инстанциации шаблонов
(*) default и deleted члены классов, и их неявные методы
(*) методы, чей definition находится внутри definition класса
(*) constexpr- и consteval-функции (на самом деле только constexpr, т.к. consteval "испаряется" и в LLVM IR его код тупо не попадает)

... они только linkonce. Надо все равно писать ключевое слово inline, чтобы было linkonce+inlinehint.

Если бы я мог редактировать стандарт, я бы переименовал inline functions в linkonce functions, потому что текущее описание в Стандарте сильно запутывает...

Интересные вопросы:
(1) Так ли сильно влияет наличие атрибута inlinehint на компиляцию? Я слышал, что компиляторы уже давно не обращают внимание на подобные подсказки...
Влияет практически незаметно. Порог для инлайнинга у обычного метода 225 попугаев, для inlinehint-метода 325 попугаев (ссылка на код), а для реальной разницы нужно ~1000 попугаев.

То есть в 99% кейсов inline constexpr void foo() и constexpr void foo() будут вести себя одинаково, однако в clang-tidy не принимают патч на удаление redundant inline, потому что остается какой-то непонятный 1% кейсов.

(2) Почему один атрибут вытекает из другого, если они ортогональны?
Чтобы компилятор мог в translation unit заинлайнить (inlinehint) функцию, TU нужно "видеть" исходник этой функции, то есть её тело. В общем случае это невозможно обеспечить, потому что если у нас N штук TU, то будет N определений одной и той же функции и линкер сломается. Поэтому эта функция должна являться linkonce, чтобы не нарушился ODR.

#compiler

Прикладные linkage types в C++ 🔗

Стандартное добавление функции в C++ происходит так: в .h-файле пишется объявление функции (которое попадает в много translation unit), а в одном .cpp-файле пишется определение функции.

Чтобы определить функцию в .h-файле, чаще всего пишут спецификатор inline (это рекомендуемый путь), в несколько раз реже static.

Посмотрим, каким будет LLVM IR (компиляторное промежуточное представление C++-кода) для int sum1(), static int sum2(), inline int sum3(): ссылка на godbolt.

У LLVM IR есть интересный список linkage types для символов, типов много. Linkage type определяет, как ведет себя символ во время линковки в бинарник. (Символ - это функция или глобальная переменная)

▪️ У sum1 дефолтный linkage type external - возможно ровно 1 определение символа. Линковщик выдаст ошибку, если в программе будет 0 или >1 определения.

▪️ У sum2 linkage type internal - символ доступен только из того translation unit, где определен. Если в процессе линковки попадется одноименный символ, то линковщик просто переименует sum2, чтобы не было коллизии.

▪️ У sum3 linkage type linkonce_odr. Это типичный weak symbol, как и некоторые другие типы (linkonce, weak).
В программе может быть несколько weak-определений одного и того же символа.
Если все определения символа являются weak, то линковщик берет рандомное определение.
Если какое-то из определений символа является strong (как у sum1), то линковщик берет strong-определение.

В чем отличие linkonce от linkonce_odr?
▪️ В общем случае weak-определения могут быть разными, поэтому компилятор не имеет права заинлайнить вызов weak-функции (после линковки у функции может оказаться совсем другое определение)
▪️ Но Стандарт С++ требует от программиста обеспечить, чтобы inline-функции имели идентичное определение (это естественным образом достигается, если определение находится в .h-файле)
▪️ Поэтому компилятор имеет право заинлайнить вызов метода sum3 - программа от этого сломаться не сможет

Скомпилируем объектный файл

> clang++ -c link.cpp

На Linux получим объектный файл формата ELF. Используем утилиту readelf для чтения таблицы символов. Чтобы вывести исходные имена методов (не mangled-имена), используем утилиту c++filt:

> readelf -s link.o | c++filt

Получим такой вывод (опустил другие символы):

Symbol table '.symtab' contains 21 entries:
   Num:    Value          Size Type    Bind   Vis      Ndx Name
     6: 00000000000000c0    18 FUNC    LOCAL  DEFAULT    2 sum2(int, int)
    14: 0000000000000000    18 FUNC    GLOBAL DEFAULT    2 sum1(int, int)
    20: 0000000000000000    18 FUNC    WEAK   DEFAULT    7 sum3(int, int)

В общем случае выгоднее использовать inline-методы, чем static-методы! Потому что так меньше загрязняется бинарник, и все статические переменные внутри функции живут в количестве 1 штуки, а не в N штук:

inline int* get_address() {
    // `dummy` займет sizeof(int) памяти, а со static-методом было бы N*sizeof(int)
    static int dummy;
    // inline-метод - возвращает один и тот же указатель
    // static-метод - уникальный для каждого translation unit
    return &dummy;
}

#madskillz

Обертка над потоком вывода 🌊

У каждой крупной компании (и в FAANG) есть своя реализации std::string и/или разных строковых утилит.

Много где, прежде чем вывести немного видоизмененную строку в поток вывода (это объект с оператором <<, например std::cout, std::stringstream), создается новая строка:

log << "Value is " << valueStr.Quote();

Метод Quote() создаст новую строку с кавычками " по бокам. Такой код встречается тысячами, и вредит перфомансу ⏱, но это удобнее, чем выводить бесконечные "\"".

Попробуем сделать по аналогии с std::boolalpha "флаг" для "бесплатного" вывода строки. Мы хотим, чтобы можно было писать так:
log << "Value is " << quote << valueStr;
И это было бы аналогично записи
log << "Value is " << '"' << valueStr << '"';

Как это можно сделать?
Пусть выражение ((объект потока) << quote) вернет объект TQuoteWrapper, а запись ((объект TQuoteWrapper) << str) вернет исходный поток с записанным туда str.

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

inline constexpr struct{} quote;

template<typename TStream>
auto operator<<(TStream& stream, decltype(quote)) {
return TQuoteWrapper{stream};
}

Сам объект TQuoteWrapper имеет оператор <<, в котором записывает то, что нужно:
template<typename TArg>
TStream& operator<<(TArg&& arg) {
return Stream_ << '"' << std::forward<TArg>(arg) << '"';
}
По ссылке на godbolt можно посмотреть, что получилось 👍

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

Другой подход к "бесплатному" выводу строки в нужном формате можно посмотреть в библиотеке abseil - Writing to Stream. В нем потоку отдается "легкий" объект:
std::cout << absl::StreamFormat("\"%s\"", valueStr);
Но есть и свои ограничения - нельзя по-полному перепахать строку (сделать escape символов) через printf-like аргумент

#compiler и #story

Как написать свой компилятор? ⚙️🛠

По моему мнению, лучший туториал по созданию компилятора своего языка на C++: My First Language Frontend

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

В туториале рассматривается, как написать компилятор для простого тьюринг-полного языка, на котором возможны такие программы:

# Compute the x'th fibonacci number.
def fib(x)
  if x < 3 then
    1
  else
    fib(x-1)+fib(x-2)

# This expression will compute the 40th number.
fib(40)

По очереди разбираются типичные вопросы и pipeline:
(1) Лексический анализ - перевод исходного кода в лексемы
(2) Синтаксический анализ - перевод лексем в AST: абстрактное синтаксическое дерево (написание несложного LL(1)-анализатора языка)
(3) Кодогенерация - перевод AST в промежуточное представление LLVM IR; на этом этапе можно узнать теорию о SSA и графе потока управления
(4) Оптимизация кода - включение нескольких оптимизаторов (список оптимизаторов тут) и теория по ним
(5) Компиляция кода в объектный файл
(6) ... и по желанию многие другие вопросы: debug-символы, типы, управление памятью, стандартная библиотека...

В компиляторе языка C++ все вышеописанные куски имеют ультимативную сложность (и всякие нестандартные пункты как стадия препроцессора 🤯), но на примере простого языка можно разобраться, как работает компилятор и даже как создать свой.

Мне больше всего понравилась возможность слинковать код на другом языке с кодом на C++: сделал небольшое описание на github.

#creepy

Можно ли рекурсивно вызывать метод main()? 🔄

(минутка бесполезной информации)

Когда-то давно я читал набор вопросов к собеседованию по C++, и там встретился такой: "можно ли вызывать метод main() из программы"?

int main() {
    int n;
    std::cin >> n;
    if (n != 0) {
        return main();
    }
    return 0;
}

Казалось бы, зачем так делать почему бы нельзя было так сделать?

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

Linkage функции main() является implementation-defined (ссылка на стандарт): обычно имя функции не манглится. Также написано, что main() не должен вызываться в программе.

Стандарт говорит, что рекурсивный вызов main() запрещен (ссылка на стандарт).

Однако все современные компиляторы успешно компилируют такой код! Они могут выводить warning, если компилировать с опцией -Wmain: ссылка на godbolt.

Поэтому ответ на вопрос такой - рекурсивно вызывать main() нельзя, но компилятор будет компилировать это, если не указывать специальные флаги как -Wmain или -pedantic.

#books

Обзор книги "C++20: Get the Details" 📚

(можно скачать тут - https://www.group-telegram.com/progbook/6082)

Стандарт C++11 по количеству и влиянию нововведений был революционным для языка, он сделал C++ фактически новым языком.

Стандарт C++20 - самый влиятельный после C++11, с кучей новых вещей.

В книге на 530 (!) страниц описываются нововведения, то есть "дифф" между C++17 и C++20. Несмотря на размер книги, воды там нет 🚱 Все написано по делу, прилагаются самые подробные объяснения и примеры кода.

Чувствуется, что в книгу вложено огромное количество труда. Почти все вещи объяснены лучше, чем "в интернете" (на cppreference.com и подобных сайтах). Для "больших" нововведений описываются предпосылки и другая редкая информация.

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

#advice

"Это как std::vector, но на 20% круче" 🕶

Часто приходится иметь дело с множеством объектов, и также как-то их переупорядочивать, находить в них объект по ключу, и так далее - в зависимости от бизнес-сценария.

Пусть у нас есть объекты класса Meal (блюда ресторана 🍝), тогда обычно несколько блюд представляют так:

std::vector<Meal> meals;

И также где-то находятся методы, которые делают то, что нужно

void SortAlphabetically(std::vector<Meal>& meals);
void SortByCostDesc(std::vector<Meal>& meals);
const Meal* FindMealById(const std::vector<Meal>& meals, std::string_view id);

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

Я несколько раз успешно применял подход - унаследоваться от std::vector и определить там все нужные методы. Получается примерно так:

class MealList : public std::vector<Meal> {
public:
    static MealList ParseFromJson(const nlohmann::json& json);

    void SortAlphabetically();
    void SortByCostDesc();
    const Meal* FindMealById(std::string_view id) const;

private:
    MealList() = default;  
};

И определения методов находятся в соответствующем .cpp-файле.

MealList держит все методы "при себе" и при этом сохраняет всю остальную семантику std::vector (например, возможность range-based for loop).

#story #retro

Путь Александра Степанова - автора STL в C++ 🔆

Для современных детей смартфоны существовали всегда, и кнопочные телефоны - это что-то древнее и не стоящее внимания, а проводные телефоны - и вовсе атрибут фильмов про СССР.

Так же для программистов, которые начали свой путь 10-15 лет назад, STL существовал всегда. Однако STL имеет интересную историю.

Я наткнулся на страницу в Википедии про Александра Степанова - автора STL и прочитал ее, много интервью с ним, и некоторые его книги. Коллекция этих материалов есть на stepanovpapers.com.

У Александра, на мой взгляд, биография начинается крайне необычно:
⬛️ Родился в 1950 году в Москве
⬛️ В 1972 году закончил мехмат МГУ
⬛️ С 1972 по 1976 год работал программистом (разработка мини-компьютера для управления гидроэлектростанциями)
⬛️ В 1977 году эмигрировал в США

Я слабо представляю себе, сколько в 1972 (!) году в мире было полноценных программистов, которые реально писали свои дебаггеры, линкеры, операционные системы реального времени. Наверное, в то время это были единичные специалисты.

Также мне было интересно, каким образом можно было эмигрировать из СССР в США в 1977 году с таким важным бэкграундом, учитывая истории про необычные побеги в те годы. К сожалению, ни в одном интервью этот вопрос не затрагивается 🙁 Лишь какие-то избитые фразы как в интервью 2003 года:

Я покинул СССР, потому что не любил советскую власть, а Microsoft - это советская власть в программировании.

Однако вернемся к интервью и книгам. Любое интервью будет интересным, потому что раскрывает какие-то малоизвестные факты. Александр вообще создатель обобщенного программирования как такового, до C++ он реализовал этот подход в языках Scheme и Ada.

Можно почитать это интервью - там присутствуют приколы, например вопрос «расшифровывается ли STL как "Stepanov and Lee"?»; а также факт, что первые идеи про обобщенное программирование пришли Александру в 1976 году в полубессознательном состоянии, когда он находился в больнице с пищевым отравлением.
Также в интервью Александр высказывает мнение о ненужности ООП и Java (определенный как money oriented programming (MOP))

Из книг мне больше понравился Notes for the Programming course at Adobe 2005-2006.
На первых страницах Александр описывает, как он в 1972-1976 годах сам себя научил принципам хорошего кода.
Сначала он писал проект (например, дебаггер), через несколько месяцев переписывал его с нуля с знанием всех ошибок дизайна, затем это повторялось, и так далее.
Затем он писал проекты не как попало, а с учетом принципов (размер функции не более 20 строк, выделение общего кода в общие функции и т.д.). Этот эксперимент был крайне удачным и упростил разработку.

Александр заметил, что чем больше программа, тем меньше у нее application-specific (или non-general) кода и больше general кода.
В современных десктопных приложениях содержание non-general кода намного меньше чем 1%. Сейчас это самоочевидно, если посмотреть на объем кода операционной системы и Qt/WinForms. Но в то время это было далеко не так очевидно, потому что разработка велась очень близко к "железу".

Сейчас обобщенное программирование - обычное дело, но в те времена это было довольно контркультурное движение. Оно не соответствует концепции "top-down design", потому что это утверждение о том, что можно хорошо спроектировать какой-то компонент без особых знаний о том, как этот компонент будет использоваться 🤔

Из упомянутой выше книги можно прочитать первые несколько глав - там находится очень редкая информация о том, как правильно дизайнить обобщенные классы (как std::vector), и о том, как должны были бы выглядеть разные места C++ с точки зрения Александра (но Страуструп запретил). Потом в книге начинается переизобретение std::move (книга 2006 года), и это читать не имеет смысла.

#story #carbon

Язык Carbon как наследник С++ - о чем молчат его авторы? 🕵️

Многие уже слышали о языке Carbon, который Google представляет как "наследник C++". Всего лишь за несколько дней туда уже наставили 16k лайков.

О нем можно рассказать с трех точек зрения: (1) почему его делают, (2) что в нем планируется, (3) что может быть дальше.

🤔 Почему его делают?
По словам авторов, основной проблемой C++ является огромная сложность внесения в него изменений.

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

Окончательный баттхерт произошел в феврале 2020 года, когда комитет отказался ломать ABI (подробнее об этом можно почитать тут), тогда стало ясно что C++ продолжит развиваться черепашьим темпом, и Google стал подпольно создавать свой C++ 2.0

🤔 Что в нем планируется?
Самое главное - то, что C++ и Carbon могут подключать хидеры друг друга, то есть в наличии двунаправленная совместимость языков (как между Java и Kotlin). Я подозреваю, что это сделано через патч в Clang, который при виде файла с нужным расширением по-нужному парсит его в промежуточное представление, а дальше всё вместе оптимизируется.

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

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

(*) сам язык: pattern matching (как в Rust), рефлексия (пока доки нет, но будет), traits (тоже как в Rust), работа с типами, в будущем memory safety, и прочее...

(*) полно мелочей: адекватная иерархия наследования, классы final по умолчанию, проверка на NRVO, и прочее...

🤔 Что может быть дальше?

Здесь я опишу факты, в которых я +- уверен, а выводы на их основе можно сделать самому 👻

(1) У Google есть гигантский админресурс, чтобы продвинуть любой нужный партии язык в массы - реклама на C++-конвенциях, массовый выпуск курсов (например на Coursera), обучение в вузах...

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

(2) У Google есть технический ресурс, чтобы создать C++ 2.0 и не сильно обоср*ться, потому что многие очень активные контрибьюторы в Clang и в Стандарт C++ работают в Google.

(3) Самое печальное: "Экономика" развития C++ и Carbon будет кардинально отличаться.

Дело в том, что если в C++ контрибьютят в основном "подвижники", крайне заинтересованные в основном нематериально люди, то Carbon разрабатывается корпорацией.

При работе в FAANG (и в десятках компаний под них косящих) важно не то, как ты делаешь, а что ты делаешь.
Повышение при прочих равных получает обычно не чувак, который круто знает C++, хорошо делает задачи и покрывает тестами, а тот, кто выкатил какую-нибудь хрень с высоким visibility и показал красивые графики. И обычно всем пофигу что там нет тестов или код говно - выкатилось, ну и хорошо.

Поэтому есть риск, что из-за личных планов "выкатить что-то крутое, показать манагеру, и пойти на повышение" Carbon может проэволюционировать в какое-то болото.

#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 глобальных переменных...
Сам код изобилует обращениями к глобальным переменным.

#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], шаблонные лямбды... Они выглядели самоочевидными, но кому-то может быть интересным 🙂

#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 у них только наружный интерфейс.

#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

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

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

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

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

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

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