Experimental chill

Автор слегка увлёкся

Я тут много писал кода в последнее время, а потом снова увлёкся всякими эзотерическими штуками вроде статей. Что произошло:

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...

www.group-telegram.com/jp/experimentalchill.com/245

13.3K viewsedited  Jun 1, 2023 at 11:16

Автор слегка увлёкся

Я тут много писал кода в последнее время, а потом снова увлёкся всякими эзотерическими штуками вроде статей. Что произошло:

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.

BY Experimental chill