Тут недавно стукнуло как я 5 лет устроился на первую работу и я, конечно, был безумно рад, что восьмая (десятая? шестая?) часть моей карьеры прошла. Учитывая, как это было порой темно, но все же я больше находил позитивных моментов. Удалось поработать с огромными движками вычислений в больших компаниях, удалось помочь стартапной тусовке. Удалось коммитить в open source и много помочь core вещам как компиляторам, стандартным библиотекам, компрессорам, индексаторам и тд. Удалось проявить какие-то свои таланты, найти область, в которой не так много людей и монетизировать и себя, и получить много счастья одновременно. Интересно, что даже за 5 лет мир меняется сильно. Скажем

* Я убил много времени на С++. К сожалению, индустрия меняется в сторону, что любой проезд по памяти стоит дороже, чем перформанс, и кажется переезд на Rust-подобное нельзя избежать. Вот сижу учу Rust, сложно, бесит, что сильно надо мышление менять, чтобы писать хороший код на Rust. Самое противное, что рядом нет того, кто бы меня дергал и рассказывал, что так неправильно. С плюсами было так, что я попал в кучку профессионалов и со временем стал понимать многие кишки C++. С Rust придет только с опытом.

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

* Я не могу сказать, что сделал какие-то продукты, которые сильно видны людям. Мне это скорее нравится, быть таким behind the scenes, но самое плохое, что приходит с опытом это ожидания и ответственность.

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

* Вещи за 5 лет стали лучше. Лучше диагностика ошибок, лучше интерфейсы ядра, быстрее библиотеки, я стал меньше раздражаться неработающим вещам, все потихоньку становится менее плохим (highly opinionated):

* Мы пробили 1M QPS чтения диска, и SSD стали намного более массовыми
* Мы наконец-то имеем серьезный и инженерный алгоритм сжатия ZSTD
* Мы поняли как не проезжать по памяти -- Rust
* Мы научились быстрым CRDT
* Мы на скейле стали делать лучше алгоритмы и кажется стало виднеться плато вычислений процессоров и памяти
* Мы научились делать серьезный и бесконечно развивающийся SIMD типа SVE
* Очень много кто переходит с x86 на Arm, а дальше скорее и RISCV
* Мы сильно продвинулись в тестировании баз данных, транзакций и тд.
* Сеть все ещё растет и предела пока нет :)
* Мы научились намного лучше делать Profile Guided Optimizations, Post Link optimizations.
* Мы показали, что JIT очень важен до сих пор (см. Rosetta)
* Все таки нашли применение AVX512
* Лучше аллокаторы, поняли как huge pages влияют на разнообразный продакшн (см. TCMalloc)
* Принесли серьезные системные языки в браузеры (WebAssembly)
* Начали сильно пробивать игры под Linux

So far мне нравится. Я буду дальше следить, что мне хочется делать, но за 5 лет я лишь чуть чуть приоткрыл сундук с магией под названием Systems Engineering. Дальше -- больше, куда мы денемся, прогресс не остановить, и все мы к нему причастны, куда ни посмотри, везде можно принести пользу

В последние несколько лет не слишком много происходит интересных компиляторных оптимизаций, которые помогают всем, тем не менее от версии к версии мы видим в районе 0.5-1% исправлений, учитывая, что апдейты происходят 2 раза в год, мы попадаем в Proebsting's law, что компиляторы становятся в 2 раза быстрее каждые 18 лет (1.005**36 ~ 1.20, 1.01**36 ~ 1.43), что было несколько раз опровергнуто, но остаётся забавной байкой :)

Я уже писал, что даже на архитектурах Arm и x86 в компиляторах полно ещё всякого делать, и the work is never done, но всегда выбираются пути наименьшего сопротивления и наиболее перспективные направления для вытаскивания процентов из разных бинарей -- Profile Guided Optimizations. Как будет исполняться код, зависит от данных, и тема как вытащить лучше оптимизации из профиля, одна из самых приносящих пользу в последнее время. Я думаю, если посчитать из открытых источников, то Inliner PGO+ThinLTO+PD Inlined String Proto, то будет в районе 7-10%, где ThinLTO даёт больше всех.

Rule of thumb сейчас, что большинство Profile Driven (PD) оптимизаций дают в раойне 0.5-1%, на сильно больше расчитывать тяжело и если вы сможете что-то такое придумать, я думаю вы спокойно можете стать легендой компиляторостроения.

На этот раз о двух вещах.

Profile driven cmov

https://discourse.llvm.org/t/rfc-cmov-vs-branch-optimization/6040

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

Плюсы cmov в том, что нет branch, минусы, что все данные подготовить надо перед инструкцией.

Идея в том, чтобы сделать cost модель, насколько дороже будет инструкция conditional mov, чем branch и применить её.

Agner Fog пишет про эвристику, которая не супер идеальна, но просто хороший дефолт:

Branch is faster than a conditional move if:

1. move is part of a dependence chain, especially a long loop-carried one,
2. and prediction rate is better than 75%; or
can avoid a lengthy calculation of non-chosen operand

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

В итоге даже прототип дал 0.5-1% поиска гугла. Я думаю уже зарелизили. Мораль этой истории показала, что не было одного или даже десяти мест, которые всё исправили, а исправились в районе пары-тройки сотен мест, которые набрались и суммарно дали такой прирост. Что не может не радовать, потому что я долго верил, что компиляторный перф сильно зависит от топ $МАЛОЕ_КОЛВО функций. Эта история поучительна и для меня.


Практика: В clang я обычно при написании кода если хочу cmov, то пишу тернарный оператор, а не if statement

uint64_t val = cond ? x : y; // usually cmov
if (cond) { val = x; } else { val = y; } // usually branch

Profile driven protobuf inlined string

В протобуфах есть поля вида string. Исторически они замаскированы под указателями, потому что люди чаще поля не используют, чем используют, а также чуть удобнее аллоцировать на общих кусках памяти под названием арены. Проблемы указателей, что их надо разыменовывать, и за это мы платим много. Если включить обычный std::string на всех, будет плохо, протобуфы разрастутся, аллокации на аренах будут сложнее и тд.

Прелесть в том, что некоторые строки очень маленькие и очень горячие, поэтому Small String Optimization может работать лучше, чем разыменовывание указателя. Решение простое, давайте мы посэмплим в проде размеры и rate с которым мы обращаемся к тем или иным полям (просто stacktraces) и перекомпилируем горячие и маленькие строки в InlinedStringField.

Снова в районе 0.5-1% выигрыша распределенного примерно по всему бинарю. Мы зарелизили InlinedStringField, но полный e2e профиль и оптимизации пока непонятно как. В целом, я думаю, что если очень надо, логику написать можно.

Красиво, две истории, когда вещи stack up среди сотен мест и дают хороший буст.

Неожиданно для себя и людей вокруг меня, я решил поменять команду.

После пары лет в Flume/MapReduce infrastructure and efficiency, я столько возложил на свои плечи, что сейчас достаточно сложно стало тащить на себе то, что взял, поэтому пытаясь что-то починить в своем подходе, я выбрал самый простой -- полностью свалить этот груз. Ухожу я на забавной ноте, когда я стал понимать наш сервис, интерфейсы очень хорошо, и кажется почувствовал, что пора. Плюс я уже не могу терпеть очень поздние встречи с Долиной, в этот раз Нью-Йорк, полегче из Лондона будет общаться.

Перехожу я в команду Efficiency League/Data center efficiency/Bare metal efficiency, где буду заниматься тем, о чем пишу здесь, в блоге: перформансом всего, чего можно дотянуться в Google: от latency Raft и поиска до software/hardware co-design. С этой командой я много работал, пора рассказать Google пару историй, попробовать десяток идей с полной поддержкой от менеджемента. Плюс в момент рецессии датацентры сильно ужимаются, так что любые выигранные ресурсы сейчас как никогда кстати.

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

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

1. Мы тут недавно выложили fuzztest. В целом если вы используете GTest, то вы можете написать что-то вроде


void MyApiAlwaysSucceedsOnPositiveIntegers(int i) {
bool success = MyApi(i);
EXPECT_TRUE(success);
}
FUZZ_TEST(MyApiTest, MyApiAlwaysSucceedsOnPositiveIntegers)
.WithDomains(/*i:*/fuzztest::Positive<int>());


И всё, у вас автоматически вместе с тестами фаззинг вашего API. То есть можно не только писать юнит тесты, но и тестировать свойства вашего API в том же файле.

После этого хоть и требуется настройка как гонять это на continuous basis, но если вы действительно паритесь насчёт тестирования ваших программ на C++, то вы добавите continuous testing на это. А локально можете выбрать, сколько вы хотите потестировать ваше API.

К сожалению, только на Bazel, но я решил портировать на CMake:
https://github.com/danlark1/fuzztest_cmake. Welcome

2. Тут zstd рассматривает одну интересную семантическую оптимизацию: нахождение оптимательного количества бит для дерева Хаффмана.

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

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

Чтобы лучше понять контекст, Zstd использует два метода сжатия -- Huffman и FSE: первый очень стандартный, когда мы символам присваиваем префиксный код, а второй исправляет недочёты Huffman: например, если какой-то символ встречается 90% раз, то теория информации говорит, что мы можем кодировать это log2(1/0.9)=0.15 битами, когда как дерево Хаффмана присваивает минимум 1. Чтобы достичь лимита придумали FSE, пока в детали углубляться не стоит, но суть в том, чтобы менять биты ответственные за символы по ходу декодирования.

Huffman быстрее, FSE медленнее из-за нестатической таблицы. FSE хорошо работает, когда данных побольше, Huffman на маленьких данных не видит большой разницы с FSE.

Zstd делит данные на две категории -- Literals и Sequences -- первое -- обычные данные, которые стоит копировать (можете для простоты думать, что это словарь), а Sequences -- команды, откуда копировать, нужно ли копировать из уже раскодированных данных. Решение о том, чтобы кодировать литералы Huffman интересное, их не очень много по сравнению с командами о копировании.

Чтобы подобрать оптимальное дерево Хаффмана мы все знаем алгоритм -- взять два самых невстречающихся, соединить, суммировать их вероятности, удалить старые.

К сожалению, чтобы записать информацию о дереве Хаффмана, нужно тоже место:

1. Для весов
2. Для самого алфавита литералов

В итоге это баланс между Huffman header и compression estimation. Чем меньше веса, тем легче их сжать, поэтому выбирается эвристика, сколько максимум бит в высоту можно заиспользовать дереву Хаффмана. Спецификация не разрешает больше, чем 11 бит -- оно скорее логично, алфавиты до 255, высоты 10 должно хватить для литералов часто. Также из интересного спецификация не хранит веса, а хранит какой высоты должен быть символ.

Эти "высоты" сами сжимаются FSE кодированием, потому что высоты чаще повторяются: 255 значений, там скорее всего много значений высоты 5, 6, 7 и тд хорошо сжимаются.

Чтобы найти этот оптимальный баланс, ничего не придумаешь, кроме как перебрать высоты: если у вас данные из алфавита A, то будете перебирать от log2(|A|) до 11: не совсем понятно как уменьшение высоты (более встречающиеся символы начинают иметь более длинные коды) влияет на суммарное сжатие (бОльшие веса сложнее кодировать), эта функция не унимодальная.

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

В итоге на 200MB при стандартном блоке выигрывается около 3КБ, когда блок поменьше (то есть FSE не очень сильно помогает сжимать), то разница уже в 360KB. Маленькие блоки встречаются в сжатии со словарем, когда очень много мелких данных приходит -- сообщения, посты, и тд.

Перф не просаживается на больших блоках, на маленьких 15%. Интересный PR, посмотрим, вольют или нет. Или другую эвристическу придумать можно.

https://blog.kagi.com/age-pagerank-over

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

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

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

Качество поиска в год растет где-то на 2 процента по метрике, которую компании сами придумывают, и она тоже по личному опыту не направлена на увеличение количества денег. В хорошие года с прорывами как DSSM, BERT в год получается где-нибудь 3%. Мы постоянно имели проблемы с тем, что рекламодатель приходит и говорит, что по их запросу их ссылка только вторая, что ж, это результат того, что мы не оптимизируем деньги в ранжировании.

Одна из проблем, о которой пишут в статье про то, что траффик поисковых движков становится revenue generator сайтов, поэтому SEOшники начинают плодиться, хитрее, система поиска в итоге сложнее, которая добавляет десятки тысяч факторов, модели супер сложными, энтропия растет, порочный круг борьбы SEO и мл продолжается. Как любые сложные системы по типу экономики, инженерии, системы в один момент становятся ... невозможными для восприятия.

Люди перестают понимать, чего ожидать от движка, разработчики перестают понимать, а что такое вообще "хорошее" ранжирование.

Асессоры, задача которых оценивать выдачу, тоже не очень заинтересованы в том, чтобы увеличить кому-то деньги. И в Яндексе, и в Google инструкции, методики анализа выдачи направлены только на релевантность, есть ли ответ по ссылке и тд.

Но чем больше вы будете думать, что вы хотите от движка на конкретных примерах, а также видеть, чего хотят другие люди, вы в один момент загрустите -- улучшать формулу на полпроцента в год очень тяжело и едва даёт осознание ощущения полезности, например, смотря на выкатку новой формулы вы увидите, может, 3-4 исправившихся запроса из корзинки в 10-20к. Люди, которые делают модели особо не понимают, что и как исправлять, потому что мы входим на территорию вопросов на машстабе сотен миллионов и миллиардов людей о том, что такое правда и ложь.

С кликбейтом тоже забавная история. Люди дают четкий сигнал на короткой дистанции, что они обожают кликбейт, зато в пределах недели они от него безумно устанут.

Что же делать?

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

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

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

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

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

Мы наконец-то зарелизили CRC32C библиотеку в abseil. Я её всю перехерачил по перфу и по API, и спасибо коллегам из C++ команды, что они её дотащили до OSS.

Поглядеть:
https://github.com/abseil/abseil-cpp/blob/master/absl/crc

Уроки и фичи:

* CRC хорошая полиномиальная чексумма, она стриминговая, вы можете добавлять чанки:

crc32c_t crc = 0;
crc = ExtendCrc32c(crc, chunk);

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

* В проде >75% вызовов до 64 байт. Поэтому мы выиграли очень много перфа, когда компилятор инлайнил с помощью PGO код в релизных сборках.

* В проде оказался большой хвост степеней двоек -- 4KB, 1MB, 4MB чексуммы доминировали какие-то проценты вычислений.

* Intel очень хорошие писала гайды о том, как надо имплементировать CRC32{C}, и, конечно, мы это и сделали.

* Только вот не одним Intel мы живём, а также есть куча разного парка железа типа AMD, старых интелов и тд. В итоге мы очень внимательно подбирали размеры буфферов для CLMUL fold и CRC fold. Получилась весьма забавная табличка что где лучше работает. CLMUL на AMD всё ещё очень медленный.

* На удивление мы побили все бенчмарки на Arm'ах N1+ и библиотеку ISA-L, которую инженеры из Arm сами пишут. Притом гайды от Intel отлично легли, и код получился унифицированным (но не обошлось и без проблем).

* Мы не ставили цели бить Apple. За самым быстрым CRC для Apple можно обратиться сюда (спойлер: они прошли по тонкой грани, когда смогли сделать fusion двух инструкций, до сих пор спорят, разрешает ли так делать лицензия Arm):
https://dougallj.wordpress.com/2022/05/22/faster-crc32-on-the-apple-m1/

* Имплементация от dougallj@ плохая на серверах. На наших T2A инстансах мы получили

dougallj@: 21.84123gb/s
Goog: 33.268118gb/s

* Оказалось, что людям нужно API как MemcpyCRC32C, чтобы скопировать и вычислять чексуммы одновременно. Это получается много где быстрее, так как можно контролировать чанки по которым зовёшь memcpy и утилизируя все пайплайны процессора.

* Non-temporal memcpy оказались полезными нашему самому низкому storage layer. Пока мы не взялись релизить флажок, но мы сделаем это в итоге. Non-temporal инструкции (проходящие мимо кешей процессора) забавные, конечно, на микробенчмарках полная ерунда, в проде чуть получше и мы реально разгрузили приличную часть давления на память с помощью них. К сожалению, не на всех процессорах, а на одном нашли даже дефект :)

* Было забавно, к сожалению, чтобы так красиво фаниться, не очень много проектов существует.

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

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

Знаете что дальше происходит? Некоторые из топ пользователей, увидев, что есть запас, просто загрузили в движок больше данных.

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

А за машины мы платим столько же. В итоге приходилось идти к пользователям и спрашивать, а каких данных они добавили, что они стали утилизировать на 10% больше.

Тут начинаются всякие tradeoffs, мол, мы увиличили качество на 0.1, ведь за железо столько же платим.

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

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

Такое же вы могли заметить и с Google Chrome. Мы за несколько лет соптимизировали background вкладки на двузначное число процентов. Люди не сильно это заметили. Но мы зато заметили, что на двузначное число процентов background вкладок от пользователей стало больше :)

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

И тут возникает вопрос, а где остановиться? А нужно ли инфраструктуру оптимизировать до коленья? Может быть, наоборот, сделать чуть медленнее, чтобы был запас на тяжелые времена.

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

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

В комментах подсказали, что это https://en.wikipedia.org/wiki/Jevons_paradox

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

Пусть у вас есть какой-то граф, по которому надо ходить в зависимости от одного из 255 символов:

Вы по нему будете ходить как-то в роде:

uint8_t table[256][NUM_STATES];
uint8_t state;
state = table[input[i]][state];

То есть если у вас есть state, символ, вы идёте по таблице инструкций от символа и переходите по state. Так можно делать в цикле, так одна из проблем заключается в том, что мы должны 2 раза обратиться к памяти, что в целом не очень хорошо, так как обращения к памяти достаточно тяжелые.

Одна из оптимизаций может заключаться в том, чтобы склеить NUM_STATES в один или несколько регистров. Скажем, если у вас битность ваших стейтов максимум 64 / NUM_STATES, то вы можете поместить это всё в один регистр и тогда таблицу и переход по состояниям графа можно описать как:

uint64_t table[256];
state = (table[input[i]] >> (state * BITS_PER_STATE)) & ((1 << BITS_PER_STATE) - 1);

Если выбрать BITS_PER_STATE = 6, то в один регистр можно запихать 10 стейтов (6 * 10 < 64 < 6 * 11) и тогда переход будет записан как

state = (table[input[i]] >> (state * 6)) & 63

Чем это выражение хорошо?

Тем, что на самом деле мы можем предпосчитать state * 6, когда будете создавать таблицу переходов. Тогда переход вообще будет выглядеть как

old_state * 6 = ((table[input[i]] >> state) & 63)

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

state = table[input[i]] >> (state & 63); // bits are lowered automatically
...
return state & 63; // lower the bits

Прелесть такого shift алгоритма в том, что на x86 оно транслируется в инструкцию shrx (сдвиги и так делаются по модулю 64)

Инструкция shrx занимает 1 такт, в итоге мы получаем алгоритм, который проходит по графу за 1 такт на символ, когда у вас есть граф переходов, и получается

1. Если всего вершин не более 10
2. Вы можете предпосчитать таблицу переходов умножая на 6
3. Без SIMD ходить по графу за 1 такт на символ

Это невероятно мощное свойство, потому что вы можете так представить

1. Поиск по строке очень многих строк (надо чтобы строка, по которой ищете была не очень длинной (порядка 9 символов (плюс 1 для обозначения терминального стейта))
2. Проверка на ASCII: всего 2 стейта, ASCII или нет
3. Регулярные выражения с не очень большим автоматом в 10 стейтов (ДКА/DFA)
4. Ходить по деревьям Хаффмана и раскодировать данные, если стейт не очень большой

Как ни странно, это огромное количество человеческих юзкейсов. Понятное дело есть SIMD, который старается искать меньше, чем за 1 такт на символ, но описанное сверху свойство показывает, что можно писать на чистом C и получать невероятную скорость.

Количества бит можно выбирать другие: например, без предосчёта BITS_PER_STATE = 4, NUM_STATES = 16, но тогда будет 2 такта на символ, что всё ещё лучше, чем адресоваться к памяти. Можно 2 регистра на state. Играться можно много.

Такая оптимизация есть в RE2, рассматривается в Golang и вообще является достаточно мощной техникой перевода ДКА на инженерный код.

В RE2 ещё забавное происходит, что если у вас есть какое-то регулярное выражение, то оно вряд ли использует много символов, скорее всего оно использует единичные символы и какие-нибудь range символов ([0-9], [a-z] и тд). Из-за этого в RE2 происходит так называется консолидация алфавита, где алфавит преобретает цвета -- range в роде [0-9] становится одним символов, в подстроках типа bar, лишь 3 символа, поэтому они будут покрашены отдельными цветами. В итоге такая эвристика сильно уменьшает алфавит, количество состояний и помогает использовать оптимизацию, описанную сверху, чаще.

Эта статья основана на блоге pervognsen.
Godbolt на код из RE2

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

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://xn--r1a.website/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://xn--r1a.website/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). Пока -- под опцией.