Сегодня прочитал статью по поводу того, что в clang санитайзеры применяются уже после некоторых оптимизаций, которые могут пользоваться неопределенным поведением, то есть вы написали плохой код, потом оптимизатор воспользовался этим, а санитайзер не поймал. Статья направлена на то, чтобы найти эти оптимизации. Результаты получились хорошими, нашли ещё несколько багов, в том числе в OSS-Fuzz.
В целом если возможно, запускайте Msan, Asan с -O0 оптимизациями (особенно Msan). Если не получается, может быть хватит у кого-то сил дотащить эту статью до LLVM. Статья милая, читается легко. Назвали такой процесс тоже смешно, Don't LookUB. А вот репозиторий ещё не открыли https://github.com/vusec/LookUB. Наука про санитайзеры все ещё развивается в вероятностные схемы.
https://goto.ucsd.edu/~gleissen/papers/dontlookub.pdf
Ещё интересная идея пришла в голову, что при всяких хеш таблицах с реальными данными порой не стоит считать хэш функции от всего объекта, для строк может хватить первого/последнего+размер и перехешировать, если видно, что хеш таблица сильно забита. Порисерчу, что вообще есть по этому поводу, иногда прям есть бинари, где хеши проблемные.
В целом если возможно, запускайте Msan, Asan с -O0 оптимизациями (особенно Msan). Если не получается, может быть хватит у кого-то сил дотащить эту статью до LLVM. Статья милая, читается легко. Назвали такой процесс тоже смешно, Don't LookUB. А вот репозиторий ещё не открыли https://github.com/vusec/LookUB. Наука про санитайзеры все ещё развивается в вероятностные схемы.
https://goto.ucsd.edu/~gleissen/papers/dontlookub.pdf
Ещё интересная идея пришла в голову, что при всяких хеш таблицах с реальными данными порой не стоит считать хэш функции от всего объекта, для строк может хватить первого/последнего+размер и перехешировать, если видно, что хеш таблица сильно забита. Порисерчу, что вообще есть по этому поводу, иногда прям есть бинари, где хеши проблемные.
GitHub
GitHub - vusec/LookUB
Contribute to vusec/LookUB development by creating an account on GitHub.
Недавно мы потратили несколько дней, чтобы найти memory corruption в C++ коде. Оказалось это была плохая сортировка.
В общем, пропозал, который все точно ждали. Давайте проверять в сортировке strict weak ordering на первых X элементов. Про квадратичный алгоритм проверки я уже писал, надо дотащить до конца и для всех.
Квадратичный алгоритм находит больше багов, кубический алгоритм даже на 100 элементах будет достаточно дорого обходиться, а вот квадратичный самое то. Сортировки >100 элементов в реальной жизни достаточно редки, чтобы в них поставить баг и не заметить.
В общем, можете почитать RFC в LLVM:
https://discourse.llvm.org/t/rfc-strict-weak-ordering-checks-in-the-debug-libc/70217
В общем, пропозал, который все точно ждали. Давайте проверять в сортировке strict weak ordering на первых X элементов. Про квадратичный алгоритм проверки я уже писал, надо дотащить до конца и для всех.
Квадратичный алгоритм находит больше багов, кубический алгоритм даже на 100 элементах будет достаточно дорого обходиться, а вот квадратичный самое то. Сортировки >100 элементов в реальной жизни достаточно редки, чтобы в них поставить баг и не заметить.
В общем, можете почитать RFC в LLVM:
https://discourse.llvm.org/t/rfc-strict-weak-ordering-checks-in-the-debug-libc/70217
Telegram
Experimental chill
Когда вы находите минимум/сортируете/делаете кучу из элементов, нужно чтобы ваши элементы удовлетворяли свойству строгого слабого порядка (по-английски strict weak ordering).
Этот порядок для компаратора comp и множества S означает несколько свойств:
1.…
Этот порядок для компаратора comp и множества S означает несколько свойств:
1.…
Очень интересная вещь происходит в memory management Linux в последнее время.
Когда вы аллоцируете память, вы создаёте страницы, обычно они по историческим причинам 4KB, и если вы большая компания, или даже запускаете базу данных, то со временем страниц становится много, появляются проблемы походов в TLB, сервер со временем начинает тормозить. В Google в статье про TCMalloc [1] мы репортили, что 20% всех циклов в датацентре мы проводим в TLB, что не очень то и радует. На помощь приходят Huge Pages, так как их размер побольше, то не происходит больших таблиц и количество TLB простаиваний происходит меньше.
Это показывает, что Huge Pages становятся уже не только хорошей оптимизацией, а в целом Must Have для приложений, которых заботит перформанс.
Проблемы начинают приходить с других сторон в этом направлении. 2MB Huge Pages достаточно сложно выделить ядру из-за большой фрагментации. Если вы на часок оставите шард поискового движка отвечать на запросы, его перф, с одной стороны, улучшается из-за прогретости индекса, с другой стороны ухудшается memory management, так как страницы начинают быть фрагментированы из-за того, что на сервере много всякого происходит. Я пока читал то, о чём сейчас пишу, узнал для себя, что ядро очень сильно разделает все страницы на movable/unmovable. Первые -- те, которые получает пользователь, их ядру легче перемещать, тем самым оно может лучше выделять память на физическом уровне. Unmovable страницы -- те, которые ядро выделяет само, для Network/IO стека, их перемещать сложно, так как ядро к ним доступ имеет мультипоточный и напрямую. Можно лочить всё, чтобы их поменять, но оверхед от такого будет ещё выше, представьте, что вы хотите получить RPC, а тут lock в ядре, оно обновляет все TLB всех ядер, RPC не проходит, беда, печаль.
Простая проблема, которая возникает -- что если 2MB страницы unmovable на физическом уровне находятся рядом с movable? Отсюда начинает сложно дефрагментировать даже movable страницы, если есть задача поближе поставить страницы на физическом уровне. Исторически в ядре утилизации памяти уделяли больше времени, чем вынесение разных видов страниц в разные регионы. Инженеры из Meta на ISCA'23 [2] выложили, наверное, одну из самых интересных статей для меня за последнее время, где они стараются выделять память для movable/unmovable регионов далеко друг от друга на уровне ядра, чтобы улучшать layout памяти на физическом уровне.
Фактически идея достаточно простая -- взять два далеких региона, сказать, что один для movable, другой для unmovable и перемещать границы. Если границы начинают пересекаться, в худшем случае ничего не сделать. Тем не менее, можно делать интересные вещи:
[unmovable region][free space][movable region]
Если есть долгоживущая неперемещаемая страница, то надо её ставить в самое лево, да и вообще, если есть хоть какие-то страницы, лучше их ставить в далёкие от границы места -- тем самым resizing имеет больше шансов быть успешным.
Следующая идея -- считать простую статистику как memory pressure. Она включает в себя время, проведенное в page faults и тому подобное в обоих регионах.
Самая сложная часть -- миграции страниц. Как уже сказано, в софте такую миграцию будет накладно сделать, поэтому инженеры из Meta построили дополнение к LLC на уровне железа. Краткая идея, что для всего процесса надо очень аккуратно оповестить TLB для инвалидации, которая разрешает копирование страницы (в это время все доступы блокируются), а потом уже TLB можно оповестить, чтобы можно было ходить в новую страницу.
Удивительное в этом всём, что приложения получают очень хороший прирост. От 2% до 14%. И код доступен [3], чтобы можно было играться. Моё понимание, что они ещё не выложили это в прод, а пока экспериментируют, но в целом выглядит, как эта тема одна из самых интересных в memory management, память не растет, мы начинаем выкручиваться как можем и делаем все более сложные схемы.
[1] Google TCMalloc Paper
[2] Contiguitas: The Pursuit of Physical Memory Contiguity in
Datacenters
[3] https://lwn.net/ml/linux-kernel/[email protected]/
Когда вы аллоцируете память, вы создаёте страницы, обычно они по историческим причинам 4KB, и если вы большая компания, или даже запускаете базу данных, то со временем страниц становится много, появляются проблемы походов в TLB, сервер со временем начинает тормозить. В Google в статье про TCMalloc [1] мы репортили, что 20% всех циклов в датацентре мы проводим в TLB, что не очень то и радует. На помощь приходят Huge Pages, так как их размер побольше, то не происходит больших таблиц и количество TLB простаиваний происходит меньше.
Это показывает, что Huge Pages становятся уже не только хорошей оптимизацией, а в целом Must Have для приложений, которых заботит перформанс.
Проблемы начинают приходить с других сторон в этом направлении. 2MB Huge Pages достаточно сложно выделить ядру из-за большой фрагментации. Если вы на часок оставите шард поискового движка отвечать на запросы, его перф, с одной стороны, улучшается из-за прогретости индекса, с другой стороны ухудшается memory management, так как страницы начинают быть фрагментированы из-за того, что на сервере много всякого происходит. Я пока читал то, о чём сейчас пишу, узнал для себя, что ядро очень сильно разделает все страницы на movable/unmovable. Первые -- те, которые получает пользователь, их ядру легче перемещать, тем самым оно может лучше выделять память на физическом уровне. Unmovable страницы -- те, которые ядро выделяет само, для Network/IO стека, их перемещать сложно, так как ядро к ним доступ имеет мультипоточный и напрямую. Можно лочить всё, чтобы их поменять, но оверхед от такого будет ещё выше, представьте, что вы хотите получить RPC, а тут lock в ядре, оно обновляет все TLB всех ядер, RPC не проходит, беда, печаль.
Простая проблема, которая возникает -- что если 2MB страницы unmovable на физическом уровне находятся рядом с movable? Отсюда начинает сложно дефрагментировать даже movable страницы, если есть задача поближе поставить страницы на физическом уровне. Исторически в ядре утилизации памяти уделяли больше времени, чем вынесение разных видов страниц в разные регионы. Инженеры из Meta на ISCA'23 [2] выложили, наверное, одну из самых интересных статей для меня за последнее время, где они стараются выделять память для movable/unmovable регионов далеко друг от друга на уровне ядра, чтобы улучшать layout памяти на физическом уровне.
Фактически идея достаточно простая -- взять два далеких региона, сказать, что один для movable, другой для unmovable и перемещать границы. Если границы начинают пересекаться, в худшем случае ничего не сделать. Тем не менее, можно делать интересные вещи:
[unmovable region][free space][movable region]
Если есть долгоживущая неперемещаемая страница, то надо её ставить в самое лево, да и вообще, если есть хоть какие-то страницы, лучше их ставить в далёкие от границы места -- тем самым resizing имеет больше шансов быть успешным.
Следующая идея -- считать простую статистику как memory pressure. Она включает в себя время, проведенное в page faults и тому подобное в обоих регионах.
Самая сложная часть -- миграции страниц. Как уже сказано, в софте такую миграцию будет накладно сделать, поэтому инженеры из Meta построили дополнение к LLC на уровне железа. Краткая идея, что для всего процесса надо очень аккуратно оповестить TLB для инвалидации, которая разрешает копирование страницы (в это время все доступы блокируются), а потом уже TLB можно оповестить, чтобы можно было ходить в новую страницу.
Удивительное в этом всём, что приложения получают очень хороший прирост. От 2% до 14%. И код доступен [3], чтобы можно было играться. Моё понимание, что они ещё не выложили это в прод, а пока экспериментируют, но в целом выглядит, как эта тема одна из самых интересных в memory management, память не растет, мы начинаем выкручиваться как можем и делаем все более сложные схемы.
[1] Google TCMalloc Paper
[2] Contiguitas: The Pursuit of Physical Memory Contiguity in
Datacenters
[3] https://lwn.net/ml/linux-kernel/[email protected]/
[[lifetimebound]]В компиляторы C++ потихоньку приходят интересные фичи с memory safety, в этот раз поговорим о [[clang::lifetimebound]]. Он предназначен для того, чтобы показать, что жизнь возвращаемого объекта может зависеть от жизни аргумента
Я частенько видел код в духе
const std::string& s = StatusOrProtobuf()->field_value();Где StatusOrProtobuf возвращает
absl::StatusOr<Proto>, где мы знаем, что статус будет всего OkStatus.И в этот момент я всегда задавался вопросом, а верно ли, что это просто неправильно? StatusOrProtobuf() будет же локальной переменной, в итоге мы берем ссылку на объект внутри локальной переменной, что вроде бы undefined behavior, так как локальная переменная разрушится.
Компиляторы и санитайзеры могут это не поймать так как примеры могут быть более интересными в духе
template<typename T, typename U>
const U &get_or_default(const std::map<T, U> &m,
const T &key,
const U &default_value);
В итоге если вернётся default value, то писать в духе
const std::string &val = get_or_default(m, "foo"s, "bar"s);некорректно. В тестах можно забыть протестировать default_value, а в проде выстрелит.
В clang привнесли атрибут [[clang::lifetimebound]], который находит всякие такие баги на этапе компиляции. Можно писать
template<typename T, typename U>
const U &get_or_default(const std::map<T, U> &m [[clang::lifetimebound]],
const T &key, /* note, not lifetimebound */
const U &default_value [[clang::lifetimebound]]);
Просто скажу, что мы в abseil облепились этими лайфтаймами и нашли сотню другую багов. Очень полезно даже для примитивных типов вроде unique_ptr::operator* и тд. Его можно ставить на аргументы функций и на функции класса пока.
Это достаточно полезно в любом месте, где у вас есть какой-нибудь контейнерный утиль, пользуйтесь.
Да, в Rust это встроено в язык, lifetimebound это упрощенный простой один lifetime
'a в Rust. За любой срач по Rust в коментах бан.Привнести такой атрибут хотели давно в P0936 и очень долго пытаются починить всякие range based for.
Wide LRC codes
Я как-то писал в канале про Erasure Codes, в том числе про LRC, который в какой-то степени стал стандартом. Напомню, что про Erasure Codes можно думать как redundancy technique -- если у вас есть данные, их можно поделить на 2 части, посчитать xor, теперь при выпадении любой из 3 получившихся частей, мы можем восстановить данные полностью. В итоге потратили 1.5x места, но redundancy 2 (при выпадении любого 1 куска данные восстанавливаются). Если копать глубже, то дополнительные k частей получаются умножением на матрицу (n + k) x n над полем F_2 или F_256, а при выпадении любых k, матрицу можно обратить и восстановить данные. Вопрос в нахождении матрицы, но так получается, что k можно брать достаточно маленьким по сравнению с n и фактически можно достигнуть любой практической redundancy k потратив (1+eps) места. LRC идут дальше, они стараются группировать некоторые из n частей вместе, чтобы обращение матрицы было частичным -- скажем, поделим всё на 12 частей, у первых 6 посчитаем XOR, у вторых 6 посчитаем XOR, попробуем найти матрицу 16 x 12, где две строки это такие линейные преобразование и ещё 2, чтобы матрица была полностью обратима. Теперь если выпал один чанк данных, то можно скачать 6 других восстановить по XOR, если два чанка в двух разных группах, то тоже всё сработает, а если выпало 3 или 2 в одной группе, ну что ж поделать, скачаем всё и обратим матрицу. Но такие случаи реже случаются, поэтому инженерия любит такое дело. Такие группы называют локальными группами, а дополнительные чанки у локальных групп -- локальные чанки, а дополнительные чанки для всей операции -- глобальные чанки.
На FAST'23 вышла статья в Google про широкие LRC коды. Это такие коды, которые делят на очень много частей, чтобы получить большую redundancy и потратить поменьше места. Холодный storage может делить данные на сотни частей и делать всего десятки дополнительных чанков получая redundancy в 6-7 c оверхедом на весь сторадж процентов в 10% (например, (96, 4, 5) делит на 96 частей, бьёт на 4 локальные группы с 5 глобальными чанками). Хоть и теория кодов очень хорошо изучена, на практике становится слегка сложно с балансом двух вещей
* Находить обратимые матрицы с свойствами локальных чанков
* Сделать операции локальных чанков достаточно простыми, скажем, обычный XOR ок, но что-то сложнее уже слегка путает инженеров. Простота также полезна для миграций -- можно ли как можно больше посчитанных чанков сохранить
Обычно LRC коды изучают как сделать операции над локальными чанками. Статья от Google показывает, что можно сделать слегка лучше -- смотреть на локальные группы как функцию не только от изначальных данных, но и от глобальных чанков, а можно также смотреть как на функцию от данных, глобальных и локальных. Так становится чуть проще размазать локальные чанки по всем данным. Определение и трюк слегка self-referential в том плане, что локальные чанки определяются через локальные, но статья считает некоторую математику, которая сходится.
Зачем это надо?
В статье можно увидеть только слегка лучше результаты по метриками redundancy, average cost of repair и тд. Цифры не ахти в сравнении и никакой супер революции этот LRC метод не привносит. Он рассказывает историю как продвинуть рисёрч слегка дальше по достаточно практичной теме как LRC коды.
Keep on pushing, статья рассказывает хорошую историю.
https://www.usenix.org/system/files/fast23-kadekodi.pdf
https://www.youtube.com/watch?v=pfnSYWEf5q4
Я как-то писал в канале про Erasure Codes, в том числе про LRC, который в какой-то степени стал стандартом. Напомню, что про Erasure Codes можно думать как redundancy technique -- если у вас есть данные, их можно поделить на 2 части, посчитать xor, теперь при выпадении любой из 3 получившихся частей, мы можем восстановить данные полностью. В итоге потратили 1.5x места, но redundancy 2 (при выпадении любого 1 куска данные восстанавливаются). Если копать глубже, то дополнительные k частей получаются умножением на матрицу (n + k) x n над полем F_2 или F_256, а при выпадении любых k, матрицу можно обратить и восстановить данные. Вопрос в нахождении матрицы, но так получается, что k можно брать достаточно маленьким по сравнению с n и фактически можно достигнуть любой практической redundancy k потратив (1+eps) места. LRC идут дальше, они стараются группировать некоторые из n частей вместе, чтобы обращение матрицы было частичным -- скажем, поделим всё на 12 частей, у первых 6 посчитаем XOR, у вторых 6 посчитаем XOR, попробуем найти матрицу 16 x 12, где две строки это такие линейные преобразование и ещё 2, чтобы матрица была полностью обратима. Теперь если выпал один чанк данных, то можно скачать 6 других восстановить по XOR, если два чанка в двух разных группах, то тоже всё сработает, а если выпало 3 или 2 в одной группе, ну что ж поделать, скачаем всё и обратим матрицу. Но такие случаи реже случаются, поэтому инженерия любит такое дело. Такие группы называют локальными группами, а дополнительные чанки у локальных групп -- локальные чанки, а дополнительные чанки для всей операции -- глобальные чанки.
На FAST'23 вышла статья в Google про широкие LRC коды. Это такие коды, которые делят на очень много частей, чтобы получить большую redundancy и потратить поменьше места. Холодный storage может делить данные на сотни частей и делать всего десятки дополнительных чанков получая redundancy в 6-7 c оверхедом на весь сторадж процентов в 10% (например, (96, 4, 5) делит на 96 частей, бьёт на 4 локальные группы с 5 глобальными чанками). Хоть и теория кодов очень хорошо изучена, на практике становится слегка сложно с балансом двух вещей
* Находить обратимые матрицы с свойствами локальных чанков
* Сделать операции локальных чанков достаточно простыми, скажем, обычный XOR ок, но что-то сложнее уже слегка путает инженеров. Простота также полезна для миграций -- можно ли как можно больше посчитанных чанков сохранить
Обычно LRC коды изучают как сделать операции над локальными чанками. Статья от Google показывает, что можно сделать слегка лучше -- смотреть на локальные группы как функцию не только от изначальных данных, но и от глобальных чанков, а можно также смотреть как на функцию от данных, глобальных и локальных. Так становится чуть проще размазать локальные чанки по всем данным. Определение и трюк слегка self-referential в том плане, что локальные чанки определяются через локальные, но статья считает некоторую математику, которая сходится.
Зачем это надо?
В статье можно увидеть только слегка лучше результаты по метриками redundancy, average cost of repair и тд. Цифры не ахти в сравнении и никакой супер революции этот LRC метод не привносит. Он рассказывает историю как продвинуть рисёрч слегка дальше по достаточно практичной теме как LRC коды.
Keep on pushing, статья рассказывает хорошую историю.
https://www.usenix.org/system/files/fast23-kadekodi.pdf
https://www.youtube.com/watch?v=pfnSYWEf5q4
Автор слегка увлёкся
Я тут много писал кода в последнее время, а потом снова увлёкся всякими эзотерическими штуками вроде статей. Что произошло:
1. Дотащил квадратичную проверку на strict weak ordering до LLVM. https://reviews.llvm.org/D150264. Дали аппрув, надеюсь, в ближайшие дни закоммитим. Фидбек был достаточно позитивный.
2. Соптимизировали снова всякие integer to ascii в abseil. На этот раз алгоритм очень похож на Paul Khuong's itoa. Мы покатили с более плохими микробенчмарками. Почему? Потому что предыдущий алгоритм брал табличку в 200 байт и получалось вот что:
а) Вы что-то делаете на сервере
б) Конвертите числа в строки, делаете доступ к памяти этой таблички
в) Делаете что-то ещё, повторяете
В итоге получается, что табличка может выйти из кеша или не попасть в кеш линии правильно (200 байт вообще занимает 4 кеш линии). В итоге будут промахи по L1, L2 кешам. Чтобы сделать бенчмарки более правдоподобными, я взял и каждые 1024 итерации вызывал инструкцию
Вообще это достаточно стандартные грабли -- если вы видите микробенчмарк, где сильно ускоряют через доступ к табличкам, то оно может работать хуже, чем если это подготовлено скалярно в коде.
Например, SIMDJSON очень долго имел проблему с парсингом маленьких json и в проде, если вы парсите jsonы не миллионами в секунду, то SIMDJSON не даст уж прям сверх преимуществ. Будьте аккуратны с алгоритмами, которые имеют статические данные, эти данные должны быть горячими.
3. Мои оптимизации хеш-таблицы в abseil для Arm уехали в Rust. https://github.com/rust-lang/hashbrown/pull/430. Мы списывались с автором hashbrown несколько раз и он подтвердил, что в Rust тоже стало на 3-5% быстрее микробенчмарки. Обсуждение длилось долго, пока мы в abseil не нашли способ ускорить. Трюк заключался в том, что можно было использовать 64 битный SIMD, а не 128 битный, как обычно думают про SSE.
Я тут много писал кода в последнее время, а потом снова увлёкся всякими эзотерическими штуками вроде статей. Что произошло:
1. Дотащил квадратичную проверку на strict weak ordering до LLVM. https://reviews.llvm.org/D150264. Дали аппрув, надеюсь, в ближайшие дни закоммитим. Фидбек был достаточно позитивный.
2. Соптимизировали снова всякие integer to ascii в abseil. На этот раз алгоритм очень похож на Paul Khuong's itoa. Мы покатили с более плохими микробенчмарками. Почему? Потому что предыдущий алгоритм брал табличку в 200 байт и получалось вот что:
а) Вы что-то делаете на сервере
б) Конвертите числа в строки, делаете доступ к памяти этой таблички
в) Делаете что-то ещё, повторяете
В итоге получается, что табличка может выйти из кеша или не попасть в кеш линии правильно (200 байт вообще занимает 4 кеш линии). В итоге будут промахи по L1, L2 кешам. Чтобы сделать бенчмарки более правдоподобными, я взял и каждые 1024 итерации вызывал инструкцию
CLFLUSH — Flush Cache Line. Текущие бенчмарки становились хуже.Вообще это достаточно стандартные грабли -- если вы видите микробенчмарк, где сильно ускоряют через доступ к табличкам, то оно может работать хуже, чем если это подготовлено скалярно в коде.
Например, SIMDJSON очень долго имел проблему с парсингом маленьких json и в проде, если вы парсите jsonы не миллионами в секунду, то SIMDJSON не даст уж прям сверх преимуществ. Будьте аккуратны с алгоритмами, которые имеют статические данные, эти данные должны быть горячими.
3. Мои оптимизации хеш-таблицы в abseil для Arm уехали в Rust. https://github.com/rust-lang/hashbrown/pull/430. Мы списывались с автором hashbrown несколько раз и он подтвердил, что в Rust тоже стало на 3-5% быстрее микробенчмарки. Обсуждение длилось долго, пока мы в abseil не нашли способ ускорить. Трюк заключался в том, что можно было использовать 64 битный SIMD, а не 128 битный, как обычно думают про SSE.
GitHub
Optimize absl::StrCat for integers · abseil/abseil-cpp@15d26cd
Previous implementation used a lookup table of 200 bytes which, if not in L1 cache, could cause memory stalls and consumes 3-4 cache lines. This is suboptimal in real world scenarious. We are going...
Спустя год паузы, я что-то написал на английском
https://danlark.org/2023/06/06/csinc-the-arm-instruction-you-didnt-know-you-wanted/
Даже вышли в топ 1 HN
https://news.ycombinator.com/item?id=36223283
https://danlark.org/2023/06/06/csinc-the-arm-instruction-you-didnt-know-you-wanted/
Даже вышли в топ 1 HN
https://news.ycombinator.com/item?id=36223283
Experimental chill
“csinc”, the AArch64 instruction you didn’t know you wanted
After a long time of not publishing anything and being passive about doing any writing in this blog, I am coming back for … however many articles I can. Today I want to talk about an underrat…
Сегодня прям праздник статей!
Я тут писал про оптимизации хеширования и сортировок с помощью Reinforcement Learning, Deepmind выложили статью, я в acknowledgements.
AlphaDev discovers faster sorting and hashing algorithms
https://www.deepmind.com/blog/alphadev-discovers-faster-sorting-algorithms
Faster sorting algorithms discovered using deep reinforcement learning
https://www.nature.com/articles/s41586-023-06004-9
Из очень хорошего, работать мне с ними понравилось. Из интересного -- результаты не самые революционные, но какие-то циклы серверов сэкономили.
HN: https://news.ycombinator.com/item?id=36228125
Я тут писал про оптимизации хеширования и сортировок с помощью Reinforcement Learning, Deepmind выложили статью, я в acknowledgements.
AlphaDev discovers faster sorting and hashing algorithms
https://www.deepmind.com/blog/alphadev-discovers-faster-sorting-algorithms
Faster sorting algorithms discovered using deep reinforcement learning
https://www.nature.com/articles/s41586-023-06004-9
Из очень хорошего, работать мне с ними понравилось. Из интересного -- результаты не самые революционные, но какие-то циклы серверов сэкономили.
HN: https://news.ycombinator.com/item?id=36228125
Deepmind
AlphaDev discovers faster sorting algorithms
In our paper published today in Nature, we introduce AlphaDev, an artificial intelligence (AI) system that uses reinforcement learning to discover enhanced computer science algorithms – surpassing those honed by scientists and engineers over decades.
Вчера взахлёб прочитал про Regex в Rust
https://blog.burntsushi.net/regex-internals/
Очень подробно про разбор выражений, проблем с юникодом, поиски подстрок, автоматы, simd ускорения и тд.
В моей практике Rust Regex до версии 1.6-1.7 был достаточно слабым решением в мире регулярок, но со временем стало получше.
Один из способов сделать хорошо описан в статье -- попробуйте какие-то большие куски имплементации вытащить как API. Можно как debug API как минимум. Имплементации и интерфейсы становятся намного чище после таких упражнений.
BurntSushi крутой чувак, очень упертый и кажется на дистанции это хорошо окупается. Всем советую прочитать статью от начала и до конца вдумчиво
https://blog.burntsushi.net/regex-internals/
Очень подробно про разбор выражений, проблем с юникодом, поиски подстрок, автоматы, simd ускорения и тд.
В моей практике Rust Regex до версии 1.6-1.7 был достаточно слабым решением в мире регулярок, но со временем стало получше.
Один из способов сделать хорошо описан в статье -- попробуйте какие-то большие куски имплементации вытащить как API. Можно как debug API как минимум. Имплементации и интерфейсы становятся намного чище после таких упражнений.
BurntSushi крутой чувак, очень упертый и кажется на дистанции это хорошо окупается. Всем советую прочитать статью от начала и до конца вдумчиво
blog.burntsushi.net
Regex engine internals as a library - Andrew Gallant's Blog
I blog mostly about my own programming projects.
1. Сначала ты пишешь о BurntSushi, а потом BurntSushi пишет тебе https://github.com/BurntSushi/memchr/pull/114. Статье указанной в PR почти год, а всё ещё раз в несколько месяцев меня кто-нибудь тегает.
2. Может, кто-то знает литературу по кешам, где eviction policies как-нибудь учатся по тому насколько тяжело будет бекенду отвечать на запрос промаха? Ситуация такая: иметь 90% попаданий лучше, чем 85% попаданий, но если 10% промахов нагибают бекенд в два раза больше, то кажется можно выбрать второй. Хотелось бы узнать, умеет ли что-то наука тут или есть ли какие-нибудь датасеты по тому как ведут себя кеши и их бекенды.
3. Поизучал я тут Iguana compression. Заявленные цифры действительно хорошо выглядят на реальных тестах. Сок Iguana заключается в том, что они очень много используют предпосчитанных масок вместе с инструкцией VPTERNLOGD. Эта инструкция расшифровывается как vector packed ternary logic. Фактически умеет делать тернарные операторы по битам 512 битных регистров -- по маске брать биты из одного или другого регистра, чего не было так быстро до AVX-2. Также ещё используются VPCOMPRESSD и тем самым хорошо умеет упаковывать биты как PEXT для скаляров. По формату им надо переводить base254 в base256 и обратно, что тоже делается табличками. В целом ощущение, что AVX-512 сейчас очень сильно растёт. Скажем, avx-512-sort и avx-512-partial-sort достаточно хорошо обгоняют мою библиотеку https://github.com/danlark1/miniselect -- хотя моя дала много буста тому же кликхаусу. Но пока всё для чисел, для более сложных компараторов не так всё просто.
Скептически долгое время относился к AVX-512, но кажется начинаем понимать как использовать для реальных задач. Интересные прорывы есть.
2. Может, кто-то знает литературу по кешам, где eviction policies как-нибудь учатся по тому насколько тяжело будет бекенду отвечать на запрос промаха? Ситуация такая: иметь 90% попаданий лучше, чем 85% попаданий, но если 10% промахов нагибают бекенд в два раза больше, то кажется можно выбрать второй. Хотелось бы узнать, умеет ли что-то наука тут или есть ли какие-нибудь датасеты по тому как ведут себя кеши и их бекенды.
3. Поизучал я тут Iguana compression. Заявленные цифры действительно хорошо выглядят на реальных тестах. Сок Iguana заключается в том, что они очень много используют предпосчитанных масок вместе с инструкцией VPTERNLOGD. Эта инструкция расшифровывается как vector packed ternary logic. Фактически умеет делать тернарные операторы по битам 512 битных регистров -- по маске брать биты из одного или другого регистра, чего не было так быстро до AVX-2. Также ещё используются VPCOMPRESSD и тем самым хорошо умеет упаковывать биты как PEXT для скаляров. По формату им надо переводить base254 в base256 и обратно, что тоже делается табличками. В целом ощущение, что AVX-512 сейчас очень сильно растёт. Скажем, avx-512-sort и avx-512-partial-sort достаточно хорошо обгоняют мою библиотеку https://github.com/danlark1/miniselect -- хотя моя дала много буста тому же кликхаусу. Но пока всё для чисел, для более сложных компараторов не так всё просто.
Скептически долгое время относился к AVX-512, но кажется начинаем понимать как использовать для реальных задач. Интересные прорывы есть.
GitHub
Add initial aarch64 neon support by redzic · Pull Request #114 · BurntSushi/memchr
This PR adds a NEON implementation of all mem{r}chr functions. This PR does not add NEON support for memmem, as deeper changes in the code are needed for the Vector trait for it to work efficiently...
1. https://www.intel.com/content/www/us/en/developer/articles/technical/advanced-performance-extensions-apx.html
Тут Intel выложили статью о том как они будут менять архитектуру ассемблера. Мне честно очень понравилось, будет выглядеть более похоже на Arm:
* Теперь будет 32 логических регистра. Тут уменьшатся в разы инструкции перекладываний со стека и на стек. Тем не менее, результаты могут быть не такими воодушевляюшими, так как современные процессоры имеют по 200-350 физических регистров (без учёта SIMD регистров) и алгоритмы переименования давным давно хорошо справляются со сложными задачами. Тем не менее, можно будет не использовать такие сложные алгоритмы
* push2, pop2: быстрее будем класть и брать со стека. Тут можно посмотреть на LDP/STP инструкции из Arm о которых я писал.
* 3 argument instructions. Инструкции будут иметь 3 аргумента, теперь на надо будет складывать память с регистром и мувать в другой регистр, можно сразу класть в другой. Тоже Arm так делает давным давно. Тут скорее всего лучше будет компиляторам такие инструкции производить.
* Conditional stores/loads -- это интересно, на Arm такого нет, я думаю хорошо взлетит во всяких compression/sorting
* Унификация SIMD. Intel тоже хочет быть похожим на SVE в Армах с непостоянной максимальной шириной максимального регистра. Поэтому вы можете спросить какая версия SIMD доступна и кодировать инструкции с помощью EVEX префикса. И даже не придётся компилировать 2 копии.
2. Тут нашли удивительную уязвимость с помощью фаззинга AMD процессоров https://lock.cmpxchg8b.com/zenbleed.html: более менее мои Ctrl+C Ctrl+V оно нашло за несколько секунд эксплуатации. Идея: давайте на разных процессорах запустим случайно сгенерированные программы, а также программы, где между инструкциями стоят lfence/mfence инструкции. Последние убивают instruction level parallelism, а значит и много оптимизаций вроде переименования регистров, speculative execution. После этого можно сверить все результаты. Если убрать все инструкции результат которых не определён, скажем, bsf (Bit Scan Forward при нуле не определён), то можно честно сравнивать выходы. Так и нашли этот баг. Удивительно крутая история.
3. Переписал Iguana Compression c Go на C++ (выложим код скорее всего). Получилось попробовать в более боевых условиях. Результаты хорошие, но не 2-3x заявленных в бенчмарках. По уровню сжатия версия без энтропийного кодирования чуть получше стандартного LZ4, а энтропийное где-то между ZSTD:2-3. В целом ничего не мешает увеличивать сжатие, так как алгоритм из LZ семейства и все алгоритмы сжатия из ZSTD можно перенести в Iguana. На Icelake писали, что где-то прибавка в 20-30%, а от себя скажу, что на Zen4 примерно всё ровно с ZSTD. AVX вещи у AMD всегда отстают на где-то 1 поколение от Intel. Догонят :)
Тут Intel выложили статью о том как они будут менять архитектуру ассемблера. Мне честно очень понравилось, будет выглядеть более похоже на Arm:
* Теперь будет 32 логических регистра. Тут уменьшатся в разы инструкции перекладываний со стека и на стек. Тем не менее, результаты могут быть не такими воодушевляюшими, так как современные процессоры имеют по 200-350 физических регистров (без учёта SIMD регистров) и алгоритмы переименования давным давно хорошо справляются со сложными задачами. Тем не менее, можно будет не использовать такие сложные алгоритмы
* push2, pop2: быстрее будем класть и брать со стека. Тут можно посмотреть на LDP/STP инструкции из Arm о которых я писал.
* 3 argument instructions. Инструкции будут иметь 3 аргумента, теперь на надо будет складывать память с регистром и мувать в другой регистр, можно сразу класть в другой. Тоже Arm так делает давным давно. Тут скорее всего лучше будет компиляторам такие инструкции производить.
* Conditional stores/loads -- это интересно, на Arm такого нет, я думаю хорошо взлетит во всяких compression/sorting
* Унификация SIMD. Intel тоже хочет быть похожим на SVE в Армах с непостоянной максимальной шириной максимального регистра. Поэтому вы можете спросить какая версия SIMD доступна и кодировать инструкции с помощью EVEX префикса. И даже не придётся компилировать 2 копии.
2. Тут нашли удивительную уязвимость с помощью фаззинга AMD процессоров https://lock.cmpxchg8b.com/zenbleed.html: более менее мои Ctrl+C Ctrl+V оно нашло за несколько секунд эксплуатации. Идея: давайте на разных процессорах запустим случайно сгенерированные программы, а также программы, где между инструкциями стоят lfence/mfence инструкции. Последние убивают instruction level parallelism, а значит и много оптимизаций вроде переименования регистров, speculative execution. После этого можно сверить все результаты. Если убрать все инструкции результат которых не определён, скажем, bsf (Bit Scan Forward при нуле не определён), то можно честно сравнивать выходы. Так и нашли этот баг. Удивительно крутая история.
3. Переписал Iguana Compression c Go на C++ (выложим код скорее всего). Получилось попробовать в более боевых условиях. Результаты хорошие, но не 2-3x заявленных в бенчмарках. По уровню сжатия версия без энтропийного кодирования чуть получше стандартного LZ4, а энтропийное где-то между ZSTD:2-3. В целом ничего не мешает увеличивать сжатие, так как алгоритм из LZ семейства и все алгоритмы сжатия из ZSTD можно перенести в Iguana. На Icelake писали, что где-то прибавка в 20-30%, а от себя скажу, что на Zen4 примерно всё ровно с ZSTD. AVX вещи у AMD всегда отстают на где-то 1 поколение от Intel. Догонят :)
Intel
Introducing Intel® Advanced Performance Extensions (Intel® APX)
These extensions expand the x86 instruction set with access to registers and features that improve performance.
Delayed decision
Хочется рассказать об оптимизациях, которые откладывают выигрыши до лучших времён. Их можно увидеть во многих системах, например, можно посчитать какую-то статистику или выучить, как правильно располагать код. Сложность таких оптимизаций в том, что они должны "продать" будущее. Какого-то единого формата как их находить особо нет, кроме как приближать данные о прошлом в настоящее. Если бы кто-то умел это делать лучше остальных идеально, у нас бы не было HFT и подобных компаний, занимающихся этим 24/7.
Такие вещи происходят от самых верхнеуровневых решений до самых низких. Приведём пример верхнеуровневого решения: кеширование.
Вы никогда не знаете, какой элемент лучше всего вытащить при переполнении кеша. Точнее знаете -- тот, который будет позже всех использован в будущем. Такой кеш называют идеальным кешом. Против него хорошо можно бенчмаркать прошлые данные, надеясь, что новые будут очень похожими. На фоне всяких идеальных кешей начали возникать теории и полным полно стратегий вытеснения -- LRU, WLRU, GDSF, ARC. Все со своими интересностями, а насколько мы может приблизиться к оптимальному результату. Оптимальный результат называют OPT, Belady's и тд, если вдруг хочется посмотреть. Что делать? В целом бенчмаркать, особо больше ничего, можно динамически что-то считать, можно машинное обучение пытаться применить. Единственное -- решение должно приниматься достаточно быстро, это же кеши. Плюс в том, что вы знаете верхнюю границу идеального результата. Старайтесь подумать, а что такое идеально тут.
Более локальные решения происходят даже на уровне аллокаторов. В TCMalloc при аллокации блока мы префетчим ещё 1 блок того же размера, потому что это лучше продаёт будущее несмотря на то, что ухудшает микробенчмарки. С одной стороны это достаточно просто и не так уж и дорого, но с другой, чтобы такое найти, надо было потратить годы и подробно смотреть на паттерны доступа.
Здесь особо нет правил, есть стратегии как можно находить такие моменты, одна из основных -- пробовать сотни различных конфигураций. Потратьте время, чтобы эти конфигурации было легко проверять. Удивительные результаты моей карьеры я не особо понимаю глубинно, лишь интуитивно методом проб и ошибок. Это что-то достаточно уникальное для software как мне кажется. Как слишком много всего, что работает.
Хочется рассказать об оптимизациях, которые откладывают выигрыши до лучших времён. Их можно увидеть во многих системах, например, можно посчитать какую-то статистику или выучить, как правильно располагать код. Сложность таких оптимизаций в том, что они должны "продать" будущее. Какого-то единого формата как их находить особо нет, кроме как приближать данные о прошлом в настоящее. Если бы кто-то умел это делать лучше остальных идеально, у нас бы не было HFT и подобных компаний, занимающихся этим 24/7.
Такие вещи происходят от самых верхнеуровневых решений до самых низких. Приведём пример верхнеуровневого решения: кеширование.
Вы никогда не знаете, какой элемент лучше всего вытащить при переполнении кеша. Точнее знаете -- тот, который будет позже всех использован в будущем. Такой кеш называют идеальным кешом. Против него хорошо можно бенчмаркать прошлые данные, надеясь, что новые будут очень похожими. На фоне всяких идеальных кешей начали возникать теории и полным полно стратегий вытеснения -- LRU, WLRU, GDSF, ARC. Все со своими интересностями, а насколько мы может приблизиться к оптимальному результату. Оптимальный результат называют OPT, Belady's и тд, если вдруг хочется посмотреть. Что делать? В целом бенчмаркать, особо больше ничего, можно динамически что-то считать, можно машинное обучение пытаться применить. Единственное -- решение должно приниматься достаточно быстро, это же кеши. Плюс в том, что вы знаете верхнюю границу идеального результата. Старайтесь подумать, а что такое идеально тут.
Более локальные решения происходят даже на уровне аллокаторов. В TCMalloc при аллокации блока мы префетчим ещё 1 блок того же размера, потому что это лучше продаёт будущее несмотря на то, что ухудшает микробенчмарки. С одной стороны это достаточно просто и не так уж и дорого, но с другой, чтобы такое найти, надо было потратить годы и подробно смотреть на паттерны доступа.
Здесь особо нет правил, есть стратегии как можно находить такие моменты, одна из основных -- пробовать сотни различных конфигураций. Потратьте время, чтобы эти конфигурации было легко проверять. Удивительные результаты моей карьеры я не особо понимаю глубинно, лишь интуитивно методом проб и ошибок. Это что-то достаточно уникальное для software как мне кажется. Как слишком много всего, что работает.
GitHub
tcmalloc/tcmalloc/internal/percpu_tcmalloc.h at 4c2f6e64e5345dc004023f2202ab358299634a0e · google/tcmalloc
Contribute to google/tcmalloc development by creating an account on GitHub.
Всё было сложно сесть и написать
Сейчас в солнечной калифорнии на саммите перформанса в гугле и было сложно сесть и написать что-то.
Unrelated to everything, хочется поговорить о уязвимостях как Inception и Zenbleed. Уязвимости интересные просто для чтения, но TL;DR мы сейчас можем читать где-то по 40-50 байт других процессов в секунду и хоть это не близко до того, чтобы эксплуатировать такие вещи на больших пространствах, забавно, что мы начинаем понимать как ломать branch predictors таким образом, чтобы красть какие-то данные.
Всё это имеет плохие последствия, если кто-то научится это эксплуатировать, также кажется, что ещё немного рисёрча и возможно уже не получится решить эту проблему всякими chicken bits в процессоре, а придётся делать настоящий pipeline flush в branch predictors. Всё это очень серьёзно скажется на перфе процессоров. Скорее всего 20-30% в среднем.
Моё мнение после общения с людьми из индустрии, что мы слишком далеко ушли в сложности в branch predictors и порой это сказывается на сложности дизайна. Самая большая проблема в этом, как ни странно, -- люди. Люди пишут код для него, плохо проверяют на безопасность, потому что рисёрч только сейчас начинает понимать, что мы написали.
Очень смешное решение предложил мой коллега -- запретить людям писать branch predictors на следующие несколько лет. С чем в целом, я согласен. Потому что формальные методы ещё не сильно выросли в этой науке, а кажется люди уже не справляются понять всеобщую картину.
Как с помощью software улучшить ситуацию? Собирать с profile guided optimizations, они хорошо унесут холодные блоки в даль от видимости. Проблема в том, что profile guided optimization (PGO) для людей как-то не сильно будет популярно, максимум так могут сделать компании. Тем не менее, такой подход простит несовершенство branch predictor, который, например, для Arm процессоров похуже, но становится неплохим, когда бинарный файл скомпилирован с PGO.
Надо как-то убирать людей из дизайна безопасносности в таких системах, люди должны только описывать, что значит безопасность и дальше использовать методы верификации. Я лично вижу в этом повторение истории с Pentium FDIV. Возможно в параллельной вселенной я бы этим позанимался.
Сейчас в солнечной калифорнии на саммите перформанса в гугле и было сложно сесть и написать что-то.
Unrelated to everything, хочется поговорить о уязвимостях как Inception и Zenbleed. Уязвимости интересные просто для чтения, но TL;DR мы сейчас можем читать где-то по 40-50 байт других процессов в секунду и хоть это не близко до того, чтобы эксплуатировать такие вещи на больших пространствах, забавно, что мы начинаем понимать как ломать branch predictors таким образом, чтобы красть какие-то данные.
Всё это имеет плохие последствия, если кто-то научится это эксплуатировать, также кажется, что ещё немного рисёрча и возможно уже не получится решить эту проблему всякими chicken bits в процессоре, а придётся делать настоящий pipeline flush в branch predictors. Всё это очень серьёзно скажется на перфе процессоров. Скорее всего 20-30% в среднем.
Моё мнение после общения с людьми из индустрии, что мы слишком далеко ушли в сложности в branch predictors и порой это сказывается на сложности дизайна. Самая большая проблема в этом, как ни странно, -- люди. Люди пишут код для него, плохо проверяют на безопасность, потому что рисёрч только сейчас начинает понимать, что мы написали.
Очень смешное решение предложил мой коллега -- запретить людям писать branch predictors на следующие несколько лет. С чем в целом, я согласен. Потому что формальные методы ещё не сильно выросли в этой науке, а кажется люди уже не справляются понять всеобщую картину.
Как с помощью software улучшить ситуацию? Собирать с profile guided optimizations, они хорошо унесут холодные блоки в даль от видимости. Проблема в том, что profile guided optimization (PGO) для людей как-то не сильно будет популярно, максимум так могут сделать компании. Тем не менее, такой подход простит несовершенство branch predictor, который, например, для Arm процессоров похуже, но становится неплохим, когда бинарный файл скомпилирован с PGO.
Надо как-то убирать людей из дизайна безопасносности в таких системах, люди должны только описывать, что значит безопасность и дальше использовать методы верификации. Я лично вижу в этом повторение истории с Pentium FDIV. Возможно в параллельной вселенной я бы этим позанимался.
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 стратегии.
Прошёл тут на 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 стратегии.
Sched
CppCon 2023: A Long Journey of Changing std::sort Imp...
View more about this event at CppCon 2023
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ов в конце концов, а.
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ов в конце концов, а.
GitHub
add aarch64 SIMD implementations of memchr and memmem (and other goodies) by BurntSushi · Pull Request #129 · BurntSushi/memchr
This PR doesn't just add aarch64-specific code, but it refactors pretty much everything about how the code is organized. There are big perf wins for aarch64 (see benchmark results below), and a...
Фаззили 5 лет и не нашли
Читал тут как в дереве хаффмана нашли out of bounds read в libwebp https://blog.isosceles.com/the-webp-0day/. Есть спекуляции, что этим пользуется Pegasus.
И снова вопрос, почему фаззинг не нашёл такой пример за 5 лет фаззинга?
Не похоже ли это на https://www.group-telegram.com/experimentalchill.com/238, когда мы в ZSTD нашли битые данные хотя фаззили достаточно несложный код 2 года?
Как я уже писал, в фаззинге нет магии, он просто пытается зайти во все строки кода, и совсем странные крайние случаи вряд ли найдёт. Всем советую прочитать анализ, а так если кто-то хочет написать сложный проект по тому, как находить такие баги чаще, то welcome. Это в самом деле a million dollar question, без преувеличения.
Читал тут как в дереве хаффмана нашли out of bounds read в libwebp https://blog.isosceles.com/the-webp-0day/. Есть спекуляции, что этим пользуется Pegasus.
И снова вопрос, почему фаззинг не нашёл такой пример за 5 лет фаззинга?
Не похоже ли это на https://www.group-telegram.com/experimentalchill.com/238, когда мы в ZSTD нашли битые данные хотя фаззили достаточно несложный код 2 года?
Как я уже писал, в фаззинге нет магии, он просто пытается зайти во все строки кода, и совсем странные крайние случаи вряд ли найдёт. Всем советую прочитать анализ, а так если кто-то хочет написать сложный проект по тому, как находить такие баги чаще, то welcome. Это в самом деле a million dollar question, без преувеличения.
Isosceles Blog
The WebP 0day
Early last week, Google released a new stable update for Chrome. The update included a single security fix that was reported by Apple's Security Engineering and Architecture (SEAR) team. The issue, CVE-2023-4863, was a heap buffer overflow in the WebP image…
Тут вышла 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 -- какая-то звезда современного рисёрча фаззинга, у него по несколько статей в год.
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 -- какая-то звезда современного рисёрча фаззинга, у него по несколько статей в год.
2023.splashcon.org
SPLASH 2023 - OOPSLA - SPLASH 2023
The ACM SIGPLAN International Conference on Systems, Programming, Languages and Applications: Software for Humanity (SPLASH) embraces all aspects of software construction and delivery, to make it the premier conference on the applications of programming languages…
Contest
Пописал тут контест от телеграма https://www.group-telegram.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.
Пописал тут контест от телеграма https://www.group-telegram.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.
Telegram
Telegram Contests
🏆 Telegram ML Competition
Prize fund: $40,000 – from which the 1st place winner will receive $15,000 if any submissions qualify for 1st place.
Deadline: 23:59 on October 15th (Dubai time)
Who can participate: Everyone
Results: October 29th, 2023
Telegram…
Prize fund: $40,000 – from which the 1st place winner will receive $15,000 if any submissions qualify for 1st place.
Deadline: 23:59 on October 15th (Dubai time)
Who can participate: Everyone
Results: October 29th, 2023
Telegram…
Давно я не писал, поэтому чуть больше в одном посте
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 . Запись будет где-то в январе :)
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 . Запись будет где-то в январе :)
Wikipedia
Задача о максимальном потоке
В теории оптимизации и теории графов, задача о максимальном потоке заключается в нахождении такого потока по транспортной сети, что сумма потоков из истока, или, что то же самое, сумма потоков в сток максимальна.