CppCon

Прошёл тут на CppCon с докладом про сортировки https://sched.co/1Qtft Проекту два с лишним года и пора сделать очень красивое завершение.

Аж сам Herb Sutter записался.

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

Я тут ещё зачитался про S3-FIFO cache eviction policy. https://blog.jasony.me/system/cache/2023/08/01/s3fifo Достаточно интересная идея, что во многих кешах существует много элементов, которые лишь единожды вставлены и мало стратегий, которые их пытаются вытеснить достаточно рано. Авторы обещают улучшенные hit rates и перформанс. Достаточно красиво и элегантно. Съевши собаку в кешах, скажу, что одна из проблем, которую почти никто не исследует это проблема, сколько промах займёт на бекендах, поэтому в каких-нибудь базах данных любят делать Weighted стратегии (условные бОльшие записи сложнее достать с бекендов). Здесь не очень понятно как это делать, и автор отговаривается:

"Unless otherwise mentioned, we ignore object size because most production systems use slab storage for memory management, for which evictions are performed within the same slab class (objects of similar sizes)."

Дьявол в деталях, по мне это небольшая халтура для такого эксперта как он :). В проде в больших кешах никто не делает кеши по slab size, это слишком затратно и сложно настраиваемо, все используют Weighted стратегии.

Resources

BurntSushi обновил ripgrep для Arm пользуясь моими советами и статьёй, что не может не радовать, теперь с его слов "In short, simple ripgrep searches (likely the most common kind) get about twice as fast on Apple silicon now."

Unrelated.

Одна из больших ошибок в науке перформанса, на которую я обращал не так много внимания в первые годы, хотя стоило бы -- утилизация. Я очень люблю разворачивать циклы, улучшать алгоритмы и тд, но микробенчмарки врут, они однопоточные часто, и они часто всю память кладут в L1/L2 кеш и получается очень красиво, мол, вот вам, соптимизировали. Сейчас я даже не говорю про промахи мимо кешей, а именно как хорошо вы можете утилизировать все ресурсы. Memory bandwidth между памятью и ядрами сейчас упирается в 30-100 GB/s и не растёт. После этого порога -- тьма. Это означает, что в целом бесполезно оптимизировать хоть что угодно -- вы упёрлись в память. На одном процессе с десяток потоков не так страшно, но когда вы пытаетесь загрузить машинку и каждый процесс кушает свои 5-10GB/s, то в целом вы никогда не увидите, что упираетесь в CPU. И опять же, бесполезно оптимизировать хоть что-то на микробенчмарках, вы упираетесь в потолок, потому что просто хотите прочитать или записать память.

Какие ошибки и эффекты у этого всего?

1. "Ух, сейчас распараллелим на 32 потока и заживём". Нет, упрётесь в потолок и будете как на однопоточном.
2. "Что-то на одной машинке 99th latency совершенно другая, хотя вроде железо одно и то же". Да, потому что соседи могут всё скушать, а вам не особо что останется.
3. "Сэкономили 10% CPU, сейчас закажем машинок поменьше". Увы, не всегда
4. "Давайте кешик побольше сделаем и заживём". Опять же, шаг влево и бекенды будут отвечать в разы хуже

На практике пока не всё так плохо, но процессоры всё ещё развиваются, а скорость передачи данных всё, у неё истек закон Мура. 3-5% в год?

Что делать?

Уменьшайте работу с памятью. Трогайте горячие данные чаще, холодные реже. Собирайте кеш промахи (LLC-load-misses в perf stat) профайлом и уменьшайте их (хотя это может помочь *соседу* на машине, а не вам). Меньше алгоритмов на табличках, больше на CPU, меньше данных в целом. Удаляйте данные, перекладывайте меньше jsonов в конце концов, а.

Фаззили 5 лет и не нашли

Читал тут как в дереве хаффмана нашли out of bounds read в libwebp https://blog.isosceles.com/the-webp-0day/. Есть спекуляции, что этим пользуется Pegasus.

И снова вопрос, почему фаззинг не нашёл такой пример за 5 лет фаззинга?

Не похоже ли это на https://www.tg-me.com/experimentalchill/238, когда мы в ZSTD нашли битые данные хотя фаззили достаточно несложный код 2 года?

Как я уже писал, в фаззинге нет магии, он просто пытается зайти во все строки кода, и совсем странные крайние случаи вряд ли найдёт. Всем советую прочитать анализ, а так если кто-то хочет написать сложный проект по тому, как находить такие баги чаще, то welcome. Это в самом деле a million dollar question, без преувеличения.

Тут вышла OOPSLA -- хорошая конференция по языкам программирования. Зацепило 3 статьи

Randomized Testing of Byzantine Fault Tolerant Algorithms
https://dl.acm.org/doi/10.1145/3586053

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

ByzzFuzz detected several bugs in the implementation of PBFT, a potential liveness violation in Tendermint, and materialized two theoretically described vulnerabilities in Ripple’s XRP Ledger Consensus Algorithm. Moreover, we discovered a previously unknown fault-tolerance bug in the production implementation of Ripple, which is confirmed by the developers and fixed.

Fat Pointers for Temporal Memory Safety of C
https://dl.acm.org/doi/10.1145/3586038

Давным давно уже пытаются создать язык Checked-C, который проверяет, всё ли хорошо с разыменовываниями указателей. Только Checked-C работает только с массивами, мол, не выходите за границы. А вот сохранения протухших указателей намного сложнее найти -- надо уже смотреть за лайфтаймами. Статья придумала жирные указатели, которые аннотируются метаданными, куда ушёл указатель и будет ли он изменён потом. Лёгкое дополнение к трансформации компиляции. 2/3 статьи о том, как это сделать быстро с ассемблером и тд. Пишут о 1-2k строк в день миграции. На самом деле вывод более интересный -- если тесты неплохие, то в целом вы получите код с unique ownership, а значит его и легче будет переписать/протранслировать на Rust уже какой-нибудь автоматической тулзой. То есть не сразу писать C -> Rust, а C -> Checked-C -> Rust, что будет менее болезненно и потенциально последняя часть автоматически.

Accelerating Fuzzing through Prefix-Guided Execution
https://dl.acm.org/doi/10.1145/3586027

Одна из проблем фаззинга, как было видно в прошлых постах, скорость с которой он сходится для багов. Иногда не находит годами. Если его ускорить раза в два, может быть будут шансы найти что-то побыстрее. В статье рассказывают как фаззинг устроен в целом, мол, если вход не увеличил покрытие, то он выбрасывается. Авторы увидели интересную особенность, что покрытие улучшается практически всегда, когда тест доходит до определенного префикса выполнения -- то есть если код веток на 20, то достаточно часто посмотреть на первые 5 и если мы пришли в те же 5 веток, то можно просто не исполнять вход дальше. Особенность интересная, но весьма теоретическая -- это число "5" для всех разное и найти его -- надо потратить какое-то время на нахождение его бинарным поиском. Но абсолютно магическим фактом кажется, что это число почему-то существует на всём, на чём потестили и достигает того же покрытия, что и обычный фаззер за 3-10x меньше времени. Прямо применить будет слегка сложно, но рисёрч продолжается. Вообще Zhendong Su -- какая-то звезда современного рисёрча фаззинга, у него по несколько статей в год.

Contest

Пописал тут контест от телеграма https://www.tg-me.com/contest/330. В целом задача -- всё, что написано в markup code в телеге -- определить, код ли это и какого языка программирования из 100 самых популярных. Как обычно, ни данных, ни условий тестирования не дали, классический телеграм.

Из уже существующий решений есть

* VSCode'овский https://github.com/yoeo/guesslang, прилагающий к нему https://github.com/yoeo/guesslangtools. Из хорошего, 55 языков поддерживает c 90%+ качеством, из плохого работает на больших кусках кода.

* Какая-то статья https://github.com/aliostad/deep-learning-lang-detection, утверждают 99%+ качества. Обучение у них на слишком хороших данных.

* Какие-то регексовские вещи, которые очевидно никогда не наберут 90%+ качества

Вторую я покрутил, повертел и получил тоже ~90% качества на средненьких таких данных.

Как брать данные

* https://libraries.io/
* https://huggingface.co/datasets/bigcode/the-stack
* https://sourcegraph.com/search -> Actions -> Export Results

В эпоху LLM, на hugging face собрали неплохой датасет, который я почему-то нашёл только в последние пару дней, чутка оттуда покачал, но особо много это не дало, а кластера для терабайтов у меня не было. В итоге использовал libraries.io и sourcegraph.

Собрал я 5M файлов, качал я это дело на 5TB машинке пару дней, github отдавал разным машинам в районе 50-100MB/s в зависимости проснулись ли прогеры из Сан Франциско :), много тротлили, но я их переиграл. Суммарно после дедупликации получилось 100GB кода.

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

.hh -> C++ и Hack

.p -> Gnuplot и OpenEdgeABL

.fs -> Forth и F#

У гитхаба есть неплохой алгоритм детекции таких disputes: heuristics.yml на регулярных выражениях. Целый день я сидел и фильтровал данные, помимо добавлял языки программирования, которых Github не знает.

Например, FunC и FIFT. В целом видна человеческая рука здесь по добавлению 2 языков программирования от уважаемого Николая. По всему интернету файлов существует в районе 1000 и спасибо sourcegraph, который смог это всё найти. Но мусора в расширениях .fc и .fift было предостаточно, выфильтровали :)

Далее обучение. Я взял guesslang и чутка крутил batchsize, hidden dnn layers и получил в среднем 88% аккуратности и 92.5% на топ50 самых популярных языках

В конце начинается самое интересное, а собственно, как достать markup comments телеграма? К сожалению, датасетов почти нет, tgstat.ru не сохраняет информацию об этом. Я покачал каких-то прогерских community и докручивал на маленьких данных.

Самое плохое, что лучше всего сработало при маленьких кусках кода просто повторить его, пока не станет 30-40 строк кода. От таких положений вещей модель начинала сходиться к правильным ответам чаще.

Ещё, конечно, не забывайте, что любой текст это Markdown, поэтому чтобы различить одно от другого надо постараться. Докручивали уже disputes какими-то регекспами из heuristics.yml и логикой, мол, если строк мало, то вряд ли это эзотерический язык. Всё равно люди компилируют C код как C++, а Hack почти в природе нет, кроме как у Meta.

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

Последние полдня потратил на то, чтобы собрать tensorflow C++ с нуля и вкомпилить в .so, потому что принимать ничего другого они не хотят. Ну что ж, значит tensorflow. Скомпилировал. Отправил 600Mb .so файл.

Зато более менее работает, 2-3 ms на 4kb.

Делал я это дело 7-8 дней, из которых 3 полных часов по 10, ещё часа по 3-4 вечерами в оставшиеся дни.

Что будет, то будет. Ради фана и узнать что-то новое делал. Узнал о многих языках программирования вроде Raku, ICON, Keyman, LOGO.

И получайте почти красивую картинку confusion matrix.

Давно я не писал, поэтому чуть больше в одном посте

1. Я тут сегодня нашёл интересное применение алгоритма поиска максимального потока, о котором вы вряд ли слышали -- для тестов. В GUnit есть функция UnorderedElementsAre(container), которая сравнивает, что два множества совпадают. Проблема в том, что для общего случая элементы могут быть несравнимы или нехешируемы, тогда проверять на равенство становится сложнее, так как запрещены сортировки и хеш-мапы. Задача решается с помощью максимального паросочетания: между двумя множествами строится граф равенства и после этого находится максимальное паросочетание. В GUnit код находится здесь. UPD. Также в комментариях подсказали, что такая абстракция удобна для того, чтобы иметь разные проверки, скажем, что в множестве есть элементы строго больше, чем в другом (пример).

2. В Google обновился C++ Style Guide на C++20. Ничего не написано про модули, ranges и корутины, потому что всё ещё нет консенсуса. В целом хорошее изменение, вещи прогрессируют.

3. Тут рассказано, сколько фаззеру надо было фаззить, чтобы найти известный сверху баг в WebRTC: https://www.srlabs.de/blog-post/advanced-fuzzing-unmasks-elusive-vulnerabilities . TL;DR 20 независимых байт, что достаточно много для фаззеров. В похожем баге в ZSTD, который мы нашли в марте, надо было около 7-8 специфичных байт после того как фаззер зашёл в нужную строчку кода. Чтобы найти баг в ZSTD и WebRTC нужны более интересные техники. Например, в ZSTD хватило бы добавлять 2^n рандомных байт в конец, а в WebRTC сделать большой if/switch на табличку в 256 байт. Кажется нужен стажёр

4. Google Pixel 8 имеет поддержку Arm MTE. Это фича, которая помечает аллокации специальными тегами на уровне битов указателей и проверяет на уровне железа, читаете ли вы валидную память. Надеюсь, мы найдем очень много всякого разного со временем.

5. Я выложил свою презентацию с CppCon про сортировки https://danlark1.github.io/cppcon_sort_2023 . Запись будет где-то в январе :)

Тут была конференция SOSP . Запомнились некоторые интересные статьи

Silent Data Corruption in Alibaba Cloud. По сравнению со статьями от Google и Meta, Alibaba раскрыла больше данных о том насколько часто находятся битые процессоры и данные в проде. Из интересного, они увидели, что если процессор сильнее нагревается, то вероятность битой инструкции экспоненциально увеличивается. Из ещё забавного -- битфлипы очень часто происходят на тех же позициях в регистре при попытках воспроизвести. Из странного, большинство багов не находят в preprod. Из не понравившегося -- много странных графиков, экстраполяция по 27 битым процессорам и тд.

Project Silica: Towards Sustainable Cloud Archival Storage in Glass. Это, наверное, самая интересная статья, которую я прочитал. Суть в том, что хранение очень холодных данных на магнитных технологиях вроде HDD и тд дорогое, надо обновлять, так как диски вылетают и не остаются на десятки лет. Авторы рассказывают о 12-летнем опыте, как можно хранить данные в стекле, которое не ржавеет и не гниет, у которого срок службы >1k лет. Да, в стекле прям вырезают биты и в итоге данные хранятся дольше.

QuePaxa: Escaping the Tyranny of Timeouts in Consensus. В консенсусных алгоритмах вроде Raft и Paxos часто таймауты вызывают переизбрание лидера. При всяких DoS аттаках система встаёт и не очень продвигается. В итоге поставишь большой таймаут -- долго будет переизбрание, маленький -- слишком много. В QuePaxa предлагают делать хеджирование запросов, чтобы проверять liveness, модификацию Paxos, чтобы несколько proposers предлагали себя с весами в зависимости от быстроты ответов. Интересная и технически непростая статья.

A Cloud-Scale Characterization of Remote Procedure Calls. Статья от Google про 700 миллиардов RPC внутри нас, что мы выучили и куда стремимся с точки зрения оверхеда и Software. Смотрим на библиотеки, scheduling, cross DC traffic. Показываем,что в DC мы всё ещё millisecond-scale и до micro-second нам ещё далеко. Много времени в статье уделяется tail latency -- сколько занимает оверхед RPC framework на 99%. Один из авторов Soheil -- невероятно приятный человек, с кем работать одно удовольствие. Статья читается просто и даёт много инсайтов, что происходит внутри с сетью с точки зрения пользователя.

Тут вышла статья от Кости Серебряного -- человек, который себе карьеру сделал на ASAN, Fuzzing и тд про GWP-ASAN. Это своеобразная модификация аллокатора, которая не включает полную мощь ASAN в проде, так как будут проблемы с оверхедом, а создаёт отдельный буффер, где страницы памяти Linux чередуются -- то, из чего можно читать и то из чего нельзя (PROT_NONE), таким образом легче словить out of bounds ошибки. При аллокациях выдаётся память из одного региона, где можно читать, при деаллокации тоже помечается PROT_NONE, а при use after free, если повезёт, и попадёт туда, куда не надо, то найдёт ошибку в C/C++ подобном коде. Тем самым случайным образом аллокации попадают в буффер и имеют шансы обнаружить ошибки уже не в тестах, а в проде. Ну, мы знаем такие техники, и вероятности не очень большие поймать при одном запуске. Прелесть такого метода в том, что оверхед минимальный, меньше 0.2%

А теперь предположим у вас есть софт, который распространяется на тысячи, миллионы людей и девайсов. Google, Apple, Meta, приложения в Google/App Store, софт Windows, игра в Steam или просто серверы и их много, и работают они долго. Так получается, что вы теперь проверяете на корректность не какой-то участок кода при запуске, а размазываете ASAN на все аллокации на тысячах и миллионах устройств.

Сотни, тысячи багов, простая имплементация и красивая история. Ни тесты, ни фаззинг не спасают от багов в проде

2311.09394.pdf

Тут выложили видео со мной на CppCon https://www.youtube.com/watch?v=cMRyQkrjEeI

Вроде даже неплохо получилось.

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

Технологический мир в последний год был сфокусирован вокруг LLM, а мне посредственно интересна эта тема. Можно поговорить про UltraFastBERT https://arxiv.org/pdf/2311.10770.pdf , где используют часть нейронов через дерево и с помощью sparse matrix multiplication достигают 78x быстрее inference, но, к сожалению, только на CPU. В целом потолок виден в уменьшении всего этого, но алгоритм не положить на GPU и это вопрос на следующий миллиард долларов. Удешевить всё дело в 80 раз даст доступ к LLM всем в каждом углу.

Я вообще редко читаю на постоянной основе чужие блоги, но блог Стивена Вольфрама мне особенно понравился в прошлом году. Например, про ChatGPT.

The basic answer, I think, is that language is at a fundamental level somehow simpler than it seems. And this means that ChatGPT is successfully able to “capture the essence” of human language and the thinking behind it. And moreover, in its training, ChatGPT has somehow “implicitly discovered” whatever regularities in language (and thinking) make this possible.
...
And perhaps there’s nothing to be said about how it can be done beyond “somehow it happens when you have 175 billion neural net weights”. But I strongly suspect that there’s a much simpler and stronger story.

В целом проекты как https://github.com/tinygrad/tinygrad могут попытаться сделать что-то около крутого вокруг идеи much simpler and stronger story. Пытаться утилизировать всё, в т. ч. на CPU имеет смысл и здравый риск. George Hotz, несмотря на всю его спорную личность, очень сильный инженер и, наверное, много в моем стиле программирования я взял от него. В универе смотрел его стримы чуть ли не 24/7 на старших курсах.

Ещё из интересного я вошёл в комитет по разработке следующего поколения SIMD на Arm -- может быть назовём SVE 3 или как-то так. Учитывая, что SVE2 и SVE2.1 было фактически задизайнено Apple и не особо развивалось у них за ненадобностью, то может быть получится продвинуть дело подальше в правильном направлении.

В C++20 завезли destroying delete operator. Его основное отличие от обычного delete -- что при удалении через destroying delete вы сначала заходите в функцию, где сами должны вызвать деструктор

struct Foo {
  ~Foo() {
    std::cout << "In Bar::~Bar()\n";
  }

  void operator delete(Foo* p, std::destroying_delete_t) {
    std::cout << "In Foo::operator delete(Foo*, std::destroying_delete_t)\n";
    p->~Foo();
    ::operator delete(p);
  }
};

https://gcc.godbolt.org/z/zqd8Yn7ff

Из интересного, вы теперь можете сами писать свои vtable: https://gcc.godbolt.org/z/EYMn1sd1o

struct Vehicle {
  const enum Types { CAR, TRUCK } type;
  Vehicle(Types t) : type(t) {}
  void operator delete(Vehicle*,  std::destroying_delete_t);
};
// Implement Car, Truck

void Vehicle::operator delete(Vehicle *p, std::destroying_delete_t) {
  switch (p->type) {
    case CAR:
      static_cast<Car*>(p)->~Car();
      break;
    case TRUCK:
      static_cast<Truck*>(p)->~Truck();
      break;
  }
  ::operator delete(p);
}

Когда вы можете писать свои vtable, вы можете классы инициализировать через memset и тд, потому что вы убираете полную инициализацию.

Например, протобуфы. Все они наследуются от MessageLite, а теперь в кодогенерации можно свою vtable написать и инициализировать все поля быстро через mem*. До этого это было undefined behavior из-за нефиксированности имплементации vtable.

https://en.cppreference.com/w/cpp/memory/new/operator_delete. Cм 27-30.

Недавно понадобилось снова открыть документацию и посмотреть что значат регистры %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.

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

Тут вышел доклад от человека, который стандартизировал атомарные операции в С++ про то, что он понял за 15+ лет от этого дела.

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

По сути: доклад достаточно самокритичный

* Показывает, что думали в 2008-2010, когда создавали. Например, тогда мультиядерные системы только появились и математические модели стали стандартом. Например, Intel до 2007 года не писала, что у них Total Store Order.
* К удивлению, большинство железок исправилось и теперь Sequentially Consistent операции стоят не сотни тактов, а единицы. И даже когда приводили в пример Arm, оказывается, что они тоже туда движутся. Разнообразие различных моделей становится всё менее важным.
* Никто не понимает memory_order_consume. Я тоже
* В какой-то степени было ошибкой класть математическую модель в стандарт. Разработчики не читают стандарт, разработчики компиляторов тоже. Получается писали только для рисерчеров. Тем не менее, какой-то формализм нужен. Открытый вопрос как это сделать для людей.
* Weak memory model теряет свои преимущества. Большинство атомарных операций это флаги, counters, кеши, намного реже lock free structures и подобное.


Ещё из забавного, примерно в это же время нашли deadlock баг в имплементации shared_mutex в кишках Windows API. С Windows Vista воспроизводится, почти уже 20 лет багу в таких примитивах.

Съездил я тут в Эдинбург на 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 у меня от его статей и лекций. Видеть таких рок-звёзд вживую воодушевляет. Мол, чувак, я над твоими работами умирал, проливал на них кофе, засыпал в обнимку, а ты тут стоишь как ни в чём ни бывало, привет!

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

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, чтобы можно было дебагать, что происходит.

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

Хайп по 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-potential

2. 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 как-то сильно измениться снова до "давайте всё разделим"

3. Я выложил 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

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

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