Забавный рисёрч вышёл от нас про Code Efficiency
"Learning to Improve Code Efficiency"
https://arxiv.org/pdf/2208.05297.pdf
Если написать очень много кода одной и той же задачи разными людьми (скажем, на LeetCode или как в статье, на Google Code Jam), можно встретить много разных подходов: кто-то напишет цикл, а кто-то вызовет функцию стандартной библиотеки. Всякие такие оптимизации и хинты это всегда знание, которое собирается кумулятивно. Такие вещи обычно делают через AST matchers и статическим анализом, но всё не написать, а обучить людей более быстрым (которые часто и более правильные) конструкциям хочется.
Предложили обучить VQ-VAE (Vector-Quantized Variational Autoencoders) модельку, которая пытается найти как подсказать человеку на какую конструкцию стоит заменить тот или иной участок не самого быстрого кода.
Результаты, конечно, игрушечные, но интересные. Так можно в целом обучать людей конструкциям языка на задачах LeetCode или competitive programming, потому что кто-то да умный найдётся как написать красиво и элегантно (или не очень, как уж пойдёт). Перформанс и корректность можно померить в отличие от красоты кода. Хорошо, что эти вещи иногда коррелируют.
В статье вот пример с тем, что есть решение посортировать -> выдать ответ или положить в кучу, но зато выйти из цикла пораньше. В реальности я бы выбрал второе, если мне был бы важен перформанс или первое, если бы я хотел элегантности. Как правильнее -- непонятно, зато понятно, как улучшить решение в С раз.
Просто красиво, как использовать -- пока непонятно
"Learning to Improve Code Efficiency"
https://arxiv.org/pdf/2208.05297.pdf
Если написать очень много кода одной и той же задачи разными людьми (скажем, на LeetCode или как в статье, на Google Code Jam), можно встретить много разных подходов: кто-то напишет цикл, а кто-то вызовет функцию стандартной библиотеки. Всякие такие оптимизации и хинты это всегда знание, которое собирается кумулятивно. Такие вещи обычно делают через AST matchers и статическим анализом, но всё не написать, а обучить людей более быстрым (которые часто и более правильные) конструкциям хочется.
Предложили обучить VQ-VAE (Vector-Quantized Variational Autoencoders) модельку, которая пытается найти как подсказать человеку на какую конструкцию стоит заменить тот или иной участок не самого быстрого кода.
Результаты, конечно, игрушечные, но интересные. Так можно в целом обучать людей конструкциям языка на задачах LeetCode или competitive programming, потому что кто-то да умный найдётся как написать красиво и элегантно (или не очень, как уж пойдёт). Перформанс и корректность можно померить в отличие от красоты кода. Хорошо, что эти вещи иногда коррелируют.
В статье вот пример с тем, что есть решение посортировать -> выдать ответ или положить в кучу, но зато выйти из цикла пораньше. В реальности я бы выбрал второе, если мне был бы важен перформанс или первое, если бы я хотел элегантности. Как правильнее -- непонятно, зато понятно, как улучшить решение в С раз.
Просто красиво, как использовать -- пока непонятно
https://www.usenix.org/system/files/osdi22-huang-lexiang.pdf
Я как-то тут писал про метастабильные падения с конференции HotOS. Как и ожидалось, академия тоже играет в индустрию, и по старой доброй традиции, если статья появляется на HotOS, то её решение или расширенная версия на OSDI. Одна статья на 2 конференции, как удобно!
Напомню, что про метастабильные падения можно думать как о падениях, из которых тяжело выйти откатив изменение -- вы что-то поменяли, откатываете, а проблема всё ещё осталась, так бывает из-за проблем retry, сброса кеша, который не может набраться, каскадные падения, невозможность обработать спайки ошибок (jitter).
В новой статье из интересного добавили группировку по реальным падениям в Cloud провайдерах, опыту твиттера и тд. Например, примерно половина из всех инцидентов возникла из-за плохой политики перезапросов, 35% из-за спайка ошибок. В статье хорошо разобраны тригеры таких состояний, которые можно применять как эвристики для их детекции и понижения нагрузки.
Хочется рассказать подробнее о _деградации_ (в статье её нет, в старом посте я её упомянул):
Что такое деградация? Деградация это достаточно редкий, но полезный трюк для того, чтобы сделать вашу систему неубиваемой, но для этого надо написать немного кода и иметь одно свойство -- возможность неполно читать данные. Иногда её ставят в ряд с congestion протоколами в сети, но редко тема выходит в сервисы.
В поисковых системах, в рекомендательных системах, в мониторинг системах, в не strongly consistent файловых системах вы можете придумать такие свойства
1. Искать по части поискового шарда
2. Задерживать показ viral постов/твитов/ютуб видосов или варьировать количество кластеров в поиске ближайших
3. Читать чуть-чуть старые данные, скажем, не для real time аналитики или mostly read only fs, a.k.a. stale reads
4. Увеличивать размеры временных корзин для сбора аналитики в мониторинг системах
Коэффициенты частичной обработки можно варьировать от очень консервативных чисел до очень неконсервативных. Можно сделать от 0 до 1 такой коэффициент.
Когда машина/система начинает испытывать трудности, коэффициент деградации можно понижать до нуля (в самом простом случае, выбирать бинпоиском число, более умно использовать всякие экспоненциальные формулы из congestion протоколов (об этом как-нибудь в другой раз)) и если есть много перезапросов или jitter из ошибок, то деградация поможет:
1. Плавно вытащить сервисы из типичных проблем перезапросов
2. Выиграть время для реагирования
3. Не сделать сильно плохо пользователям, искать по 80% поискового шарда не так уж и плохо
4. В случае критических глобальных проблем с датацентрами, мисконфигурацией, переживать неожиданное увеличение нагрузки намного легче
Другой пример, который мне пришёл на ум после прочтения статьи это time to live в файловых системах: хочется давать возможность людям ставить time to live на папки, но иногда бывает так, что кто-то решит удалить 3 миллиарда файлов и происходит следующее
1. Начинаем удалять папку
2. Не справляемся за сутки
3. Другие пользователи жалуются, что их файлы не удаляются
В итоге 3 недели удаляем 3 миллиарда файлов, другие файлы не удаляем. Чтобы сделать какой-то честный garbage collection, надо хитрить на клиентах (не показывать им файлы) или удалять в зависимости от редкости -- люди готовы подождать 3 недели для удаления 3 миллиардов файлов, но 3 недели для одного не очень. Тонкий баланс метастабильности как UX. И всё таки данные удалять надо, privacy, все дела.
Приятная для чтения статья, много всяких примеров можно придумать в голове
Я как-то тут писал про метастабильные падения с конференции HotOS. Как и ожидалось, академия тоже играет в индустрию, и по старой доброй традиции, если статья появляется на HotOS, то её решение или расширенная версия на OSDI. Одна статья на 2 конференции, как удобно!
Напомню, что про метастабильные падения можно думать как о падениях, из которых тяжело выйти откатив изменение -- вы что-то поменяли, откатываете, а проблема всё ещё осталась, так бывает из-за проблем retry, сброса кеша, который не может набраться, каскадные падения, невозможность обработать спайки ошибок (jitter).
В новой статье из интересного добавили группировку по реальным падениям в Cloud провайдерах, опыту твиттера и тд. Например, примерно половина из всех инцидентов возникла из-за плохой политики перезапросов, 35% из-за спайка ошибок. В статье хорошо разобраны тригеры таких состояний, которые можно применять как эвристики для их детекции и понижения нагрузки.
Хочется рассказать подробнее о _деградации_ (в статье её нет, в старом посте я её упомянул):
Что такое деградация? Деградация это достаточно редкий, но полезный трюк для того, чтобы сделать вашу систему неубиваемой, но для этого надо написать немного кода и иметь одно свойство -- возможность неполно читать данные. Иногда её ставят в ряд с congestion протоколами в сети, но редко тема выходит в сервисы.
В поисковых системах, в рекомендательных системах, в мониторинг системах, в не strongly consistent файловых системах вы можете придумать такие свойства
1. Искать по части поискового шарда
2. Задерживать показ viral постов/твитов/ютуб видосов или варьировать количество кластеров в поиске ближайших
3. Читать чуть-чуть старые данные, скажем, не для real time аналитики или mostly read only fs, a.k.a. stale reads
4. Увеличивать размеры временных корзин для сбора аналитики в мониторинг системах
Коэффициенты частичной обработки можно варьировать от очень консервативных чисел до очень неконсервативных. Можно сделать от 0 до 1 такой коэффициент.
Когда машина/система начинает испытывать трудности, коэффициент деградации можно понижать до нуля (в самом простом случае, выбирать бинпоиском число, более умно использовать всякие экспоненциальные формулы из congestion протоколов (об этом как-нибудь в другой раз)) и если есть много перезапросов или jitter из ошибок, то деградация поможет:
1. Плавно вытащить сервисы из типичных проблем перезапросов
2. Выиграть время для реагирования
3. Не сделать сильно плохо пользователям, искать по 80% поискового шарда не так уж и плохо
4. В случае критических глобальных проблем с датацентрами, мисконфигурацией, переживать неожиданное увеличение нагрузки намного легче
Другой пример, который мне пришёл на ум после прочтения статьи это time to live в файловых системах: хочется давать возможность людям ставить time to live на папки, но иногда бывает так, что кто-то решит удалить 3 миллиарда файлов и происходит следующее
1. Начинаем удалять папку
2. Не справляемся за сутки
3. Другие пользователи жалуются, что их файлы не удаляются
В итоге 3 недели удаляем 3 миллиарда файлов, другие файлы не удаляем. Чтобы сделать какой-то честный garbage collection, надо хитрить на клиентах (не показывать им файлы) или удалять в зависимости от редкости -- люди готовы подождать 3 недели для удаления 3 миллиардов файлов, но 3 недели для одного не очень. Тонкий баланс метастабильности как UX. И всё таки данные удалять надо, privacy, все дела.
Приятная для чтения статья, много всяких примеров можно придумать в голове
Рубрика: интересные компиляторы
Поговорим просто про сложение. На x86 сложение имеет 2 операнда
Когда вы складываете несколько чисел подряд (скажем, для простоты 4 числа x1 = x1 + x2 + x3 + x4), то это делается в 3 инструкции
Такие оптимизации называются tree reduction, чтобы первые две операции исполнялись параллельно в процессоре, так как у них нет зависимости. В итоге такие операции занимают 2 цикла вместо 3.
К сожалению, так как в x86 сложение принимает только 2 операнда, так сделать не получится, либо надо складывать числа как x1 += x2, x3, x4 (цепочка из 3), либо складывать x3 += x4, что не всегда хочется или можно (скажем, менять x2, x3, x4 не хочется). Есть инструкция lea, но на x86 не всегда хватает регистров, чтобы сделать это быстро, поэтому в целом tree reduction не очень применяется.
Так вот, так как clang слишком сильно и годами оптимизировался Долиной под x86, такие сложения редко оптимизировались в целом и оставались просто через add.
И да, clang как-то слишком топорно оптимизирует сложения 4 чисел на Arm, где у нас 16 регистров вообще
То есть цепочка из 3, когда увидел, прям ощутились оптимизации, на которые забили, когда смотрели на код x86. И такие вещи забавно прослеживаются, когда смотришь декомпиляцию clang под Arm -- много оптимизаций или их отсутствие как на платформе x86.
GCC, кстати получше это делает
Интересная заключительная мораль в том, что мы даже сложения чисел не можем адекватно соптимизировать в 2022. Ну бывает, что ж
Поиграться: https://gcc.godbolt.org/z/1nozoz1M4
Поговорим просто про сложение. На x86 сложение имеет 2 операнда
addq %reg1, %reg2, что означает reg2 += reg1. На ARM сложение имеет 3 операнда add x3, x2, x1, что означает x3 = x1 + x2.Когда вы складываете несколько чисел подряд (скажем, для простоты 4 числа x1 = x1 + x2 + x3 + x4), то это делается в 3 инструкции
x5 = x1 + x2
x6 = x3 + x4
x1 = x5 + x6
Такие оптимизации называются tree reduction, чтобы первые две операции исполнялись параллельно в процессоре, так как у них нет зависимости. В итоге такие операции занимают 2 цикла вместо 3.
К сожалению, так как в x86 сложение принимает только 2 операнда, так сделать не получится, либо надо складывать числа как x1 += x2, x3, x4 (цепочка из 3), либо складывать x3 += x4, что не всегда хочется или можно (скажем, менять x2, x3, x4 не хочется). Есть инструкция lea, но на x86 не всегда хватает регистров, чтобы сделать это быстро, поэтому в целом tree reduction не очень применяется.
Так вот, так как clang слишком сильно и годами оптимизировался Долиной под x86, такие сложения редко оптимизировались в целом и оставались просто через add.
И да, clang как-то слишком топорно оптимизирует сложения 4 чисел на Arm, где у нас 16 регистров вообще
add x13, x13, x9
add x13, x13, x10
add x13, x13, x12
То есть цепочка из 3, когда увидел, прям ощутились оптимизации, на которые забили, когда смотрели на код x86. И такие вещи забавно прослеживаются, когда смотришь декомпиляцию clang под Arm -- много оптимизаций или их отсутствие как на платформе x86.
GCC, кстати получше это делает
add x1, x4, x1
add x6, x3, x2
add x1, x6, x1
Интересная заключительная мораль в том, что мы даже сложения чисел не можем адекватно соптимизировать в 2022. Ну бывает, что ж
Поиграться: https://gcc.godbolt.org/z/1nozoz1M4
gcc.godbolt.org
Compiler Explorer - C++
// We're going to do these two things in almost every function. Prevents
// compiler from optimizing away.
#define DECLARE5 \
uint64_t data1, data2, data3, data4, data5;
#define FAKE_DEP5 \
asm volatile("" \
: "+r" (data1), "+r" (data2), "+r"…
// compiler from optimizing away.
#define DECLARE5 \
uint64_t data1, data2, data3, data4, data5;
#define FAKE_DEP5 \
asm volatile("" \
: "+r" (data1), "+r" (data2), "+r"…
Experimental chill
На дворе 2022 год Мы находим оптимизации в mem*/str* функциях на мажорных платформах в 20%, которые были доступны как лет 10 Да, это патч в glibc. В целом история такая: на x86 достаточно легко переходить из векторного кода в скалярный -- если есть вектор…
А вот и блог в армах про SSEшные PMOVMSKB
https://community.arm.com/arm-community-blogs/b/infrastructure-solutions-blog/posts/porting-x86-vector-bitmask-optimizations-to-arm-neon
HN: https://news.ycombinator.com/item?id=32642768
https://community.arm.com/arm-community-blogs/b/infrastructure-solutions-blog/posts/porting-x86-vector-bitmask-optimizations-to-arm-neon
HN: https://news.ycombinator.com/item?id=32642768
Arm
Porting x86 vector bitmask optimizations to Arm NEON
Arm NEON is different from x86 SSE in many ways. In this blog, Google's engineer Danila Kutenin shows how to translate popular x86 vector bitmask optimizations to Arm while retaining high performance, resulting in significant improvements across various major…
Для выполнения работы (goodput от good and throughput/output) на CPU программам необходим доступ к RAM. Скорость, с которой программы могут передавать данные в/из оперативной памяти, не растет так быстро, как производительность процессоров, получающие новые фичи на каждое ядро и большее количество ядер.
В 95-2000 все много рассказывали про Memory Wall, что мол, DRAM не будет расти так быстро. Это уже реальность, не растёт.
В целом доступ к RAM остался в около 100ns, даже если вы меняете один процессор на другой, вы получаете меньше преимуществ, если вы постоянно промахиваетесь по кешам. L1/L2/L3 растут, да, но и там есть предел, и вряд ли они будут больше сотни мегабайт. Поэтому когда вы оптимизируете программу, очень полезно посмотреть на так называемые LLC (Last Level Cache) Misses.
Советы тут какие-то дурацкие, мол
1. Никогда не используйте структуру linked list, это промах по памяти на каждую итерацию
2. Не используйте бакетные хеш таблицы, они очень плохи, так как промахиваются постоянно. Используйте хэш таблицы с открытой адресацией
3. Лишний раз не копируйте объекты и тут языки вроде C/C++/Rust выигрывают, потому что там явно указываешь, что копировать, а что нет
4. Делаете по возможности структуры более компактными
Если будете итерироваться и использовать id в векторе/слайсе чаще, процессор хуже будет класть данные в кеши, по возможности, когда это очень важно, делаете два отдельных вектора id и name.
5. Даже какие-то обычные операции в роде сложения матриц нельзя делать как вектор векторов/массив массивов, правильно хранить всё в одном куске памяти и логически разделять строки
6. Если объекты логически большие, структурные как json или protobuf, создавайте арены/memory pool, когда вы кладёте много объектов на один и тот же кусок памяти. Самый простой пример -- вектор строк, если строки разбросаны в памяти, то даже банальные операции типа сортировки будут в разы медленнее не потому, что строки надо больше сравнивать, а потому, что всегда есть плата пойти в память. Поэтому строки со Small String Optimization и пишут в библиотеках, плюс они выигрывают на скейле.
7. Если вы можете утилизировать память, делать более предсказуемой доступы, то вы будете выигрывать у других приложений. Пример -- ClickHouse хорошо понял историю поколоночного формата, потому что памяти так удобнее: утилизация всего сервера в итоге растёт. Библиотеки вроде ZSTD просто напичканы software prefetches, а процессоры Intel/AMD/ARM делают отдельные инструкции для копирования памяти произвольного размера.
8. Обрабатывайте меньше данных в памяти. Сжатие как минимум, как максимум -- слежка сколько вы тратите на пользователя/entity данных. Я находил на своём опыте какие-то огромные пробелы в том, зачем мы храним столько данных. Хоть и бизнесы скейлятся, как правило начинается бардак в схемах/логах. Детектить такие вещи тяжело. SQL со своими селективными предикатами здесь побеждает обычные языки программирования и MapReduce, в последнем надо писать код -- ставить трекеры на форматы в компилируемых языках тяжело.
Развитие SIMD, больше правильных структурированных форматов, подстройка парсеров под данные, самокорректирующиеся под data оптимизации вроде JIT будут доминировать в ближайшее время развитие data proc. Истории с прорывами происходят вроде SIMDJSON и тд, но никакого систематичного решения пока не видно, эта область имеет шансы сильно развиться или умереть, принимая, что это в какой-то степени предел и надо думать в других направлениях типа GPU/TPU/Quantum/FPGA/etc.
В Google мы репортим среднюю утилизацию сервера в 60% и проблемы с памятью одни из самых противных -- данных просто тьма, решения вроде использовать flat_hash_map, а не unordered_map помогают лишь держать это число на плаву. Тот, кто поймёт эту историю лучше всего, будет платить за датацентры меньше всего денег.
В эпоху рецессии кажется это может быть ещё более важно. Постараюсь сделать серию из постов про то, как увеличивать полезность при помощи уменьшения процессинга памяти. Тут много нетривиальных компромиссов.
В 95-2000 все много рассказывали про Memory Wall, что мол, DRAM не будет расти так быстро. Это уже реальность, не растёт.
В целом доступ к RAM остался в около 100ns, даже если вы меняете один процессор на другой, вы получаете меньше преимуществ, если вы постоянно промахиваетесь по кешам. L1/L2/L3 растут, да, но и там есть предел, и вряд ли они будут больше сотни мегабайт. Поэтому когда вы оптимизируете программу, очень полезно посмотреть на так называемые LLC (Last Level Cache) Misses.
Советы тут какие-то дурацкие, мол
1. Никогда не используйте структуру linked list, это промах по памяти на каждую итерацию
2. Не используйте бакетные хеш таблицы, они очень плохи, так как промахиваются постоянно. Используйте хэш таблицы с открытой адресацией
3. Лишний раз не копируйте объекты и тут языки вроде C/C++/Rust выигрывают, потому что там явно указываешь, что копировать, а что нет
4. Делаете по возможности структуры более компактными
struct Data {
int id;
std::string name;
};
Если будете итерироваться и использовать id в векторе/слайсе чаще, процессор хуже будет класть данные в кеши, по возможности, когда это очень важно, делаете два отдельных вектора id и name.
5. Даже какие-то обычные операции в роде сложения матриц нельзя делать как вектор векторов/массив массивов, правильно хранить всё в одном куске памяти и логически разделять строки
6. Если объекты логически большие, структурные как json или protobuf, создавайте арены/memory pool, когда вы кладёте много объектов на один и тот же кусок памяти. Самый простой пример -- вектор строк, если строки разбросаны в памяти, то даже банальные операции типа сортировки будут в разы медленнее не потому, что строки надо больше сравнивать, а потому, что всегда есть плата пойти в память. Поэтому строки со Small String Optimization и пишут в библиотеках, плюс они выигрывают на скейле.
7. Если вы можете утилизировать память, делать более предсказуемой доступы, то вы будете выигрывать у других приложений. Пример -- ClickHouse хорошо понял историю поколоночного формата, потому что памяти так удобнее: утилизация всего сервера в итоге растёт. Библиотеки вроде ZSTD просто напичканы software prefetches, а процессоры Intel/AMD/ARM делают отдельные инструкции для копирования памяти произвольного размера.
8. Обрабатывайте меньше данных в памяти. Сжатие как минимум, как максимум -- слежка сколько вы тратите на пользователя/entity данных. Я находил на своём опыте какие-то огромные пробелы в том, зачем мы храним столько данных. Хоть и бизнесы скейлятся, как правило начинается бардак в схемах/логах. Детектить такие вещи тяжело. SQL со своими селективными предикатами здесь побеждает обычные языки программирования и MapReduce, в последнем надо писать код -- ставить трекеры на форматы в компилируемых языках тяжело.
Развитие SIMD, больше правильных структурированных форматов, подстройка парсеров под данные, самокорректирующиеся под data оптимизации вроде JIT будут доминировать в ближайшее время развитие data proc. Истории с прорывами происходят вроде SIMDJSON и тд, но никакого систематичного решения пока не видно, эта область имеет шансы сильно развиться или умереть, принимая, что это в какой-то степени предел и надо думать в других направлениях типа GPU/TPU/Quantum/FPGA/etc.
В Google мы репортим среднюю утилизацию сервера в 60% и проблемы с памятью одни из самых противных -- данных просто тьма, решения вроде использовать flat_hash_map, а не unordered_map помогают лишь держать это число на плаву. Тот, кто поймёт эту историю лучше всего, будет платить за датацентры меньше всего денег.
В эпоху рецессии кажется это может быть ещё более важно. Постараюсь сделать серию из постов про то, как увеличивать полезность при помощи уменьшения процессинга памяти. Тут много нетривиальных компромиссов.
research.google
Borg: the Next Generation
1. Выложили Silifuzz https://github.com/google/silifuzz/
Теперь у нас есть open source тулы как фаззить процессоры. Одно дело у нас есть свой зоопарк железа, другое -- может пригодиться многим другим. Напомню коротко, что идея брать корпусы у эмуляторов и, о вау, это уже достаточно, чтобы находить баги в процессорах. Новость получила слишком мало охвата. Пока x86, над Arm'ами работают коллеги
2. У меня полностью отменилась поездка в США и вообще чёрт знает, когда я встречусь со своей командой. Google какие-то решения сверху выдал непонятные, посмотрим, куда это приведёт, но зато у меня есть целая неделя вне саммита. Попишу кода.
3. На процессорах Arm оказалось, что парсить протобуфы можно даже быстрее, чем на x86. Всё это благодаря иструкциям ubfx (bit field extract) -- оно может брать любое количество бит внутри регистра и делать из этого число. Так как у протобуфов каждый из байтов имеет 7 бит со значением, получается быстрее. Мы выложили эти оптимизации и теперь пост выше про tree reduction имеет больше смысла -- советую почитать описание и код. Мы замучились заставить компилятор генерировать код, нужный нам
Ещё один check, что софтом на Arm'ах занимались как-то посредственно.
4. У меня есть идея написать гайд как у Agner Fog про серверные и клиентские процессоры Arm. У маэстро всё про x86, многие пользуются им, а про Arm почти ничего нет.
5. Я не очень понимаю, как софт подвержен энтропии. Я понимаю, что всё в мире ей подвержено, но недавно мы нашли в своём проекте баг, который kept me up at night, к сожалению сломались транзакционные гарантии. Баг был в коде как минимум 7 лет. Мы его починили, но оценить, сколько пользователей просто не заметило потерянных данных непонятно как. Остаётся только разводить руки, но осознание, что никакое тестирование его не поймало просто ужасное. И что поймать такие вещи в проде худшее, что может случиться с инфраструктурой. Да и воспроизвели мы его только в проде. И починили, смотря на метрику в проде. Локально воспроизвести не получается никак.
6. Блог на community.arm получил достаточно много референсов у разработчиков (в том числе Lemire), делиться вещами надо, кажется я рассказал о том, что болело у разработчиков библиотек (раз, два, три, четыре, пять).
Я хочу стримить, как я пишу код. У меня возникает откуда-то странное желание это делать. Насмотрелся на George Hotz, наверное.
Чёт сумбурно, но продуктивность хлещет, начинается мой любимый сезон года, осень, зима, когда можно уютно что-то делать
Теперь у нас есть open source тулы как фаззить процессоры. Одно дело у нас есть свой зоопарк железа, другое -- может пригодиться многим другим. Напомню коротко, что идея брать корпусы у эмуляторов и, о вау, это уже достаточно, чтобы находить баги в процессорах. Новость получила слишком мало охвата. Пока x86, над Arm'ами работают коллеги
2. У меня полностью отменилась поездка в США и вообще чёрт знает, когда я встречусь со своей командой. Google какие-то решения сверху выдал непонятные, посмотрим, куда это приведёт, но зато у меня есть целая неделя вне саммита. Попишу кода.
3. На процессорах Arm оказалось, что парсить протобуфы можно даже быстрее, чем на x86. Всё это благодаря иструкциям ubfx (bit field extract) -- оно может брать любое количество бит внутри регистра и делать из этого число. Так как у протобуфов каждый из байтов имеет 7 бит со значением, получается быстрее. Мы выложили эти оптимизации и теперь пост выше про tree reduction имеет больше смысла -- советую почитать описание и код. Мы замучились заставить компилятор генерировать код, нужный нам
Ещё один check, что софтом на Arm'ах занимались как-то посредственно.
4. У меня есть идея написать гайд как у Agner Fog про серверные и клиентские процессоры Arm. У маэстро всё про x86, многие пользуются им, а про Arm почти ничего нет.
5. Я не очень понимаю, как софт подвержен энтропии. Я понимаю, что всё в мире ей подвержено, но недавно мы нашли в своём проекте баг, который kept me up at night, к сожалению сломались транзакционные гарантии. Баг был в коде как минимум 7 лет. Мы его починили, но оценить, сколько пользователей просто не заметило потерянных данных непонятно как. Остаётся только разводить руки, но осознание, что никакое тестирование его не поймало просто ужасное. И что поймать такие вещи в проде худшее, что может случиться с инфраструктурой. Да и воспроизвели мы его только в проде. И починили, смотря на метрику в проде. Локально воспроизвести не получается никак.
6. Блог на community.arm получил достаточно много референсов у разработчиков (в том числе Lemire), делиться вещами надо, кажется я рассказал о том, что болело у разработчиков библиотек (раз, два, три, четыре, пять).
Я хочу стримить, как я пишу код. У меня возникает откуда-то странное желание это делать. Насмотрелся на George Hotz, наверное.
Чёт сумбурно, но продуктивность хлещет, начинается мой любимый сезон года, осень, зима, когда можно уютно что-то делать
GitHub
GitHub - google/silifuzz
Contribute to google/silifuzz development by creating an account on GitHub.
Это будет не очень технический пост.
Как человек немного олдскульного типа для которого сильно важен текст, я с огорчением смотрю, как текстовый поиск по интернету потихоньку начинает проигрывать short video based формату, а.к.а. TikTok [1]. Много репортов о том, что Gen Z начинает там больше искать информацию и меньше предпочитает стандартные поисковики типа Google или Яндекс. Да даже я тому же ютубу не сильно рад, но, видимо, мы такие человеки, что любим смотреть на людей, и это удобнее, посмотреть рецепт/упражнение/интерьер за 10-15 секунд.
К ТикТоку можно относиться по-разному -- кто-то считает это гениальным изобретением, кто-то полным сатанизмом. Про себя скажу, что TikTok на меня влияет достаточно плохо, мой attention span уменьшается, а как инженер я сильно люблю концентрироваться на чём-то. После даже 15 минут TikTok меня заставляет чувствовать тревожно. То же происходит с Instagram и Youtube Shorts. Но и позитивные вещи есть, больше видишь разнообразия, больше осведомлённость и осознания о социальных движениях. Humanitarian idea of being always connected to people воплащается в бесконечном объёме.
Да, наверное, будучи даже самим представителем вида Gen Z, я понимаю, почему TikTok или Reddit чувствуются как след шаг: аутентичность. Когда работал в поиске, одна из самых тяжелых задач -- как балансировать между качеством (релевантностью) и "кликбейтом" (можно сказать, пользовательскими предпочтениями). Первое рассказывает правду, второе заставляет людей возвращаться на платформу. Сухая правда людям не нравится, второе на долгой дистанции деградирует доверие. Баланс, проведение границы всегда невозможно тяжелый вопрос, на который нет ответа. Где накрутка Search Engine Optimization (SEO), а где реальный и полезный контент. Это были самые сложные вопросы даже для разработчика бекенда как я. Я любил и люблю шутить, что все проблемы в мире это либо scaling, либо draw the line проблемы -- как расшириться и где провести границу. Интересно, что алгоритм TikTok страдает как-то меньше в сознании людей от SEO, может быть, не успели накрутить или понять как накручивать. Я точно уверен, что со временем это будет одна из самых тяжелых проблем.
В Китае есть приложение RED [2] с очень похожими отзывыми (и какими-то заоблачными 4.9/5), что Baidu кажется скучным, а вот на RED можно делиться короткими видео и быть КРИЭЙТОРОМ, сделать сайтик самому сложнее. Понравился отзыв: Baidu is full of theoretical knowledge. On RED, you see experiences from real people. Скорее всего и Google и Яндекс ждёт что-то похожее. Пообщавшись с некоторыми людьми, слыша фразу "Google is kinda boring", волосы дыбом, мол, вы даже не представляете, что надо сделать, чтобы запустить поисковики на сотни миллиардов документов. Boring, блин :)
Тем не менее, вот Reddit люблю, но какие же не очень поиски у TikTok/Reddit/Twitter, реально надо прийти и сделать им нормально.
Как человек, который любит олдскул типа Википедии, обычного текста, огромного скейла, статей на arxiv, в голове происходит принятие, что теперь мир такой. И это нормально. Технологии меняют этику, или наоборот, спорить здесь можно бесконечно :)
По природе мы все любим людей, теперь люди стали везде и всюду с этими платформами.
[1] https://www.theverge.com/23365101/tiktok-search-google-replacement
[2] https://apps.apple.com/us/app/%E5%B0%8F%E7%BA%A2%E4%B9%A6-%E6%A0%87%E8%AE%B0%E6%88%91%E7%9A%84%E7%94%9F%E6%B4%BB/id741292507
Как человек немного олдскульного типа для которого сильно важен текст, я с огорчением смотрю, как текстовый поиск по интернету потихоньку начинает проигрывать short video based формату, а.к.а. TikTok [1]. Много репортов о том, что Gen Z начинает там больше искать информацию и меньше предпочитает стандартные поисковики типа Google или Яндекс. Да даже я тому же ютубу не сильно рад, но, видимо, мы такие человеки, что любим смотреть на людей, и это удобнее, посмотреть рецепт/упражнение/интерьер за 10-15 секунд.
К ТикТоку можно относиться по-разному -- кто-то считает это гениальным изобретением, кто-то полным сатанизмом. Про себя скажу, что TikTok на меня влияет достаточно плохо, мой attention span уменьшается, а как инженер я сильно люблю концентрироваться на чём-то. После даже 15 минут TikTok меня заставляет чувствовать тревожно. То же происходит с Instagram и Youtube Shorts. Но и позитивные вещи есть, больше видишь разнообразия, больше осведомлённость и осознания о социальных движениях. Humanitarian idea of being always connected to people воплащается в бесконечном объёме.
Да, наверное, будучи даже самим представителем вида Gen Z, я понимаю, почему TikTok или Reddit чувствуются как след шаг: аутентичность. Когда работал в поиске, одна из самых тяжелых задач -- как балансировать между качеством (релевантностью) и "кликбейтом" (можно сказать, пользовательскими предпочтениями). Первое рассказывает правду, второе заставляет людей возвращаться на платформу. Сухая правда людям не нравится, второе на долгой дистанции деградирует доверие. Баланс, проведение границы всегда невозможно тяжелый вопрос, на который нет ответа. Где накрутка Search Engine Optimization (SEO), а где реальный и полезный контент. Это были самые сложные вопросы даже для разработчика бекенда как я. Я любил и люблю шутить, что все проблемы в мире это либо scaling, либо draw the line проблемы -- как расшириться и где провести границу. Интересно, что алгоритм TikTok страдает как-то меньше в сознании людей от SEO, может быть, не успели накрутить или понять как накручивать. Я точно уверен, что со временем это будет одна из самых тяжелых проблем.
В Китае есть приложение RED [2] с очень похожими отзывыми (и какими-то заоблачными 4.9/5), что Baidu кажется скучным, а вот на RED можно делиться короткими видео и быть КРИЭЙТОРОМ, сделать сайтик самому сложнее. Понравился отзыв: Baidu is full of theoretical knowledge. On RED, you see experiences from real people. Скорее всего и Google и Яндекс ждёт что-то похожее. Пообщавшись с некоторыми людьми, слыша фразу "Google is kinda boring", волосы дыбом, мол, вы даже не представляете, что надо сделать, чтобы запустить поисковики на сотни миллиардов документов. Boring, блин :)
Тем не менее, вот Reddit люблю, но какие же не очень поиски у TikTok/Reddit/Twitter, реально надо прийти и сделать им нормально.
Как человек, который любит олдскул типа Википедии, обычного текста, огромного скейла, статей на arxiv, в голове происходит принятие, что теперь мир такой. И это нормально. Технологии меняют этику, или наоборот, спорить здесь можно бесконечно :)
По природе мы все любим людей, теперь люди стали везде и всюду с этими платформами.
[1] https://www.theverge.com/23365101/tiktok-search-google-replacement
[2] https://apps.apple.com/us/app/%E5%B0%8F%E7%BA%A2%E4%B9%A6-%E6%A0%87%E8%AE%B0%E6%88%91%E7%9A%84%E7%94%9F%E6%B4%BB/id741292507
The Verge
I tried replacing Google with TikTok, and it worked better than I thought
TikTok won’t kill Google yet, but it’s a new and fun way to think about search.
Store Forwarding penalties
Представьте вы пишете по указателю данные. Далее по этому указателю или где-то рядом вы читаете эти данные. Современные процессоры нынче очень хитрые и могут не читать память при такой инструкции. Это называется «store-to-load forwarding» и ускоряет программы, поскольку load инструкции не нужно ждать, пока данные будут записаны в кэш, а затем снова считываться. Пример такой последовательности очень простой:
Процессоры могут в регистр %eax сразу писать из регистра %xmm0 не дожидаясь пока в память будет что-то записано. Там есть всякие пенальти, если данные поменялись в другом треде походу этой оптимизации, но речь немного не о них сегодня.
Так получилось, что мы нашли какие-то безумные штрафы на Intel и Arm. Например
Intel:
1. Загрузить 2 байта
2. Прочитать второй следующей инструкцией
Работает в 2-3 раза дольше, чем
1. Загрузить 2 байта
2. Прочитать первый
Решил сделать бенчмарк, который загружает Х байт (X = 2,4,8,16), читает Y байт (Y = 1,2,4,8,16) по оффсету Z (Z = 0..15) с условием, что Y + Z <= X. Получились цифры как на картинках для AMD Rome, Intel Skylake и Graviton 2.
Выводы
1. AMD всегда хорошо применяет эту оптимизацию
2. Intel плохо работает, если грузить 2-й байт при загрузке 2. Также плохо, если при загрузке 16 байт мы читаем 4/8, и они переходят границу в 8 байт (размер регистра, походу)
3. Arm работают плохо, кроме выравнивания по 0, reg_size/2.
Это важно всяким small string optimization, rope/cord, compressors, потому что они используют стек как данные и одновременно как идентификаторы, а большие или маленькие они.
Решил сделать бенчмарк, на Rust. https://github.com/danlark1/store_forwarding
Agner Fog писал про это, но мало.
Если поменять layout absl::Cord на обратный, Arm ускоряется, по табличке грузить 1 байт по оффсету 0 лучше, чем по 15 :)
Представьте вы пишете по указателю данные. Далее по этому указателю или где-то рядом вы читаете эти данные. Современные процессоры нынче очень хитрые и могут не читать память при такой инструкции. Это называется «store-to-load forwarding» и ускоряет программы, поскольку load инструкции не нужно ждать, пока данные будут записаны в кэш, а затем снова считываться. Пример такой последовательности очень простой:
movaps %xmm0, (%rsp) # Сохраняем 16 байт по адресу
mov 2(%rsp), %eax # Читаем 4 байта с адреса +2
Процессоры могут в регистр %eax сразу писать из регистра %xmm0 не дожидаясь пока в память будет что-то записано. Там есть всякие пенальти, если данные поменялись в другом треде походу этой оптимизации, но речь немного не о них сегодня.
Так получилось, что мы нашли какие-то безумные штрафы на Intel и Arm. Например
Intel:
1. Загрузить 2 байта
write_unaligned<2>(ptr)2. Прочитать второй следующей инструкцией
read_unaligned<1>(ptr + 1)Работает в 2-3 раза дольше, чем
1. Загрузить 2 байта
write_unaligned<2>(ptr)2. Прочитать первый
read_unaligned<1>(ptr)Решил сделать бенчмарк, который загружает Х байт (X = 2,4,8,16), читает Y байт (Y = 1,2,4,8,16) по оффсету Z (Z = 0..15) с условием, что Y + Z <= X. Получились цифры как на картинках для AMD Rome, Intel Skylake и Graviton 2.
Выводы
1. AMD всегда хорошо применяет эту оптимизацию
2. Intel плохо работает, если грузить 2-й байт при загрузке 2. Также плохо, если при загрузке 16 байт мы читаем 4/8, и они переходят границу в 8 байт (размер регистра, походу)
3. Arm работают плохо, кроме выравнивания по 0, reg_size/2.
Это важно всяким small string optimization, rope/cord, compressors, потому что они используют стек как данные и одновременно как идентификаторы, а большие или маленькие они.
Решил сделать бенчмарк, на Rust. https://github.com/danlark1/store_forwarding
Agner Fog писал про это, но мало.
Если поменять layout absl::Cord на обратный, Arm ускоряется, по табличке грузить 1 байт по оффсету 0 лучше, чем по 15 :)
Так как я уже не могу закончить этот пост неделю, напишу, что есть. Главное -- писать, остальное не так важно.
Что такое хорошая хеш-функция?
Этот вопрос на первый взгляд всегда кажется более научным, чем практическим. Да, в теории есть какие-то критерии. Даже пытались выстроить 5 уровней хэш-функции. Что взломать сложно или какие-то c-way-collisions найти очень быстро нельзя.
Криптографические хэши очень давно устоялись в индустрии и если перформанс для вас не так важен, SHA-3 и вперед.
В науке практически ничего невозможно доказать про хэш-функции кроме universal hashing, поэтому индустрия здесь надеется на смысл, чтобы хоть как-то предсказать хэши было сложно в случае хэш-таблиц.
И я тут даже не хочу говорить о каких-то хэшах типа MurMur, Farmhash, Cityhash, Wyhash, и тд. Если вам интересно, можете посмотреть их сравнение на smhasher: этот репозиторий кстати очень недооценён, сравнивать хэш-функции на коллизии, случайность стоит, а вот мало кто такой неблагодарной работой занимается.
Вопрос, который я решал последние пару месяцев и о котором я всё не мог написать, а как находить хэш-функции с хорошим распределением и ещё желательно, чтобы они были быстрыми?
Мир как-то слишком мало ответов знает на этот вопрос. Можно даже проще сформулировать: даны не более 16 байт (hi, lo) и длина, какое минимальное количество инструкций надо, чтобы получить хороший хэш?
Так как много вычислений хэшей происходит именно на всяких числах, маленьких строках, много циклов проводится в хэш таблицах, доминирующие элементы маленькие.
А что важно хэштаблице? Коллизии, потом скорее усложнение их поиска и чтобы "на проде" работало нормально. Коллизии чаще встречаются на размерах степеней двойки, как делают, скажем flat_hash_* в Abseil и Folly. Поэтому важно, чтобы нижние биты не сильно совпадали даже если нет коллизий :)
Итак, у нас есть хэш таблицы, у них не очень большие ключи и просто туча применений.
Инструкции CRC32 впаяны прям в процессоры x86 и Arm. Хоть это вычисление достаточно быстрое, CRC32C никогда не был сделан для хэш-таблиц, падает статистические тесты. Достаточно много коллизий, когда данные не слишком отличаются, это фактически означает, что если вы будете добавлять какие-нибудь указатели или числа/строки с одинаковым суффиксом, то коллизий будет достаточно много.
Этот факт я не особо знал. а вот ClickHouse повсеместно использует crc для хешей, можно идти ломать их join или что-нибудь ещё 😊 (не проверял, terms and conditions apply).
Ещё один страшный факт, что даже 64 битные crc32 инструкции возвращают 32 бита, если ваша хэштаблица приближается к 2^26 элементов, коллизий будет уже очень много.
Далее это число 128 битное, сделаем xor верхней и нижней части, это будет хэш для 8 байт. Для 16 повторить ещё раз c верхней частью и seed как результат нижней части.
На удивление это имеет достаточно хорошее распределение.
Зачем делать xor? Потому что если seed+number чётное, то умножение будет очень предсказуемым и нижние биты предсказуемы чаще. Считается, что при умножении средние и верхние биты числа не очень предсказуемы. Это хорошо на практике показано у PCG-random. Поэтому разбавить нижние биты всегда нужно чем-то.
Похожую идею можно увидеть даже у MurMur:
3 инструкции не работают совсем, лучшая 4 инстручная последовательность
Что такое хорошая хеш-функция?
Этот вопрос на первый взгляд всегда кажется более научным, чем практическим. Да, в теории есть какие-то критерии. Даже пытались выстроить 5 уровней хэш-функции. Что взломать сложно или какие-то c-way-collisions найти очень быстро нельзя.
Криптографические хэши очень давно устоялись в индустрии и если перформанс для вас не так важен, SHA-3 и вперед.
В науке практически ничего невозможно доказать про хэш-функции кроме universal hashing, поэтому индустрия здесь надеется на смысл, чтобы хоть как-то предсказать хэши было сложно в случае хэш-таблиц.
И я тут даже не хочу говорить о каких-то хэшах типа MurMur, Farmhash, Cityhash, Wyhash, и тд. Если вам интересно, можете посмотреть их сравнение на smhasher: этот репозиторий кстати очень недооценён, сравнивать хэш-функции на коллизии, случайность стоит, а вот мало кто такой неблагодарной работой занимается.
Вопрос, который я решал последние пару месяцев и о котором я всё не мог написать, а как находить хэш-функции с хорошим распределением и ещё желательно, чтобы они были быстрыми?
Мир как-то слишком мало ответов знает на этот вопрос. Можно даже проще сформулировать: даны не более 16 байт (hi, lo) и длина, какое минимальное количество инструкций надо, чтобы получить хороший хэш?
Так как много вычислений хэшей происходит именно на всяких числах, маленьких строках, много циклов проводится в хэш таблицах, доминирующие элементы маленькие.
А что важно хэштаблице? Коллизии, потом скорее усложнение их поиска и чтобы "на проде" работало нормально. Коллизии чаще встречаются на размерах степеней двойки, как делают, скажем flat_hash_* в Abseil и Folly. Поэтому важно, чтобы нижние биты не сильно совпадали даже если нет коллизий :)
Итак, у нас есть хэш таблицы, у них не очень большие ключи и просто туча применений.
Попытка 1: crcИнструкции CRC32 впаяны прям в процессоры x86 и Arm. Хоть это вычисление достаточно быстрое, CRC32C никогда не был сделан для хэш-таблиц, падает статистические тесты. Достаточно много коллизий, когда данные не слишком отличаются, это фактически означает, что если вы будете добавлять какие-нибудь указатели или числа/строки с одинаковым суффиксом, то коллизий будет достаточно много.
Этот факт я не особо знал. а вот ClickHouse повсеместно использует crc для хешей, можно идти ломать их join или что-нибудь ещё 😊 (не проверял, terms and conditions apply).
Ещё один страшный факт, что даже 64 битные crc32 инструкции возвращают 32 бита, если ваша хэштаблица приближается к 2^26 элементов, коллизий будет уже очень много.
Попытка 2: 128 битное умножение
Мы в abseil выбрали approach слегка другой, а название ему 128 битное умножение
(seed + number) * prime_numberДалее это число 128 битное, сделаем xor верхней и нижней части, это будет хэш для 8 байт. Для 16 повторить ещё раз c верхней частью и seed как результат нижней части.
На удивление это имеет достаточно хорошее распределение.
Зачем делать xor? Потому что если seed+number чётное, то умножение будет очень предсказуемым и нижние биты предсказуемы чаще. Считается, что при умножении средние и верхние биты числа не очень предсказуемы. Это хорошо на практике показано у PCG-random. Поэтому разбавить нижние биты всегда нужно чем-то.
Похожую идею можно увидеть даже у MurMur:
uint64_t fmix64 ( uint64_t k )
{
k ^= k >> 33;
k *= BIG_CONSTANT(0xff51afd7ed558ccd);
k ^= k >> 33;
k *= BIG_CONSTANT(0xc4ceb9fe1a85ec53);
k ^= k >> 33;
return k;
}
Попытка 3: перебор
Для 16 байт мы знаем, что есть хэш функция с хорошим распределением в 6 инструкций. Вопрос, а какое минимальное? Можно взять какой-нибудь set и перебрать. Вопрос в том, какие данные брать: я решил брать около 1000 входов, где есть случайные числа и все их соседи, где отличаются на 2 бита.3 инструкции не работают совсем, лучшая 4 инстручная последовательность
nohatcoder.dk
Hash levels
A categorisation system for different types of hash functions.
r0 = hi - seed;
r1 = lo + 0x71b1a19b907d6e33;
r2 = r0 * r1;
r3 = r2 ^ r2_hi;
return r3;
Ломается на распределениях побольше. Всего перебор дал где-то 40 вариантов, все сломались на бОльших распределениях.Можно перебирать 5 инструкций, но количество операций уже растёт слишком экспоненциально. На каждом шаге выбор где-то из 100 вариантов (все пары переменных * операции (+-^*,shift,rotate,crc,&,|)), в итоге даже если не разрешать все сдвиги или rotate, получается много. 115^n примерно, где n количество инструкций, на каждую итерацию надо проверить около 1000 входов на коллизии, что достаточно затратно. В итоге для n = 5, 10^15-10^16 итераций, ну можно запустить map reduce pipeline на часы. Ура, нашли 25k вариантов.
Дальше я пока сдался, потому что ощущение, что я схожу с ума. Чтобы отсеивать дальше, надо уметь больше распределений или запускать прям smhasher на все найденные.
Ну либо пойти к DeepMind, пусть их RL штуки находят хэш функции, наверное, можно поумнее.
Но мне кажется я вот вот либо докажу, что не существует хорошей 5 инстручной хеш функции для 16 байт, либо найду её наконец-то. Даже если все найденные свалятся, то никто не знает, может, я просто не добавил нужную инструкцию в перебор.
Мораль: перебирать ассемблер адски тяжело. Отсеивать плохие хэш-функции быстро адски тяжело. Ускорения в оба направления могут помочь нам дать лучшие хэш-функции. Пока вопрос открыт. Продолжаю рисёрч.
Pastebin
I0924 09:59:05.335746 3458926 main.cc:521] Better than baseline: 3761 3 3 14 374 - Pastebin.com
Pastebin.com is the number one paste tool since 2002. Pastebin is a website where you can store text online for a set period of time.
Тут недавно стукнуло как я 5 лет устроился на первую работу и я, конечно, был безумно рад, что восьмая (десятая? шестая?) часть моей карьеры прошла. Учитывая, как это было порой темно, но все же я больше находил позитивных моментов. Удалось поработать с огромными движками вычислений в больших компаниях, удалось помочь стартапной тусовке. Удалось коммитить в open source и много помочь core вещам как компиляторам, стандартным библиотекам, компрессорам, индексаторам и тд. Удалось проявить какие-то свои таланты, найти область, в которой не так много людей и монетизировать и себя, и получить много счастья одновременно. Интересно, что даже за 5 лет мир меняется сильно. Скажем
* Я убил много времени на С++. К сожалению, индустрия меняется в сторону, что любой проезд по памяти стоит дороже, чем перформанс, и кажется переезд на Rust-подобное нельзя избежать. Вот сижу учу Rust, сложно, бесит, что сильно надо мышление менять, чтобы писать хороший код на Rust. Самое противное, что рядом нет того, кто бы меня дергал и рассказывал, что так неправильно. С плюсами было так, что я попал в кучку профессионалов и со временем стал понимать многие кишки C++. С Rust придет только с опытом.
Ещё добавляет тот факт, что мир меняется, а есть текущая реальность, в которой надо много часов писать на С++. В итоге получается, что свободное время убиваешь на то, чтобы подтянуться к индустрии. Например, не было постов на этой неделе, потому что я писал libgav1 на Rust, и я ужасно замучился. Rust мне не заходит из-за того, что он слишком много берет на себя, но индустрия решает свои проблемы, я просто боюсь обесценивания своих скилов, скорее всего :)
* Я не могу сказать, что сделал какие-то продукты, которые сильно видны людям. Мне это скорее нравится, быть таким behind the scenes, но самое плохое, что приходит с опытом это ожидания и ответственность.
Да, меня спокойно наймут на позиции перформанса и инфраструктуры, и я себе подписал небольшой приговор? Мол, от человека уровня меня ждут сильных результатов -- кроме инфры таких сильных результатов я не покажу. Кажется все ок? Страшно остановиться здесь, упустить время для развития. Плюс не так много времени есть помимо работы, сейчас я в той позиции когда едва хватает на жизнь и подучить Rust.
* Вещи за 5 лет стали лучше. Лучше диагностика ошибок, лучше интерфейсы ядра, быстрее библиотеки, я стал меньше раздражаться неработающим вещам, все потихоньку становится менее плохим (highly opinionated):
* Мы пробили 1M QPS чтения диска, и SSD стали намного более массовыми
* Мы наконец-то имеем серьезный и инженерный алгоритм сжатия ZSTD
* Мы поняли как не проезжать по памяти -- Rust
* Мы научились быстрым CRDT
* Мы на скейле стали делать лучше алгоритмы и кажется стало виднеться плато вычислений процессоров и памяти
* Мы научились делать серьезный и бесконечно развивающийся SIMD типа SVE
* Очень много кто переходит с x86 на Arm, а дальше скорее и RISCV
* Мы сильно продвинулись в тестировании баз данных, транзакций и тд.
* Сеть все ещё растет и предела пока нет :)
* Мы научились намного лучше делать Profile Guided Optimizations, Post Link optimizations.
* Мы показали, что JIT очень важен до сих пор (см. Rosetta)
* Все таки нашли применение AVX512
* Лучше аллокаторы, поняли как huge pages влияют на разнообразный продакшн (см. TCMalloc)
* Принесли серьезные системные языки в браузеры (WebAssembly)
* Начали сильно пробивать игры под Linux
So far мне нравится. Я буду дальше следить, что мне хочется делать, но за 5 лет я лишь чуть чуть приоткрыл сундук с магией под названием Systems Engineering. Дальше -- больше, куда мы денемся, прогресс не остановить, и все мы к нему причастны, куда ни посмотри, везде можно принести пользу
* Я убил много времени на С++. К сожалению, индустрия меняется в сторону, что любой проезд по памяти стоит дороже, чем перформанс, и кажется переезд на Rust-подобное нельзя избежать. Вот сижу учу Rust, сложно, бесит, что сильно надо мышление менять, чтобы писать хороший код на Rust. Самое противное, что рядом нет того, кто бы меня дергал и рассказывал, что так неправильно. С плюсами было так, что я попал в кучку профессионалов и со временем стал понимать многие кишки C++. С Rust придет только с опытом.
Ещё добавляет тот факт, что мир меняется, а есть текущая реальность, в которой надо много часов писать на С++. В итоге получается, что свободное время убиваешь на то, чтобы подтянуться к индустрии. Например, не было постов на этой неделе, потому что я писал libgav1 на Rust, и я ужасно замучился. Rust мне не заходит из-за того, что он слишком много берет на себя, но индустрия решает свои проблемы, я просто боюсь обесценивания своих скилов, скорее всего :)
* Я не могу сказать, что сделал какие-то продукты, которые сильно видны людям. Мне это скорее нравится, быть таким behind the scenes, но самое плохое, что приходит с опытом это ожидания и ответственность.
Да, меня спокойно наймут на позиции перформанса и инфраструктуры, и я себе подписал небольшой приговор? Мол, от человека уровня меня ждут сильных результатов -- кроме инфры таких сильных результатов я не покажу. Кажется все ок? Страшно остановиться здесь, упустить время для развития. Плюс не так много времени есть помимо работы, сейчас я в той позиции когда едва хватает на жизнь и подучить Rust.
* Вещи за 5 лет стали лучше. Лучше диагностика ошибок, лучше интерфейсы ядра, быстрее библиотеки, я стал меньше раздражаться неработающим вещам, все потихоньку становится менее плохим (highly opinionated):
* Мы пробили 1M QPS чтения диска, и SSD стали намного более массовыми
* Мы наконец-то имеем серьезный и инженерный алгоритм сжатия ZSTD
* Мы поняли как не проезжать по памяти -- Rust
* Мы научились быстрым CRDT
* Мы на скейле стали делать лучше алгоритмы и кажется стало виднеться плато вычислений процессоров и памяти
* Мы научились делать серьезный и бесконечно развивающийся SIMD типа SVE
* Очень много кто переходит с x86 на Arm, а дальше скорее и RISCV
* Мы сильно продвинулись в тестировании баз данных, транзакций и тд.
* Сеть все ещё растет и предела пока нет :)
* Мы научились намного лучше делать Profile Guided Optimizations, Post Link optimizations.
* Мы показали, что JIT очень важен до сих пор (см. Rosetta)
* Все таки нашли применение AVX512
* Лучше аллокаторы, поняли как huge pages влияют на разнообразный продакшн (см. TCMalloc)
* Принесли серьезные системные языки в браузеры (WebAssembly)
* Начали сильно пробивать игры под Linux
So far мне нравится. Я буду дальше следить, что мне хочется делать, но за 5 лет я лишь чуть чуть приоткрыл сундук с магией под названием Systems Engineering. Дальше -- больше, куда мы денемся, прогресс не остановить, и все мы к нему причастны, куда ни посмотри, везде можно принести пользу
В последние несколько лет не слишком много происходит интересных компиляторных оптимизаций, которые помогают всем, тем не менее от версии к версии мы видим в районе 0.5-1% исправлений, учитывая, что апдейты происходят 2 раза в год, мы попадаем в Proebsting's law, что компиляторы становятся в 2 раза быстрее каждые 18 лет (1.005**36 ~ 1.20, 1.01**36 ~ 1.43), что было несколько раз опровергнуто, но остаётся забавной байкой :)
Я уже писал, что даже на архитектурах Arm и x86 в компиляторах полно ещё всякого делать, и the work is never done, но всегда выбираются пути наименьшего сопротивления и наиболее перспективные направления для вытаскивания процентов из разных бинарей -- Profile Guided Optimizations. Как будет исполняться код, зависит от данных, и тема как вытащить лучше оптимизации из профиля, одна из самых приносящих пользу в последнее время. Я думаю, если посчитать из открытых источников, то Inliner PGO+ThinLTO+PD Inlined String Proto, то будет в районе 7-10%, где ThinLTO даёт больше всех.
Rule of thumb сейчас, что большинство Profile Driven (PD) оптимизаций дают в раойне 0.5-1%, на сильно больше расчитывать тяжело и если вы сможете что-то такое придумать, я думаю вы спокойно можете стать легендой компиляторостроения.
На этот раз о двух вещах.
Profile driven cmov
https://discourse.llvm.org/t/rfc-cmov-vs-branch-optimization/6040
Эта оптимизация забавна тем, что иногда код с if условиями сложно предугадать, а profile driven оптимизации исторически наоборот, любят ставить горячий код поближе.
Плюсы cmov в том, что нет branch, минусы, что все данные подготовить надо перед инструкцией.
Идея в том, чтобы сделать cost модель, насколько дороже будет инструкция conditional mov, чем branch и применить её.
Agner Fog пишет про эвристику, которая не супер идеальна, но просто хороший дефолт:
Profile driven protobuf inlined string
В протобуфах есть поля вида string. Исторически они замаскированы под указателями, потому что люди чаще поля не используют, чем используют, а также чуть удобнее аллоцировать на общих кусках памяти под названием арены. Проблемы указателей, что их надо разыменовывать, и за это мы платим много. Если включить обычный std::string на всех, будет плохо, протобуфы разрастутся, аллокации на аренах будут сложнее и тд.
Прелесть в том, что некоторые строки очень маленькие и очень горячие, поэтому Small String Optimization может работать лучше, чем разыменовывание указателя. Решение простое, давайте мы посэмплим в проде размеры и rate с которым мы обращаемся к тем или иным полям (просто stacktraces) и перекомпилируем горячие и маленькие строки в InlinedStringField.
Снова в районе 0.5-1% выигрыша распределенного примерно по всему бинарю. Мы зарелизили InlinedStringField, но полный e2e профиль и оптимизации пока непонятно как. В целом, я думаю, что если очень надо, логику написать можно.
Красиво, две истории, когда вещи stack up среди сотен мест и дают хороший буст.
Я уже писал, что даже на архитектурах Arm и x86 в компиляторах полно ещё всякого делать, и the work is never done, но всегда выбираются пути наименьшего сопротивления и наиболее перспективные направления для вытаскивания процентов из разных бинарей -- Profile Guided Optimizations. Как будет исполняться код, зависит от данных, и тема как вытащить лучше оптимизации из профиля, одна из самых приносящих пользу в последнее время. Я думаю, если посчитать из открытых источников, то Inliner PGO+ThinLTO+PD Inlined String Proto, то будет в районе 7-10%, где ThinLTO даёт больше всех.
Rule of thumb сейчас, что большинство Profile Driven (PD) оптимизаций дают в раойне 0.5-1%, на сильно больше расчитывать тяжело и если вы сможете что-то такое придумать, я думаю вы спокойно можете стать легендой компиляторостроения.
На этот раз о двух вещах.
Profile driven cmov
https://discourse.llvm.org/t/rfc-cmov-vs-branch-optimization/6040
Эта оптимизация забавна тем, что иногда код с if условиями сложно предугадать, а profile driven оптимизации исторически наоборот, любят ставить горячий код поближе.
Плюсы cmov в том, что нет branch, минусы, что все данные подготовить надо перед инструкцией.
Идея в том, чтобы сделать cost модель, насколько дороже будет инструкция conditional mov, чем branch и применить её.
Agner Fog пишет про эвристику, которая не супер идеальна, но просто хороший дефолт:
Branch is faster than a conditional move if:
1. move is part of a dependence chain, especially a long loop-carried one,
2. and prediction rate is better than 75%; or
can avoid a lengthy calculation of non-chosen operand
В clang я обычно при написании кода если хочу cmov, то пишу тернарный оператор, а не if statement
uint64_t val = cond ? x : y; // usually cmov
if (cond) { val = x; } else { val = y; } // usually branchProfile driven protobuf inlined string
В протобуфах есть поля вида string. Исторически они замаскированы под указателями, потому что люди чаще поля не используют, чем используют, а также чуть удобнее аллоцировать на общих кусках памяти под названием арены. Проблемы указателей, что их надо разыменовывать, и за это мы платим много. Если включить обычный std::string на всех, будет плохо, протобуфы разрастутся, аллокации на аренах будут сложнее и тд.
Прелесть в том, что некоторые строки очень маленькие и очень горячие, поэтому Small String Optimization может работать лучше, чем разыменовывание указателя. Решение простое, давайте мы посэмплим в проде размеры и rate с которым мы обращаемся к тем или иным полям (просто stacktraces) и перекомпилируем горячие и маленькие строки в InlinedStringField.
Снова в районе 0.5-1% выигрыша распределенного примерно по всему бинарю. Мы зарелизили InlinedStringField, но полный e2e профиль и оптимизации пока непонятно как. В целом, я думаю, что если очень надо, логику написать можно.
Красиво, две истории, когда вещи stack up среди сотен мест и дают хороший буст.
Phoronix
LLVM Clang 15 Delivers Some Small x86_64 Performance Improvements But Mostly Flat
Released last month was LLVM/Clang 15 and since then a number of Phoronix readers have been inquiring about Clang 15 compiler benchmarks or there the lack of on Phoronix
Неожиданно для себя и людей вокруг меня, я решил поменять команду.
После пары лет в Flume/MapReduce infrastructure and efficiency, я столько возложил на свои плечи, что сейчас достаточно сложно стало тащить на себе то, что взял, поэтому пытаясь что-то починить в своем подходе, я выбрал самый простой -- полностью свалить этот груз. Ухожу я на забавной ноте, когда я стал понимать наш сервис, интерфейсы очень хорошо, и кажется почувствовал, что пора. Плюс я уже не могу терпеть очень поздние встречи с Долиной, в этот раз Нью-Йорк, полегче из Лондона будет общаться.
Перехожу я в команду Efficiency League/Data center efficiency/Bare metal efficiency, где буду заниматься тем, о чем пишу здесь, в блоге: перформансом всего, чего можно дотянуться в Google: от latency Raft и поиска до software/hardware co-design. С этой командой я много работал, пора рассказать Google пару историй, попробовать десяток идей с полной поддержкой от менеджемента. Плюс в момент рецессии датацентры сильно ужимаются, так что любые выигранные ресурсы сейчас как никогда кстати.
В целом этот год какой-то сложный и странный. Я стал больше жить, привел свою жизнь в ещё больший порядок, и вечера стали важным средством для того, чтобы эту самую жизнь жить, а не писать код.
Все мы меняемся, я не исключение. Я думаю эта история на ещё год-два, но самое слабое место программистов -- планирование, поэтому как пойдет, так и будет.
После пары лет в Flume/MapReduce infrastructure and efficiency, я столько возложил на свои плечи, что сейчас достаточно сложно стало тащить на себе то, что взял, поэтому пытаясь что-то починить в своем подходе, я выбрал самый простой -- полностью свалить этот груз. Ухожу я на забавной ноте, когда я стал понимать наш сервис, интерфейсы очень хорошо, и кажется почувствовал, что пора. Плюс я уже не могу терпеть очень поздние встречи с Долиной, в этот раз Нью-Йорк, полегче из Лондона будет общаться.
Перехожу я в команду Efficiency League/Data center efficiency/Bare metal efficiency, где буду заниматься тем, о чем пишу здесь, в блоге: перформансом всего, чего можно дотянуться в Google: от latency Raft и поиска до software/hardware co-design. С этой командой я много работал, пора рассказать Google пару историй, попробовать десяток идей с полной поддержкой от менеджемента. Плюс в момент рецессии датацентры сильно ужимаются, так что любые выигранные ресурсы сейчас как никогда кстати.
В целом этот год какой-то сложный и странный. Я стал больше жить, привел свою жизнь в ещё больший порядок, и вечера стали важным средством для того, чтобы эту самую жизнь жить, а не писать код.
Все мы меняемся, я не исключение. Я думаю эта история на ещё год-два, но самое слабое место программистов -- планирование, поэтому как пойдет, так и будет.
1. Мы тут недавно выложили fuzztest. В целом если вы используете GTest, то вы можете написать что-то вроде
И всё, у вас автоматически вместе с тестами фаззинг вашего API. То есть можно не только писать юнит тесты, но и тестировать свойства вашего API в том же файле.
После этого хоть и требуется настройка как гонять это на continuous basis, но если вы действительно паритесь насчёт тестирования ваших программ на C++, то вы добавите continuous testing на это. А локально можете выбрать, сколько вы хотите потестировать ваше API.
К сожалению, только на Bazel, но я решил портировать на CMake:
https://github.com/danlark1/fuzztest_cmake. Welcome
2. Тут zstd рассматривает одну интересную семантическую оптимизацию: нахождение оптимательного количества бит для дерева Хаффмана.
https://github.com/facebook/zstd/pull/3302
В Zstd сжатие хаффмана используется, когда сжимаются литеральные строки -- то есть данные, которые нужно скопировать как есть.
Чтобы лучше понять контекст, Zstd использует два метода сжатия -- Huffman и FSE: первый очень стандартный, когда мы символам присваиваем префиксный код, а второй исправляет недочёты Huffman: например, если какой-то символ встречается 90% раз, то теория информации говорит, что мы можем кодировать это log2(1/0.9)=0.15 битами, когда как дерево Хаффмана присваивает минимум 1. Чтобы достичь лимита придумали FSE, пока в детали углубляться не стоит, но суть в том, чтобы менять биты ответственные за символы по ходу декодирования.
Huffman быстрее, FSE медленнее из-за нестатической таблицы. FSE хорошо работает, когда данных побольше, Huffman на маленьких данных не видит большой разницы с FSE.
Zstd делит данные на две категории -- Literals и Sequences -- первое -- обычные данные, которые стоит копировать (можете для простоты думать, что это словарь), а Sequences -- команды, откуда копировать, нужно ли копировать из уже раскодированных данных. Решение о том, чтобы кодировать литералы Huffman интересное, их не очень много по сравнению с командами о копировании.
Чтобы подобрать оптимальное дерево Хаффмана мы все знаем алгоритм -- взять два самых невстречающихся, соединить, суммировать их вероятности, удалить старые.
К сожалению, чтобы записать информацию о дереве Хаффмана, нужно тоже место:
1. Для весов
2. Для самого алфавита литералов
В итоге это баланс между Huffman header и compression estimation. Чем меньше веса, тем легче их сжать, поэтому выбирается эвристика, сколько максимум бит в высоту можно заиспользовать дереву Хаффмана. Спецификация не разрешает больше, чем 11 бит -- оно скорее логично, алфавиты до 255, высоты 10 должно хватить для литералов часто. Также из интересного спецификация не хранит веса, а хранит какой высоты должен быть символ.
Эти "высоты" сами сжимаются FSE кодированием, потому что высоты чаще повторяются: 255 значений, там скорее всего много значений высоты 5, 6, 7 и тд хорошо сжимаются.
Чтобы найти этот оптимальный баланс, ничего не придумаешь, кроме как перебрать высоты: если у вас данные из алфавита A, то будете перебирать от log2(|A|) до 11: не совсем понятно как уменьшение высоты (более встречающиеся символы начинают иметь более длинные коды) влияет на суммарное сжатие (бОльшие веса сложнее кодировать), эта функция не унимодальная.
Тем не менее, большинство из них унимодальны. Такую эвристику и решают выбрать -- взять какую-то точку и попытаться пойти в обе стороны пока уменьшается результат суммарного сжатия на блоке сжатых данных.
В итоге на 200MB при стандартном блоке выигрывается около 3КБ, когда блок поменьше (то есть FSE не очень сильно помогает сжимать), то разница уже в 360KB. Маленькие блоки встречаются в сжатии со словарем, когда очень много мелких данных приходит -- сообщения, посты, и тд.
Перф не просаживается на больших блоках, на маленьких 15%. Интересный PR, посмотрим, вольют или нет. Или другую эвристическу придумать можно.
void MyApiAlwaysSucceedsOnPositiveIntegers(int i) {
bool success = MyApi(i);
EXPECT_TRUE(success);
}
FUZZ_TEST(MyApiTest, MyApiAlwaysSucceedsOnPositiveIntegers)
.WithDomains(/*i:*/fuzztest::Positive<int>());
И всё, у вас автоматически вместе с тестами фаззинг вашего API. То есть можно не только писать юнит тесты, но и тестировать свойства вашего API в том же файле.
После этого хоть и требуется настройка как гонять это на continuous basis, но если вы действительно паритесь насчёт тестирования ваших программ на C++, то вы добавите continuous testing на это. А локально можете выбрать, сколько вы хотите потестировать ваше API.
К сожалению, только на Bazel, но я решил портировать на CMake:
https://github.com/danlark1/fuzztest_cmake. Welcome
2. Тут zstd рассматривает одну интересную семантическую оптимизацию: нахождение оптимательного количества бит для дерева Хаффмана.
https://github.com/facebook/zstd/pull/3302
В Zstd сжатие хаффмана используется, когда сжимаются литеральные строки -- то есть данные, которые нужно скопировать как есть.
Чтобы лучше понять контекст, Zstd использует два метода сжатия -- Huffman и FSE: первый очень стандартный, когда мы символам присваиваем префиксный код, а второй исправляет недочёты Huffman: например, если какой-то символ встречается 90% раз, то теория информации говорит, что мы можем кодировать это log2(1/0.9)=0.15 битами, когда как дерево Хаффмана присваивает минимум 1. Чтобы достичь лимита придумали FSE, пока в детали углубляться не стоит, но суть в том, чтобы менять биты ответственные за символы по ходу декодирования.
Huffman быстрее, FSE медленнее из-за нестатической таблицы. FSE хорошо работает, когда данных побольше, Huffman на маленьких данных не видит большой разницы с FSE.
Zstd делит данные на две категории -- Literals и Sequences -- первое -- обычные данные, которые стоит копировать (можете для простоты думать, что это словарь), а Sequences -- команды, откуда копировать, нужно ли копировать из уже раскодированных данных. Решение о том, чтобы кодировать литералы Huffman интересное, их не очень много по сравнению с командами о копировании.
Чтобы подобрать оптимальное дерево Хаффмана мы все знаем алгоритм -- взять два самых невстречающихся, соединить, суммировать их вероятности, удалить старые.
К сожалению, чтобы записать информацию о дереве Хаффмана, нужно тоже место:
1. Для весов
2. Для самого алфавита литералов
В итоге это баланс между Huffman header и compression estimation. Чем меньше веса, тем легче их сжать, поэтому выбирается эвристика, сколько максимум бит в высоту можно заиспользовать дереву Хаффмана. Спецификация не разрешает больше, чем 11 бит -- оно скорее логично, алфавиты до 255, высоты 10 должно хватить для литералов часто. Также из интересного спецификация не хранит веса, а хранит какой высоты должен быть символ.
Эти "высоты" сами сжимаются FSE кодированием, потому что высоты чаще повторяются: 255 значений, там скорее всего много значений высоты 5, 6, 7 и тд хорошо сжимаются.
Чтобы найти этот оптимальный баланс, ничего не придумаешь, кроме как перебрать высоты: если у вас данные из алфавита A, то будете перебирать от log2(|A|) до 11: не совсем понятно как уменьшение высоты (более встречающиеся символы начинают иметь более длинные коды) влияет на суммарное сжатие (бОльшие веса сложнее кодировать), эта функция не унимодальная.
Тем не менее, большинство из них унимодальны. Такую эвристику и решают выбрать -- взять какую-то точку и попытаться пойти в обе стороны пока уменьшается результат суммарного сжатия на блоке сжатых данных.
В итоге на 200MB при стандартном блоке выигрывается около 3КБ, когда блок поменьше (то есть FSE не очень сильно помогает сжимать), то разница уже в 360KB. Маленькие блоки встречаются в сжатии со словарем, когда очень много мелких данных приходит -- сообщения, посты, и тд.
Перф не просаживается на больших блоках, на маленьких 15%. Интересный PR, посмотрим, вольют или нет. Или другую эвристическу придумать можно.
GitHub
GitHub - google/fuzztest
Contribute to google/fuzztest development by creating an account on GitHub.
https://blog.kagi.com/age-pagerank-over
Я как человек поработав очень близко с поисковым движком, где компания зарабатывает на рекламе (Яндекс), скажу, что такие статьи выглядят очень смешными.
Я понимаю, что очень легко сказать, что реклама становится источником bias, что движкам выгодно оптимизировать деньги, а не результат, но в реальности это совсем не так.
Реклама и качество очень сильно разделены, максимально сильно, чтобы такого не происходило. Настолько, что пулы для обучения моделей закрыты от аналитиков с обеих сторон.
Качество поиска в год растет где-то на 2 процента по метрике, которую компании сами придумывают, и она тоже по личному опыту не направлена на увеличение количества денег. В хорошие года с прорывами как DSSM, BERT в год получается где-нибудь 3%. Мы постоянно имели проблемы с тем, что рекламодатель приходит и говорит, что по их запросу их ссылка только вторая, что ж, это результат того, что мы не оптимизируем деньги в ранжировании.
Одна из проблем, о которой пишут в статье про то, что траффик поисковых движков становится revenue generator сайтов, поэтому SEOшники начинают плодиться, хитрее, система поиска в итоге сложнее, которая добавляет десятки тысяч факторов, модели супер сложными, энтропия растет, порочный круг борьбы SEO и мл продолжается. Как любые сложные системы по типу экономики, инженерии, системы в один момент становятся ... невозможными для восприятия.
Люди перестают понимать, чего ожидать от движка, разработчики перестают понимать, а что такое вообще "хорошее" ранжирование.
Асессоры, задача которых оценивать выдачу, тоже не очень заинтересованы в том, чтобы увеличить кому-то деньги. И в Яндексе, и в Google инструкции, методики анализа выдачи направлены только на релевантность, есть ли ответ по ссылке и тд.
Но чем больше вы будете думать, что вы хотите от движка на конкретных примерах, а также видеть, чего хотят другие люди, вы в один момент загрустите -- улучшать формулу на полпроцента в год очень тяжело и едва даёт осознание ощущения полезности, например, смотря на выкатку новой формулы вы увидите, может, 3-4 исправившихся запроса из корзинки в 10-20к. Люди, которые делают модели особо не понимают, что и как исправлять, потому что мы входим на территорию вопросов на машстабе сотен миллионов и миллиардов людей о том, что такое правда и ложь.
С кликбейтом тоже забавная история. Люди дают четкий сигнал на короткой дистанции, что они обожают кликбейт, зато в пределах недели они от него безумно устанут.
Что же делать?
Мое мнение, что поисковый рынок давно монополизирован. Конкуренция Google нужна, очень как нужна на мировом масштабе. Тем не менее, статьи как kagi ничего не поменяют, потому что если даже они вырастут, они столкнутся с теми же проблемами -- трафик сильно завязан в современном мире на деньги и внимание как бы они ни старались отойти от модели рекламы.
Если принять тот факт, что нам как человечеству нужен поисковый движок, чтобы что-то узнавать, то нужно менять философию. Например,
* Запрещать рекламные ссылки
* Публично публиковать, что движок делает с плохими запросами. Так появляется доверие, credit
* Может быть уйти от капитализма совсем и поиск должен быть приватным/некоммерческим
* Поступать по морали. Да, эта фраза может вас рассмешить, но когда вы отвечаете за правду и ложь на миллиарде людей, мораль и принципы должны быть. Если разные движки и разные морали, это тоже нормально.
Некоторые пункты легче сделать из этого списка, некоторые намного сложнее: как держать финансово инфраструктуру на сотни миллиардов, а то и триллионы ссылок, когда поиск должен отвечать сотни тысяч запросов в секунду и при этом быть 99.99 доступным, просто сложно. Иметь принципы как Википедия при отсутствия контроля публикуемой информации непонятно. Можно ли нам, Гуглу что-то тут сделать изнутри, неясно, можно ли сделать прорыв в релевантности, неясно. Что нужно людям, неясно. Что такое правда и ложь, неясно. Это не значит, что не надо стараться.
Это действительно сложная задача, мы устали от Гугла и Яндекса, что-то новое точно появится. Пока мы упёрлись в локальным максимум.
Я как человек поработав очень близко с поисковым движком, где компания зарабатывает на рекламе (Яндекс), скажу, что такие статьи выглядят очень смешными.
Я понимаю, что очень легко сказать, что реклама становится источником bias, что движкам выгодно оптимизировать деньги, а не результат, но в реальности это совсем не так.
Реклама и качество очень сильно разделены, максимально сильно, чтобы такого не происходило. Настолько, что пулы для обучения моделей закрыты от аналитиков с обеих сторон.
Качество поиска в год растет где-то на 2 процента по метрике, которую компании сами придумывают, и она тоже по личному опыту не направлена на увеличение количества денег. В хорошие года с прорывами как DSSM, BERT в год получается где-нибудь 3%. Мы постоянно имели проблемы с тем, что рекламодатель приходит и говорит, что по их запросу их ссылка только вторая, что ж, это результат того, что мы не оптимизируем деньги в ранжировании.
Одна из проблем, о которой пишут в статье про то, что траффик поисковых движков становится revenue generator сайтов, поэтому SEOшники начинают плодиться, хитрее, система поиска в итоге сложнее, которая добавляет десятки тысяч факторов, модели супер сложными, энтропия растет, порочный круг борьбы SEO и мл продолжается. Как любые сложные системы по типу экономики, инженерии, системы в один момент становятся ... невозможными для восприятия.
Люди перестают понимать, чего ожидать от движка, разработчики перестают понимать, а что такое вообще "хорошее" ранжирование.
Асессоры, задача которых оценивать выдачу, тоже не очень заинтересованы в том, чтобы увеличить кому-то деньги. И в Яндексе, и в Google инструкции, методики анализа выдачи направлены только на релевантность, есть ли ответ по ссылке и тд.
Но чем больше вы будете думать, что вы хотите от движка на конкретных примерах, а также видеть, чего хотят другие люди, вы в один момент загрустите -- улучшать формулу на полпроцента в год очень тяжело и едва даёт осознание ощущения полезности, например, смотря на выкатку новой формулы вы увидите, может, 3-4 исправившихся запроса из корзинки в 10-20к. Люди, которые делают модели особо не понимают, что и как исправлять, потому что мы входим на территорию вопросов на машстабе сотен миллионов и миллиардов людей о том, что такое правда и ложь.
С кликбейтом тоже забавная история. Люди дают четкий сигнал на короткой дистанции, что они обожают кликбейт, зато в пределах недели они от него безумно устанут.
Что же делать?
Мое мнение, что поисковый рынок давно монополизирован. Конкуренция Google нужна, очень как нужна на мировом масштабе. Тем не менее, статьи как kagi ничего не поменяют, потому что если даже они вырастут, они столкнутся с теми же проблемами -- трафик сильно завязан в современном мире на деньги и внимание как бы они ни старались отойти от модели рекламы.
Если принять тот факт, что нам как человечеству нужен поисковый движок, чтобы что-то узнавать, то нужно менять философию. Например,
* Запрещать рекламные ссылки
* Публично публиковать, что движок делает с плохими запросами. Так появляется доверие, credit
* Может быть уйти от капитализма совсем и поиск должен быть приватным/некоммерческим
* Поступать по морали. Да, эта фраза может вас рассмешить, но когда вы отвечаете за правду и ложь на миллиарде людей, мораль и принципы должны быть. Если разные движки и разные морали, это тоже нормально.
Некоторые пункты легче сделать из этого списка, некоторые намного сложнее: как держать финансово инфраструктуру на сотни миллиардов, а то и триллионы ссылок, когда поиск должен отвечать сотни тысяч запросов в секунду и при этом быть 99.99 доступным, просто сложно. Иметь принципы как Википедия при отсутствия контроля публикуемой информации непонятно. Можно ли нам, Гуглу что-то тут сделать изнутри, неясно, можно ли сделать прорыв в релевантности, неясно. Что нужно людям, неясно. Что такое правда и ложь, неясно. Это не значит, что не надо стараться.
Это действительно сложная задача, мы устали от Гугла и Яндекса, что-то новое точно появится. Пока мы упёрлись в локальным максимум.
Kagi
The Age of PageRank is Over | Kagi Blog
When Sergey Brin and Larry Page came up with the concept of PageRank in their seminal paper The Anatomy of a Large-Scale Hypertextual Web Search Engine ( http://infolab.stanford.edu/pub/papers/google.pdf ) (Sergey Brin and Lawrence Page, Stanford University…
Мы наконец-то зарелизили CRC32C библиотеку в abseil. Я её всю перехерачил по перфу и по API, и спасибо коллегам из C++ команды, что они её дотащили до OSS.
Поглядеть:
https://github.com/abseil/abseil-cpp/blob/master/absl/crc
Уроки и фичи:
* CRC хорошая полиномиальная чексумма, она стриминговая, вы можете добавлять чанки:
Неважно как вы дробите эти чанки, если в конкатенации получаются те же данные, то чексумма совпадёт. Это позволяет сервисам типа мап редьюса разделять динамически данные на чанки разной длины и проверять в конце, что всё сходится.
* В проде >75% вызовов до 64 байт. Поэтому мы выиграли очень много перфа, когда компилятор инлайнил с помощью PGO код в релизных сборках.
* В проде оказался большой хвост степеней двоек -- 4KB, 1MB, 4MB чексуммы доминировали какие-то проценты вычислений.
* Intel очень хорошие писала гайды о том, как надо имплементировать CRC32{C}, и, конечно, мы это и сделали.
* Только вот не одним Intel мы живём, а также есть куча разного парка железа типа AMD, старых интелов и тд. В итоге мы очень внимательно подбирали размеры буфферов для CLMUL fold и CRC fold. Получилась весьма забавная табличка что где лучше работает. CLMUL на AMD всё ещё очень медленный.
* На удивление мы побили все бенчмарки на Arm'ах N1+ и библиотеку ISA-L, которую инженеры из Arm сами пишут. Притом гайды от Intel отлично легли, и код получился унифицированным (но не обошлось и без проблем).
* Мы не ставили цели бить Apple. За самым быстрым CRC для Apple можно обратиться сюда (спойлер: они прошли по тонкой грани, когда смогли сделать fusion двух инструкций, до сих пор спорят, разрешает ли так делать лицензия Arm):
https://dougallj.wordpress.com/2022/05/22/faster-crc32-on-the-apple-m1/
* Имплементация от dougallj@ плохая на серверах. На наших T2A инстансах мы получили
* Было забавно, к сожалению, чтобы так красиво фаниться, не очень много проектов существует.
Поглядеть:
https://github.com/abseil/abseil-cpp/blob/master/absl/crc
Уроки и фичи:
* CRC хорошая полиномиальная чексумма, она стриминговая, вы можете добавлять чанки:
crc32c_t crc = 0;
crc = ExtendCrc32c(crc, chunk);
Неважно как вы дробите эти чанки, если в конкатенации получаются те же данные, то чексумма совпадёт. Это позволяет сервисам типа мап редьюса разделять динамически данные на чанки разной длины и проверять в конце, что всё сходится.
* В проде >75% вызовов до 64 байт. Поэтому мы выиграли очень много перфа, когда компилятор инлайнил с помощью PGO код в релизных сборках.
* В проде оказался большой хвост степеней двоек -- 4KB, 1MB, 4MB чексуммы доминировали какие-то проценты вычислений.
* Intel очень хорошие писала гайды о том, как надо имплементировать CRC32{C}, и, конечно, мы это и сделали.
* Только вот не одним Intel мы живём, а также есть куча разного парка железа типа AMD, старых интелов и тд. В итоге мы очень внимательно подбирали размеры буфферов для CLMUL fold и CRC fold. Получилась весьма забавная табличка что где лучше работает. CLMUL на AMD всё ещё очень медленный.
* На удивление мы побили все бенчмарки на Arm'ах N1+ и библиотеку ISA-L, которую инженеры из Arm сами пишут. Притом гайды от Intel отлично легли, и код получился унифицированным (но не обошлось и без проблем).
* Мы не ставили цели бить Apple. За самым быстрым CRC для Apple можно обратиться сюда (спойлер: они прошли по тонкой грани, когда смогли сделать fusion двух инструкций, до сих пор спорят, разрешает ли так делать лицензия Arm):
https://dougallj.wordpress.com/2022/05/22/faster-crc32-on-the-apple-m1/
* Имплементация от dougallj@ плохая на серверах. На наших T2A инстансах мы получили
dougallj@: 21.84123gb/s
Goog: 33.268118gb/s
* Оказалось, что людям нужно API как MemcpyCRC32C, чтобы скопировать и вычислять чексуммы одновременно. Это получается много где быстрее, так как можно контролировать чанки по которым зовёшь memcpy и утилизируя все пайплайны процессора.
* Non-temporal memcpy * Было забавно, к сожалению, чтобы так красиво фаниться, не очень много проектов существует.
GitHub
abseil-cpp/absl/crc at master · abseil/abseil-cpp
Abseil Common Libraries (C++). Contribute to abseil/abseil-cpp development by creating an account on GitHub.
Одна из проблем, которая меня ломает в последнее время, и я её вижу не в первый раз -- почему мы порой не видим прямой экономии денег от оптимизации ресурсов? Я прям сильно погрузился, что не так с некоторыми проблемами и, к сожалению, у меня не появилось хороших ответов.
Пусть есть движок обработки данных. Пусть есть X машин (порядка сотен тысяч), это лимит для одной стадии обработки для одного пользователя -- дальше начинаются проблемы с координацией. Мы смогли подвинуть этот лимит до 1.1X машин, который мы сильно оптимизировали, это был большой проект. Мы увидели, что координирующему мастеру стало полегче, то есть мы можем больше скейлиться, больше аллоцировать ресурсов. Мы увидели, что некоторым топ пользователям стало легче.
Знаете что дальше происходит? Некоторые из топ пользователей, увидев, что есть запас, просто загрузили в движок больше данных.
В итоге наши оптимизации практически не видны после месяца, пользователи могут скейлиться больше.
А за машины мы платим столько же. В итоге приходилось идти к пользователям и спрашивать, а каких данных они добавили, что они стали утилизировать на 10% больше.
Тут начинаются всякие tradeoffs, мол, мы увиличили качество на 0.1, ведь за железо столько же платим.
И вице-президентам это очень сложно объяснить -- почему инфраструктура занимает столько же? Вы что, ничего не делаете? Приходится ходить по пользователям, и спрашивать, почему они стали больше обрабатывать -- их ответ: "потому что нам показалось, что инфраструктура позволяет".
И здесь ничего кроме как бегать за ними невозможно придумать. Можно нормализировать по количеству данных и тд, но эта метрика тоже не самая стабильная.
Такое же вы могли заметить и с Google Chrome. Мы за несколько лет соптимизировали background вкладки на двузначное число процентов. Люди не сильно это заметили. Но мы зато заметили, что на двузначное число процентов background вкладок от пользователей стало больше :)
В Яндексе я тоже помню, что при оптимизации поиска на 10ms, мы видели больше запросов в секунду, потому что людям нравится, когда всё быстро. Когда всё быстро, они склонны этим больше пользоваться.
И тут возникает вопрос, а где остановиться? А нужно ли инфраструктуру оптимизировать до коленья? Может быть, наоборот, сделать чуть медленнее, чтобы был запас на тяжелые времена.
Пока я вижу ответ только в SLO, если мы договорились, что что-то работает счастливо для людей, то не обязательно при оптимизации мы увидим сокращение расходов на инфраструктуру.
Только вот команда, которая увеличила качество на 0.1, получила хедкаунт и славу, а нам пришлось объяснять, что мы то соптимизировали, нормализованная метрика улучшилась. Только расходов мы не сократили. А мерить железо и доллары на счастье людей очень тяжело и не в нашей компетенции
В комментах подсказали, что это https://en.wikipedia.org/wiki/Jevons_paradox
Пусть есть движок обработки данных. Пусть есть X машин (порядка сотен тысяч), это лимит для одной стадии обработки для одного пользователя -- дальше начинаются проблемы с координацией. Мы смогли подвинуть этот лимит до 1.1X машин, который мы сильно оптимизировали, это был большой проект. Мы увидели, что координирующему мастеру стало полегче, то есть мы можем больше скейлиться, больше аллоцировать ресурсов. Мы увидели, что некоторым топ пользователям стало легче.
Знаете что дальше происходит? Некоторые из топ пользователей, увидев, что есть запас, просто загрузили в движок больше данных.
В итоге наши оптимизации практически не видны после месяца, пользователи могут скейлиться больше.
А за машины мы платим столько же. В итоге приходилось идти к пользователям и спрашивать, а каких данных они добавили, что они стали утилизировать на 10% больше.
Тут начинаются всякие tradeoffs, мол, мы увиличили качество на 0.1, ведь за железо столько же платим.
И вице-президентам это очень сложно объяснить -- почему инфраструктура занимает столько же? Вы что, ничего не делаете? Приходится ходить по пользователям, и спрашивать, почему они стали больше обрабатывать -- их ответ: "потому что нам показалось, что инфраструктура позволяет".
И здесь ничего кроме как бегать за ними невозможно придумать. Можно нормализировать по количеству данных и тд, но эта метрика тоже не самая стабильная.
Такое же вы могли заметить и с Google Chrome. Мы за несколько лет соптимизировали background вкладки на двузначное число процентов. Люди не сильно это заметили. Но мы зато заметили, что на двузначное число процентов background вкладок от пользователей стало больше :)
В Яндексе я тоже помню, что при оптимизации поиска на 10ms, мы видели больше запросов в секунду, потому что людям нравится, когда всё быстро. Когда всё быстро, они склонны этим больше пользоваться.
И тут возникает вопрос, а где остановиться? А нужно ли инфраструктуру оптимизировать до коленья? Может быть, наоборот, сделать чуть медленнее, чтобы был запас на тяжелые времена.
Пока я вижу ответ только в SLO, если мы договорились, что что-то работает счастливо для людей, то не обязательно при оптимизации мы увидим сокращение расходов на инфраструктуру.
Только вот команда, которая увеличила качество на 0.1, получила хедкаунт и славу, а нам пришлось объяснять, что мы то соптимизировали, нормализованная метрика улучшилась. Только расходов мы не сократили. А мерить железо и доллары на счастье людей очень тяжело и не в нашей компетенции
В комментах подсказали, что это https://en.wikipedia.org/wiki/Jevons_paradox
Wikipedia
Jevons paradox
economical theory that increased efficiency in use of a resource also tends to increase consumption of that resource
Одна из оптимизаций в регулярных выражениях, поисках по строкам и подобных state transition алгоритмов заключается в достаточно хитрой оптимизации инструкций.
Пусть у вас есть какой-то граф, по которому надо ходить в зависимости от одного из 255 символов:
Вы по нему будете ходить как-то в роде:
Одна из оптимизаций может заключаться в том, чтобы склеить NUM_STATES в один или несколько регистров. Скажем, если у вас битность ваших стейтов максимум 64 / NUM_STATES, то вы можете поместить это всё в один регистр и тогда таблицу и переход по состояниям графа можно описать как:
Тем, что на самом деле мы можем предпосчитать state * 6, когда будете создавать таблицу переходов. Тогда переход вообще будет выглядеть как
Инструкция shrx занимает 1 такт, в итоге мы получаем алгоритм, который проходит по графу за 1 такт на символ, когда у вас есть граф переходов, и получается
1. Если всего вершин не более 10
2. Вы можете предпосчитать таблицу переходов умножая на 6
3. Без SIMD ходить по графу за 1 такт на символ
Это невероятно мощное свойство, потому что вы можете так представить
1. Поиск по строке очень многих строк (надо чтобы строка, по которой ищете была не очень длинной (порядка 9 символов (плюс 1 для обозначения терминального стейта))
2. Проверка на ASCII: всего 2 стейта, ASCII или нет
3. Регулярные выражения с не очень большим автоматом в 10 стейтов (ДКА/DFA)
4. Ходить по деревьям Хаффмана и раскодировать данные, если стейт не очень большой
Как ни странно, это огромное количество человеческих юзкейсов. Понятное дело есть SIMD, который старается искать меньше, чем за 1 такт на символ, но описанное сверху свойство показывает, что можно писать на чистом C и получать невероятную скорость.
Количества бит можно выбирать другие: например, без предосчёта BITS_PER_STATE = 4, NUM_STATES = 16, но тогда будет 2 такта на символ, что всё ещё лучше, чем адресоваться к памяти. Можно 2 регистра на state. Играться можно много.
Такая оптимизация есть в RE2, рассматривается в Golang и вообще является достаточно мощной техникой перевода ДКА на инженерный код.
В RE2 ещё забавное происходит, что если у вас есть какое-то регулярное выражение, то оно вряд ли использует много символов, скорее всего оно использует единичные символы и какие-нибудь range символов ([0-9], [a-z] и тд). Из-за этого в RE2 происходит так называется консолидация алфавита, где алфавит преобретает цвета -- range в роде [0-9] становится одним символов, в подстроках типа
Эта статья основана на блоге pervognsen.
Godbolt на код из RE2
Пусть у вас есть какой-то граф, по которому надо ходить в зависимости от одного из 255 символов:
Вы по нему будете ходить как-то в роде:
uint8_t table[256][NUM_STATES];
uint8_t state;state = table[input[i]][state];
То есть если у вас есть state, символ, вы идёте по таблице инструкций от символа и переходите по state. Так можно делать в цикле, так одна из проблем заключается в том, что мы должны 2 раза обратиться к памяти, что в целом не очень хорошо, так как обращения к памяти достаточно тяжелые.Одна из оптимизаций может заключаться в том, чтобы склеить NUM_STATES в один или несколько регистров. Скажем, если у вас битность ваших стейтов максимум 64 / NUM_STATES, то вы можете поместить это всё в один регистр и тогда таблицу и переход по состояниям графа можно описать как:
uint64_t table[256];
state = (table[input[i]] >> (state * BITS_PER_STATE)) & ((1 << BITS_PER_STATE) - 1);
Если выбрать BITS_PER_STATE = 6, то в один регистр можно запихать 10 стейтов (6 * 10 < 64 < 6 * 11) и тогда переход будет записан какstate = (table[input[i]] >> (state * 6)) & 63
Чем это выражение хорошо?Тем, что на самом деле мы можем предпосчитать state * 6, когда будете создавать таблицу переходов. Тогда переход вообще будет выглядеть как
old_state * 6 = ((table[input[i]] >> state) & 63)
В итоге это эквивалентно выглядит какstate = table[input[i]] >> (state & 63); // bits are lowered automatically
...
return state & 63; // lower the bits
Прелесть такого shift алгоритма в том, что на x86 оно транслируется в инструкцию shrx (сдвиги и так делаются по модулю 64)Инструкция shrx занимает 1 такт, в итоге мы получаем алгоритм, который проходит по графу за 1 такт на символ, когда у вас есть граф переходов, и получается
1. Если всего вершин не более 10
2. Вы можете предпосчитать таблицу переходов умножая на 6
3. Без SIMD ходить по графу за 1 такт на символ
Это невероятно мощное свойство, потому что вы можете так представить
1. Поиск по строке очень многих строк (надо чтобы строка, по которой ищете была не очень длинной (порядка 9 символов (плюс 1 для обозначения терминального стейта))
2. Проверка на ASCII: всего 2 стейта, ASCII или нет
3. Регулярные выражения с не очень большим автоматом в 10 стейтов (ДКА/DFA)
4. Ходить по деревьям Хаффмана и раскодировать данные, если стейт не очень большой
Как ни странно, это огромное количество человеческих юзкейсов. Понятное дело есть SIMD, который старается искать меньше, чем за 1 такт на символ, но описанное сверху свойство показывает, что можно писать на чистом C и получать невероятную скорость.
Количества бит можно выбирать другие: например, без предосчёта BITS_PER_STATE = 4, NUM_STATES = 16, но тогда будет 2 такта на символ, что всё ещё лучше, чем адресоваться к памяти. Можно 2 регистра на state. Играться можно много.
Такая оптимизация есть в RE2, рассматривается в Golang и вообще является достаточно мощной техникой перевода ДКА на инженерный код.
В RE2 ещё забавное происходит, что если у вас есть какое-то регулярное выражение, то оно вряд ли использует много символов, скорее всего оно использует единичные символы и какие-нибудь range символов ([0-9], [a-z] и тд). Из-за этого в RE2 происходит так называется консолидация алфавита, где алфавит преобретает цвета -- range в роде [0-9] становится одним символов, в подстроках типа
bar, лишь 3 символа, поэтому они будут покрашены отдельными цветами. В итоге такая эвристика сильно уменьшает алфавит, количество состояний и помогает использовать оптимизацию, описанную сверху, чаще.Эта статья основана на блоге pervognsen.
Godbolt на код из RE2
GitHub
re2/re2/prog.cc at main · google/re2
RE2 is a fast, safe, thread-friendly alternative to backtracking regular expression engines like those used in PCRE, Perl, and Python. It is a C++ library. - google/re2