Experimental chill

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 невозможно читать, например.

Сегодня поздний пост, но как есть. Одна из оптимизаций, которая мне пришла в голову, и к которой у меня было не так много 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'а. Иногда даже проработав годы в индустрии, попросту не хватает тулинга. Я вообще думаю, что надо этим намного больше заниматься, чем самим перформансом

В панике, что после недели не о чем писать Я до занятием перформанса и 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. Много всякого интересного было. Завтра что-то более содержательное напишу, сегодня как-то так

Давайте попробуем продвинуть вчерашнюю на 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://t.me/experimentalchill/178), это репрезентативные бенчмарки гугла. Мы теперь им пользуемся, чтобы смотреть на изменения! И люди им тоже пользуются пытаются. Пример: https://github.com/protocolbuffers/protobuf/pull/11102#issuecomment-1374878279. Микробенчмарки исправились на 50%, а макробенчмарк за 1-1.5%, что тоже очень круто!

Когда вы находите минимум/сортируете/делаете кучу из элементов, нужно чтобы ваши элементы удовлетворяли свойству строгого слабого порядка (по-английски 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 и соответственно показать больше проблем.

Я тут писал про оптимальное нахождение коротких и хороших хэш функций. В общем, после моих страданий мы нашли хэш функцию (коммит в 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

Ой, забыл, счастье точно не наступает, потому что график выглядит обычно не так, а примерно как на картинке. Ещё он не особо воспроизводим, но с этим поменьше проблем. Стоит уметь считать запросы к диску, если кеш предотвращает их. Возможное решение: отключать кеши и смотреть, сколько ваша система сжирает $СЧАСТЬЯ_ПОЛЬЗОВАТЕЛЕЙ/$ДЕНЕГ/$ВАШИХ_НЕРВОВ. Метрика чуть более стабильная. Так как ресайзить кеш тогда? Я видел * На глазок * С помощью машинного обучения: пусть график мл выучит. Работает кстати не так плохо как кажется * Удалить кеш и забыть как страшный сон Не забывайте добавлять метрики: * hit/miss/cache size * Сколько в среднем живут ключи и значения, их распределение. * В кешах есть такая шутка, что оптимальный кеш это тот, который вытесняет элемент, который позже всего в будущем будет запрошен. Такой минимум называют Belady Min. Его нельзя заимплеменить, потому что он должен знать будущее. Тем не менее, посчитать метрику и сравнивать LRU/LARC/другие политики можно по историческим данным.

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

Сегодня начинается двухнедельный марафон постов. Я каждый день постараюсь писать что-то содержательное. Ибо накопилось, а мотивации сдампить нет. Плана тоже нет. Как будет ехать, так и поедет. 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 же :)

Одна из оптимизаций в регулярных выражениях, поисках по строкам и подобных 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

Одна из проблем, которая меня ломает в последнее время, и я её вижу не в первый раз -- почему мы порой не видим прямой экономии денег от оптимизации ресурсов? Я прям сильно погрузился, что не так с некоторыми проблемами и, к сожалению, у меня не появилось хороших ответов. Пусть есть движок обработки данных. Пусть есть X машин (порядка сотен тысяч), это лимит для одной стадии обработки для одного пользователя -- дальше начинаются проблемы с координацией. Мы смогли подвинуть этот лимит до 1.1X машин, который мы сильно оптимизировали, это был большой проект. Мы увидели, что координирующему мастеру стало полегче, то есть мы можем больше скейлиться, больше аллоцировать ресурсов. Мы увидели, что некоторым топ пользователям стало легче. Знаете что дальше происходит? Некоторые из топ пользователей, увидев, что есть запас, просто загрузили в движок больше данных. В итоге наши оптимизации практически не видны после месяца, пользователи могут скейлиться больше. А за машины мы платим столько же. В итоге приходилось идти к пользователям и спрашивать, а каких данных они добавили, что они стали утилизировать на 10% больше. Тут начинаются всякие tradeoffs, мол, мы увиличили качество на 0.1, ведь за железо столько же платим. И вице-президентам это очень сложно объяснить -- почему инфраструктура занимает столько же? Вы что, ничего не делаете? Приходится ходить по пользователям, и спрашивать, почему они стали больше обрабатывать -- их ответ: "потому что нам показалось, что инфраструктура позволяет". И здесь ничего кроме как бегать за ними невозможно придумать. Можно нормализировать по количеству данных и тд, но эта метрика тоже не самая стабильная. Такое же вы могли заметить и с Google Chrome. Мы за несколько лет соптимизировали background вкладки на двузначное число процентов. Люди не сильно это заметили. Но мы зато заметили, что на двузначное число процентов background вкладок от пользователей стало больше :) В Яндексе я тоже помню, что при оптимизации поиска на 10ms, мы видели больше запросов в секунду, потому что людям нравится, когда всё быстро. Когда всё быстро, они склонны этим больше пользоваться. И тут возникает вопрос, а где остановиться? А нужно ли инфраструктуру оптимизировать до коленья? Может быть, наоборот, сделать чуть медленнее, чтобы был запас на тяжелые времена. Пока я вижу ответ только в SLO, если мы договорились, что что-то работает счастливо для людей, то не обязательно при оптимизации мы увидим сокращение расходов на инфраструктуру. Только вот команда, которая увеличила качество на 0.1, получила хедкаунт и славу, а нам пришлось объяснять, что мы то соптимизировали, нормализованная метрика улучшилась. Только расходов мы не сократили. А мерить железо и доллары на счастье людей очень тяжело и не в нашей компетенции В комментах подсказали, что это https://en.wikipedia.org/wiki/Jevons_paradox

Мы наконец-то зарелизили 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 инструкции (проходящие мимо кешей процессора) забавные, конечно, на микробенчмарках полная ерунда, в проде чуть получше и мы реально разгрузили приличную часть давления на память с помощью них. К сожалению, не на всех процессорах, а на одном нашли даже дефект :) * Было забавно, к сожалению, чтобы так красиво фаниться, не очень много проектов существует.