Последние посты
Experimental chill
2 сент. 2025 г., 03:57
Latency profilerПредставьте ситуацию, вы пишете код на Python, вызываете посередине библиотеку, например, для inference, понимаете, что программа работает медленно. Собираете профиль с помощью стандартных утилит вроде perf, и в итоге видите следующую картину90% Matmul 10% some PythonСмотрите на это, расстраивайтесь, ведь умножение матриц скорее всего так сильно соптимизировано, что можно даже не пытаться.К счастью, не все так просто. Perf собирает события со всех потоков и CPU, которые суммируются. В итоге если вдруг умножение матриц было на многих ядрах, скажем, 8, то вы увидите в профиле, что вес matmul в 8 раз больше.Недавно в perf добавили --latency, тулза, которая делит все события на количество активных CPU. После этого вы можете увидеть профиль в духе40% matmul 60% some PythonТеперь оптимизировать питон есть смысл для задержки (latency), ведь профиль показывает, чтоPhoronixLinux 6.15 Perf Tooling Introduces New Support For Latency ProfilingThe perf tools changes were merged today for the Linux 6.15 kernelExperimental chill
10 июл. 2025 г., 20:31
Trivially relocatableВ C++ есть большая группа людей (включая меня), которая любит брать оптимизации из C -- mem функции возможно являются сильнейшим преимуществом C перед многими другими языками в перформансе. В C++ об этом думали и делали аттрибут std::trivially_copyable, который разрешает копировать как memcpy. Отлично работает на примитивных структурах и в целом C++ такой быстрый в том числе и из-за этого.Но бывают и более интересные кейсы. Когда вы добавляете элементы в std::vector, рано или поздно вам надо будет реаллоцировать. Вы будете копировать числа/делать std::move объектов из предыдущего вектора. В ситуации с числами можно звать memcpy, они тривиальны, всё отлично. Но на самом деле звать memcpy можно и не только на тривиально копируемые типы, а, например, на unique_ptr<T>, или QString (который с ref count), или vector<int>!Ведь копирование указателей, чисел видаKDABQt and Trivial Relocation (Part 1): What is relocation? | KDABDiscover how Qt optimizes container operations with byte-level manipulations, including trivial relocation for types like int and QString.Experimental chill
15 мая 2025 г., 13:04изменён
Size based vectorhttps://discourse.llvm.org/t/adding-a-size-based-vector-to-libc-s-unstable-abi/86306Мы тут в Гугле экспериментировали с тем как репрезентовать вектор. Существует два способа:1. Указатель на начало, конец и указатель на конец вместимости2. Или указатель на начало, размер и вместимостьОба варианта имеют свои особенности и слабые места. Первый вариант плох тем, что когда вы хотите посчитать size(), то вы вычитаете два указателя: end - begin. Вычитание указателей в численном представлении эквивалентно формуле (end_as_num - begin_as_num) / sizeof(T), где T -- тип вектора. Вот это деление на константу порой выбешивает, например, когда sizeof(T) не является степенью двойки. Компилятору приходится это деление переводить в умножение и теперь когда вы вызываете size(), то у вас откуда-то страшные конструкции вида https://godbolt.org/z/zKGz7nEE6Но первый вариантLLVM Discussion ForumsAdding a size-based vector to libc++’s unstable ABIAdding a size-based vector to libc++’s unstable ABI tl;dr We can significantly improve the runtime performance of std::vector by changing its representation from three pointers to one pointer and two integers. This document explains the details of this change…Experimental chill
23 апр. 2025 г., 09:33изменён
Сегодня про закон Литтла.Недавно очень много читал про теорию очередей — это математика того, как работа или юниты работы исполняются в системе, особенно когда в системе есть ожидание, лимиты и задержки, когда ресурсы станут доступны. Это довольно актуально для разработки серверов и связи нагрузки с тем, сколько надо давать ресурсов на сервис.Как теория очередей связана с нагрузкой? Закон Литтла, один из самых простых и легко понимаемых результатов теории очередей, гласит, что среднее количество клиентов в системе равно средней скорости прибытия, умноженной на среднее время пребывания в системе. В этом случае клиенты — это запросы в обработке, скорость прибытия — это объем трафика, представленного серверу, а время пребывания — это количество времени, необходимое для обработки каждого запроса. Закон доказывается не самым простым, но вполне понимаемым для студента образом. НаWikipediaLittle's lawtheorem in queueing theoryExperimental chill
25 мар. 2025 г., 12:39
1. Объявили результаты TON: дали серебро, оказался 6-7 по топу (Mindful Kitten), дали $5000. Я доволен, так как не упоролся, но и позанимался чем-то интересным.2. Meta рассказала про свою версию GWP/Perforator -- профилирование всех датацентров.So, the engineer typed an “&” after the auto keyword to indicate we want a reference instead of a copy. It was a one-character commit, which, after it was shipped to production, equated to an estimated 15,000 servers in capacity savings per year!Немного смешно читать такой маркетинг, потому что давным давно такие штуки мы уже сделали в Google и автоматизировали по самое не хочу. В целом поздравляю, такие вещи позволяют держать CapEx в порядке и возможно помогут избежать хоть каких-то увольнений (a.k.a. могло быть и хуже).3. https://dl.acm.org/doi/10.1145/3651890.3672262В Google очень много данных надо копировать между датацентрами --Engineering at MetaStrobelight: A profiling service built on open source technologyWe’re sharing details about Strobelight, Meta’s profiling orchestrator. Strobelight combines several technologies, many open source, into a single service that helps engineers at Meta improve effic…Experimental chill
5 февр. 2025 г., 13:53
January update (старею)1. Мой (первый) стажёр из Яндекса опубликовал Perforator — сборщик профилей и перформанса на всём кластере. После 7 лет Сергей уже оч сильный инженер, конечноhttps://github.com/yandex/perforatorhttps://habr.com/ru/companies/yandex/articles/875070/В Гугле мы занимаемся именно этим (GWP), так что потихоньку мои ученики меня превосходят, а я старею.Почитайте, хорошо всё сделано, но у меня, конечно, конфликт интересов :)2. Закончил писать контест от телеграма по оптимизации валидации TON блоков. Суть была в том, чтобы надо было заооптимизировать код Коли Дурова, который они с командой написали в 2018-2019(?). Там около 40к строк кода, попросили заооптимизировать валидацию блоков, это где-то 10к строк кода. Читал я это дело несколько дней, но мультипоточные идеи там не супер хороши, потому что блоки валидировать надо последовательно и только лишь небольшиеGitHubGitHub - yandex/perforator: Perforator is a cluster-wide continuous profiling tool designed for large data centersPerforator is a cluster-wide continuous profiling tool designed for large data centers - yandex/perforatorExperimental chill
12 янв. 2025 г., 18:55изменён
Compressed pairВ стандартной библиотеке C++ множество контейнеров принимают allocator<A>, который по дефолту занимает 0 байт. Но в C++ не могут быть структуры (в отличие от C) с sizeof равным нулю. Значит элементами класса их не сделать бесплатно. В итоге приходилось использовать Empty Base Optimization, когда наследование от класса с нулевым размером оптимизируется в void. Чтобы это как-то унифицировать, в libc++ сделали compressed_pair<A, B>, чтобы можно было писать члены класса и зафиксировать ABI. Делали A каким-то нужным полем, а B, например, аллокатором, тем самым sizeof сохранялся.В C++20 добавили атрибут [[no_unique_address]], который запрещает адресоваться к структурам размера ноль, а если более точно, то при попытке так сделать даст какой-то адрес какого-то члена класса.Спустя 4 года завезли в libc++ и заменили compressed_pair. Патч тащили 9 месяцев, потому чтоGitHub[libc++] Replace `__compressed_pair` with `[[no_unique_address]]` by philnik777 · Pull Request #76756 · llvm/llvm-projectThis significantly simplifies the code, improves compile times and improves the object layout of types using __compressed_pair in the unstable ABI. The only downside is that this is extremely ABI s...Experimental chill
11 янв. 2025 г., 18:39
https://www.vldb.org/pvldb/vol16/p2132-afroozeh.pdfПрочитал тут статью с VLDB про формат данных в базах данных, который даёт много идей на подумать. Даже есть репозиторий https://github.com/cwida/FastLanesАвторы ставят перед собой несколько целей для дизайна формата хранения целых чиселSIMD friendlyПоддерживает все виды несложного сжатия: parquet, delta encoding, RLEНу так как я что-то делал в этой области, статья написано хорошо! Упрощённо: предлагается хранить, например, не 64 битные числа, а каждый байт в 8 колонках. Для меньшего количества бит происходит более интересное чередование, но суть похожа, все это пакуется в 1024 битные регистры.Чтобы поддержать такое сжатие и воспользоваться всеми преимуществами, авторы перебирали форматы и научились в целом находить Наименьшее Общее Кратное того, как биты должны быть расположены, чтобы все 3 формата сжатия удовлетворить. КExperimental chill
4 янв. 2025 г., 09:28
S3 localityТут я хотел рассказать о каких-то челленджах в построении storage систем по типу S3. Обычно в таком духе я спрашиваю людей на собеседованиях, поэтому тут мысли вслух, любые совпадения случайны.Всё понятно с корректностью -- храним метаданные транзакционно, чтобы ни дай бог ничего не потерять, Paxos нам в помощь, это много работы, но хотя бы понятно как сделать.Диски хоть и дешёвые, но на масштабах S3 любая экономия байт уходит за миллионы/сотни миллионов долларов. S3 сжимает данные с помощью ZSTD https://news.ycombinator.com/item?id=32529412 и внутри скорее всего есть какой-нибудь Erasure Coding, чтобы не хранить дорогие копии.Понятное дело, что когда вы загружаете данные, никто не будет сжимать или хранить в памяти весь файл, поэтому скорее всего данные как-то разбиваются на чанки по несколько мегабайт максимум, иначе было бы очень дорого поддерживать такую систему.Experimental chill
3 янв. 2025 г., 10:51
Отличный пост сегодня на hn, трюк знакомый, пугающий, и вроде даже в комментариях разобрались. https://news.ycombinator.com/item?id=42579969 https://tavianator.com/2025/shlx.htmlАвтор поста обнаружил, что при таком патче в определённых условиях.LOOP: - MOV RCX, 1 + MOV ECX, 1Инструкция SHLX RAX, RAX, RCX (означающая RAX = RAX << RCX) ускоряется в три раза на Alder Lake.Почему?Решение этой загадки скорее всего заключается в том, что в Alder Lake увели много инструкций в стадию rename -- это когда процессор не ждёт регистра и его результата, а выдаёт новый готовый регистр (возможно с метаданными, например, что к нему надо что-то добавить). Например, лучше всего это видно в случаях циклов.loop: inc rax cmp rax, rcx jb .loopExperimental chill
15 нояб. 2024 г., 22:03
Мы тут выложили апдейт по тому, что будет с С++ в Google. В общем, на Rust у нас уже можно писать, Carbon все ещё разрабатывается, а с C++ мы будем включать bounds checks во всех приложениях. Спойлер: включили bound checks во всяких векторах и строчках, немногоGoogle Online Security BlogRetrofitting spatial safety to hundreds of millions of lines of C++Posted by Alex Rebert and Max Shavrick, Security Foundations, and Kinuko Yasuda, Core Developer Attackers regularly exploit spatial mem...Experimental chill
16 окт. 2024 г., 07:31изменён
Мы тут выложили апдейт по тому, что будет с С++ в Google. В общем, на Rust у нас уже можно писать, Carbon все ещё разрабатывается, а с C++ мы будем включать bounds checks во всех приложениях.Спойлер: включили bound checks во всяких векторах и строчках, немного CPU скушало, но все в пределах нормы. Были страхи, что встретим запрос смерти, который положит весь прод, пока не встретили, но появилась и у вас возможность уложить весь прод :)https://security.googleblog.com/2024/10/safer-with-google-advancing-memory.htmlGoogle Online Security BlogSafer with Google: Advancing Memory SafetyPosted by Alex Rebert, Security Foundations, and Chandler Carruth, Jen Engel, Andy Qin, Core Developers Error-prone interactions between ...Experimental chill
30 авг. 2024 г., 08:31
Fast Commits в fsyncЯ с универских времен изучал fsync, но только на уровне, что этот вызов -- самая последняя инстанция перед тем, как сказать диску, что надо всё на него сбросить. К своему удивлению, спустя несколько лет, я наткнулся на работу коллеги про Fast Commits, которая пытается соптимизировать fsync в EXT4 в Linux уже несколько лет, и, кажется, у этого дела виднеется свет в конце тунеля. Также получили на USENIX ATC 2024 best paper award https://www.usenix.org/conference/atc24/presentation/shirwadkarfsync в EXT4 работает через алгоритм JBD2 (Journaling Block Device v2), который хранит последние операции работы с диском и применяет их, гарантируя, что всё корректно применится даже в случае отказа машинки. Первый инсайт, который я узнал -- всё это дело происходит раз в 5 секунд и при каждом вызове fsync.Второй инсайт, что JBD2 хранит минимум 3 блока по 4kb на каждуюExperimental chill
17 июл. 2024 г., 17:18
Тут с сожалением сообщу, что мейнтейнер 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, LegenGitHubRe: Junyer · Issue #502 · google/re2The 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...Experimental chill
5 июл. 2024 г., 13:17
Удивительно, не думал, что об этом писали, но мы аж 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 вставлял элемент в кеш только если его читали во второй раз (то есть было два промаха сравнительно недавно). Прожило этоWikipediaAdaptive replacement cachecache management algorithmExperimental chill
21 июн. 2024 г., 11:54
__is_bitwise_cloneablehttps://discourse.llvm.org/t/extension-for-creating-objects-via-memcpy/76961Команда протобуфа решает интересную проблему: протобуфы хоть и похожи на обычные структуры, но они со временем разрослись, и вообще они виртуальные классы для того, чтобы можно было с ними удобно работать. И у пользователей есть ожидание, что они почти похожи на примитивные структуры. Иногда кто-то напишет свой формат и скажет, что он быстрее протобуфов, потому что проще!Когда мы копируем какой-то протобуф, то часто можно скопировать просто все биты примитивных полей, что является простой задачей для memcpy. Но проблема, memcpy вызывает undefined behavior на таких классах из-за виртуальности, и нетривиальной копируемости, и проблем с лайфтаймами. В C++23 аж добавили https://en.cppreference.com/w/cpp/memory/start_lifetime_as , так как даже ужасный std::launder не решил никакихLLVM Discussion ForumsExtension for creating objects via memcpyTLDR: we’re looking for a well-defined way to create objects with vptrs via memcpy. We have a common code pattern on creating new message objects in protobuf parser: // Message is almost trivial, except that it has virtual methods class Message { public:…Experimental chill
5 июн. 2024 г., 08:23изменён
1. Не так часто в основной курс алгоритмов и структур данных можно включить новый не очень сложный алгоритм. Его Кнут назвал CVM алгоритмом для подсчёта количества различных элементов в потоке элементов. Действительно очень простой алгоритм https://arxiv.org/pdf/2301.10191 . Кнут написал целую статью про него https://cs.stanford.edu/~knuth/papers/cvm-note.pdf . Удивительно как я всё реже занимающийся такими вещами даже смог осилить доказательство. К сожалению или к счастью он не лучше по оценкам, чем HyperLogLog, но зато не использует никакого хеширования. Из хорошего, я думаю единицы в мире умеют доказывать оценку HyperLogLog, а тут получается, что можно даже доказать что-то за лекцию.2. Тут вышли очередные бенчмарки хештаблиц. Скажу, что как обычно побенчмаркали какие-то огромные таблицы, которые в реальной жизни не так часты. Может быть для баз данных бывает такое, но для обычнойExperimental chill
23 апр. 2024 г., 09:56
LLAMAКогда вы занимаетесь перформансом, одно из полезных упражнений для проделывания в голове -- анализ скорости света. В простом варианте надо задать себе вопрос "А какой реально лимит сделать то, что делаем мы в библиотеке/программе?".Очевидный ответ, понятное дело, ноль, лимита нет. Но если подумать, всегда есть некоторые ограничения. Приведём примеры:Компрессия -- лимит: memcpy. Скопировать данные уж точно надо будетХеширование -- проход по массиву, уж точно надо будет все данные прогрузить и сделать хотя бы одну инструкцию с нимиАллокатор -- хмм, уже не очень понятноАнализы скорости света выходят всё чаще и чаще, например, теоретические лимиты в математике/алгоритмах и так далее. Они часто оказываются неприменимы, но они действительно могут помочь понять, куда смотреть, находить какие-то эвристики для того, чтобы приблизиться к этому лимиту.Тут вышла статья сExperimental chill
7 апр. 2024 г., 10:58
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.tarSubstack2023-11-26 arXiv roundup: Big potential wins, 1 bit per parameter, Simplifying transformersStella Nera: Achieving 161 TOp/s/W with Multiplier-free DNN Acceleration based on Approximate Matrix MultiplicationExperimental chill
7 апр. 2024 г., 10:58
Хайп по LLM спадает, наконец-то можно писать что-то в блоге и не чувствовать, что я отстаю от жизни :)1. Почитал тут хороший разбор как можно ускорить всякие перемножения матриц.В целом это статья про approximate matrix multiplication, я лично мало знал, что там происходит. Особенно это хорошо работает, когда одна матрица статична, как, например, в LLM.Когда вы перемножаете матрицы, вы делаете очень много разных операций с разными числами, поэтому всегда интересен вопрос, а можно ли умножать одинаковые числа и знать куда их вставлять -- одно решение это уменьшать множество чисел над которыми происходит умножение: -1, 0, 1. Другой подход -- оставлять матрицу, но не перемножать все строки и столбцы.Статья предлагает группировать похожие строки/столбцы в один блок (в offline обучить для статичной матрицы), в котором можно найти несколько центроидов с помощью k-means. ДальшеSubstack2023-11-26 arXiv roundup: Big potential wins, 1 bit per parameter, Simplifying transformersStella Nera: Achieving 161 TOp/s/W with Multiplier-free DNN Acceleration based on Approximate Matrix Multiplication
