#list

Чуть-чуть разгребаюсь с беклогом (со скоростью черепахи конечно). Вот вам пачка ссылок почитать:

1. У Жени (автора @cxx95) есть вот такая замечательная статья про создание нового ключевого слова в C++: defer. И не читами с деструкторами и макросами, а честным патчем кланга.

2. В посте выше обнаружилась ссылка на статью про историю LLVM (местами правда со спорными тезисами). Довольно интересно.

3. The true price of virtual functions in C++.
Тут можно почитать о том, какие проблемы возникают при использовании виртуальных функций (с пруфами в виде бенчмарков) и о том, как с этим попытаться побороться, если вам оч надо. Стало чуть понятнее, почему иногда вместо наследования упарываются с CRTP.

4. Хороший (хотя может и немного скучноватый) доклад про рандом в плюсах. Тут разбирается их концептуальное устройство, какие-то проблемы с реализацией своего рандома и немного best practice.
По проблемам есть такой пример: пусть e -- какой-то random engine. Мы хотим сэмулировать бросок кубика:

e() % 6 + 1

Но такое решение имеет несколько проблем, из-за которых кубик становится не совсем честным. Предлагаю посмотреть : )

5. Ещё у меня есть список интересных вопросов на stackoverlfow, которыми хотелось бы поделиться (по чуть-чуть конечно🙃):
- про branch prediction;
- почему std::reduce требует для операции коммутативность (мы когда-то писали свой и не налагали такие требования, потому возник вопрос; спойлер: для векторизации);
- про использование auto вместе с приватными типами.

====================
В Москве видел машины убера с надписью Uber -> ub. Надеюсь, это не о качестве их кода.

#pub #algo
Пиу-пау.
Если вам так же как и мне нравится узнавать интересные (пусть и бесполезные) идеи, которые вы никогда на практике не заюзаете, предлагаю почитать мою новую статью про нестандартные (но простые) структуры данных.
https://habr.com/ru/post/673776/

#common

(сейчас будет капитан очевидность, но получите)

Я очень люблю рефакторить.

Прям кипятком ссусь. Сегодня в любом более менее взрослом проекте с несколькими разработчиками огромное количество кода. Всю смысловую нагрузку уже давно невозможно держать в голове. Ты можешь понимать какие-то основные подходы написанного. Может даже детали реализации (зачем именно так что-то было сделано). Но помнить абсолютно всё нереально. И это проблема.

Размеры текущей кодовой базы, в которой вы ежедневно сидите, только растут. С каждой новой таской вы приходите в пусть даже уже и знакомые (хотя часто всё равно нет) места и тратите время на то, чтобы понять вводные, которые вам код предоставляет. Иногда вы пытаетесь разобраться даже в своём собственном коде (я вот недавно наткнулся на непонятное место, которое накодил полгода назад; пришлось покопаться и вспомнить, что меня сподвигло на такой код). Рассогласованность действий разработчиков тоже подкидывает хаоса. Кто-то может сидеть в конкретном сервисе довольно продолжительное время, а кто-то мимокрокодилом пролетел и закоммитил что-то некрасивое/объёмное просто потому что он не знал, что принято/можно сделать лучше. После какого-то времени начинаешь замечать, что одни действия делаются по-разному, что где-то используются обобщения для сокращения количества кода, а где-то нет. С приходом новых участников возникает всё больше вопросов, почему тут сделано так, а тут нет. На это всё тратится время. Очень драгоценное время.

Чтобы со всем этим бороться, можно:
1. Помнить про ревью.
Делать хорошее ревью это важно. Не только с точки зрения корректности логики, но и удачности технической реализации. У меня иногда прохождение ревью занимает столько же, сколько и сама задача (и это не потому что я говнокодер, честно; а потому что ревьюеры обладает более широкой экспертизой и оставляют замечательные комментарии).
Отдавать на ревью не одному человеку. Понятно, что кто-то понимает конкретно в этом месте больше, чем другие. У меня недавно был кейс, когда один коллега оставил неплохое, но небольшое ревью на пр, а чувак из соседней команды, которому пр попался совершенно случайно, накидал комментов ещё на два целых рабочих дня. И всё по делу. Понятно, что тут стоит найти компромисс между полезностью и потраченным количеством человекачасов, но если есть возможность, почему ей не воспользоваться.
Если у вас нет практики ревью (такое бывает, да), всеми силами пытаться её ввести или хотя бы просить ревью на свои задачи. Особенно поначалу это позволяет многому научиться.
2. Тратить время не только на продуктовые задачи, но и на технические. Если в планы на следующий отрезок времени/спринт/самое ближайшее будущее у вас есть возможность запланировать/сделать/убедить коллег в необходимости что-нибудь зарефакторить, постарайтесь этим заняться. Это облегчит жизнь не только вам, но и всем разработчикам вокруг.
3. Ради бога, если вы в процессе решения задачи увидели что-то, что можно позже исправить, запишите это. А то некрасивый код так и останется неисправленным, пусть и обнаруженным. Всё помнить нереально и неполезно.

Сейчас речь идёт именно о (не)больших технических изменениях, потому что крупных продуктовых рефакторингов за свой небольшой опыт я пока не увидел (может вот сейчас наблюдаю за стартом такого процесса). Там всё примерно так же, только чуточку сложнее.

Есть кстати движение под названием Dead Code Society, которое продвигает идею выпиливания неиспользуемого кода. Слышал, что в больших компаниях есть похожие внутренние штуки (например довольно сильное в Meta). У нас тоже вроде что-то такое имеется, но как там у ребят успехи, хз. Свечку не держал.

UPD.
Рад, что вы пользуетесь реакциями кроме 👍 : )
Но их особенно приятно видеть.

#highload

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

Потому возникло такое понятия, как backend for frontend: набор ручек как прослойка между бекендом и фронтендом, которые объединяют популярные (и логические) связки вызовов ручек.

Давайте поймём, какие плюсы мы получаем от внедрения такого подхода.

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

Во-вторых, при использовании bff появляется возможность отдавать не просто результаты GET/POST/других запросов, из которых необходимо на устройстве пользователя согласно некоторой логике создавать отображение, а отдавать готовую html-разметку для тупого её отображения (мб с js-скриптами). Вы разгружаете клиент: ему достаточно сделать всего один запрос (ещё слышал, что индексирующие роботы при поиске делают лишь один запрос по адресу, потому ранжирование будет более точным и на основе всех данных, а не куска, который вернула всего одна ручка). На bff можно удалять ненужные данные, пришедшие с бекенда (информацию, ненужную для отображения/удалить ненужные данные при пагинации). Соответственно можно и менять status code ответа (т.к. правила для бекенда возвращать не 200 не всегда удобны для фронтенда и 200 им вполне сгодилось бы).

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

#list

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

2. Как известно, std::stack, std::queue, std::priority_queue это адаптеры (контейнеры, которые используют в качестве базы другой контейнер). С std::queue всё понятно. Тут определённо стоит использовать std::deque. У std::priority_queue по дефолту используется std::vector. Тут тоже всё хорошо. Но у std::stack используется std::deque. Seems strange. Ведь нам нужно только push_back, back и pop_back. Откуда такая неконсистентность? Я где-то читал, что это сделано, чтобы стек можно было использовать с некопируемыми объектами, ведь дек реаллоцируется без копирования. Но этот аргумент применим и к очереди с приоритетами. Короч тут непонятно.
С другой стороны, преимущество вектора это расположение данных в памяти подряд и скорость доступа к случайному элементу. В случае очереди с приоритетами это довольно важно. В случае стека нет. Ему это просто не нужно.

3. В std::forward_list нет метода size. Я так понимаю, что поинт такой: если вы используете односвязный список, вы пытаетесь экономить, потому экономьте максимально.

4. Известный факт, что методы/функции не умеют в частичную специализацию. Но что делать, если очень хочется? Можно написать обёртку с помощью структуры/класса.

5. Чувак на хабре рассказал про плюсы и выгорание.

6. Пост про мощь f-строк в питоне.

7. Очень забавный опрос про парадокс вагонетки с абсурдными вопросами. Займёт минут 10-15, но может вы что-то для себя поймёте : )

8. За последнюю статью на хабре у меня появилась возможность пригласить одного участника. Так что если вы не являетесь полноправным членом этого сообщества, но у вас есть желание что-нибудь запостить, приходите в лс. Если мне зайдёт (не хочется его в пустоту отдать), обязательно приглашу вас. Я не обладаю широкой экспертизой, но смогу накинуть каких-то комментариев по содержанию.

================
Недавно две недели наблюдал, как чувак пытался сбилдить проект на маке с M1. Решением для компиляции какой-то допотопной библиотеки было перенести объявление переменной чуть выше. Я думаю, вы понимаете, почему это может что-то починить, но в вакууме звучит как угар.
Поступило предложение запилить пропозал про выпиливание C++. Иногда я тоже об этом думаю.

#cpp

Набрёл на путеводитель по неопределённому поведению (Nekrolm/ubbok). Оставлю удовольствие прочесть вам это самостоятельно, а я расскажу об интересных вещах, моментах которые я не знал/не осознавал.

1. Одним из способов проверки уб в вашем коде может быть тестирование функций/методов на компиляции с помощью constexpr (т.к. в constexpr контексте неопределённое поведение не компилируется).

2. Integer promotion.
В С++ арифметические операции определены не для всех числовых типов. Например, для всех типов меньше int’а их нет. В таких случаях перед выполнением операций над любым указанным типом (даже беззнаковым!!) происходит приведение к int (знаковому!):

unsigned short x = 0xFFFF;
unsigned short y = 0xFFFF;
auto z = x * y;

Здесь будет переполнение int, которое является уб. Стало страшно.

4. std::min объявлен как (одна из версий)

template< class T >
constexpr const T& min( const T& a, const T& b );

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

const auto& x = std::min(1, 2);

Если вам это критично, можно использовать версию с std::initializer_list. Она возвращает по значению:

template< class T >
constexpr T min( std::initializer_list<T> ilist );

5. std::make_tuple применяет грубо говоря std::decay_t ко всем аргументам. Это вроде факт известный. Но интересно, что случай, когда аргументом является std::reference_wrapper обрабатывается отдельно, из-за чего тип такого аргумента станет T&.

И вот так делать не стоит:

std::tie(x, y) = std::tie(y, x);

Это unspecified.

6. Посмотрим на такой код:

std::vector<bool> v;
v.push_back(false);
std::cout << v[0] << " ";
const auto b = v[0];
auto c = b;
c = true;
std::cout << c << " " << b;

Как думаете, что он выведет?
Неправильно. Результатом будет 0 1 1.

Я давно знал, что std::vector<bool> таит в себе опасности, но чтобы такие…

7. В С++ есть правило: если что-то может быть засчитано за объявление функции, оно будет за него засчитано. И тут начинается разного рода флекс.
Когда-то в начале второго курса я хотел инициализировать поля класса с помощью вызова конструктора круглыми скобками, но программа упорно не компилировалась. Тогда я понял проблему лишь спустя несколько часов после сдачи контрольной работы. Будьте внимательными.

8. Интересный пример:

int x = 5;
auto x_ptr = &x; // валидный указатель, его МОЖНО разыменовывать
auto x_end_ptr = (&x) + 1; // валидный указатель, но его НЕЛЬЗЯ разыменовывать
auto x_invalid_ptr = (&x) + 2; // невалидный указатель, само его существование недопустимо.

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

Этот код содержит уб:

std::string str = "hell";
str.erase(str.begin() + 4 + 1 - 3);

Несмотря на то, что указатель str.begin() + 4 + 1 - 3 является валидным указателем, на моменте прибавления единицы мы получаем невалидный указатель, лежащий за end() строки -> ub.

9. gcc 1.7 в некоторых случаях уб (которое получалось задетектить) пытался запускать одну из нескольких игр.

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

===================
Если у вас есть свободное время, можете поправить опечатки/ошибки. Или может даже вкинуть свой необычный пример неопределённого поведения. Так сказать стать open source community member.

Как правильно заметил автор, 80% проблем с уб от висячих ссылок. Я когда-то смотрел лекции Ильи Мещерина по плюсам, где он сказал, что несколько раз в крупных проектах дебагал висячие ссылки. Тогда я посмеялся и подумал, как такое можно вообще допустить, а буквально через месяц 8 часов провёл за ровно тем же занятием на работе. Больше не смеюсь.

#list

1. Недавно думал, почему пустая структура в C++ всегда весит один байт (стандарт требует, чтобы у двух различных объектов были различные адреса).
Давайте подумаем, что может сломаться, если так сделать.
Как в таком случае должны выглядеть массивы? По факту это будет n элементов (число n компилятор часто хранит слева от указателя), расположенных по одному адресу. Т.к. объект нулевого размера не хранит данных, а всю информацию о типе компилятор имеет, можно все вызовы функций делать от одного адреса (это никак на объект не повлияет). В случае, когда мы делаем arr[i], компилятор может отдавать один и тот же элемент. Если объект используется как обёртка над какими-то операциями (в конструкторе/деструкторе), их вызов корректен (правда деструктор дважды по одному адресу это ub, но, предположим, закостылили). При итерировании по массиву мы помним число n, потому понимаем, когда пора остановиться, а когда начинается ub -> можем пытаться оптимизировать. По этим же причинам удаление массива -- операция конечная. Конечно возникают проблемы с реализацией end() для кастомных контейнеров, т.к. элемент, расположенный за последним, становится недостижимым, но условно можно обязать пользователей определять end() как arr + sizeof(char). На этом поиск проблем я остановил. Хотя есть ощущения, что сломается что-то гораздо более сложное (целый мир strict aliasing).
Понятно, что как будто можно было бы в такое научиться, но язык и так очень нетривиален, чтобы ещё такие навороты делать. Хотя зачатки подобного уже есть (EBO/EBCO, [[no_unique_address]], VLA/FAM о которых я уже упоминал).
Вообще зачем об этом думать. Например я в последнее время часто использую такую структуру:

template <typename T>
struct To {};

которая используется для tag dispatching. И раз такой аргумент нужен только для выбора перегрузки функции, можно было бы его оптимизировать в ноль байт. Как-то от этого и раскрутилась мысль.
Кстати Rust умеет как-то с типами нулевого размера работать: раз, два. Может какой-нибудь поклонник этого языка расскажет чуть больше в комментариях : )

2. Я думаю, все знакомы с правилом пяти. Оно гласит, что если вы определяете что-то одного из конструктор копирования/перемещения, аналогичных operator= или деструктора, вы должны написать и все остальные. Это не требование компиляторов, а правило хорошего тона, иначе вступают в силу сложные правила того, как работает компилятор при генерации остальных методов.
Интересно, что такой подход как будто противоречит single-responsibility principle, который говорит, что класс должен отвечать за что-то одно. Поинт в том, что если у вас определён хотя бы что-то одно из указанного, вы должны определить все пять == научить объект манипулировать данными ещё как-то кроме методов, поддерживающих некоторый инвариант класса.
Потому гораздо полезнее правило нуля: не писать никого вообще. И вы наверняка им пользовались. Если у вас в полях класса есть какие-то нетривиальные объекты, компилятор сам справится корректно их скопировать/переместить/удалить. Потому что, на самом деле, писать что-то из пяти этих особых методов вам нужно очень редко (чему конечно противоречит опыт обучения, когда мы постоянно переписываем какие-то (не)стандартные контейнеры и пишем подобное постоянно).

3. Чувак поясняет, почему double/float в любом языке программирования на самом деле не вещественные числа (спойлер: формально с точки зрения математики числа в компьютере не могут представить все вещественные числа). Статью заминусили. Как мне кажется, вполне справедливо, потому что если все в мире понимают о чём речь, зачем воду мутить?

4. Известный факт, что можно объявлять структуры/классы в функциях/методах. Но почему-то нельзя так же объявить шаблон структуры/класса. Причин никаких это запрещать не обнаружил. Даже нашёл бумагу с исправлением: link.

#list

1. В последней статье на хабре я писал про sparse set и приводил ссылку на реализацию в folly. Правда он был insert-only. Но ведь одна из его фишек именно в том, что его можно быстро чистить. Потому решил закоммитить это счастье (впервые что-то на кодерском коммичу в чужие репозитории; раньше коммитил в какие-то опенсорс сайтики: англ e-maxx и несколько других про алгоритмы). У меты интересный флоу работы с пр-ами: подписать какое-то соглашение (вроде норм), увидеть упавшие билды (мастер тоже не собирается), ревью, после чего твой пр они переносят во внутреннюю экосистему, где двое суток что-то собирается, и потом закрывают пр и видимо мержат опенсорсную версию folly и внутреннюю. Необычно.
Ещё у меня есть коммит в userver, но честно говоря, не коммит а параша)

2. Недавно увидел фичу на ютубе (хотя есть она давно): если навести на таймлайн видео, над красно-серой полоской будет полупрозрачная серая полоса, похожая на рельеф холмов в профиль. Это частота просмотров различных частей видео. Не знаю, как это реализовано, но, думаю, можно с использованием t-digest. Эта структура данных позволяет относительно дёшево хранить распределения величин. В ней у вас есть какое-то количество центроидов (центроид == диапазон значений + их количество в этом диапазоне). Если при просмотре пользователь задел диапазон, увеличиваете счётчик в центроиде для этого диапазона, после чего можете сгладить эти значения для красивого отображения.
Ещё такую структуру можно использовать для подсчёта перцентилей какой-то метрики. Например для промежутка от 0 до 100 процентов взять 200 центроидов и для любого значения (p50, p95, p98) брать префиксную сумму значений центроидов по этой метрике. Такая сд и реализуется не прям сложно, и является довольно информативной (особенно учитывая, что абсолютная точность вам не нужна).

3. Тут окончили обсуждать C23 (да, C; не C++). На первый взгляд выглядит, как будто C начинает местами догонять — и даже обгонять — плюсы, но мы-то знаем, что пропасть бесконечна…
Вот часть того, что комитет решил добавить в C23 (более полный список можете найти тут):
- #embed — возможность получать данные из внешних файлов на компиляции. По опыту go (go:embed) это и код экономит, и пользователя в рантайме не задевает. Удобно. В плюсах такое тоже тащат (последнее обновление было 20ого апреля);
- __has_include, который подъехал в C++20;
- гарантированное two’s complement для представления чисел;
- несколько новых директив препроцессора: #warning, #elifdef, #elifndef;
- уже знакомые из плюсов атрибуты: [[deprecated]], [[fallthrough]], [[maybe_unused]], [[nodiscard]] и [[noreturn]];
- realloc() с нулевым размером запрашиваемой памяти становится undefined behaviour (Andrei Alexandrescu на одном из докладов на CppCon сказал, что всего два человека в мире знают, когда правильно эту функцию использовать, похехал). Интересно, что такое изменение позволяет делать🤔;
- nullptr;
- немного прокачали енамы;
- constexpr;
- всякие литералы для чисел, разделитель разрядов ‘ как в плюсах, удаление триграфов (давно пора, хотя мы когда-то чуть-чуть так лабы в универе обфусцировали), auto (но я не нашёл пруфов, только на reddit писали) и ещё много всего.


Факт, что принимающая ноль аргументов в C функция должна помечаться void довольно известный:

int f(void) {}

Но я никогда не думал, что будет, если написать в плюсовом стиле:

int f() {}

Такая функция принимает любое число аргументов, но работать с ними как с VA_ARGS не получится: для этого нужно иметь хотя бы один аргумент. Например так:

void f(int numargs, ...) {}

#cpp
https://habr.com/ru/company/yandex/blog/678760/

#cpp

30 июля была яндексовая C++ Zero Cost Conf. Ощущения смешанные.

Антон Полухин сделал ещё один анонс, как и за пару дней до, о появлении userver в опенсорсе. Вообще странновато, почему они называют это секретной новостью на конфе, если днём ранее выложили пост, и несколькими неделями ранее выложили фреймворк в паблик на гитхаб (который был широко замечен, что как будто их удивляет).
Вообще мы в Лавке живём в юсерверной экосистеме, и по моим ощущениям это приятно. Я конечно не делал чего-то технически сверхсложного, но почти всё, с чем встречался, удобно.

Был приконый небольшой доклад про сжатие вещественных чисел в ClickHouse.

Новости из мира C++ от Полухина. В целом, всё то же, что было в недавней статье про C++23, но меня очень насторожило, что несколько раз звучала фраза вроде “круто, что у С получилось протащить, значит и в С++ появится”. Как-то мда.
Ещё он несколько раз шутил, что вот вы ждали эту фичу 30 лет, и вот она. Но это не смешно, это грустно…

Был доклад с 4мя кейсами про оптимизацию различных ситуаций. Первая — ускорение вычисления расстояния по координатам, хотя Андрей Аксёнов рассказывал об этом ещё в 2019м в рамках целого доклада.
В целом доклад не очень интересный, потому что описанные задачи довольно простые, и крутых идей в решениях я не увидел. Наверное не то, что хотелось бы на конфе такого уровня.

Более менее зашёл доклад про ускорение бинарного поиска.

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

========================
Иногда хочется поделиться рандомными мыслями, очень слабо связаными с прогой или не связаными с ней вообще. И не хотелось бы засорять этот канал, т.к. тут хочется двигаться в сторону образования, а не рассуждений. Потому я сделал @dzikart, чтобы делиться подобным там. Писать туда буду крайне нерегулярно и хз о чём вообще. Если вам интересно, приходите (минимум один человек сказал, что будет читать подобное : ) ).

Ещё у меня есть полумёртвый канал с мемами @memesfromhole.

#common

Сборщики мусора в других языках.

В Go используется улучшенная версия BF Mark, которая неплохо работает в многопоточной среде. Тут важным достижением сборщика мусора является то, что stop-the-world занимает константное время, как у ZGC в Java.
Единственная возможность настройки сборщика мусора -- это переменная окружения GOGC. GOGC есть размер всей кучи приложения относительно общего размера всех достижимых объектов, т.е. GOGC равное 100 означает, что размер всей кучи приложения на 100% больше размера всех достижимых объектов. Если требуется уменьшить общее количество времени работы сборщика мусора, стоит увеличить GOGC. Если же допускается отдать больше времени сборке мусора, но выиграть себе память — нужно уменьшить GOGC. Вот какая-то история успеха настройки сборщика мусора в Uber.
Тут вот есть какая-то статья под названием Go Does Not Need a Java Style GC. Можно освежить какие-то штуки в памяти и посмотреть на различия языков и, соответственно, их сборщиков мусора.

В одном из самых популярных компиляторов для языка программирования JavaScript под названием V8 используется композиция нескольких сборщиков мусора. Основной абстракцией при сборке мусора является сборка мусора с поколениями. Тут их 3, причём каждое лежит в своём сборщике мусора.
Самые молодые объекты появляются в оптимизированном mark-compact сборщике мусора. Обычно он добавляет освободившиеся блоки во freelist, но иногда принимает решение запустить операцию уплотнения. Следующее поколение -- объекты-подростки, которые содержатся в копирующем сборщике мусора. Последнее поколение живёт в простом mark-sweep сборщике. Из-за того, что он чистится довольно редко, высокая эффективность тут не требуется.

В C# используется оптимизированный mark-compact с тремя поколениями. В D используется сборщик мусора со stop-the-world этапами маркировки и фоновым sweep этапом. В языке программирования Nim существует несколько сборщиков мусора: подсчёт ссылок; mark-sweep; boehm; сборщик мусора Golang; оптимизированный подсчёт ссылок; оптимизированный подсчёт ссылок с разрешением циклов; отсутствие сборщика мусора.
Также сборщики мусора используются в других известных языках программирования: Rust (тут какие-то рассуждения о том, каким его можно сделать), BASIC, Dylan, Lisp и lisp-подобные языки, Lua, ML, Prolog и др. Даже у git есть (он там используется для уплотнения инфы и очистки лишней и запускается автоматически при некоторых популярных операциях, так что вы постоянно его используете : ) )!

=============================
Рано или поздно появится последний пост по сборщикам, в котором посмотрим на сборщики на/для C++. И тут конечно интересны больше технические моменты, чем концептуальные. Если вы не понимаете, как конкретно могут работать те или иные моменты в реализации gc для плюсов, напишите в комментариях. Постараюсь не забыть и написать об этом (если не разберёмся на месте).

#list

1. Интересный факт, что вот такой код является корректным:

void f() {
constexpr const MyType& var = some_global_var;
}

Подробнее, как и почему это работает, можно посмотреть в докладе Как объявить константу в C++?

2. Давайте посмотрим на такой код:

int a[] = {1, 2, 3, 4, 5};

struct A {
int a[] = {1, 2, 3, 4, 5};
};

Первое объявление переменной скомпилируется, а структура нет. Компилятор не справится вывести размер для int a[], т.к. у вас могут быть разные конструкторы, из которых размер выведется другой. Вот такой код выведет размер 5 для массива a:

struct B {
B() : a{1,2,3,4,5} {}
int a[];
};

Если же в структуре A сделать a static inline, то всё чинится (понятно почему). Где такое может сыграть роль? На уровне повыше:

class Type {
std::vector v{1, 2, 3, 4, 5};
};

Такое тоже не компилируется, но уже из-за того, что не работает CTAD (примерно по тем же причинам).

3. У знакомого (@KonstantinTomashevich) обнаружился блог про геймдев и C++. Если вам интересна специфика этой области, можно следить за новыми постами на канале.

Я в целом не поклонник геймдева (может как-нибудь расскажу в @dzikart), но какие-то технические моменты были интересны и познавательны.

4. Очень забавный видос (всего 7 минут) про неожиданные забавные конструкции в C++.

5. Хватит ссылаться на TIOBE.

6. В конце зимы узнал про escape analysis в go и всё хотел написать про это пост, но непонятно зачем, если есть хорошая статья.

7. Вкинул полмысли про рабочее время.

#algo

Деревья в алгоритмах 1/2.

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

Мне идейно очень нравится декартово дерево (пусть оно и довольно известно). Тут и все свойства обычного bst, и это в некотором роде вероятностная структура данных. А если писать неявное, то появляется возможность делать много разных операций как у дерева отрезков, но с большей вариативностью: перемещать части массива данных, менять местами чёт/нечёт и при желании даже копировать отрезки (с персистентной версией).
Splay-деревья тоже bst но обладают замечательным свойством: элементы, которые ищут чаще, со временем оказываются выше, что позволяет тратить меньше времени на их поиск в будущем. Хз, как часто они используются, но в вакууме свойство очень приятное.
Scapegoat tree в отличие от других bst старается не хранить в нодах ничего кроме key-value и указателей на детей и вместо небольшой перебалансировки на каждую операцию делает большие перебалансировки поддеревьев, но редко.

Рядом с обычными bst есть различные версии B-деревьев, которые активно используются в базах данных и файловых системах. Стандартное B-дерево это просто обобщение bst, где разрешается иметь более двух детей/элементов в ноде, что позволяет лучше работать с кешами + ускорить операции работы с большими блоками данных. Следующая версия B-дерева это B+-дерево, которое имеет немного другую структуру и быстрее работает при последовательном обходе. Тут же можно найти B*-tree (которое пытается плотнее упаковывать данные) и B*+-tree (которое, неожиданно, комбинирует фичи двух прошлых). Известными частными случаями B+-tree являются 2-3 и 2-3-4 деревья. Есть ещё какие-то чуть-чуть апдейченные версии вроде counted b-tree.

Далее идут различные боры (или префиксные деревья). Из интересного тут есть цифровые боры, которые позволяют работать с множеством чисел асимптотически эффективнее, чем со стандартными bst (в основном используя факт о максимально значении в множестве). Например это Van Emde Boas tree, X-fast trie и Y-fast trie (эти три умеют делать стандартные операции bst с лучшей асимптотикой, хотя может с памятью похуже), Fusion tree (а это в несколько новых операций). А есть вообще упоротые штуки вроде Hash Array Mapped Trie. Видел ещё ternary search tree, которое бор с не более чем тремя детьми. Это достигается введением нод разного типа и особых правил с ними. При использовании вы иногда просто юзаете ноды как ребро, опуская символ из неё. Ещё есть сжатые боры вроде Radix trie/Patricia tree.

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

#algo

Деревья в алгоритмах 2/2.

Очень часто деревья используются во всяких геометрических штучках. Самым простым примером кмк является binary space partitioning: вся плоскость это корень; по мере разделения областей к вершине, представляющей какую-то часть плоскости, добавляется два ребёнка (т.е. дерево всегда полное). Примерно таким же, но в терминах множеств объектов в мультиразмерном пространстве, занимаются ball trees.

Ещё сд:
- Rope -- это сд, позволяющая эффективно (ну +-) работать со строками; хотя олимпиадники любят использовать не по назначению, когда надо уметь обращаться по индексам во множестве;
- Zipper -- идиома из функционального программирования. Тут рядом есть Finger tree;
- дерево интервалов (не путать с деревом отрезков);
- или совсем молодое дерево палиндромов.

Пачка фактов:
1. Дерево отрезков можно писать за 2n памяти просто перенумеровав вершины.
2. Есть упрощённая версия реализации красно-чёрных деревьев — left-leaning reb-black trees (левое или может левацкое кчд). Аналогично есть левацкая куча. Ещё как вариация кчд есть AA-tree.
3. Слышал, что в STL любят кчд, потому что у тебя не более двух поворотов на каждую операцию, в то время как условное авл-дерево может сильно измениться.
4. Большинство индексов в базах данных построены на той или иной структуре данных. Тут можно посмотреть на небольшой лес.
5. По факту кучи тоже деревья (в графовой терминологии), но писать ещё миллион букав не хотелось, потому можете сами глянуть тут.

Если вы знаете ещё что-нибудь из этой оперы, смело накидывайте в комментарии.

#list

1. Нашёл вот такой proposal, где указано множество конструкций из C/C++, которые работают по-разному (и соответственно предлагается это пофиксить). Из интересного тут много кейсов с оператором запятая, скобками и тернарником (везде замешаны lvalue и другие категории значений). Ещё прикольно, что в C тип можно объявлять где хочется:

void func(struct S { int x; } s);

В С++ в отличие от C можно делать так:

void bar(void);
void foo(void) {
return bar(); // OK
}

Выглядит странно, но по факту это можно юзать как замену вызову функции и return в две строки.

Ещё символьные литералы в C это int, а не char (т.е. sizeof(‘a’) == sizeof(int)).
Вот такое тоже в плюсах не скомпилится:

char buf[] = u8"text";

потому что u8 это const char8_t, когда в C это char.

И пустую структуру/enum в C создать нельзя.

Короче тут гора всего интересного. Предлагаю изучить самим (дока правда огромная, но вы справитесь : ) ).

2. Давайте посмотрим на две сигнатуры функций:

template <int I> void f(A<I>, A<I+10>);
template <int I> void f(A<I>, A<I+1+2+3+4>);

При выборе перегрузки компилятор споткнётся, т.к. после инстанцирования они эквивалентны. Однако с точки зрения грамматики это разные сигнатуры, потому заранее такое задетектить не получится. Такой код ill-formed, no diagnostic required (ifndr), т.е. компиляторы вольны обрабатывать такой код любым удобным образом. Можно сказать, что это некоторого рода уб.

3. Узнал об aliasing constructor у std::shared_ptr. Какие-то дикие вещи совсем. Почитать можно вот тут.

4. Интересно, что в go использование указателей вместо значений несёт в себе гораздо бОльшие неприятности, чем в C++. Всё из-за сборщика мусора и escape analysis. Об этом можно почитать вот в такой интересной статье. Там же можно узнать, как эффективнее работать со слайсами и скрывать указатели от escape анализа.

5. Ещё вот нашлась статья под названием “Как мы себя обманываем, только бы продолжать пользоваться Golang”. Не скажу, что она убедительна, но что-то есть.

6. Небольшой тестик, чтобы выяснить, кто вы из C++.

#cpp

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

Известно, что шаблоны функций/классов должны реализовываться в хедерах, потому что при разделении на объявление/определение компилятор не сможет сматчить, где и что ему инстанцировать. Однако это не значит, что нельзя написать шаблон функции в одном месте (например хедере), а инстанцировать его в .cpp (при соблюдении некоторых условий). Делается это при помощи явного инстанцирования в .cpp и extern template в месте, где не нужно инстанцировать этот шаблон:

// .hpp

template <typename T>
T max(T lhs, T rhs) { return lhs; }

extern template int max<int>(int, int); // запретили инстанцирование на месте

// какой-то .cpp

#include <.hpp>

template int max<int>(int, int);

В данном случае мы спасаемся от инстанцирования функции в каждом месте, где происходит #include <.hpp>, и компилятор сможет найти уже инстанцированную вверсию в .cpp. Получается, можно экономить [на спичках] на инстанцировании, если вы знаете, какие типы будет принимать ваша функция. Ещё чуть-чуть можно увидеть у Жени.

Очень рад, что всё время за изучением SFINAE, было потрачено не зря, т.к. приходилось писать какие-то [тривиальные] проверки на наличие поля у структуры в шаблоннах функций, хотя если бы я увидел конструкции с std::declval и самим SFINAE впервые, мог бы знатно охренеть.

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

Думаю, каждый согласится, что знание типов переменных очень важно. И понимание кода стало затрудняться с появлением auto. Конечно, можно использовать аккуратно для недублирования типов или там, где они очевидны, но иногда все рамки адекватности нарушаются, из-за чего можно только страдать. Я использую вот такой небольшой трюк, чтобы узнать тип нужной переменной:

template <typename T>
struct Type;
[[maybe_unused]] Type<decltype(var)> tt;

Объявляем переменную incomplete шаблонного типа, после чего компилятор сообщит, что не получилось создать такую переменную, и напишет полный тип var без потери важной информации.

Т.к. в коде довольно много всяких std::variant и std::visit рядом с ними, приходится использовать очень крутую обёртку, использование которой выглядит примерно так:

std::visit(Overloaded{
[](const Type1& a) {},
[](const Type2& a) {},
[](const Type3& a) {},
[](const auto& a) {},
}, var);

А реализуется она вот так:

template <class... Ts>
struct Overloaded : Ts... {
using Ts::operator()...;
};
template <class... Ts>
Overloaded(Ts...)->Overloaded<Ts...>;

Кмк оч красиво и просто.

И самая конфета это математика.
Несмотря на то, что у нас дефолтный микрохайлоад с продуктовой разработкой, какие-то базовые штуки из матстата оказались довольно полезными. Например как аккуратно настроить аллерты, учитывая исторические данные, чтобы они пореже флапали. Тут можно покрутить доверительные интервалы и подобное, чтобы подобрать подходящие значения.

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

#cpp

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

Немного из метапрограммирования 1/2.

1. type_identity (С++20).

Это очень простой хелпер для реализации множества других type trait’ов:

template <typename T>
struct type_identity { using type = T; };

Например можно использовать вот так:

template <typename T>
struct remove_reference : type_indentity<T> {};
template <>
struct remove_reference<T&> : type_indentity<T> {};
template <>
struct remove_reference<T&&> : type_indentity<T> {};

Конечно же, можно сокращать гораздо более сложные конструкции.

2. void_t (C++17).

void_t это алиас на void:

template <typename…>
using void_t = void;

Это очень маленький кусочек кода, который позволяет творить на самомо деле очень крутые вещи. Обычно он используется для валидации выражений на компиляции и включения SFINAE.

Давайте посмотрим, какие с void_t есть проблемы.

struct One { using x = int; };
struct Two { using y = int; };

template <typename T, std::void_t<typename T::x>* = nullptr>
void f() {}
template <typename T, std::void_t<typename T::y>* = nullptr>
void f() {}

int main() {
f<One>();
f<Two>();
}

При попытке скомпилировать данный код, мы получим redefinition of function f. Но мы же знаем, что всё должно работать! Давайте попробуем заменить void_t на что-то другое (покажем только изменившийся код):

template <typename ...Args> using MyType = void;
template <typename T, MyType<typename T::x>* = nullptr>
void f() {}
template <typename T, MyType<typename T::y>* = nullptr>
void f() {}

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

struct MyTypeT {};
template <typename ...Args> using MyType = MyTypeT;

Сейчас мы увидим те же ошибки компиляции, что и ранее. Но если мы сделаем ещё одно небольшое изменение:

struct MyTypeT {};
template <typename ...Args> struct MyType : MyTypeT {};

всё заработает.

Или если мы реализуем void_t вот так:

template <typename T, typename…>
struct void_t_impl : type_identity<T> {}

template <typename… Args>
using void_t = typename void_t_impl<void, Args…>::type;

и заюзаем такой в первом примере, всё заработает!

Давайте поймём, почему не работает. template type alias’ы с C++11 являются упрощённой конструкцией в языке, специально чтобы все штуки вроде type_trait_t/type_trait_v работали как можно быстрее. И по факту они просто заменяются на то, что алиасят. В C++14 решили сказать, что все dependent штуки из шаблонов templated type alias’ов должны где-то запоминаться (хотя вообще-то никакого запоминания инстанцированных версий у них нет). Получилось противоречие в стандарте, когда вообще-то должно запоминаться и разруливаться в смысле SFINAE, но получается, что просто заменяется на void и ничего не работает. Тогда как со структурой такого не происходит.

Пример отсюда. Более подробное пояснение тут.

#cpp

Немного из метапрограммирования 2/2.

3. add_lvalue_reference.

Давайте попробуем написать стандартную метафункцию, добавляющую lvalue ссылку к типу (далее будем опускать написание алиасов _v/_t для краткости):

template <typename T>
struct add_lvalue_reference : type_indentity<T&> {};

add_lvalue_reference_t:
int&& -> int&
int& -> int&
int -> int&

А что для void? Для void ответ void& даст ошибку компиляции, что не очень приятно. Можем сделать частичную специализацию. Только стоит помнить про все возможные комбинации cv-квалификаторов, что означает не одну специализацию, а четыре. Плюс такое решение не является устойчивым во времени: во-первых, на текущий момент void единственный тип, для которого не может быть добавлена lvalue reference, но не будет ли в будущем ещё одного, неизвестно; во-вторых, cv-квалификаторы тоже могут расшириться до условных cvlgbtq-квалификаторов, из-за чего придётся дописать множество специализаций. Очень некрасиво и топорно. Хочется какое-то более аккуратное решение, которое будет работать для всех типов, которые вызывают подобную проблему. Можно сделать вот так:

template <typename T, typename Enable>
struct alr_impl : type_indentity<T> {};

template <typename T>
struct alr_impl<T, remove_reference_t<T&>> : type_indentity<T&> {};

template <typename T>
struct add_lvalue_reference : alr_impl<T, remove_reference_t<T>> {};

Работает это просто. Для вызова add_lvalue_reference<SomeType> происходит попытка сматчить вызов и частичную специализацию (т.к. частное всегда предпочтительнее общего). В этой специализации делается remove_reference_t<T&>, что для cv void не скомпилируется -> случается SFINAE -> специализация выбрасывается из списка кандидатов и выбирается базовый шаблон.
Этот код конечно можно упростить:

template <typename T, class Enable>
struct alr_impl : type_indentity<T> {};

template <typename T>
struct alr_impl<T, void_t<T&>> : type_indentity<T&> {};

template <typename T>
struct add_lvalue_reference : alr_impl<T, void> {};

В частичной специализации делается проверка на то, является ли выражение T& well-formed. Если да, то специализация для <T, void> срабатывает.

Аналогичным способом можно реализовать add_rvalue_reference, add_pointer и много других type traits.

Пример отсюда. Там можно посмотреть и несколько других более нетривиальных примеров.

4. Различные вычисления на компиляции могут замедлять время сборки вашего проекта. И вам может захотеться что-то сделать с этим. Но как померять время компиляции? Для clang в этом вам поможет флаг -ftime-trace. Я так долго откладывал рассказ об этом флаге, что кто-то уже это сделал, причём с разбором того, как это работает.

5. И из повседневных мелочей.
- Вот так интересно можно юзать кастомный компаратор для std::set:

bool cmp(X a, X b) { ... }
using Cmp = std::integral_constant<decltype(&cmp), &cmp>;
std::set<X, Cmp> st;

Лёгким движением руки мы сделали из функции структуру.

- Мне нравится, что посчитать N-е Фибоначчи втупую (через N-1 и N-2 числа) на шаблонах работает за O(n), когда через constexpr функцию за O(n!). Просто потому что инстанцирование шаблонов == мемоизация вычисленных значений.
- Вы можете написать почти все type trait’ы с помощью C++ (кроме очень специфических вроде is_union, is_class и др.), но в стандартных библиотеках множество из них реализуются через compiler intrinsics, т.к. это тупо быстрее.


Но вообще лишний раз подумайте, нужно ли вам заниматься чем-то подобным. На самом деле большинство проблем, которые вы можете захотеть решить метапрограммированием/SFINAE, решаются без этих инструментов гораздо проще и понятнее. Или ищите готовое (например в бусте). А лучше переходите на C++20.

#common

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

Поэтому и появился этот канал.

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

И поэтому я стараюсь влетать в другие образовательные инициативы, которые мне попадаются. Например этой осенью я буду менторить в яндексовой Школе Бекенд Разработки на треке по C++. Плюсовая ШБР запускается впервые. Там будут реально топовые лекторы, менторы и кураторы, которые широко известны своей деятельностью не только внутри компании, но и в сообществе. А некоторые из них мои непосредственные коллеги, у которых я за срок чуть менее года многому научился (и, чувствую, ещё многому научусь).

Сейчас идёт набор в Школу интерфейсов, а ещё в ШБР на три трека (С++, Python и Java). Флоу примерно такой: на первом этапе лекции и семинары, а на втором работа над реальными проектам в московском офисе Яндекса. Поступить просто: подаёте заявку, делаете тестовое до 14ого сентября 23:59 мск, после чего проходите интервью.

Узнать подробнее и податься можно тут: https://clck.ru/wcP34

===============================
Студентом в ШБР я не был, но пересматривал лекции прошлых лет (которые кстати вы легко найдёте в открытом доступе), и могу сказать, что вся инфа жутко полезна в реальной практике. Так что это очень прикладная программа для интересующихся.

#cpp

Сегодня тривиальный пост.

Как распарсится это выражение?

a+++++b;

Варианты:
- ((a++) ++) + b;
- a + (++(++b));
- (a++) + (++b);

Последнее можно отмести сразу, т.к. очень плохо обобщается на более сложные случаи (как вообще такое разбирать?). Давайте выберем из двух других.
В C++ разбор идёт примерно слева направо сверху вниз, причём в текущий токен парсер пытается набрать как можно больше символов (это называется maximum munch, т.е. такая жадная стратегия), потому тут конечно можно распарсить как a + ++++b, но можно добрать ещё один плюс, чтобы получился не бинарный оператор плюс, а постфиксный инкремент, потому верен первый вариант. Ну и тут же легко понять, почему это не скомпилируется: a++ это prvalue (значение оригинального идентификатора a изменяется, но возвращается копия), когда как инкремент/декремент требуют lvalue в качестве аргумента.

Обратите внимание, что если тут расставить пробелы, то всё будет работать как надо (потому что пробел заканчивает набор текущего токена).

По примерно тем же причинам до C++11 нельзя было писать что-то вроде

std::vector<std::vector<int>> v;

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

Я уже чуть-чуть писал про most vexing parse. Давайте посмотрим ещё чуть-чуть.

Когда вы пишете вот такое в глобальном неймспейсе:

Type func(OtherType);

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

class X {
public:
X() {}
X(Type obj) : obj(obj) {}
private:
Type obj();
};

Вполне можно думать, что раз приватное и мы инициализируем, то это поле, но это так же объявление функции с именем obj, из-за чего такой код не скомпилируется.

Или более дикие примеры:

struct X {};
struct Y {
Y(const X&) {}
void f() {}
};

int main() {
Y y(X());
y.f();
}

Код не скомпилируется на выражении y.f(), из-за того, как мы инициализируем объект y: на самом деле это тоже объявление функции y, возвращающей Y и принимающей X. По-хорошему конечно использовать фигурные скобки для инициализации: Y y{X()}, — а можно поставить ещё одну пару скобок вокруг X: Y y((X())).

Короч будьте внимательны и читайте ошибки компиляции.