О таких вещах хочется писать почти сразу :)

https://github.com/facebook/zstd/pull/3517

Нашли ещё поцарапанные данные в ZSTD. Удивительный факт в том, что этому багу 2 года.

На этот раз никакое тестирование, фаззинг, который 2 года фаззил этот код, не помог. Нашли случайно, а баг ещё одна манифестация Silent Data Corruption. Из хорошего это замечательный кейс для фаззера, почему не нашел, что можно сделать, чтобы фаззинг такое находил хотя бы за недели.

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

Советую обновиться тем, кто использует. Проблемы были в ZSTD level 13-22. decompress(compress) (редко) возвращал другие данные.

C++17 -> C++20

По традиции, рассказываю, что может пойти не так, когда вы хотите переехать с C++17 на C++20. В среднем вы не должны ничего заметить, но различий достаточно, чтобы заглянуть в страшные уголки плюсов.

От самых страшных до не самых страшных

1. Spaceship operator<=>

Единственная фича, которая уменьшила количество слов в стандарте и добавила головной боли компиляторным инженерам. Сломаться может интересно: если у типа есть implicit оператор вида


struct Int {
int i;
operator bool() const {
// Returns true if not 0, false if 0.
return i;
}
};

Тогда <=> оператор в первую очередь применит оператор меньше к кастуемому типу, в итоге

std::pair{Int{1}, Int{2}} < std::pair{Int{3}, Int{4}}

вернёт 1 в C++17, 0 в C++20.

Достаточно опасно, так как сильно меняет семантику. Как чинить? Писать explicit operator. Пример падения в проде.

2. operator== ambiguity


struct B {};
struct D : B {
bool operator==(const B& other);
};
D d;
bool eq = d == d; // работает в C++17, но не в C++20

На самом деле та же проблема. Бьярне и компания написали целую статью про это тут. Если коротко, то в C++20 написали правила, чтобы операторы == и != вели себя логичным образом, что !(a == b) это a != b. С другой стороны это создаёт проблему в духе


struct S {
friend bool f(S, const S&) { ... }
friend bool f(const S&, S) { ... }
};

bool b = f(S{}, S{});

И в итоге operator== и operator!= считаются одними и те же функциями. Это поломало много проектов, поэтому компиляторы быстро взяли фикс из C++23, и проблем больше нет https://godbolt.org/z/7e4E6qhbM.

3. Всякие проблемы с std::string_view против std::vector<std::string*like> и тд

Конструкция {"a", "b"} вызывает лёгкий ужас, так как в C++20 в string_view добавили конструктор от 2 итераторов и "a" и "b" являются const char* start и const char* end, что очень плохо заканчивается: вы читаете чёрт пойми какую память.

std::vector<std::string_view>{{"a", "b"}}

Теперь создаёт палёный string_view из локации, где "a" -- начало, потом где "b" -- конец, а в C++17 создавало 2 строки. Санитайзеры не ловят. https://gcc.godbolt.org/z/jboa5rbfa. Самое ядро заключается в том, что {"a", "b"} создают не initializer_list, а обычную string_view

Зато можно всякого интересного придумать.

Например, можно добавить в libc++ код в духе


template <int M, int N>
constexpr basic_string_view(char_type (&a)[M], char_type (&b)[N]) : basic_string_view() {
_LIBCPP_ASSERT(&a == &b);
}

И он будет падать в рантайме, в санитайзерах, орать warningами и быть ещё standard compliant. Выстрел в ногу, но всё таки элегантно чинится.

4. Всё остальное кажется достаточно минорным, атомики перестали быть trivially constructible, поэтому их в union не очень стоит класть, добавили слова concept, requires, добавились constexpr контейнеры, поэтому все шаблоны вектора должны быть полными типами. Стали делать std::move на начальное значение в std::accumulate, поэтому функция аккумулирования перестала принимать lvalue references. Aggregates теперь не компилируются, если есть конструкторы. Всё это чинится проходом по всему и достаточно прямолинейно.

Я думаю по сложности C++14 -> C++17 был проще, чем C++17 -> C++20, но тоже со своими интересными решениями, как noexcept как часть типа и тд. Всё равно суммарно набирается работы, хоть и не так много.

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

Google Performance Tips of the Week

Мои коллеги выложили https://abseil.io/fast/. Я очень надеюсь там публиковаться, думаю, один эпизод в следующие месяцы будет под моим авторством.

Это похожий на сборник C++ Tips of the Week https://abseil.io/tips/ от Google. Хоть каждую неделю мы не выкладываем эпизоды, но сохранилась традиция часто писать про одну идею, чтобы рассказать что-то интересное и полезное, особенно тем, кто задается вопросом, а можно ли что-то улучшить в их приложениях.
Это хорошие, понятные, промодерированные, проверенные временем эпизоды с 6-7 ревью от топ экспертов в Google.

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

Paxos, Raft и тд

Моё отношение к консенсусным протоколам менялось. В универе я их понял на уровне, что консенсусы возможны, потом на практике я видел как баги в Paxos/Raft есть и будут всегда, но последние 1-2 года багов стало как-то сильно меньше, и привыкнув к алгоритмам, потихоньку приходит осознание в их детальных различиях, в том числе полученные горьким опытом.

Мне захотелось ещё раз прочитать разницу между Paxos и Raft и как они живут вместе с FLP теоремой.

Последняя гласит, что детерминированный консенсус невозможен в полностью асинхронной сети, когда сообщения могут не доставляться или доставляться с задержкой. Выбор лидера в Raft может никогда не завершиться, на практике борются с этим с помощью случайных таймаутов. У Paxos два proposer могут никогда не договориться о решении, что тоже на практике лечат случайными таймаутами. Это отличный вопрос на собеседовании, чтобы отсечь тех, кто видит в Raft ответы на все вопросы, о негативных результатах надо тоже знать.

По моему мнению на практике самая большая разница в том, что при потере лидера Paxos может медленнее восстанавливаться:

1. Paxos выбирает лидера исходя из id узла, и если он отстает на немного от закоммиченных значений, то ему надо их применить, поэтому если сервер с большим id выигрывает, бывают проблемы и спайки в ожидании запросов. Случайный id не всегда хорошо коррелирует с живностью. На практике в больших системах много работы надо доделать, например, всякие обновления метаданных, и это начинает быть заметно.
2. В Raft узлы с бОльшим количеством закоммиченных чаще выигрывают, но зато у Raft больше шансов получить ситуацию, когда много проголосовали за 2 кандидата и надо переизбрать ещё раз. Вторая ситуация происходит реже, поэтому Raft более практичен.

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

1. Raft и Paxos имплементируются по статьям.
2. В Raft есть проблемы с network partitioning, если узлы видят разные подмножества, может быть бабах (Cloudflare). Подробный разбор и как сконфигурировать etcd и всё сломать можно прочитать в статье.

Дальше происходит, что написание нового кода приводит к багам, которые чинятся годами. Тем не менее, ситуация намного улучшилась, в etcd 3.4 добавили Raft Prevotes, чтобы избежать проблем с сетью. Но потом чинить баги всё равно пришлось. Вещи становятся лучше со временем в таких примитивах, это не может не радовать.

Самое удивительное в этой индустрии, насколько она наполнена людьми, которые, мол, думают, что поняли консенсус. Из-за того, что консенсусы нетривиальны, редки, я вижу много от людей в виде: "выучи TLA+", "напиши автоматическое доказательство", "а ты слышал про EPaxos, он лучше, чем Paxos". Ребят, мне бы понять первую статью. И не врать себе, что задача просто сложная.

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

[1] Различия Paxos и Raft
[2] Вообще читайте всё, что написано от Heidi Howard, она топ эксперт в мире по консенсусным протоколам
[3] etcd network partitioning failure, инцидент от Cloudflare
[4] Имплементации Raft
[5] Ещё более простое объяснение Raft с иммутабельными цепочками. Чем больше иммутабельности, тем легче нам понимаются перезаписи и тд

Sparse Ngrams Devlog. Part 1

Следующие несколько постов, дней, недель я буду много постить о сайд проекте, а именно о GitHub Indexing Codesearch, а именно Sparse Ngrams solutions. Мне надоели Russ Cox trigram индекс и Zoekt. Посмотрим куда приведёт:

https://github.com/danlark1/sparse_ngrams

Основную идею я уже писал в блоге выше, а именно мы должны взять все ngrams, хеши биграм которых на концах больше, чем в середине. Так как хеши не зависят от input, то подстроки будут иметь подмножество такого разбиения. А всего таких ngram не более 2n.

Понятно, что при запросе не надо разбивать таким алгоритмом и в статье GitHub сказано, что At query time, we use the exact same algorithm, but keep only the covering ngrams, as the others are redundant. Covering ngrams -- такой же алгоритм, только надо удостовериться, нет никакой подстроки другой в множестве.

У меня в тесте для for(int i=42 как раз получается интересная история: всяких ngram много:

"for", "or(", "for(", "r(i", "for(i", "(in", "int", "(int", "nt ", "t i", " i=", "t i=", "i=4", "t i=4", "nt i=4", "(int i=4", "=42"

А covering ngrams меньше, они более репрезентативны и должны быстрее отвечать на запрос из-за ngram =42 и (int i=4.

"for(i", "(int i=4", "=42"

Как строятся такие ngrams и coverage? Сначала добавляем все триграмы как мельчайшие единицы. Потом алгоритм в точности является sliding min/max window (LeetCode полезно решать вообще). Когда мы добавляем следующий хеш в стек, надо выкинуть все элементы, которые меньше по хешу из конца. В итоге в первом случае мы когда убираем из стека, мы добавляем этот range ngrams, а во втором случае добавляем все убывающие последовательности. На картинке в статье, к сожалению, ошибка (пропущена "ste"). Covering ngrams в строке "chester " (с пробелом) в этом случае будут "chester ". Потому что пока все значение после девятки меньше девяти, то мы будем добавлять в стек (один раз уберем из стека по ходу, но эту ngram не добавим пока не дойдём до конца), а когда наткнёмся на 7, надо будет всё убрать до начала и в итоге мы найдём очень большую ngram. А для подстроки "chester" (без пробела) covering ngrams будут "che", "hes", "este", "ter". Потому что когда мы дойдём до нулевого хеша, у нас sliding window закончится, и надо обработать хвост. Единственная возрастающая последовательность это "1 2", поэтому добавляем "este", остальное -- обычные триграмы как мельчайшие единицы. Асимптотика -- линейная, потому что добавляем и убираем из стека каждый элемент суммарно не более двух раз.

Алгоритм весь получился на 70 строк кода.

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

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

Не смогу пройти мимо релиза бывших коллег из яндекса -- YTsaurus

https://github.com/YTsaurus/YTsaurus

https://medium.com/yandex/ytsaurus-exabyte-scale-storage-and-processing-system-is-now-open-source-42e7f5fa5fc6

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

Поздравляю, это крутой релиз.

CMake Fuzztest is official

Я уломал, и мы будем поддерживать CMake в Google FuzzTest.

https://github.com/google/fuzztest/pull/177

Вообще, конечно, про CMake можно много чего говорить, но больше хочется рассказать про то, что в C++ проектах в Google поддерживается только Bazel, потому что он везде и на него не надо тратить силы. А на CMake нужно очень много сил.

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

Теперь можете просто добавить зависимость и писать что-то в духе

add_executable(first_fuzz_test first_fuzz_test.cc)
# Optional user provided target_link_libraries.
link_fuzztest(first_fuzz_test)

И всё. Сложнее конфигурации будут в случаях, когда вы сами используйте absl и re2, но тут уже сами разберётесь. Мини дока здесь.

Мне это понадобилось, потому что я очень сильно хотел в свои sparse_ngrams добавить FUZZ_TEST. Убил полвыходного и добавил CMake в FUZZ_TEST, заодно бонус в гугле отхвачу. sparse_ngrams не сильно продвинулись из-за этого..

Надо отдохнуть

Я не поспеваю за тем, что происходит сейчас в мире. LLM что-то меняют, а я как-то не успеваю с ними подружиться, а ощущение, что сейчас ими занимаются чуть ли не все. Что-то интересное вырисовывается, по крайней мере много кто пользуется этой технологией. Я не особый фанат ML, попытка обесценить интеллект происходит, и много интересных вопросов возникает от "Да это всё фигня" до "Кажется все в будущем будут только операторами GPT". Принимать одну точку зрения не хочется и в чате я тоже против heated дискуссий. Возможно просто продолжать свои интересы и встроить это в свои тулзы будет хорошо.

Я сейчас уеду в отпуск на 2 недели, без связи, подумать и к чему-то прийти. Пока какой-то дамп, что интересного я надумал (not related to LLMs):

1. То, что я целый год не постил ничего на danlark.org, как-то заставляет меня грустить. За последний год я и правда стал писать с меньшим огнём. Но и если честно, постил я туда порой через кранчи и бессонные ночи. В этом году хотелось спать больше :)

2. По поводу перфа в последнее время хочется больше смотреть в сторону Last Level Cache Misses, так как я уже много писал, что скорость памяти не растёт, значит любые циклы, которые мы простаиваем в памяти, будут только хуже сказываться на всём остальном. Оптимизируя как мы ходим по памяти, ускорим все остальные процессы. Особенно в Cloud environment, когда LLC Miss это отобранная работа у соседа. Сложность с этим -- померить "до" и "после", бенчмарки обычно хорошо прогружены.
Такая же история происходит и с branch misses: но тут хотя бы есть интересные решения как cmov инструкции и их семейство. С памятью тяжелее, пробросить новые регистры через SRAM в архитектуру непосильно, надо сидеть и думать как реинжинирить решения.
Ещё интересная идея для баз данных: возьмите любой запрос и посмотрите, а сколько write инструкций в память вы делаете? Оказалось, что какой-нибудь ClickHouse проводит 25% из всех циклов работы с памятью в запись при запросе, well, чтения из базы? Что? :)

3. Хочу втаскивать простой ML в оптимизацию конфигов и параметров. Статьи по этому существуют: Machine Learning Framework to Improve Storage System Performance (acm). Самые простые вещи, которые хочется конфигурировать -- размеры кешей, уровни компрессии данных и тд. Руками замучаешься каждый раз это делать.

4. Больше визуализации данных. Осознавая, что человеческий visual cortex очень силён, хочется больше глядеть и понимать код исходя из реальности. Скажем, в flame graphs я бы с радостью смотрел, является ли frame в for цикле, так можно находить всякие квадратичные-кубические алгоритмы. Пока как-то это сложно делать.

5. Как ни странно, в Arm мы всё ещё продолжаем вкладываться, но мой интерес упал, потому что происходит какая-то неинтересная работа -- починено с сотню багов и перф, ну, просто норм. Дальше надо строить процессоры, и это очень сложный процесс по соединению software и hardware. Я отошёл слегка от дел, но планирую чуть побольше там сидеть.

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

Я приехал с очень мне нужного отпуска. Мы начинаем 1 неделю постов каждый день. То, что будет в голове, о том и буду писать.

1. ZSTD 1.5.5 выложили с фиксом нашего corruption и упомянули меня. Мораль на самом деле здесь интересная, потому что мы фаззили в OSS-Fuzz этот код два года и не нашли этот баг. Почему? Потому что все таки фаззинг не магия, я начал писать огромный пост про то, почему фаззинг не работает в таких случаях и скорее всего нашел бы этот баг только за 150-1000 лет. Обновитесь, баг вряд ли задел хоть единого пользователя на миллион, но экзабайты данных тестируют на прочность все.

2. Сортировку в LLVM откатили в 16.0.1, но оставили в Head. С моралью, что пользователи стали репортить проблемы с неправильными компараторами. Поставили немного чеков на это и к LLVM 17 сортировку должны все таки устаканить. Мораль, что такой проект уже занимает два года. Я бы сказал, что это адски медленно, но вот это состояние, когда надо что-то менять на миллиарды пользователей.

3. Я читал тут статью про систему мониторинга Monarch (готовился для моего менти). И это чуть ли не единственная статья, где говорится про скейл Гугла. 144к инстансов, на каждом скорее всего минимум по 4 CPU, можете посчитать, сколько занимает просто мониторинг на 2020 год. А потом сравнить с топ компьютерами мира. Просто забавный факт, не более. Должно получится около 1000 петафлопс. Цифры не воспринимайте серьезно, это просто прикидка и реальность скорее всего более сложная.

libuv наконец-то замержил io_uring, не прошло и нескольких лет

https://github.com/libuv/libuv/pull/3952

Вообще я фанат libuv, мне легче в нем пишется код. В Boost.Asio сложнее, скажем, примитивы синхронизации не такие явные, и поэтому часто возникает интеграция непонятных велосипедов. Наверное, из минусов, что libuv задумывался как чистый event loop, а boost.asio как networking asynchronous protocol, поэтому в первом вы увидите всякую работу с диском, а во втором прицепы из SSL, что может быть иногда удобнее.

Не то, чтобы я эксперт и сварщик asynchronous protocols, но на субъективное ощущение libuv кажется легче для восприятия.

В общем, прогресс едет, вещи становятся получше, рад за libuv и поздравляю их с поддержкой io_uring

Сегодня прочитал статью по поводу того, что в clang санитайзеры применяются уже после некоторых оптимизаций, которые могут пользоваться неопределенным поведением, то есть вы написали плохой код, потом оптимизатор воспользовался этим, а санитайзер не поймал. Статья направлена на то, чтобы найти эти оптимизации. Результаты получились хорошими, нашли ещё несколько багов, в том числе в OSS-Fuzz.

В целом если возможно, запускайте Msan, Asan с -O0 оптимизациями (особенно Msan). Если не получается, может быть хватит у кого-то сил дотащить эту статью до LLVM. Статья милая, читается легко. Назвали такой процесс тоже смешно, Don't LookUB. А вот репозиторий ещё не открыли https://github.com/vusec/LookUB. Наука про санитайзеры все ещё развивается в вероятностные схемы.

https://goto.ucsd.edu/~gleissen/papers/dontlookub.pdf



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

Недавно мы потратили несколько дней, чтобы найти memory corruption в C++ коде. Оказалось это была плохая сортировка.

В общем, пропозал, который все точно ждали. Давайте проверять в сортировке strict weak ordering на первых X элементов. Про квадратичный алгоритм проверки я уже писал, надо дотащить до конца и для всех.

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

В общем, можете почитать RFC в LLVM:
https://discourse.llvm.org/t/rfc-strict-weak-ordering-checks-in-the-debug-libc/70217

Очень интересная вещь происходит в memory management Linux в последнее время.

Когда вы аллоцируете память, вы создаёте страницы, обычно они по историческим причинам 4KB, и если вы большая компания, или даже запускаете базу данных, то со временем страниц становится много, появляются проблемы походов в TLB, сервер со временем начинает тормозить. В Google в статье про TCMalloc [1] мы репортили, что 20% всех циклов в датацентре мы проводим в TLB, что не очень то и радует. На помощь приходят Huge Pages, так как их размер побольше, то не происходит больших таблиц и количество TLB простаиваний происходит меньше.

Это показывает, что Huge Pages становятся уже не только хорошей оптимизацией, а в целом Must Have для приложений, которых заботит перформанс.

Проблемы начинают приходить с других сторон в этом направлении. 2MB Huge Pages достаточно сложно выделить ядру из-за большой фрагментации. Если вы на часок оставите шард поискового движка отвечать на запросы, его перф, с одной стороны, улучшается из-за прогретости индекса, с другой стороны ухудшается memory management, так как страницы начинают быть фрагментированы из-за того, что на сервере много всякого происходит. Я пока читал то, о чём сейчас пишу, узнал для себя, что ядро очень сильно разделает все страницы на movable/unmovable. Первые -- те, которые получает пользователь, их ядру легче перемещать, тем самым оно может лучше выделять память на физическом уровне. Unmovable страницы -- те, которые ядро выделяет само, для Network/IO стека, их перемещать сложно, так как ядро к ним доступ имеет мультипоточный и напрямую. Можно лочить всё, чтобы их поменять, но оверхед от такого будет ещё выше, представьте, что вы хотите получить RPC, а тут lock в ядре, оно обновляет все TLB всех ядер, RPC не проходит, беда, печаль.

Простая проблема, которая возникает -- что если 2MB страницы unmovable на физическом уровне находятся рядом с movable? Отсюда начинает сложно дефрагментировать даже movable страницы, если есть задача поближе поставить страницы на физическом уровне. Исторически в ядре утилизации памяти уделяли больше времени, чем вынесение разных видов страниц в разные регионы. Инженеры из Meta на ISCA'23 [2] выложили, наверное, одну из самых интересных статей для меня за последнее время, где они стараются выделять память для movable/unmovable регионов далеко друг от друга на уровне ядра, чтобы улучшать layout памяти на физическом уровне.

Фактически идея достаточно простая -- взять два далеких региона, сказать, что один для movable, другой для unmovable и перемещать границы. Если границы начинают пересекаться, в худшем случае ничего не сделать. Тем не менее, можно делать интересные вещи:

[unmovable region][free space][movable region]

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

Следующая идея -- считать простую статистику как memory pressure. Она включает в себя время, проведенное в page faults и тому подобное в обоих регионах.

Самая сложная часть -- миграции страниц. Как уже сказано, в софте такую миграцию будет накладно сделать, поэтому инженеры из Meta построили дополнение к LLC на уровне железа. Краткая идея, что для всего процесса надо очень аккуратно оповестить TLB для инвалидации, которая разрешает копирование страницы (в это время все доступы блокируются), а потом уже TLB можно оповестить, чтобы можно было ходить в новую страницу.

Удивительное в этом всём, что приложения получают очень хороший прирост. От 2% до 14%. И код доступен [3], чтобы можно было играться. Моё понимание, что они ещё не выложили это в прод, а пока экспериментируют, но в целом выглядит, как эта тема одна из самых интересных в memory management, память не растет, мы начинаем выкручиваться как можем и делаем все более сложные схемы.

[1] Google TCMalloc Paper
[2] Contiguitas: The Pursuit of Physical Memory Contiguity in
Datacenters
[3] https://lwn.net/ml/linux-kernel/[email protected]/

[[lifetimebound]]

В компиляторы C++ потихоньку приходят интересные фичи с memory safety, в этот раз поговорим о [[clang::lifetimebound]]. Он предназначен для того, чтобы показать, что жизнь возвращаемого объекта может зависеть от жизни аргумента

Я частенько видел код в духе

const std::string& s = StatusOrProtobuf()->field_value();

Где StatusOrProtobuf возвращает absl::StatusOr<Proto>, где мы знаем, что статус будет всего OkStatus.

И в этот момент я всегда задавался вопросом, а верно ли, что это просто неправильно? StatusOrProtobuf() будет же локальной переменной, в итоге мы берем ссылку на объект внутри локальной переменной, что вроде бы undefined behavior, так как локальная переменная разрушится.

Компиляторы и санитайзеры могут это не поймать так как примеры могут быть более интересными в духе


template<typename T, typename U>
const U &get_or_default(const std::map<T, U> &m,
const T &key,
const U &default_value);

В итоге если вернётся default value, то писать в духе

const std::string &val = get_or_default(m, "foo"s, "bar"s);

некорректно. В тестах можно забыть протестировать default_value, а в проде выстрелит.

В clang привнесли атрибут [[clang::lifetimebound]], который находит всякие такие баги на этапе компиляции. Можно писать


template<typename T, typename U>
const U &get_or_default(const std::map<T, U> &m [[clang::lifetimebound]],
const T &key, /* note, not lifetimebound */
const U &default_value [[clang::lifetimebound]]);

Просто скажу, что мы в abseil облепились этими лайфтаймами и нашли сотню другую багов. Очень полезно даже для примитивных типов вроде unique_ptr::operator* и тд. Его можно ставить на аргументы функций и на функции класса пока.

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

Да, в Rust это встроено в язык, lifetimebound это упрощенный простой один lifetime 'a в Rust. За любой срач по Rust в коментах бан.

Привнести такой атрибут хотели давно в P0936 и очень долго пытаются починить всякие range based for.

Wide LRC codes

Я как-то писал в канале про Erasure Codes, в том числе про LRC, который в какой-то степени стал стандартом. Напомню, что про Erasure Codes можно думать как redundancy technique -- если у вас есть данные, их можно поделить на 2 части, посчитать xor, теперь при выпадении любой из 3 получившихся частей, мы можем восстановить данные полностью. В итоге потратили 1.5x места, но redundancy 2 (при выпадении любого 1 куска данные восстанавливаются). Если копать глубже, то дополнительные k частей получаются умножением на матрицу (n + k) x n над полем F_2 или F_256, а при выпадении любых k, матрицу можно обратить и восстановить данные. Вопрос в нахождении матрицы, но так получается, что k можно брать достаточно маленьким по сравнению с n и фактически можно достигнуть любой практической redundancy k потратив (1+eps) места. LRC идут дальше, они стараются группировать некоторые из n частей вместе, чтобы обращение матрицы было частичным -- скажем, поделим всё на 12 частей, у первых 6 посчитаем XOR, у вторых 6 посчитаем XOR, попробуем найти матрицу 16 x 12, где две строки это такие линейные преобразование и ещё 2, чтобы матрица была полностью обратима. Теперь если выпал один чанк данных, то можно скачать 6 других восстановить по XOR, если два чанка в двух разных группах, то тоже всё сработает, а если выпало 3 или 2 в одной группе, ну что ж поделать, скачаем всё и обратим матрицу. Но такие случаи реже случаются, поэтому инженерия любит такое дело. Такие группы называют локальными группами, а дополнительные чанки у локальных групп -- локальные чанки, а дополнительные чанки для всей операции -- глобальные чанки.

На FAST'23 вышла статья в Google про широкие LRC коды. Это такие коды, которые делят на очень много частей, чтобы получить большую redundancy и потратить поменьше места. Холодный storage может делить данные на сотни частей и делать всего десятки дополнительных чанков получая redundancy в 6-7 c оверхедом на весь сторадж процентов в 10% (например, (96, 4, 5) делит на 96 частей, бьёт на 4 локальные группы с 5 глобальными чанками). Хоть и теория кодов очень хорошо изучена, на практике становится слегка сложно с балансом двух вещей

* Находить обратимые матрицы с свойствами локальных чанков
* Сделать операции локальных чанков достаточно простыми, скажем, обычный XOR ок, но что-то сложнее уже слегка путает инженеров. Простота также полезна для миграций -- можно ли как можно больше посчитанных чанков сохранить

Обычно LRC коды изучают как сделать операции над локальными чанками. Статья от Google показывает, что можно сделать слегка лучше -- смотреть на локальные группы как функцию не только от изначальных данных, но и от глобальных чанков, а можно также смотреть как на функцию от данных, глобальных и локальных. Так становится чуть проще размазать локальные чанки по всем данным. Определение и трюк слегка self-referential в том плане, что локальные чанки определяются через локальные, но статья считает некоторую математику, которая сходится.

Зачем это надо?

В статье можно увидеть только слегка лучше результаты по метриками redundancy, average cost of repair и тд. Цифры не ахти в сравнении и никакой супер революции этот LRC метод не привносит. Он рассказывает историю как продвинуть рисёрч слегка дальше по достаточно практичной теме как LRC коды.

Keep on pushing, статья рассказывает хорошую историю.

https://www.usenix.org/system/files/fast23-kadekodi.pdf
https://www.youtube.com/watch?v=pfnSYWEf5q4

Автор слегка увлёкся

Я тут много писал кода в последнее время, а потом снова увлёкся всякими эзотерическими штуками вроде статей. Что произошло:

1. Дотащил квадратичную проверку на strict weak ordering до LLVM. https://reviews.llvm.org/D150264. Дали аппрув, надеюсь, в ближайшие дни закоммитим. Фидбек был достаточно позитивный.

2. Соптимизировали снова всякие integer to ascii в abseil. На этот раз алгоритм очень похож на Paul Khuong's itoa. Мы покатили с более плохими микробенчмарками. Почему? Потому что предыдущий алгоритм брал табличку в 200 байт и получалось вот что:

а) Вы что-то делаете на сервере
б) Конвертите числа в строки, делаете доступ к памяти этой таблички
в) Делаете что-то ещё, повторяете

В итоге получается, что табличка может выйти из кеша или не попасть в кеш линии правильно (200 байт вообще занимает 4 кеш линии). В итоге будут промахи по L1, L2 кешам. Чтобы сделать бенчмарки более правдоподобными, я взял и каждые 1024 итерации вызывал инструкцию CLFLUSH — Flush Cache Line. Текущие бенчмарки становились хуже.

Вообще это достаточно стандартные грабли -- если вы видите микробенчмарк, где сильно ускоряют через доступ к табличкам, то оно может работать хуже, чем если это подготовлено скалярно в коде.
Например, SIMDJSON очень долго имел проблему с парсингом маленьких json и в проде, если вы парсите jsonы не миллионами в секунду, то SIMDJSON не даст уж прям сверх преимуществ. Будьте аккуратны с алгоритмами, которые имеют статические данные, эти данные должны быть горячими.

3. Мои оптимизации хеш-таблицы в abseil для Arm уехали в Rust. https://github.com/rust-lang/hashbrown/pull/430. Мы списывались с автором hashbrown несколько раз и он подтвердил, что в Rust тоже стало на 3-5% быстрее микробенчмарки. Обсуждение длилось долго, пока мы в abseil не нашли способ ускорить. Трюк заключался в том, что можно было использовать 64 битный SIMD, а не 128 битный, как обычно думают про SSE.

Спустя год паузы, я что-то написал на английском

https://danlark.org/2023/06/06/csinc-the-arm-instruction-you-didnt-know-you-wanted/

Даже вышли в топ 1 HN

https://news.ycombinator.com/item?id=36223283

Сегодня прям праздник статей!

Я тут писал про оптимизации хеширования и сортировок с помощью Reinforcement Learning, Deepmind выложили статью, я в acknowledgements.

AlphaDev discovers faster sorting and hashing algorithms
https://www.deepmind.com/blog/alphadev-discovers-faster-sorting-algorithms

Faster sorting algorithms discovered using deep reinforcement learning
https://www.nature.com/articles/s41586-023-06004-9

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

HN: https://news.ycombinator.com/item?id=36228125