Собрал посты за этот год.

2022: link.

Посты:
- ещё полезности из опыта;
- о шаблонах из доклада Alexandrescu;
- доклады с highload от 05.2022 и не только: первая часть, вторая часть;
- выжимка с открытой встречи РГ21 C++;
- про инициализацию;
- базово про кодировки;
- some cute tricks;
- про атрибуты;
- первоапрельский пост🤡;
- про проблемы с union и function-try-block;
- про ревью;
- несколько докладов с Saint Highload++ 2022;
- hashcash для пагинации;
- концептуально про рекомендательные системы;
- про разные оптимизации в C++;
- A/B-тестирование;
- чуть-чуть про содержимое gcc;
- С++ Zero Cost Conf 2023: Москва, Белград;
- проект моих ребят: 3music.app;
- про быстрое вычисление линейных дп матрицами;
- “обновил” пост про дженерики;
- про аналитику на фронте;
- про время;
- пачки фактов и ссылок: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19;

Про поиск:
- про различные задачи поиска;
- что обычно есть в поисковых движках;
- boolean retrieval model;
- про исправление опечаток.

Одна cтатья:
- три движка для одной Лавки: как эволюционировала система поиска в сервисе.

Одно выступление:
- обработка ошибок и C++ на Intern Meetup Week.

Не техническое:
- как я себя мотивирую табличкой в экселе;
- мотивашки на каждый день.

====================================

И про остальное. Фулл версия тут: t.me/dzikart/42

Подался на highload и не прошёл. Зато сгонял на него посмотреть вживую. Раньше таких мероприятий не посещал.

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

Почти весь год ходил к психологу и очень вкачал голову. Всё-таки, если с умом к этому подходить, можно ощутимо продвинуться.

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

Иногда пишу в @dzikart, иногда что-то пощу в @memesfromhole и недавно открыл @khdocs.

4 раза получал предложения что-то тут порекламить за денюжку. Не поддался (может быть пока).

Особо не болел. Занимался спортом. Наконец-то читал книжки и отрастил бороду.

Взял топ-1 на чемпионате по кикеру в минском офисе Яндекса😼

[Вроде пока] бросил [регулярное] употребление никотина❌

Новых татуировок нет.

Не умер, что особенно приятно.

#cpp

С Новым Годом🥳 Начнём 2024й с простенького.

Curiously recurring template pattern.

CRTP -- типичный подход к реализации статического полиморфизма.

Давайте посмотрим на реализацию:

template <typename Child>
struct Parent {
  int SomeFunc() {
    return static_cast<Child*>(this)->SomeFunc();
  }
}; 

struct Child : Parent<Child> {
  int SomeFunc() { return 228; }
};

Тут мы завели родителя, который предоставляет некоторый интерфейс и умеет вызывать метод у ребёнка, кастуя себя к его типу. А вот у ребёнка происходит наследование от родителя, которого мы параметризовали этим самым ребёнком. Потому этот подход так и называется.

static_cast к указателю на ребёнка из this называется "Barton and Nickman trick".

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

Parent* p = new Child;
std::cout << p->SomeFunc();

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

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

std::vector<Parent<Child>> v;

Другой тип тут нормально не положишь.

Пользоваться этим нужно аккуратно. Например в реализации выше следующий код -- ub:

// Parent<Child> p; p.SomeFunc(); // CE!

А ещё легко словить проблемы, если вдруг вы отнаследуете разные классы от родителя с одним и тем же параметром в шаблоне.

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

Где это используется?

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

Из примеров подобного -- std::enable_shared_from_this. Представим, что мы хотим сделать метод, который будет возвращать std::shared_ptr на наш класс:

struct bad {
  std::shared_ptr<bad> get() { 
    return std::shared_ptr<bad>(this); 
  }
};

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

struct good : std::enable_shared_from_this<good> {
  std::shared_ptr<good> get() {
    return shared_from_this(); // from enable_shared_from_this
  }
};

Обычно такую структуру реализуют с std::weak_ptr внутри, который и раздаёт std::shared_ptr.

Можно продолжить в этом направлении и реализовать, например,
- миксин, который будет добавлять operator>, если у класса есть operator<;
- миксин, при наследовании от которого у вас автоматически считается количество живых в данный момент программы экземпляров ребёнка.

(это простые задачки, так что оставим упражнением).

Для первого даже в буст либу завезли (boost::operators), которая позволяет избежать бойлерплейта при написании операторов.

Тут можно посмотреть больше примеров использования CRTP.

============================

Хорошего года, ребят🥳🥳🥳

#algo #cpp

🥳 Недавно понял, что в статье, где упоминал sparse set, не описал процесс удаления одного элемента из него.
Предположим, у нас есть такой sparse set:

dense: 0 1 2 3 4 |
sparse: 0 1 2 3 4

| показывает текущий конец сета.

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

dense: 0 1 2 3 | 4
sparse: 0 1 2 3 4

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

dense: 0 3 2 | 1 4
sparse: 0 3 2 1 4

Готово! Сделал пр в folly.
Мб про sparse set как-нибудь статью на хабр накидаю.

😎 Дальше с CppCon 2023:
- Exceptionally Bad: The Misuse of Exceptions in C++ & How to Do Better;
- The Au C++ Units Library: Handling Physical Units Safely, Quickly, & Broadly;
- C++ Modules: Getting Started Today;
- std::linalg: Linear Algebra coming to Standard C++.

На последнем мы немножко остановимся и глянем, что же там такое есть. cppref с описанием того, что лежит в хедере (правда там все подстраницы пустые ещё).

Хедер включается так:

#include <linalg>

Докладчик рассказывает про несколько важных кусков, о которых думают, когда речь идёт о библиотеках для линала:
- многомерные массивы и итерация по ним (доступно сейчас в C++17 и расширяется с C++23 (mdspan) и C++26 (submdspan));
- работа и базовые операции с векторами (в математическом смысле) и матрицами (как раз то, что предполагается затянуть в новой либе);
- low-level math problems, такие как решение систем линейных уравнений, поиск собственных значений и прочее (сейчас нет пропозалов по этим кускам в язык, но есть различные third-party либы);
- higher-level math problems: statistical inference и другие штуки.

Единицей работы с объектами является std::mdspan. Из базовых операцией над матрицами вы можете делать:
- scale -- умножение на скаляр;
- conjugated -- получение сопряжённой;
- transposed -- неоижиданно, транспонирование;
- conjugate_transpose.

Для векторов: scale, add, dot, vector_sum_of_squares, vector_two_norm, vector_abs_sum и другие.

Для операций матрица-вектор: matrix_vector_product и другие умножения, а так же какие-то rank-1 update, которые я сходу не осознал ввиду скудности остаточных знаний в математике.

Для матрица-матрица кроме произведения аналогично много всяких других произведений и каких-то апдейтов. Только ещё есть произведение/решение систем для треугольных матриц.

В целом большая часть доклада это рассказ про "стандарт" BLAST, эффективные вычисления и прочее около. В конце чувак показывает, как можно сделать разложение Холецкого с помощью новой либы.

🙂 Хотел недавно на clang 16.xxx + libc++ поюзать constexpr std::string. Хотелка в целом понятная и простая: завести constexpr переменную в global scope:

constexpr std::string kSomeVal = "string";

Круто, да? А вот хер там был! Почитайте пояснение. Так сказать, СМОТРЕТЬ ДО КОНЦА🤔❌❌

🤨 А ещё на днях не обнаружил у std::stack метод clear. И что это!

#cpp #common

🤔🤔🤔
На днях пришла гениальная мысль стандартизировать __builtin_popcount. Глупец! В C++20 уже есть std::popcount.

Вообще я помню свою небольшую эволюцию в подсчёте единичных битов. Очевидно, можно сделать втупую:

while (n > 0) {
if (n & 1) ++cnt;
n >>= 1;
}

Потом я узнал, что можно считать за кол-во единичных битов (ого как мы ускорились!):

while (n > 0) {
n &= n - 1;
}

А потом я нашёл статью на хабре и понял, что не знаю ещё очень много. Впрочем, ничего нового.

Там оказывается подвезли много всего. Из понятно-полезного std::has_single_bit -- является ли число степенью двойки.

🤨🤨🤨
Ещё недавно решил поюзать constexpr std::string. Основной кейс юзания у меня это завести константы вроде

constexpr std::string kSomeText = "short_text";

Круто, скажете вы! Не работает, скажу я. Можно почитать тут.

😏😏😏
Валера написал интересный пост про реализацию SharedMutex в yaclib: https://news.1rj.ru/str/reverse13/720

☕️☕️☕️
У Вадима Кравченко недавно вышел хороший пост про код-ревью.

Ну и хватит пока. И вам, и мне.

#cpp

Получился очень загруженный месяц. Чтобы не уходить в новый с одним постом закидываю второй😂

0. C++26 — прогресс и новинки от ISO C++.

1. На reddit есть тред про то, как сложно заставить вектор освободить память.

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

Естественным желанием будет вызвать clear(). Но clear() только установит size_ в ноль (ну конечно ещё почистит объекты). Это в целом логично и естественно, т.к. помогает писать более производительный код.

operator= тоже не чистит память. Например можно глянуть на __assign_with_size (одна из веток в операторе копирования).

Ну можно ещё попробовать shrink_to_fit(). И хотя обычно компиляторы честно чистят ненужную память, стандарт говорит, что это non-binding метод (i.e. необязательный). С другой стороны, ну говорит и говорит. Компиляторы обычно чистят, значит норм.

Стопроцентным вариантом будет просто присвоить пустой вектор:

vec = std::vector<T>{};

Ну или деструктор явно позвать🥳

> Пока копался c вектором, обнаружил новый метод в std::list: prepend_range (C++23). В других контейнерах подобные тоже подъехали.

2. [видео] Eric Landström: The bugs I remember.

3. Core Guidelines are not Rules.

4. И выцепил пару пропозалов из февральской рассылки:
- inplace_vector
- std::constexpr_v
- std::unitialized<T>

==============================
Там выходит C++Russia 2023 на ютубчик. Не хочу выкладывать по докладу. Подождём ещё какое-то время, пока появятся все доклады, которые мне понравились, и закину пачкой.

#highload

Выложили записи SaintHighload++ 2023! Делюсь тем, что понравилось.

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

1. Octree, или Сказ о поиске пути в 3D.
В общих чертах интересно. Всё-таки геймдев крута с точки зрения задач. Жаль, что я в среднем продукт не одобряю.
Есть правда ощущение, что то ли я глупый, то ли чуваки очень много всего проскакали галопом и местами совсем непонятно, что же имеется в виду и как это должно работать.

2. Групповые чаты в Одноклассниках 🙂

3. Как сделать поиск в интернет-магазине.
Задача мне хорошо знакомая. Специфика/проблемы тоже. Было интересно.

4. Архитектура ленты и рекомендаций ВКонтакте.
Пару моментов:
- на одном из первых слайдов докладчик говорит, что вот у них в p50 ответ за 600мс. Я чёт угарнул, потому что кто вообще смотрит на p50. Ну p95 ещё с натягом ок. Но как будто p98/p99 гораздо важнее, особенно для таких огромных сервисов. Выглядит как политический ход, т.к. в перцентилях выше какой-то разнос в таймингах.
- на другом слайде был скрин из паблика Душа пацана. Посмеялся.
- я когда-то ранжированием ленты был оч недоволен, потому что у меня паттерн в ВК был зайти и посмотреть 25 записей за последние сутки из трёх пабликов, на которые я подписан. А тут они начали что-то воротить. И отключить емнип первое время было нельзя. Но конечно понятно, что это всё на метрики в целом влияет почти наверняка хорошо.
- в какой-то момент докладчик начал рассказывать, как они генерят PHP код, с поведением эквивалентным поведению ML-модели, который потом по классике транслируется в плюсы. Hahaha, classic ☺️

5. 7 петабайт логов в Elastic. Как мы это сделали?
Неплохо про базу эластика рассказали с упором на свой кейс.

Вот так немножко получилось. Как-то остальное либо не заинтересовало, либо просто не понравилось в процессе.

#cpp

Наконец выложили все интересные мне доклады с C++ Russia 2023. Вот они слева направо:

1. Designing Robust APIs: How to Write C++ Code that's Safe, Extensible, Efficient & Easy to Use 🤔

2. Учим Кукушку Летать, или ConcurrentHashMap with Seqlocks 🥴

3. Санитайзеры и стандарт не спасут 🤨

4. Имплементируем класс tuple в 100 строк кода ☺️

5. C++ трюки из userver ☺️

6. Как правильно писать компараторы 🥳

7. Семантические процессы в C++ 🤨

8. И два отдельных, которые относительно похожи по теме + немножко расширили сознание про то, какие штуки чуваки делают на плюсах:
- Демосцена: в погоне за wow-фактором 🤔
- Sizecoding: взгляд изнутри 🤔

Ну напостил, теперь можно и отдыхать.