#common

Узнал про такую штуку как hashcash. Он используется в различных криптоштуках в качестве proof-of-work. Но сейчас мы не будем останавливаться на битке и подобных вещах. Хочется рассказать о том, как такое можно использовать в житейских простых задачах вроде пагинации (писал немного про неё тут).

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

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

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

Собственно примерно поэтому и называется hashcash: вы кешируете множество объектов с помощью кеширования каждого из них.

Ещё из проблем тут есть:
- т.к. хеширование двух различных объектов может давать один хеш, вы можете отсеять что-то, что на самом деле не показывали, но, насколько я могу понимать, это обычно не крит, потому что с таким же успехом товар мог отфильтроваться на каком-нибудь другом этапе рекомендаций (отбор кандидатов, после ранжирования оказаться слишком низко, реранкинг). Если такое возникает часто, опять же можно посмотреть в сторону других хеш-функций, которые дают более разнообразные результаты;
- т.к. с каждым запросом кол-во показанных сущностей растёт, сам курсор тоже будет расти. Тут можно выбрать какое-то ограничение для длины курсора с трейдоффом кол-во показанного юзеру контента <-> технические возможности вашей системы. Если вы понимаете, что из всех пользователей долистывает до 300ого айтема только полпроцента, может не так страшно не показывать больше 300 объектов? Ну и оч длинную строку парсить на бекенде не хочется, т.к. это потенциально таймауты (а ещё та же проблема на клиенте, а ещё нагрузка на сеть вырастает). Можно опять же выбрать хеш-функцию так, чтобы она давала более короткие хеши, но тут важно не переборщить, чтобы не получить прошлую проблему в большом объёме.

Концептуально про рекомендательные системы расскажу попозже.

#common

Рекомендательные системы 1/2.

Опустим часть с мотивацией нужности подобных штук.

Пусть у нас есть множество пользователей и айтемов, которые мы рекомендуем. И пусть у нас есть история оценок по каждому пользователю, как он оценивал те или иные айтемы. Задача — научиться предсказывать оценку пользователя по какому-то ранее неоценённому айтему.
У вас может не быть явной системы оценивания, но могут быть другие сигналы — клики на айтемы, покупки айтемов, их просмотр/прослушивание, если вы какой-то видео-/аудиохостинг. Потому фидбек от пользователя делится на explicit (когда он явно сообщает, что ему что-то (не)нравится) и implicit (когда непонятно, нравится ли пользователю что-то, но можно выдвигать гипотезы, что действие пользователя означает).

Часто в таких штуках применяется коллаборативная фильтрация — методы в рексистемах, основанные на похожести айтемов и взаимодействии пользователя с айтемами.
Из терминов рядом ещё есть User2User (user based) и Item2Item рекомендации. Думаю, тут смысл понятен.
Есть ещё контентный подход — когда рекомендуют айтемы по схожести контента в них.
Ну и гибридные есть, которые сразу обе концепции совмещают, потому что у каждого подхода есть свои pros/cons, которые при совмещении могут закрываться.

На этапе ранжирования важной проблемой является кол-во данных. Фактически не представляется возможным отранжировать все существующие айтемы и взять из них топ, просто потому что это очень трудозатратно. Потому есть отбор кандидатов — какой-то относительно дешёвый способ сузить общее кол-во айтемов к небольшому множеству, чтобы все последующие действия производить только с ними. Тут конечно важно не испортить полноту айтемов, чтобы было вообще из чего в итоге выбирать. Как это можно делать:
- эвристически: выбирать самое популярное (в целом, или по геопозиции, или среди такого же возраста, или что угодно ещё);
- коллаборативно (item2item): офлайн посчитать 100 похожих айтемов для каждого, сложить это в какое-нибудь key-value и в онлайне взять для ста интересующих нас айтемов по 100 кандидатов. Отскорить итоговые 10k;
- юзать контентные похожести (взять какое-нибудь hnsw и для каждого айтема брать 100 самых близких в пространстве объектов);
- что-то продуктовое: докинуть чего-нибудь нового, например.

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

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

#common

Рекомендательные системы 2/2.

Есть ещё такой трабл как feedback loop. Это когда рексистема из-за того, что рекомендует какие-то конкретные классы айтемов, будет всё чаще рекомендовать именно эти классы айтемов, т.к. по ним всё больше и больше фидбека. Ещё система может подстроиться под большинство популярных айтемов/пользователей и каким-то конкретным, выбивыющимся из общей картины пользователям, рекомендовать не самый подходящий контент.
Простые решения тут:
- можно подмешивать случайные айтемы в выдачу;
- делить рекомендации по тегам/темам/чему-то ещё.

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

Можно ещё сказать, что поиск и рекомендашки похожи по задаче, но в поиске у вас обычно есть какой-то конкретный запрос, когда в рекомендациях запрос — история поведения пользователя, что немного задачу усложняет.

Но я не настоящий сварщик в мльных штучках всяких. Просто интересно стало.

#cpp

Немножко отдельных фактов из одного доклада с C++ Russia.

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

delete [] { return new int; }();

Скомпилируется ли этот код? Ответ: нет. А почему?

Семантически этот код можно считать корректным. Мы вызываем лямбду, которая возвращает нам указатель на выделенную память, которую тут же удаляем.
Давайте посмотрим на грамматику для [expr.delete]:

delete-expression:
:: opt delete cast-expression
:: opt delete [] cast-expression

Т.е. тут либо delete с [expr.cast], либо delete []. Вроде всё корректно. У нас может быть выбрана первая альтернатива, потому выражение является корректным. Однако если почитать стандарт повнимательнее, мы увидим

Whenever the delete keyword is immediately followed by empty square brackets, it shall be interpreted as the second alternative.

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

2. Из интересного ещё такой пример:

int override = 0; // ok
int private = 0; // error

Почему первое работает, а второе нет?
В языке есть специальные слова, которые не являются ключевыми. Они являются идентификаторами со специальным значением (final, import, module, override). И если у компилятора есть сомнения, является ли это специальным значением, он разрешает это в пользу ответа нет. Т.е. подстраивается под существующий контекст.

Эти два примера из очень приятного доклада Константина Владимирова про семантические процессы в C++.

У автора, кроме потрясающих курсов по плюсам на youtube, есть ещё канал в тг: @cpp_lects_rus.

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

=========================
У меня тут на днях google benchmark не хотел в cmake подтягиваться, потому что чуваки переименовали master в main. Вот она западная толлерантность. Из-за неё проекты не собираются.

#highload #cpp

1. Старые песни о главном: How to design software architecture: Top tips and best practices.

2. eBay’s Blazingly Fast Billion-Scale Vector Similarity Engine.

3. API Design Reviews Are Dead. Long Live API Design Reviews!

4. Solving Undefined Behavior in Factories with constinit from C++20.

#cpp

Немножко про оптимизации и C++ 1/2 [это база].

0. SSO -- small/short string optimization.
Если мы посмотрим на sizeof(std::string), почти наверняка (без упоминания специфических архитектур и старых компиляторов) мы увидим 32 (что больше, чем ожидаемые 24 при стандартной схеме с указателем на данные и двумя чиселками size и capacity). Примерно потому что на самом деле строка выглядит так:

template <typename T>
struct basic_string {
char* begin_;
size_t size_;
union {
size_t capacity_;
char sso_buffer[16];
};
};

Что позволяет хранить значения маленьких строк сразу на стеке -> не тратить время на аллокацию/деаллокацию. Но, конечно же, есть и минусы. Например, кроме того, что ваш sizeof может стать больше (может и не стать, всё зависит от размера вашего буфера), вы ещё делаете move-операции более дорогими.

У bfilipek есть небольшая статья про то, как узнать размер этого буфера с помощью constexpr/constinit. А тут на so можно посмотреть какой-то домашний бенчмарк с пруфом, что это действительно что-то ускоряет.

sso -- частный случай small object/buffer optimization.
Такой подход также применяется в std::function. Затрекать можно следующим кодом:

auto f = [i = 0]() { std::cout << &i << ' '; };
std::function<void()> alpha = f;
alpha();
std::function<void()> beta = std::move(alpha);
beta();

Если данные хранятся на куче, то при муве мы просто переложим указатель на область памяти из alpha в beta. Если же данные будут хранится на стеке, то придётся перекладывать сам объект и адреса в выводе будут разные (gb).

Ещё sbo используют в различных реализациях small_vector. Причём если в случае std::string/std::function вы храните либо на стеке, либо на куче, то тут иногда делают вперемешку: могут часть оставить в буффере, а часть вынести на кучу; ну или на кучу всё, чтобы данные лежали в непрерывном куске памяти.

1. Empty base [class] optimization (ebo/ebco).

Имеем такой код:

struct A {};
struct B : A {};

Как известно, в C++ sizeof пустого объекта -- 1 байт. Т.е. у B размер должен быть хотя бы 2 байта. Но конечно же это не так. Он всё ещё 1 байт, потому что в дело вступает ebco.

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

Предположим, мы хотим использовать кастомный делитер с std::unique_ptr. Как сделать так, чтобы хранение делитера не занимало памяти? В случае, если делитер это какой-то stateless класс-функтор, от него можно отнаследоваться. Тогда в дело вступает ebco, что позволяет не занимать лишний байт, но при этом использовать operator(). Обычно это делают с помощью compressed_pair (реализовано это примерно разбором случаев на компиляции, когда можно наследоваться от типа, а когда нет; если нельзя, то тип просто хранится как член класса). Так что, если вам нужен кастомный делитер, лучше делать его без состояния.

Рядом с ebco обычно говорят ещё про атрибут [[no_unique_address]] (C++20). Когда вы помечаете какой-то из членов класса подобным атрибутом, вы говорите, что этот объект может не иметь уникального адреса в памяти и потенциально перекрываться с другими членами класса. Так с C++20 вы можете реализовать compressed_pair гораздо проще:

template <typename T, typename U>
struct compressed_pair {
[[no_unique_address]] T _val1;
[[no_unique_address]] U _val2;
};

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

Про другие атрибуты писал тут: https://news.1rj.ru/str/thisnotes/218.

#cpp

Немножко про оптимизации и C++ 2/2.

2. Про RVO/NRVO писал ранее: t.me/thisnotes/198.

Рядом с этой темой можно посмотреть доклад про move-only C++ design.

3. Про девиртуализацию писал Женя: t.me/cxx95/88.

==============================
4. strlen elision.
Как известно, функция strlen работает за длину строки. Соответственно, если вы используете её в циклах:

for (int i = 0; i < strlen(str); ++i) {…}

Вы автоматом ловите квадрат в асимптотике. Потому хорошей практикой является выносить вот эту границу справа в отдельную переменную:

for (int i = 0, end = strlen(str); i < end; ++i) {}

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

int main() {
return std::strlen(“hi”);
}

компилятор сделает вам:

main: # @main
mov eax, 2
ret

Ну это база.

Недавно на собесе меня попросили написать strlen. Потом ещё каким-то образом попросили это дело поускорять. Кек, что таким ещё занимаются. Хотя конечно, если погуглить, можно найти что-нибудь вроде такого или такого. Так что может и не без оснований, но лучше я вкину вот такую статью про полезность собеседований подобного рода.

Как писали на каком-то сабреддите:

Optimize strlen by not using it.

Доклад Константина теперь доступен по ссылке: https://www.youtube.com/watch?v=lc3UkIZ4zOY&t=110s

Категорически рекомендую.

#highload

Пару ссылочек.

1. What I Wish I Had Known Before Scaling Uber to 1000 Services.

У uber есть вот такая статья про domain-oriented архитектуру. Ключевая идея — объединять сервисы в домены по бизнесовому назначению и ходить в домены снаружи исключительно через gateway (там конечно ещё много всяких тонкостей и сложностей), что позволяет навести некоторый порядок в вашей архитектуре и том, как ваши бекенды взаимодействуют.

2. What is a Vector Database?

Хорошая и понятная статья про хранение векторов.

==========================
Оч устал за последнее время. Отваливаюсь отдыхать на пару недель.

#common

0. У Вадима Кравченко вышел большой пост про то, как быть хорошим ментором. Очень годный. Там ещё внутри миллион ссылок на другие более узкие статьи. Может я со временем их вычитаю и донесу частями самое интересное.

Рядом ещё могу вкинуть статью из вастрик клуба: Ты ментор. Не обосрись.

1. What’s Wrong With OpenAPI? Чуваки рассказывают, что не так с OpenAPI и что они сделали, чтобы жить лучше. Выглядит даже прикона.

2. Приконая статья про различные способы организовать ваши команды. Мы вообще работаем кросс-функциональным подходом. Словил себя на мысли, что часть недостатков такого подхода сказалась и на мне.

3. Интересная статья (правда по верхам) про эволюцию подходов к организации архитектуры вашего бекенда.

#highload #pub

Мы с коллегой немножко напряглись и написали статью про то, как у нас работает поиск. Прошу к столу.
https://habr.com/ru/companies/yandex/articles/748134/

#cpp

C++ Zero Cost Conf 2023.

Трек в Белграде (link на трансляцию).

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

Второй — Акторная система YDB: история оптимизаций, позволивших обогнать конкурентов. Ещё не было ни одного доклада от челов из YDB, который мне зашёл, так что я скипнул. Мб потому что предметная область в целом не оч интересна.

Андрей Аксёнов рассказывал доклад под названием “Очередная крафтовая хеш-таблица”. Я в целом к его манере рассказывать привык, но какой-то конкретики в докладе не увидел. Можно послушать, но какие-то абстрактные рассуждения получились.
Хотя в целом я доклады Андрея люблю, потому что после них потом можно сидеть и гуглить всякие штуки довольно долго, просто потому что он упоминает много всего.

Был доклад от Александра Малкова про grpc и userver. Слушать немножко тяжеловато.
Я полгода назад смотрел, что там и как поддерживается и в тот момент нужны были довольно большие приседания, чтобы получить то, что есть для http. Если ребята и правда там поддержали много всего нужного, круто.
Правда словил вайб, что чересчур реклама какая-то фреймворка, но может докладчику реально очень нравится. В целом мы на нём живём. Проблем не ощущается.

Доклад Александра Боргардрта не слушал, т.к. он рассказывал то же самое на C++ Russia в мае (мб конечно что-то поменялось, но я не завлёкся послушать фулл доклад ради каких-то точечных отличий).
Я правда послушал его ответы на вопросы и что-то как-то токсично..

Последний доклад — Парсим числа через SIMD от Сергея Слотина (у него в прошлом году был неплохой доклад про ускорение бинпоиска). Я походу не оч осознал задачу, но там ускоряется парсинг чисел в json. Что это за джсоны такие интересно, в которых чисел так много, что подобные приседания становятся полезны.

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

Потраченного времени не жаль, но верю, что ребята могут и сделают в будущем лучше.

#common

Мои ребята делают стартап со стримингом музыки.

Суть кратко:
- есть треки, на которые вы можете покупать nft;
- когда этот трек слушается на платформе, вы (пользователь) получаете доход в токенах;
- исполнитель получает доход как обычно + часть токенов с продаж nft;
- вы можете поддерживать артистов и зарабатывать на угадывании трендов.

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

#common #algo

Сегодня немножко математики.

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

Предположим у нас есть следующее дп (не будем расписывать в общем виде):

dp[i] = 2dp[i-1] + 3dp[i-2] - dp[i-3]

с какой-то базой. Например

dp[0, 1, 2] = {1, 2, 3}

Предположим, мы хотим вычислить несколько конкретных значений (dp[10^3], dp[10^15], то есть значения с очень большими номером), а не все (обычно так и бывает).

Давайте посмотрим на это в виде матриц. Базовая матрица у нас имеет вид (это не определитель, я просто скобки не умею нормально рисовать):

| 1 |
a = | 2 |
| 3 |

где a_i это соответственно dp_i, i \in [0; 2].

Если мы перемножим матрицу ниже на столбец выше

| 0 1 0|
M = | 0 0 1|
|-1 3 2|

мы получим вектор

| 2 |
| 3 |
| 11 |

в котором мы по факту получили сдвиг в нашей дп-шной последовательности на 1 вперёд (то есть вычислили dp[2], dp[3] и dp[4]).

А теперь предположим, мы хотим найти dp[n]. Конечно, эту последовательность умножений можно повторять раз за разом n - 3 раза, пока мы не получим нужный элемент. Но в чём тогда был смысл подобных движений? Давайте сначала нашу матрицу перехода бинарно возведём в (n-3)-ю степень и только потом умножим вектор a. Чтобы получить ответ, достаточно будет взять последний элемент получившегося столбца:

ans = (bin_pow(M, n - 3) * a)[2];

То есть по факту вы можете считать любую подобную “линейную” последовательность быстро для любого адекватного значения n. Я когда-то, например, писал нахождение n-ого числа Фибоначчи на компиляции. Тут правда надо быть аккуратным с глубиной рекурсии и возможно подкрутить флаг -ftemplate-depth.

#common

1. Ubiquitous Caching: a Journey of Building Efficient Distributed and In-Process Caches at Twitter.
Доклад прикольный, но у infoq есть проблема, что они выкладывают именно расшифровку (т.е. картиночки вы не увидите). А сам доклад слушать тяжеловато (какие-то траблы со звуком). Может лучше тогда посмотреть короткий видос про устройство Segcache тут.

2. Building a strong knowledge sharing culture on engineering teams.
Это скорее заметка, которая рекламит конкретный продукт. И заголовок у неё кликбейтный. Но проблемы с документацией ребята описали хорошо.

3. HTTP/3 From A To Z: Core Concepts.

4. Should That Be a Microservice? Keep These Six Factors in Mind.

Ну и на этом пока всё.

Неделя получилась плотнее обычного по постам, но это выброс : )