Сегодня начинается двухнедельный марафон постов. Я каждый день постараюсь писать что-то содержательное. Ибо накопилось, а мотивации сдампить нет. Плана тоже нет. Как будет ехать, так и поедет.

1.

Я в апреле прошлого года писал про то, что мы собираемся менять стандартную сортировку в LLVM.

Как обычно, после 8 месяцев ревью, мы всё таки закоммитили это после консультации с Android+Chrome командой и с Meta. Ура, в LLVM 16 будет новая сортировка. Примерно по скорости как pdqsort, быстрее для больших типов из-за меньшего кол-ва сравнений на рандомных данных.

2.

Я в последнее время занимался очень много компрессией данных. Хочется рассказать историю. В Google работает человек, который придумал brotli -- такой алгоритм сжатия (https://github.com/google/brotli), который использовался в Google, чтобы переехать с zlib в году так 2013. Как примерно и все разработчики алгоритмов сжатия, выглядит это всё в ретроспективе странно, идеи были взяты из теории, обсуждения на https://encode.su/ и так далее. Алгоритм сам по себе неплохой, только вот автор (jyrki@) кажется сильно огорчился, когда вышла zstd. zstd хоть и сама вышла после обсуждения на encode.su.

Спустя несколько лет, мы в Google переехали на zstd, потому что он

* Намного быстрее разжимает
* Лучше поддерживается
* Намного приятнее общаться с автором хоть автор zstd работает в Meta
* Начинает выигрывать у brotli

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

Только это вот не правда для lvl1-4, которые самые распространнённые в мире из-за того, что они сжимают хотя бы 75MB/s. Даже какой-то бенчмарк это показывает (раз, два, три). Я смог выбить лучше rate у brotli при достаточно высоких левелах, но скорость разжатия оставляет желать лучшего (3x от zstd). Фактически brotli лучше для round-trip на высоких левелах и если данные вообще не трогать. Но высокие левела это уже сжатие в 10MB/s, что просто не очень :)

Jyrki любит ходить в комментарии на HN, очень расстраивается, когда его поделие основанное на brotli JPEG XL убирают из Chrome.

Правда в том, что в Facebook всё на zstd, Amazon S3 на zstd, в Google (мне разрешили признаться) мы используем zstd в 15 раз больше, чем brotli. Brotli остался хоть и хорошим решением, которое появилось до zstd, сейчас оно проигрывает почти по всем фронтам. Brotli почти никак не развивается и просто уходит немного в серую даль.

Плохо только то, что мне сейчас приходится работать с Jyrki для переезда последнего крупного клиента brotli на zstd. И это просто ад, чтобы доказать, что brotli надо закопать. Коммуникация и эскалация помогают. С цифрами спорить сложно, но когда есть зацепиться хоть к одной цифре, человек за неё цепляется. Кажется людям сложно отпустить своё поделие. Понимаю, наверное, мне тоже было бы сложно.

Используйте zstd, библиотека получше поддерживается, чем наш старый brotli. Никаких чувств, что наша компания сделала что-то хуже, чем соперник, в итоге всё равно в open source же :)

Как ставить размер кеша?

У вас есть какие-то запросы к другому серверу или диску, рано или поздно кто-нибудь из сидящих в зале вскрикнет: "Надо добавить кеш!". Задачу можно смело отдать стажёру, он её сделает, все люди будут сидеть счастливыми. И самое смешное, что почти все согласятся, что это было важно и нужно, из-за этого кешей плодятся десятки, а то и сотни. Кеши все любят, у них намного меньше проблем с консистентностью (кеш не ответил, ничего страшного или не добавили в кеш из-за погодных/датацентровых проблем, тоже ничего прям страшного). Добавим в следующий разок.

Тем не менее, кеши очень сильно добавляют головной боли в том, а как померить их качество. Для этого надо очень хорошо понимать, что вы сохраняете/где выигрывайте.

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

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

Стоит уметь считать запросы к диску, если кеш предотвращает их. Возможное решение: отключать кеши и смотреть, сколько ваша система сжирает $СЧАСТЬЯ_ПОЛЬЗОВАТЕЛЕЙ/$ДЕНЕГ/$ВАШИХ_НЕРВОВ. Метрика чуть более стабильная.

Так как ресайзить кеш тогда? Я видел

* На глазок
* С помощью машинного обучения: пусть график мл выучит. Работает кстати не так плохо как кажется
* Удалить кеш и забыть как страшный сон

Не забывайте добавлять метрики:

* hit/miss/cache size
* Сколько в среднем живут ключи и значения, их распределение.
* В кешах есть такая шутка, что оптимальный кеш это тот, который вытесняет элемент, который позже всего в будущем будет запрошен. Такой минимум называют Belady Min. Его нельзя заимплеменить, потому что он должен знать будущее. Тем не менее, посчитать метрику и сравнивать LRU/LARC/другие политики можно по историческим данным.

Я тут писал про оптимальное нахождение коротких и хороших хэш функций. В общем, после моих страданий мы нашли хэш функцию (коммит в abseil), которая

* Быстрее процентов на 20, чем мы имели в absl::Hash
* Работает на входных данных от 9 до 16 байт
* Проходит так же SMHasher, что и предыдущая с исключением очень sparse inputs

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

Чтобы её найти, мы с Deepmind очень много поработали. Идея была такая: загрузить много входных данных с SMHasher, микробенчмарков. Загрузить очень похожие на входные -- буквально поменять 1-2 битика. Дальше взять эти входные данные, загрузить в AlphaZero инструкции x86, описать правила игры в ассемблер, дать оптимизировать количество коллизий и latency.

В итоге сработало и не очень следующее:

1. Считать количество коллизий на обычные 64 бита дало плохие результаты. Плохие в том плане, что AlphaZero любило находить хэш функции, которая не меняет нижние биты или верхние 32. В итоге стоило считать коллизии верхних/нижних 32 бит, нижних 16 и 8. После этого стало получше.
2. Запретить агенту играть с инструкциями по типу crc32, потому что из них получаются хорошие 32 битные хеши, но не 64.

В целом всё, дальше агент нашёл несколько вариантов. Мы посмотрели, побенчмаркали. Очень много времени убили, чтобы просто запустить эту махину, потому что по памяти промахиваться нельзя, странные load операции нельзя и тд. AlphaZero реально полюбила трюк с умножением и xor двух частей умножения 64x64->128 бит.

Не думаю, что такой подход (ML-based assembly generation) полюбится комьюнити, да и результат объяснить сложно. Плюс ещё тут функция оптимизации полегче. В целом так как нашим business needs удовлетворяет, мы себе и оставим пока не увидим проблем.

Философский вывод для меня был в том, что AlphaZero легче научить играть в шахматы, чем писать ассемблер.

В целом, с людьми так же.


Для 9-16 байт была имплементация, которая умножала два раза. Новая имплементация от AlphaZero получилась только с одним:

uint64_t lo = UnalignedLoad64(p);
uint64_t hi = UnalignedLoad64(p + len - 8);
lo = rotr(lo, 53); // right rotate by 53
state += kConstantPrime;
lo += state;
state ^= hi;
uint128 mul = static_cast<uint128>(state) * lo;
return static_cast<uint64_t>(mul) ^ (mul >> 64);

https://github.com/abseil/abseil-cpp/commit/74eee2aff683cc7dcd2dbaa69b2c654596d8024e

Когда вы находите минимум/сортируете/делаете кучу из элементов, нужно чтобы ваши элементы удовлетворяли свойству строгого слабого порядка (по-английски strict weak ordering).

Этот порядок для компаратора comp и множества S означает несколько свойств:

1. Антирефлексивность: comp(x, x) всегда false, 1 < 1 очевидно неправда
2. Ассиметричность: comp(x, y) и comp(y, x) не могут быть оба true
3. Транзитивность: если comp(x, y) и comp(y, z), то comp(x, z)
4. Транзитивность эквивалентности. Мы назовём 2 элемента эквивалентными, если comp(x, y) и comp(y, x) оба false. Тогда если x, y эквивалентны, а также y, z эквивалентны, то x и z тоже эквивалентны.

Если все эти свойства удовлетворяются, то все алгоритмы нахождения минимумов/максимумов/сортировок просто работают. Из-за этого всякие проблемы с тем, что сортировка floats с NaN не работают (так как comp(NaN, x) и comp(NaN, x) всегда false и свойство 4 ломается).

Тем не менее, дальше возникает инженерный вопрос, а если мне передают элементы в поиск минимума/любой другой алгоритм, как можно сообщить пользователю, что элементы не удовлетворяют порядку?

Можно все свойства проверить. Как вы можете видеть, надо проверять все тройки, это |S|^3 сравнений.

Если у вас линейный алгоритм поиска минимума или сортировка за |S| log |S|, то это ни в какие ворота не лезет.

Можно взять sample из 5-10 элементов и проверить в дебаг моде. Тоже вариант, и он даёт плоды найти сломанные компараторы.

Удивительный факт заключается в том, что существует алгоритм, который отвечает "да" или "нет" на вопрос, а удовлетворяет ли множество строгому слабому порядку за O(|S|^2) сравнений.

Это уже намного лучше. На тысячу элементов вы можете проверить 30-40 и замедлив вызовы всего в 2 раза.

Для этого надо

1. Посортировать множество каким-нибудь алгоритмом. Если строгое слабое свойство не выполняется, то этот алгоритм не должен падать. Учтите, что всякие std::sort могут упасть, а вот heap sort/bubble sort можно написать, чтобы даже если всё сломано, они выдадут какой-то результат.
2. Найти первый P, что comp(S[0], S[P]) is true. Если такого P нет, то P равно |S|.
3. Проверить все пары A, B до индекса P, что comp(S[A], S[B]) и comp(S[B], S[A]) false. Это означает, что все элементы до P должны быть эквивалентными
4. Проверить декартово произведение индексов A < P и B >= P, что comp(S[A], S[B]) is true и comp(S[B], S[A]) is false. Это означает, что P является разделительной точкой, чтобы элементы уже можно было сравнивать.
5. Если все проверки прошли, убрать первые P элементов и повторить. Если что-то не прошло, вернуть FALSE

Такой алгоритм работает за |S|^2 сравнений, так как если мы убираем P_1, ..., P_k элементов на каждой итерации, то мы делаем

P_1^2 + P_1(|S| - P_1) + P_2^2 + P_2(|S| - P_1 - P_2) + ... <= P_1|S| + P_2|S| + ... = |S|^2 сравнений.

Доказательство почему оно возвращает правду я написал в своём репозитории с удобным шаблонным вызовом

https://github.com/danlark1/quadratic_strict_weak_ordering

Надо тащить в LLVM/GCC/Rust/D, whatever, потому что у всех проверки не сильно мощные, а эта может найти больше, так как позволяет больше элементов забрать в sample и соответственно показать больше проблем.

Давайте попробуем продвинуть вчерашнюю на Hacker News: https://news.ycombinator.com/item?id=34312306. Плевать, если не зачтёт

Ещё вчера спрашивали зачем это, скинули репозиторий, где находили с помощью проверок достаточно большое количество багов в софте: https://github.com/yugr/sortcheck#what-are-current-results

1. Сегодня я проснулся, и мы лишь нашли ещё один corruption в zstd. https://github.com/facebook/zstd/issues/3416

2. Вообще мне недавно понравился пост про "Things they didn't teach you about Software Engineering": https://vadimkravcenko.com/shorts/things-they-didnt-teach-you/

Там есть пункт про "Assume everything has bugs" и "You work with uncertainty most of the time".

В software самые важные уроки, которые я освоил

* Всё всегда разломано. Держится всё буквально на соплях
* Если что-то не разломано, время это разломает
* Куда ни посмотри, везде можно сделать лучше
* Нулевая job security, все очень быстро меняется, язык, который учил через 3 года может быть уже нерелевантным. В бекенде чуть получше и тут хотя бы вкладываться в алгоритмы/науку о распределённых системах/старый МЛ, но всегда ощущение, что если я не почитаю статей за месяц, я деградирую.
* Самый сильный рост как инженера был это находить certainty из uncertainty. Для этого надо было очень хорошо освоить свои тулзы, поиск по коду, IDE, vim и тд.

3. Я тут писал про fleetbench недавно (https://www.tg-me.com/experimentalchill/178), это репрезентативные бенчмарки гугла. Мы теперь им пользуемся, чтобы смотреть на изменения! И люди им тоже пользуются пытаются. Пример:
https://github.com/protocolbuffers/protobuf/pull/11102#issuecomment-1374878279. Микробенчмарки исправились на 50%, а макробенчмарк за 1-1.5%, что тоже очень круто!

В панике, что после недели не о чем писать


Я до занятием перформанса и MapReduce в Google работал над файловыми системами. Не очень большая, но и не очень маленькая. Было пространство сделать хорошо, заниматься интересными распределёнными системами и не сломать слишком много.

Мне вспомнилось как мы сильно, очень сильно старались отделить сервер метаданных, который хранит как расположены чанки данных, решает в каком порядке всё применять через Paxos и сервер, который читает и создаёт чанки с данными. Метаданные легче, они менее требовательны к security, но самое главное, что сервисы почти независимы. При записи файла вы можете создать чанк, пойти с id этого чанка и положить его в метаданные. Если что-то происходит с сервисом метаданных, всё то, что вы пишете будет куда-то записано, и мы хоть и попотеем, если будет беда, но данные не потеряем.

Помогло раз, когда при релизе был баг, мы смогли восстановить все данные и как-то мануально их отдать. Это был хороший урок, что когда вы пишете storage систему, делаете что угодно, но главное не теряете данные. Удаляйте только с TTL в несколько дней, чтобы можно было отревертить, делайте read only modes и так далее. Проверяйте консистентность раз в день, всё это достаточно полезно находить сюрпризы раньше, чем позже.

По поводу этого мне нравится, что Ceph (при всех его проблемах с расширением) делался с этим умом

https://docs.ceph.com/en/latest/architecture/

В SQLite тоже много написано о том, что очень сложно поцарапать базу https://www.sqlite.org/lockingv3.html

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

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

Завтра что-то более содержательное напишу, сегодня как-то так

Сегодня поздний пост, но как есть.

Одна из оптимизаций, которая мне пришла в голову, и к которой у меня было не так много open source решений это просмотр коротких циклов. Почему это интересно?

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


for (int i = 0; i < n; ++i) {
data[i] ^= other_data[i];
}

К сожалению, тут есть проблема, что data и other_data могут пересекаться и такая проблема называется aliasing. Компилятору порой просто нет информации, чтобы это предотвратить. Иногда это вырождается во что-то страшное как просто побайтовый цикл или что-нибудь ещё неприятное.

Компиляторы С/C++ стараются создавать SIMD блоки, если указатели не пересекаются (см внизу https://gcc.godbolt.org/z/o7xhadsMq). Проблема в том, что так происходит не всегда, и векторизация просто не самый надёжный способ, оно растит бинарь достаточно мощно.

Скажем есть большой бинарь ClickHouse. Проблема, с которой я столкнулся -- я хочу увидеть в большом бинаре и после всех performance тестов (их тысячи) короткие hot циклы, скажем, 5-6 инструкций, они скорее всего не очень векторизованы из-за каких-то таких проблем. Мы видели кейсы, когда мы находили случайно такие пропущенные оптимизации

https://github.com/ClickHouse/ClickHouse/pull/9442
https://github.com/ClickHouse/ClickHouse/pull/9304

Единственная проблема в том, что я не понимаю как это сделать без открывания питона и парсинга objdump. Я хочу задать какой-нибудь SQL запрос с функцией LAG, где каждый ряд это инструкция, и есть какое-то количество колонок с адресами и прыжками, каунтерами, сколько раз мы посемплили ту или иную инструкцию.

В итоге я использую что-то вроде

objdump -Mintel -ldSrwC --no-show-raw-insn --visualize-jumps=extended-color

И смотрю _напрямую_

И всё равно надо открывать питон и потратить день, чтобы написать колоночный формат disasm'а. Иногда даже проработав годы в индустрии, попросту не хватает тулинга. Я вообще думаю, что надо этим намного больше заниматься, чем самим перформансом

https://arxiv.org/pdf/2301.02432.pdf

Myths and Legends in High-Performance Computing

Статья хоть немного странно выглядит в качестве научной статьи, но достаточно интересно описывает то, какие мифы и легенды в High Performance Computing существуют.

Миф 1: Квантовые вычисления вытеснят HPC!
Миф 2: Мир захватит deep learning!
Миф 3: Сугубо точная специализация железа, как в смартфонах, позволит выйти за рамки закона Мура!
Миф 4: Все будет работать на каком-то ускорителе! (FPGA)
Миф 5: Программируемые железки дадут вам 100-кратное ускорение!
Миф 6: Скоро мы будем работать на Zettascale!
Миф 7: Системам следующего поколения нужно больше памяти на ядро!
Миф 8: Мы будем разъединять ресурсы из материнской платы (a.k.a стойки только с памятью, только с дисками и тд)
Миф 9: Приложения продолжают улучшаться. Даже на старом оборудовании!
Миф 10: Фортран мертв, да здравствует DSL!
Миф 11: HPC перейдет к низкой или смешанной точности!
Миф 12: Все высокопроизводительные вычисления будут поглощены Clouds!

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

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


However, we have to be cautious that—
just as hardware improvements have physics and engineering
limits—the “Algorithmic Moore’s Law” also has its own
limits: numerical stability, hitting asymptotic limits, etc. That
being said, those limits might not be as clear and quantifiable
as the limits on hardware. That is since even if one numerical
method hits its limit, domain experts can often reduce/precondition their problem to another numerical method that is
more efficient.

выглядит недостаточно происследованным. Негативные результаты в алгоритмической теории очень сложны. И если мы сможем положить много задач на SIMD или избавиться от перекладываний данных, чтобы не упираться в memory wall, изменения будут происходить и происходят -- SIMDJSON, лучшие базы данных, лучше компрессоры, лучше кеши и так далее. Ускорений в 1024x я не жду, но честно верю, что любой текущий софт можно раз в 5-6 ускорить, к сожалению, что-то оптимальное не очень человечное -- SIMDJSON невозможно читать, например.

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

Вообще это достаточно метафизическая фраза, которая сработала на меня. Не факт, что работает у других, и историй я слышал много.

Вещи, без которых я не могу жить в рабочем дне:

1. Понятное дело, Google
2. Поиск по коду. Пользуйтесь IDE, пользуйтесь cs.github.com, возможно пользуйтесь copilot. Когда у вас есть API, какая-то мелкая задача, все эти вещи дают быструю скорость просмотра, быстрое обучение мыслительному процессу как устроен тот или иной фреймворк. В один момент вы начинаете понимать от корки до корки как устроены библиотеки, языки, концепты. Примеры, понимание дизайна помогают привыкать. Чем быстрее ваши методы нахождения информации, тем быстрее вы выучите. В какой-то степени IDE даже хуже, потому что кодовая база проекта имеет малую видимость, а поиск по коду гитхаба имеет все репозитории мира.

Пример: я учу https://github.com/3b1b/manim для рисовалки анимаций для математики. Документация не оч, зато тысячи примеров https://github.com/3b1b/videos. Придумал себе задачу, пошел учить, за день учишь прилично, за месяц уже плаваешь в этом. За 3 находишь баги, репортишь, за год пишешь свое (шутка) :)

3. Люди, без них вообще не понимаю как. Мой САМЫЙ сильный рост был, когда я смотрел как мой босс пишет код, ищет информацию, пользуется своими тулзами, фактически скринкаст рабочего дня. Мыслительный процесс профессионала просто невероятно важен. Я всегда с джунами включаю свой экран и показываю как решать их проблемы систематично через тулзы. Постоянно смотрю на других и учусь у них.
4. Понимать тулзы. Я почти уверен, что очень много, кто не знает как работает git, shell, vim, системы сборки и тд. Это безумно глубокие темы, идти смотреть в код, попробовать все команды сильно позволяет расти с точки зрения осознания, а что вообще можно сделать за пару минут.
5. Читать статьи, следить за релизами. Кто-то сделал лучше? Почему вас это останавливает сделать? Принципы/философия/лицензии/бюрократия?

Тулзы, люди и т.д. как раз создают ощущение определенности, когда у вас задачи не получаются. Понятное дело можно ещё тут много говорить про математику, алгоритмы, теорию про P/NP для всяких отрицательных результатов, но такие вещи пригождаются меньше в software engineering.

Помните, что как индустрия Software Engineering существует лет 50 максимум. Мы едва начинаем понимать, что работает, а что нет. Все очень быстро меняется, понимать как решать неопределенность и постоянно учиться позволило мне достаточно быстро вырасти. Возможно это неплохая стратегия, возможно я ошибаюсь.

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

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

Мы тут выложили Protobuf Table-Driven Parser.

Основная идея, что для каждого отдельного типа Protobuf мы генерировали огромный кусок кода, и он рос линейно/супер линейно с количеством полей в протобуфе.

Рост происходил из-за того, что компилятору мы давали код в духе


auto [tag, wire_format] = ReadTag(ptr);
if (tag == kMessageProtoTagNumber) {
ptr = ParseMessage(ptr);
}
if (tag == kIntProtoTagNumber) {
ptr = ParseVarInt32(ptr);
}

И так далее. В итоге был огромный кусок кода и компилятор уставал аллоцировать регистры, делать push, pop регистров при входе/выходе из вложенных функций, компиляция росла. Я писал об этом аж 1.5 года назад https://www.tg-me.com/experimentalchill/95 про аттрибут [[musttail]]. И теперь то самое начало давать свои плоды.

Так как формат фиксированный, мы можем просто брать функцию из значения тега и вызывать её, сохраняя все регистры и заставив компилятор не делать push/pop. 6 параметров регистров мы спрятали PROTOBUF_TC_PARAM_DECL.

#define PROTOBUF_TC_PARAM_DECL \
::proto2::MessageLite *msg, const char *ptr, \
::proto2::internal::ParseContext *ctx, \
::proto2::internal::TcFieldData data, \
const ::proto2::internal::TcParseTableBase *table, uint64_t hasbits

В итоге оно выглядит как

data.read_tag<type>();
data.read_data<type>();
ptr += size_read;
SetField(data.offset(), ptr);
has_bits |= 1 << data.index_idx();
ReadInstruction()
dispatch to next Instruction from table

Пример можно посмотреть здесь.

Плюсы, которые мы получили:

1. Мы сильно уменьшили размер генерируемого кода и время компиляции. Теперь нам нужна только таблица с инструкциями что делать для того или иного поля
2. У нас нет переполнения стека из-за отсутствия push/pop, теперь мы поддерживаем сообщения любой вложенности
3. По перфу нейтрально -- выиграли в push/pop, проиграли в статичности функций
4. Легче понимать профили бинарей, что они парсят на уровне сообщений
5. Только 1 имплементация парсинга на всех
6. Мы сможем менять формат протобуфов даже на ходу

Как мы сможем его менять? Скажем, при типе int32 мы пишем varint. Если число отрицательное, мы пишем 5 байт из-за того, что отрицательные числа наполнены единицами. А что если мы хотим написать его в типе sint32, чтобы писать меньше? В прошлые разы мы генерировали парсинг на основании типа и формата поля, то есть цикл парсинга мог воспринимать тип только строго.

Теперь мы можем писать int32, скажем, как

1. Если положительное, просто в varint
2. Если отрицательное, в отрицательном varint
3. Цикл парсинга всё поймёт, так как привязки к типу нет, и число в память напишется как напишется
4. Мы сэкономили байты и не проиграли в парсинге

Такие оптимизации можно делать даже на ходу -- алгоритм сериализации можно подменить так же.

Проблема в том, что очень много старых версий протобуфов, где логика парсинга строго привязана к типу. Она была привязана к типу из-за перфа, не очень хотелось писать код, который парсит int32 в зависимости от потенциально разных wire formats, теперь -- это не важно и по дизайну не медленнее старого подхода.

Пройдёт 3-5 лет, и мы сможем так делать по дефолту (build horizon). Пока -- под опцией.

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

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

Писать продолжу чуть чаще, чем в старом формате -- полтора-два раза в неделю с такими забегами раз в полгода.

Ну а вот вам интересный факт: если вы отключите L1/L2 префетчеры для кешей, то вероятно для своих серверных или жёстких по памяти процессов вы получите прирост производительности

https://www.reddit.com/r/pcmasterrace/comments/usoko0/disabling_hardware_prefetcher_l1_and_l2_led_to_a/

Почему? Потому что мы все больше упираемся в память, а префетчеры могут ошибаться и занимать вообще место для работы с памятью. Результаты будут скорее всего смешанными, то есть вероятно вы увидите прирост, но некоторые части кода сильно замедлятся. Особенно те, которые работают с большими кусками памяти.

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

Если вы работаете в HFT и у вас AMD машинки, я думаю, такую тему можно попробовать.

https://twitter.com/jorgbrown/status/1616711913106444289

Это один из моих коллег. Наверное, он лучше всех разбирается в микро и макро компиляторных оптимизациях в мире. Он мне рассказывал про m68k, как важно следить за компилятором и просто я читал много его тредов. В прошлом году он сэкономил несколько миллионов долларов Гуглу. После 18 лет работы его уволили. Вообще никто не понимает, почему.

Я пока остался, но для Европы процесс увольнений в Гугле затянется на несколько месяцев. Что будет, то будет. Но проживать такие события интересно

Донаты

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

В идеале я бы работал только на себя, может, это приблизит меня к этой цели. Без отдачи аудитории сложно вычитывать каждое слово, а с ростом аудитории растёт ответственность. Я верю, что это поможет мне увеличить качество блога в разы и реализовать амбициозные идеи.

Донаты:

https://www.patreon.com/danlark/ -- Patreon
https://boosty.to/danlark -- Patreon, но для русских читателей
https://www.paypal.com/donate/?hosted_button_id=UNZQYV2YP2RBE -- Paypal, если вы хотите остаться незаметным
ETH: 0xDD1b1927dF4533Dcc8975496670228fbC303F941 -- крипта для совсем незаметных

Маленькие суммы позволят получать доступ к постам на 1 день раньше (в итоге качество написанного текста будет расти). Большие донаты дадут возможность проводить регулярные 1:1 (менторство, обучение, консультации) со мной. Рекламы в канале пока ещё долго не будет.

Илья Токарь, мой сокомандник, засветился на Phoronix https://www.phoronix.com/news/LLVM-Google-Light-AVX-Option

Я писал про то, что поддерживать зоопарк железа достаточно трудно и из-за этого сложнее использовать новые инструкции процессоров. После 12 лет (AVX вышел в 2011) на таком разнообразии стало возможным делать шаги в сторону включения AVX по умолчанию, но есть несколько нюансов:

1. Герцовость процессора понижается, если использовать сложные инструкции из AVX/AVX2 на процессорах года до 2016. Для простоты можете считать, что если есть операция умножения или работа с float, то понизится, если нет, то нет
2. Стандартные инструкции вида загрузить/положить в память/сделать shuffle байт не понижают герцовость
3. В компиляторах есть флаги -mavx -mavx2 и так далее, которые не очень учитывают герцовость. В итоге, чтобы таких эффектов не было, можно было только разрешить работать с 16 байтными регистрами xmm семейства
В итоге Илья решил добавить так называемый LightAVX флаг, чтобы можно было использовать 32 байтные инструкции, которые не вредят окружению и не понижают герцовость. Доступно с LLVM 16.

Тем не менее хочу сказать, что просто включение AVX не даст много преимуществ, да, всякие копирования памяти может быть улучшатся, но самые большие ускорения вы скорее всего увидите из-за Bit Manipulation Instruction Set. Они умеют занулять младщий единичный бит, делать операции AND NOT (~x & y) и больше используются компиляторами. Сейчас включить BMI и не включить AVX невозможно, зато станет возможным включить LightAVX и BMI и насладиться большинством ускорений. Такое только подходит для пользователей, кто должен работать с большим разнообразием процессоров -- базы данных, большие cloud компании и тд. Если у вас есть контроль за железом, пользуйтесь всем, чем можно.

1. В ZSTD появился externalMatchfinder, вы теперь можете писать свои алгоритмы компрессии. Для чего?

Очень много запросов от индустрии по ускорению ZSTD, поэтому разные компании хотят построить hardware акселераторы для компрессии. Инженеры из Meta задизайнили решение. На выход вы даёте множество ZSTD_Sequence -- тройки из (litLength, matchLength, offset) -- сколько скопировать "просто так", потом сколько скопировать от уже раскодированного и откуда взять оффсет раскодированного. Далее ZSTD сам уже применит Huffman, FSE.

Полезно, в PR в репозитории не мало упоминаний людей из Intel, что-то явно хотят сделать.

2. Я недавно перечитывал статью про Borg -- система оркестрации в Google и обратил внимание на интересную деталь. Если коротко, когда приходит новое задание, Borg должен посчитать оценку, на какие машины лучше всего его положить. Я задался интересным вопросом, ведь машин сотни тысяч/миллионы, как они избавляются от квадратичного роста. Оказалось, решение достаточно интересное, надо просто смотреть в случайном порядке, и оно само сойдётся:

Relaxed randomization: It is wasteful to calculate feasibility and scores for all the machines in a large cell, so the scheduler examines machines in a random order until it has found “enough” feasible machines to score

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

3. Мы тут недавно списывались с людьми, которые пишут в Rust хештаблицу с открытой адресацией похожую на abseil'овский flat_hash_map, зовут их hashbrown. Нашли интересный момент:

В Abseil мы вычисляем хеши H1, H2, первый хеш для того, чтобы понять куда в таблицу с открытой адресацией положить элемент (по модулю степени двойки), второй для того, чтобы положить в отдельный массив и фильтровать элементы до того, как мы будем их сравнивать. Первому мы даём 57 бит хеша, второму лишь 7, чтобы помещался в один байт и оставался битик, чтобы пометить удалённые или несуществующие элементы.

Интересный момент, а откуда эти 7 бит брать из вычисленного хеша в 64 бита? Мы решили брать нижние 7 бит, потому что хеши на верхних битах иногда ведут себя плохо, не хватает энтропии. В итоге чтобы поддержать таблицу из 2^N элементов, нам достаточно где-то N+7 бит энтропии. В итоге можно считать не 64 битные хеши, а лишь 48, так как хеш таблицы размера 2^40 огромные.

В Rust решили брать старшие 7 бит из 64. Это даёт свои плюсы. Нам в любом случае надо сделать сдвиг (в abseil на 7, в rust на 57). А вот в Abseil нам надо ещё сделать маску на нижние 7, когда как вычисление по модулю для нахождения позиции можно брать без какой либо операции в Rust. В итоге Rust использует на 1 инструкцию меньше, зато им стоит поддерживать, что старшие биты в хеше должны иметь достаточно энтропии.

Такие трейдоффы.

На этой неделе была тьма анонсов про поиски. Вышел новый Bing, в Google анонсировали Bard.

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

А зато мне хочется сильно похвалить команду GitHub за то, что теперь cs.github.com индексирует 45 миллионов репозиториев с 115 млрд файлов.

У обратных индексов по всему, что связано с кодом история достаточно давняя и не сильно заисследованная: Russ Cox рассказывал про то, что обратная индексация по триграмам и токенизация запроса по им работает достаточно хорошо, но на масштабах GitHub они признались, что такой подход работает только до поры до времени. Почему? Потому что мы любим писать всякие циклы через последовательности for ( и поэтому они плохо фильтруют документ, если в запросе есть триграма for. В Google мы рассказывали, что долго использовали суффиксные структуры, но в итоге решили использовать решение о sparse n-grams, которое хорошо заработало, и в статье GitHub упоминается. Немного истории:

Если вы будете использовать 4, 5 граммы, то есть индексировать 4-5 подряд символов в document_id и позицию, то индекс сильно вырастет, поэтому это как-то непрактично, а 2-граммы не сильно хорошо фильтруют. Но хочется добавить и подстроки побольше, чтобы быстрее фильтровать. Чтобы запрос хорошо фильтровал, надо чтобы разбивка n-grams у подстроки запроса была подмножеством разбивки документа (то есть если есть подстрока s в запросе, то любая надстрока S в документе должна иметь n-grams от s), иначе будет некорректный поиск. В итоге придумали схему, которая в среднем увеличивает индекс в пару раз и добавляет приличное количество подстрок бОльшей длины:

На каждую биграму посчитать хэш, поставить на позиции значения хешей. Взять только те подстроки, в которых все значения хешей внутри строго меньше, чем на краях. Так как хеши не зависят от подстрок, свойство о разбивки подстрок выполняется. С другой стороны количество строк увеличится в среднем в константу раз, так как количество подстрок попавших в индекс при переходе с длины n на n+1 уменьшается в среднем в экспоненциальное количество раз. Если аккуратно выписать все выражения, количество строк в индексе будет примерно в 2 раза больше, а по размеру в большую, но удобную константу, когда индексация происходит построчная. Инженерно можно ещё запретить слишком большие n-grams, хорошо пожать с алгоритмом и положить на SSD. В итоге будет индекс GitHub, который хорошо расширяется. Интересные задачи у них скорее всего связаны с метаданными, метаданные на 115млрд растут всё таки линейно, но об этом они ничего не написали :(

В итоге если вы ищете какое-нибудь выражения с очень частой подстрокой типа for (int i = 42, то вы не будете искать пересечения триграм с for, которая находится в каждом файле, а будете искать в том числе какую-нибудь большую подстроку вида i = 42, что встречается реже. В итоге меньше проверок на вхождение, лучше фильтрация. А если вы ищете то, что находится в миллионах документов, скажем, вы просто ввели запрос for, то там не так важно что вернуть, непонятно что вы и хотите, если спрашиваете такое, и документов скорее всего будет много.

В добавочку:

Пригласили на LLVM Code Generation and Optimization Symposium, буду рассказывать с коллегами про то как мы меняли std::sort в LLVM и в Google. Спойлер: у истории есть продолжение, а именно хоть огня и не было, а вот ускорений в проде по сравнению с микробенчмарками мы не увидели

https://llvm.org/devmtg/2023-02-25/

Если мне, конечно, одобрят визу в Канаду к концу февраля :)

SIMDProto

Я убил приличное количество времени думая о проблемах с памятью в последнее время. Одна из них -- можно ли как-то быстрее парсить protobufs. Хочу здесь поделиться, с какими проблемами я столкнулся, и почему это сложнее, чем кажется.

Самая главная проблема, что практически невозможно парсить varints быстро. Попробую дать интуицию:

В JSON вы можете найти символы ", {, }, [, ], : достаточно быстро, они будут в какой-то степени разделителями, показывая где начало и где конец поля. После этого вам надо найти все позиции и на каждый найденный символ найти второй соответствующий, например, на открывающую скобку -- закрывающую. Это зависимость (цепочка) длины 1, остальные байты легко пропускаются, итерации по битам делать не надо.

У протобуфов числа устроены таким образом, что мы должны смотреть на старший бит байта, чтобы понять, какой следующий -- что это продолжение числа или начало нового поля? В итоге, чтобы понять разделители и их индексы, нужно решать достаточно длинные цепочки, и в итоге парсер прыгает как-то по одному-двум байтам. Если хочется выйти из лимита, как 1 cycle на байт для чисел, тегов и тд, нужно уметь обрабатывать varints пачками, притом пачками в том смысле, чтобы varint спокойно могли находиться между других полей, в том числе широкие вектора могут состоять из такого ужаса:

1. [строка][tag][varint][tag][size][строка]

2. [varint][tag][varint][tag][varint]

И так далее. В итоге если вы посчитаете огромное количество различных конфигураций, будет не так красиво и в итоге нужна ветвистая логика для всех случаев, сложные инструкции как tzcnt, чтобы считать пропускные биты и итерации по битам с 2 cycle на байт.

Тем не менее у нас есть кандидаты для парсинга varint с помощью SIMD.

Любые попытки написать даже простой код заканчиваются неудачно. В итоге сейчас SIMDJSON быстрее и популярнее протобуфов. Даже по скорости на 1 бит информации (JSON обычно весит больше, чем прото).

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