Тут с сожалением сообщу, что мейнтейнер RE2, по совместительству мой друг, Paul Wankadia, неожиданно скончался. RE2 используется очень много где, в Google Sheets, антиспаме и где только.

https://github.com/google/re2/issues/502

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

Он присылал мне всякие статьи про компрессию и кэширование, а я ему скидывал ужасные баги продакшена, которые он обожал. Он даже сделал внутри Гугла чатик "Production Immaturity" и теперь этот чатик наполнен призрачной пустотой.

Он убедил Jeff Dean откатить его оптимизации и сам смог исправить loading page of Google на 25% в бородатом 2009.

Он взял RE1 от Russ Cox и Ken Thompson и смог 10+ лет поддерживать в новую версию. Мы 2 месяца с ним общались, каким должен быть RE3, но поняли, что пока будет сложно, но этот момент должен был настать ближе, чем нам казалось.

RIP, Legend

GitHub

Re: Junyer · Issue #502 · google/re2

The univsrse is broken and so many people are upset about Junyer passing away at such an early age - he would be mortified at how many people loved him and his work and him being a decent human. He...

Удивительно, не думал, что об этом писали, но мы аж 2 года назад выложили статью про так называемый Flash cache! https://www.usenix.org/conference/atc22/presentation/yang-tzu-wei

Проблема: HDD дешёвый и, в основном, данные лежат на нём, но вот читать часто горячие куски с HDD не хочется. По всему гуглу перед чтением из Colossus (successor to Google File System) стоит SSD cache. Кеш этот большой и автоматический, то есть ничего пользователям не надо делать.

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

Была выбрана LARC стратегия, потому что 60% всех чтений с диска -- одноразовые, а LARC вставлял элемент в кеш только если его читали во второй раз (то есть было два промаха сравнительно недавно). Прожило это дело лет 6, со временем стало недостаточно, потому что если вы прочитали 1000 файлов, а потом ещё раз 1000 файлов быстро, то окажется, что вы очень сильно и быстро нагрузили SSD. Эту проблему пытались полечить SSD Throttler, чтобы писать меньше в короткие промежутки, но такое решение не учитывало разнообразие того, как ведут себя разные клиенты. Кому-то реально надо прочитать два раза, но зато потом не будет никаких промахов. Ещё одна проблема, что LARC всё таки промахивается два раза перед тем, как не промахиваться и в итоге была эвристика, которая оценивала, хорош ли LARC и выключала себя, если промахиваться два раза всё таки было странным. Всё обростало эвристиками и сложностями, и надо было переделывать на что-то более автоматическое.

В итоге решение было многогранным: взять много стратегий по своей жёсткости и оценивать насколько они хорошо работают в режиме реального времени. Учитывать это для принятие решений.

Были выбраны такие стратегии:

NeverAdmit < AdmitOnSecondMiss < AdmitOnMiss < AdmitOnWrite.

То есть никогда не вставлять блоки, вставлять только если промазали 2 раза, вставлять, если промазали (но не совсем как LRU, а с TTL) и вставлять если записали или промазали.

Чтобы понять какие стратегии самые лучшие, решаются задачи о рюкзаке. С данным TTL, статистикой доступа от клиентов и разными стратегиями, стоимостью разных операций (прочитать с HDD и тд), определяется оптимальная стратегия. Раз в какое-то время снова решают такие задачи. Выбирают один TTL с лучшей стратегией.

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

Внутри этот кеш достаточно известен, потому что находится во всех дэшбордах.

Wikipedia

Adaptive replacement cache

cache management algorithm

1. Не так часто в основной курс алгоритмов и структур данных можно включить новый не очень сложный алгоритм. Его Кнут назвал CVM алгоритмом для подсчёта количества различных элементов в потоке элементов. Действительно очень простой алгоритм https://arxiv.org/pdf/2301.10191 . Кнут написал целую статью про него https://cs.stanford.edu/~knuth/papers/cvm-note.pdf . Удивительно как я всё реже занимающийся такими вещами даже смог осилить доказательство. К сожалению или к счастью он не лучше по оценкам, чем HyperLogLog, но зато не использует никакого хеширования. Из хорошего, я думаю единицы в мире умеют доказывать оценку HyperLogLog, а тут получается, что можно даже доказать что-то за лекцию.

2. Тут вышли очередные бенчмарки хештаблиц. Скажу, что как обычно побенчмаркали какие-то огромные таблицы, которые в реальной жизни не так часты. Может быть для баз данных бывает такое, но для обычной бизнес логики большинство хеш таблиц десятки, максимум сотни элементов. absl::flat_hash_* был задизайнен именно для небольшого количества элементов. Мы кстати тут недавно поддержали Small Object Optimization.

3. Наконец-то std::pair станет тривиально копируемой, если оба элемента тривиально копируемы (правда под флагом другого ABI в libcxx). Не думал, что этот день настанет. Как раз 4 года назад у меня был блог об этом.

4. Блогу практически 5 лет. Я рад, что легаси блога живёт и даже вот вчера он появился на hacker news снова.

Признаться, 5 лет назад совсем другие мысли в голове были. Тогда я был юным, смелым, писал через силу и хотел, чтобы меня заметили. Взросление даёт о себе знать, да и мотивации поменялись.

5 лет назад хотелось делать большие распределенные системы, сейчас хочется заниматься в основном перформансом и обучением людей, так как очень сильно заинтересовали темы как экономика компаний, capacity engineering. В целом оптимизации, идеи, инновации в перформансе сильно хорошо окупаются (особенно в эпоху бесконечных трат на AI). Распутывать клубки, например, откуда пришли те или иные траты интересно как никогда.

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

LLAMA
Когда вы занимаетесь перформансом, одно из полезных упражнений для проделывания в голове -- анализ скорости света. В простом варианте надо задать себе вопрос "А какой реально лимит сделать то, что делаем мы в библиотеке/программе?".

Очевидный ответ, понятное дело, ноль, лимита нет. Но если подумать, всегда есть некоторые ограничения. Приведём примеры:

Компрессия -- лимит: memcpy. Скопировать данные уж точно надо будет

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

Аллокатор -- хмм, уже не очень понятно

Анализы скорости света выходят всё чаще и чаще, например, теоретические лимиты в математике/алгоритмах и так далее. Они часто оказываются неприменимы, но они действительно могут помочь понять, куда смотреть, находить какие-то эвристики для того, чтобы приблизиться к этому лимиту.

Тут вышла статья с технологией LLAMA (нет, не моделькой от фейсбука и название поста специально привлекает ваше внимание, потому что хайповые вещи я обсуждаю очень редко). А именно Learned Lifetime-Aware Memory Allocator.

https://dl.acm.org/doi/pdf/10.1145/3654642#page=89

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

Статья рассказывает, что если брать полный стектрейс аллокации и запоминать сколько объект поживёт, то с помощью LLM можно предсказывать сколько объект будет жить, и получить намного лучшую упаковку на реальных программах. К сожалению, запуск даже простых LLM и стектрейсов занимает микросекунды, когда TCMalloc возвращает память почти всегда за наносекунды.

Почему стектрейсы?

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

Что делать с перфом?

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

Из интересного, да, перформанс аллокатора замедлился раза в 3-4, но перформанс всей программы замедлился всего на 12%. Если посчитать, сколько занимает аллокатор, то в целом получается, что решения аллокатора ускоряют всё остальное. Поэтому не надо бояться проводить немного больше в аллокаторе -- его решения влияют на последующие результаты.

Что в итоге?

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

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

We applied insights from this work to Temeraire, in order to make better decisions about when to break up huge pages in this allocator, which led to an estimated 1% throughput improvement across Google’s fleet

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

1. Я выложил Snappy 1.2.0. Добавили уровень 2 компрессии. Одним из неожиданных результатов оказалось, что декомпрессия ускорилась. Почему? Если почитать формат, на каждом шагу, Snappy выбирает одно из 4 действий как именно скопировать данные. Уровень два сместил эту статистику в более длинные копирования строк, поэтому декомпрессия улучшилась даже несмотря на то, то код декомпрессии абсолютно branchless. Дальнейшие эксперименты это подтверждают ещё больше. До LZ4 далеко (там на моей станции 4000MB/s везде), но наконец-то я нашёл как двигаться к этому лимиту. В целом история достаточно грустная, так как snappy никому кроме гугла практически не нужен, но об идее рассказать захотелось, потому что библиотеки умрут, алгоритмы и идеи останутся.

snappy 1.2.0 lvl1 636 MB/s 3173 MB/s 101436030 47.86 silesia.tar snappy 1.2.0 lvl2 460 MB/s 3330 MB/s 94740855 44.70 silesia.tar

Davis Summarizes Papers

2023-11-26 arXiv roundup: Big potential wins, 1 bit per parameter, Simplifying transformers

Stella Nera: Achieving 161 TOp/s/W with Multiplier-free DNN Acceleration based on Approximate Matrix Multiplication They built a crazy fast hardware accelerator based on my approximate matrix multiplication paper. By “crazy fast,” I mean they get 15x higher…

Хайп по LLM спадает, наконец-то можно писать что-то в блоге и не чувствовать, что я отстаю от жизни :)

1. Почитал тут хороший разбор как можно ускорить всякие перемножения матриц.

В целом это статья про approximate matrix multiplication, я лично мало знал, что там происходит. Особенно это хорошо работает, когда одна матрица статична, как, например, в LLM.

Когда вы перемножаете матрицы, вы делаете очень много разных операций с разными числами, поэтому всегда интересен вопрос, а можно ли умножать одинаковые числа и знать куда их вставлять -- одно решение это уменьшать множество чисел над которыми происходит умножение: -1, 0, 1. Другой подход -- оставлять матрицу, но не перемножать все строки и столбцы.

Статья предлагает группировать похожие строки/столбцы в один блок (в offline обучить для статичной матрицы), в котором можно найти несколько центроидов с помощью k-means. Дальше остаётся перемножать только эти центроиды и присваивать значение к самому близкому центроиду. В целом это вся идея, запомнить центроиды в памяти легко и получается красивая история про vector quantization. А алгоритмы нахождения k-means очень хорошо работают инженерно.

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

https://dblalock.substack.com/p/2023-11-26-arxiv-roundup-big-potential2. Progressive Partitioning for Parallelized Query Execution in
Google’s Napa

Ох, тут надолго объяснять, давайте я сначала объясню зачем Napa в Google была сделана. Всё это можно найти в статье на VLDB'2021.

В гугле много разных систем сделали со временем, но часто возникали ситуации, когда, скажем для логов, где не так важна свежесть данных, надо было пользоваться совершенно другим решением нежели для поиска. Приходилось поддерживать несколько систем. Спустя 15 лет, решили сделать одну систему, которая подходила бы для всего, надо лишь просто указать, что именно хочется -- warehouse, freshness или resource cost.

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

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

Первая идея заключается в том, что если уже есть B-tree данные и есть новые данные (их называют дельты), то не стоит оценивать точно идеальную партицию, а стоит оценивать (min, max). Дальше применяется жадный алгоритм деления. У него свои недостатки, но на реальных данных работает неплохо, а вскоре, Napa (как и ClickHouse), все холодные данные переведит на LSM и делает компакции. Эта идея позволяет не сильно долго думать о том как вставить данные в дерево и иметь какие-то неплохие партиции.

Вторая идея заключается в том, что мы храним статистику (min, max), чтобы понять, стоит ли нам делить партиции дальше или нет в зависимости от размера. Чтобы понять это, надо идти вниз по дереву. Это делается статистически, если ошибка накапливается, чтобы её уменьшить. Чем больше времени проводишь это делать -- тем лучше становятся партиции. Здесь клиенты могут указывать баланс, сколько они хотят тратить время на улучшение партиции и тем, чтобы результат отдали как можно скорее.

Моё лично мнение, что системы как Napa показывают какую-то цикличность дизайна от "давайте сделаем монолит" до "разделим всё до мелких кусков" до "давайте всё таки сделаем монолит". В идеале нужен какой-то баланс. Работая с Napa у меня как раз всегда возникали вопросы, насколько эти хитрые алгоритмы переживут 5-10 лет и экзабайты данных. Я ставлю, что не переживут и Napa как-то сильно измениться снова до "давайте всё разделим"

Davis Summarizes Papers

2023-11-26 arXiv roundup: Big potential wins, 1 bit per parameter, Simplifying transformers

Stella Nera: Achieving 161 TOp/s/W with Multiplier-free DNN Acceleration based on Approximate Matrix Multiplication They built a crazy fast hardware accelerator based on my approximate matrix multiplication paper. By “crazy fast,” I mean they get 15x higher…

FunИнтересное для меня применение LLM: писать фаззеры, чтобы увеличить покрытие кода.

https://github.com/google/oss-fuzz-gen

В целом даём функции public API, которые не покрыты, пытаемся для них написать фаззер с помощью LLM, исправляем ошибки компиляции через промпты, запускаем фаззеры и находим баги. 6 новых багов, много покрытия, не особо надо думать как писать фаззер, если не знакомы, красиво и полезно.

https://www.brendangregg.com/blog/2024-03-17/the-return-of-the-frame-pointers.html -- the return of the frame pointers.

Давным давно мы в компиляторах по умолчанию выключили сохранение информации о стеке в регистре %rbp, потому что регистров в 32 битных системах стало не хватать, а бенчмарки показывали иногда много преимуществ. Из проблем -- полностью мёртвый дебаг, gdb работает через раз, поцарапанные профили и вообще ноль уважения к более низкоуровневым языкам.
В Google мы давно всё собираем с frame pointer, потому что оптимизации с хорошими профилями дают больше преимуществ, чем отдать один регистр, тем более на x64.

В 2023 году теперь обычные линуксовые дистрибуторы вроде Fedora и Arch будут собирать с frame pointers, чтобы можно было дебагать, что происходит.

Почитайте статью, написана легко и красиво.

GitHub

GitHub - google/oss-fuzz-gen: LLM powered fuzzing via OSS-Fuzz.

LLM powered fuzzing via OSS-Fuzz. Contribute to google/oss-fuzz-gen development by creating an account on GitHub.

Съездил я тут в Эдинбург на CGO (compiler generation and optimization).

Вообще, понравилось, я как-то странным образом перезарядился, хотя и не самый основной мой профиль.

Понравились след доклады:

LLVM performance workshop

• Practical use of BOLT

BOLTу уже 8 лет и 6 в open source, технология уже достаточно стабильная и много принесла пользы в мире postlink optimization. Из нового для себя и интересного -- теперь BOLT подгружает только функции, которые затронуты профилем и не вытягивает по 200GB памяти на больших бинарных файлах, а также начали экспериментировать с RISC-V. В остальном как обычно -- надо чуть чуть правильно собрать бинарь, чуть чуть не ошибиться в сборе профиля и будет всё хорошо.

• The next 700 ML-optimizations in LLVM

Всяких разных ML decision making оптимизаций набралось огого сколько, но вот в LLVM притащить и запустить в прод всё ещё тяжело. Почему? Да потому что одни используют Tensorflow, другие PyTorch, третьи JAX, четвёртые на сях написали backpropagation. С этим всем приходит идея унифицировать используемый формат, чтобы хоть как-то договориться. Модели разрешат достаточно простые, в одном формате и работа идёт полным ходом. Приятно видеть прогресс и что всё таки достаточно консервативное общество компиляторостроения принимает в себя инновации.

SLaDe: A Portable Small Language Model Decompiler for Optimized Assembly

Декомпиляция и построение обратного кода это жуткий процесс использующий тысячи человекочасов (чего только стоит полный реверс инжиниринг GTA III). С развитием LLM, оказывается можно неплохо так упростить -- LLMки сами неплохо понимают как написать код, чтобы получить нужный ассемблер. Хорошая статья и отличные инновации в декомпиляции!

Compiler Testing with Relaxed Memory Models
Ещё одна статья, чтобы потестировать модели памяти. Из отличного, 9.6 миллионов очень хороших тестов на мультипоточность атомарных операций. Chef's kiss

High-Throughput, Formal-Methods-Assisted Fuzzing for LLVM
Ещё одна статья от звезды фаззинга John Regehr. В LLVM существует тула формальной верификации оптимизаций -- Alive2. Разработчики иногда забывают написать тесты к крайним случаям (или забывают какие-нибудь важные аннотации к инструкциям), поэтому на удивление никто не попробовал случайно сделать мутацию тестов LLVM и прогнать через Alive2. 33 бага, всё полыхает, всё в огне, всё починили, красиво капец.

Из удивительного я на конференции случайно на ланче сел с Lee Smith. Он рассказывал про retirement, что работал в Arm, что до сих пор помогает, я слушал, интересно то как. Ну прикольный дядька, я подумал. Загуглил через полчаса -- да он один из основателей Arm!

Познакомился с Michael Scott, его lock free queue я писал в универе, изучал lock free priority queue и вообще половину знаний concurrency у меня от его статей и лекций. Видеть таких рок-звёзд вживую воодушевляет. Мол, чувак, я над твоими работами умирал, проливал на них кофе, засыпал в обнимку, а ты тут стоишь как ни в чём ни бывало, привет!

Честно для меня в целом конференция по знаниям была весьма скучная, но последние две встречи зарядили особенно неожиданно. Ну и друзья в Эдинбурге добавили красок к городу :)

conf.researchr.org

Program - CGO 2024

Important Dates Student Travel Grants: January 24, 2024 Early Registration Deadline: February 2, 2024 Conference Period: March 2 – 6, 2024 Register for the conference The International Symposium on Code Generation…

Long time no see

1. Мне очень понравилась статья о memory profiling от Дениса: https://easyperf.net/blog/2024/02/12/Memory-Profiling-Part1
   В целом он очень правильно описал основы -- вам нужно смотреть на Virtual Memory как общее пространство и лимит ядра, RSS как внутреннюю работу и memory footprint -- сколько памяти в каждые X ms вы трогаете. Например, если вы видете много спайков в количестве тронутой памяти, то скорее всего у вас много локальных и мелкоживучих аллокаций, можно задать вопрос, можно ли что-то переиспользовать и улучшить кеш локальность.
   Если говорить на практике, то я очень сильно смещён в сторону TCMalloc и jemalloc, друг у друга списываем, по паре людей в Google и Meta занимаются практически исключительно ими, так что должно быть достаточно подтюнено. Хорошое представление о том, как написать аллокатор для ваших десктопов, можно почитать тут. Рассказывается о ptmalloc2 используемый в линуксовых дистрибутивах, о том как в целом разделять аллокации и тд. Про память я в этом блоге писал много.

2. LZ4 получил уровень компрессии что-то между Fast и Hash Chain. Напомним, что LZ компрессия работает как команды "вставить текст как есть" и "скопировать из уже раскодированного текста и записать оффсет".
   Fast уровень работает так:
   Возьмём хеш таблицу, будем добавлять в неё 4 байта с каждой позиции. Если нашли такие же 4 байта, смотрим сколько байт совпало и добавляем инструкцию о копировании из предыдущего. Минусы такого подхода, что он никак не учитывает то, как дешёво кодировать оффсеты, например, стоит ли взять совпадение подальше и больше покрыть байт или поближе и закодировать оффсет подешевле. Из этого появился алгоритм Hash Chain -- запомним очень много позиций и будем оценивать, что из них дешевле. Hash Chain много добавляет всяких проблем с промахами по кешам и поэтому достаточно медленный.
   Добавили уровень, который что-то посередине, а именно использует 2 хеш таблицы -- для 8 байт и для 4-5 байт. Сначала смотрит, нет ли подлиннее данных, а потом уже покороче как в fast. Скорость просаживается меньше, поэтому и получается где-то посередине.

3. Тут прошёл FOSDEM 2024, много всякого интересного, больше всего понравилось посмотреть, а что же такое load average в Linux (и почему не стоит на него смотреть) и бесконечный лист оптимизаций Query Planner в PostgreSQL

easyperf.net

Memory Profiling Part 1. Introduction | Easyperf

Недавно понадобилось снова открыть документацию и посмотреть что значат регистры %fs и %gs: я помню что-то про thread local storage, но не более.

Наткнулся на очень красивый ответ об истории

https://stackoverflow.com/questions/10810203/what-is-the-fs-gs-register-intended-for/10810340

The original intention behind the segment registers was to allow a program to access many different (large) segments of memory that were intended to be independent and part of a persistent virtual store. The idea was taken from the 1966 Multics operating system, that treated files as simply addressable memory segments. No BS "Open file, write record, close file", just "Store this value into that virtual data segment" with dirty page flushing. ... There was still a need for threads to access thread local store, and each thread needed a a pointer ... somewhere in the immediately accessible thread state (e.g, in the registers) ... to thread local store. Since Windows and Linux both used FS and GS (thanks Nick for the clarification) for this purpose in the 32 bit version, AMD decided to let the 64 bit segment registers (GS and FS) be used essentially only for this purpose (I think you can make them point anywhere in your process space; I don't know if the application code can load them or not). Intel in their panic to not lose market share to AMD on 64 bits, and Andy being retired, decided to just copy AMD's scheme.

Stack Overflow

What is the "FS"/"GS" register intended for?

So I know what the following registers and their uses are supposed to be: CS = Code Segment (used for IP) DS = Data Segment (used for MOV) ES = Destination Segment (used for MOVS, etc.) SS = Stack