Этот пост я написал ещё в июле, но он мне показался скучным. Сегодня я его случайно рассказал паре людей и им понравилось, поэтому вот.
В распределённых приложениях и даже на обычных серверах невероятно сложно мерить перформанс mem* функций (например, memcpy для копирования памяти, memset для её выстановления, memmem для поиска, memcmp для сравнения) из-за того, что эти функции пытаются утилизировать всё железо, а у вас вряд ли прям всегда есть контроль над тем железом, где вы запускаете код. В итоге одни имплементации работают быстрее, другие медленнее.
В итоге все делают свои велосипеды, которые доходят до жуткого ассемблера:
Facebook Folly
Glibc вообще 13 имплементаций имеет для x86_64
Musl
И все реализации разные, кто-то хвост обрабатывает с захлёстом, кто-то просто по байту копирует в конце, кто-то хочет по выровненной памяти копировать, кто-то хочет мимо кэша, а кто-то как ядро Linux использует `rep movsb` (для совместимости со старыми процессорами). На стековерфлоу люди спорят, а что всё таки лучше. Горячая тема, а консенсуса всё ещё нет, слишком много факторов. Кто-то скажет, надо взять имплементации от Intel, кто-то скажет, что, мол, эта задача решена и зачем её решать.
Мой ответ на этот спор, на самом деле, будет таким, что надо бы сначала попрофилировать размеры этих mem* функций. Чем мы и занялись в Google.
В итоге оказалось, что mem* функции в 95%+ вызываются от супер мелких размеров (до 128), а до 1кб было 99%+ вызовов. На таких данных сложно разогнаться векторизацией и всякими супер-охеренными-AVX512 инструкциями. Поэтому мы написали свой memcpy для не очень больших данных, чтобы оно хорошо работало, выиграли свои 0.x-1.y% циклов и успокоились.
А паре людей всё ещё не давала спать идея о том, что хватит писать одну имлементацию на всех и пора бы уже для всех приложений заниматься нормальными оптимизациями. Для супер низкоуровневых вещей пора бы уже уметь оптимизировать прям под железо.
Что мы сделали:
Мы взяли все известные стратегии для memcpy/memset и остальных функций.
Собрали их в единый и удобный для чтения код, а не ужас glibc, musl и других libc библиотек
Начали использовать AutoFDO (Feedback Driven Optimizations) для того, чтобы собирать распределение, скорость работы разных memcpy на разном железе
При компиляции с профилем выбираем лучшие имплементации в паре (тип процессора, распределение)
Используем их для железа, на котором запускается приложение
Итог:
Мы выиграли 1% всего железа в Google. Это очень много :)
Улучшили на 0.65%+-0.1% пропускную способность нижней поисковой компоненты
Раскатили это на топ X самых прожорливых бинарей в Google (FDO требует настройки)
Мы начали делать свою libc в LLVM, потому что glibc имеет LGPL лицензию, которая не позволяет так оптимизировать, а musl не работает адекватно с санитайзерами. В итоге будет статически линкованная библиотека C, где работают санитайзеры и не имеет проблем с лицензией.
Порадовались, написали статью. Конец.
Из примечательного из статьи: да, мы не используем AVX на серверах из-за downclocking. Ну и мы прекратили спор о том, какая имплементация лучше — пусть машины сами решают, что для них быстрее.
[1] Статья про automemcpy
[2] LLVM libc
[3] Бенчмарки
[4] Статья про AutoFDO
В распределённых приложениях и даже на обычных серверах невероятно сложно мерить перформанс mem* функций (например, memcpy для копирования памяти, memset для её выстановления, memmem для поиска, memcmp для сравнения) из-за того, что эти функции пытаются утилизировать всё железо, а у вас вряд ли прям всегда есть контроль над тем железом, где вы запускаете код. В итоге одни имплементации работают быстрее, другие медленнее.
В итоге все делают свои велосипеды, которые доходят до жуткого ассемблера:
Facebook Folly
Glibc вообще 13 имплементаций имеет для x86_64
Musl
И все реализации разные, кто-то хвост обрабатывает с захлёстом, кто-то просто по байту копирует в конце, кто-то хочет по выровненной памяти копировать, кто-то хочет мимо кэша, а кто-то как ядро Linux использует `rep movsb` (для совместимости со старыми процессорами). На стековерфлоу люди спорят, а что всё таки лучше. Горячая тема, а консенсуса всё ещё нет, слишком много факторов. Кто-то скажет, надо взять имплементации от Intel, кто-то скажет, что, мол, эта задача решена и зачем её решать.
Мой ответ на этот спор, на самом деле, будет таким, что надо бы сначала попрофилировать размеры этих mem* функций. Чем мы и занялись в Google.
В итоге оказалось, что mem* функции в 95%+ вызываются от супер мелких размеров (до 128), а до 1кб было 99%+ вызовов. На таких данных сложно разогнаться векторизацией и всякими супер-охеренными-AVX512 инструкциями. Поэтому мы написали свой memcpy для не очень больших данных, чтобы оно хорошо работало, выиграли свои 0.x-1.y% циклов и успокоились.
А паре людей всё ещё не давала спать идея о том, что хватит писать одну имлементацию на всех и пора бы уже для всех приложений заниматься нормальными оптимизациями. Для супер низкоуровневых вещей пора бы уже уметь оптимизировать прям под железо.
Что мы сделали:
Мы взяли все известные стратегии для memcpy/memset и остальных функций.
Собрали их в единый и удобный для чтения код, а не ужас glibc, musl и других libc библиотек
Начали использовать AutoFDO (Feedback Driven Optimizations) для того, чтобы собирать распределение, скорость работы разных memcpy на разном железе
При компиляции с профилем выбираем лучшие имплементации в паре (тип процессора, распределение)
Используем их для железа, на котором запускается приложение
Итог:
Мы выиграли 1% всего железа в Google. Это очень много :)
Улучшили на 0.65%+-0.1% пропускную способность нижней поисковой компоненты
Раскатили это на топ X самых прожорливых бинарей в Google (FDO требует настройки)
Мы начали делать свою libc в LLVM, потому что glibc имеет LGPL лицензию, которая не позволяет так оптимизировать, а musl не работает адекватно с санитайзерами. В итоге будет статически линкованная библиотека C, где работают санитайзеры и не имеет проблем с лицензией.
Порадовались, написали статью. Конец.
Из примечательного из статьи: да, мы не используем AVX на серверах из-за downclocking. Ну и мы прекратили спор о том, какая имплементация лучше — пусть машины сами решают, что для них быстрее.
[1] Статья про automemcpy
[2] LLVM libc
[3] Бенчмарки
[4] Статья про AutoFDO