Experimental chill

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 доступным, просто сложно. Иметь принципы как Википедия при отсутствия контроля публикуемой информации непонятно. Можно ли нам, Гуглу что-то тут сделать изнутри, неясно, можно ли сделать прорыв в релевантности, неясно. Что нужно людям, неясно. Что такое правда и ложь, неясно. Это не значит, что не надо стараться. Это действительно сложная задача, мы устали от Гугла и Яндекса, что-то новое точно появится. Пока мы упёрлись в локальным максимум.

1. Мы тут недавно выложили fuzztest. В целом если вы используете GTest, то вы можете написать что-то вроде 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, посмотрим, вольют или нет. Или другую эвристическу придумать можно.

Неожиданно для себя и людей вокруг меня, я решил поменять команду. После пары лет в Flume/MapReduce infrastructure and efficiency, я столько возложил на свои плечи, что сейчас достаточно сложно стало тащить на себе то, что взял, поэтому пытаясь что-то починить в своем подходе, я выбрал самый простой -- полностью свалить этот груз. Ухожу я на забавной ноте, когда я стал понимать наш сервис, интерфейсы очень хорошо, и кажется почувствовал, что пора. Плюс я уже не могу терпеть очень поздние встречи с Долиной, в этот раз Нью-Йорк, полегче из Лондона будет общаться. Перехожу я в команду Efficiency League/Data center efficiency/Bare metal efficiency, где буду заниматься тем, о чем пишу здесь, в блоге: перформансом всего, чего можно дотянуться в Google: от latency Raft и поиска до software/hardware co-design. С этой командой я много работал, пора рассказать Google пару историй, попробовать десяток идей с полной поддержкой от менеджемента. Плюс в момент рецессии датацентры сильно ужимаются, так что любые выигранные ресурсы сейчас как никогда кстати. В целом этот год какой-то сложный и странный. Я стал больше жить, привел свою жизнь в ещё больший порядок, и вечера стали важным средством для того, чтобы эту самую жизнь жить, а не писать код. Все мы меняемся, я не исключение. Я думаю эта история на ещё год-два, но самое слабое место программистов -- планирование, поэтому как пойдет, так и будет.

В последние несколько лет не слишком много происходит интересных компиляторных оптимизаций, которые помогают всем, тем не менее от версии к версии мы видим в районе 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 пишет про эвристику, которая не супер идеальна, но просто хороший дефолт: 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 Первое условие говорит, что ждать подготовки данных для cmov иногда бывает долго, а второе условие говорит, что если мы не выбираем какой-то операнд, то он не должен быть слишком тяжелым и предсказание branch не должно быть слишком хорошим (рандомные данные самое оно). В итоге даже прототип дал 0.5-1% поиска гугла. Я думаю уже зарелизили. Мораль этой истории показала, что не было одного или даже десяти мест, которые всё исправили, а исправились в районе пары-тройки сотен мест, которые набрались и суммарно дали такой прирост. Что не может не радовать, потому что я долго верил, что компиляторный перф сильно зависит от топ $МАЛОЕ_КОЛВО функций. Эта история поучительна и для меня. Практика:В clang я обычно при написании кода если хочу cmov, то пишу тернарный оператор, а не if statement uint64_t val = cond ? x : y; // usually cmov if (cond) { val = x; } else { val = y; } // usually branch Profile driven protobuf inlined string В протобуфах есть поля вида string. Исторически они замаскированы под указателями, потому что люди чаще поля не используют, чем используют, а также чуть удобнее аллоцировать на общих кусках памяти под названием арены. Проблемы указателей, что их надо разыменовывать, и за это мы платим много. Если включить обычный std::string на всех, будет плохо, протобуфы разрастутся, аллокации на аренах будут сложнее и тд. Прелесть в том, что некоторые строки очень маленькие и очень горячие, поэтому Small String Optimization может работать лучше, чем разыменовывание указателя. Решение простое, давайте мы посэмплим в проде размеры и rate с которым мы обращаемся к тем или иным полям (просто stacktraces) и перекомпилируем горячие и маленькие строки в InlinedStringField. Снова в районе 0.5-1% выигрыша распределенного примерно по всему бинарю. Мы зарелизили InlinedStringField, но полный e2e профиль и оптимизации пока непонятно как. В целом, я думаю, что если очень надо, логику написать можно. Красиво, две истории, когда вещи stack up среди сотен мест и дают хороший буст.

Тут недавно стукнуло как я 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. Дальше -- больше, куда мы денемся, прогресс не остановить, и все мы к нему причастны, куда ни посмотри, везде можно принести пользу

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 байт, либо найду её наконец-то. Даже если все найденные свалятся, то никто не знает, может, я просто не добавил нужную инструкцию в перебор. Мораль: перебирать ассемблер адски тяжело. Отсеивать плохие хэш-функции быстро адски тяжело. Ускорения в оба направления могут помочь нам дать лучшие хэш-функции. Пока вопрос открыт. Продолжаю рисёрч.

Так как я уже не могу закончить этот пост неделю, напишу, что есть. Главное -- писать, остальное не так важно. Что такое хорошая хеш-функция? Этот вопрос на первый взгляд всегда кажется более научным, чем практическим. Да, в теории есть какие-то критерии. Даже пытались выстроить 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 инстручная последовательность

Store Forwarding penalties Представьте вы пишете по указателю данные. Далее по этому указателю или где-то рядом вы читаете эти данные. Современные процессоры нынче очень хитрые и могут не читать память при такой инструкции. Это называется «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 :)

Это будет не очень технический пост. Как человек немного олдскульного типа для которого сильно важен текст, я с огорчением смотрю, как текстовый поиск по интернету потихоньку начинает проигрывать 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

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, наверное. Чёт сумбурно, но продуктивность хлещет, начинается мой любимый сезон года, осень, зима, когда можно уютно что-то делать

Для выполнения работы (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. Делаете по возможности структуры более компактными 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 помогают лишь держать это число на плаву. Тот, кто поймёт эту историю лучше всего, будет платить за датацентры меньше всего денег. В эпоху рецессии кажется это может быть ещё более важно. Постараюсь сделать серию из постов про то, как увеличивать полезность при помощи уменьшения процессинга памяти. Тут много нетривиальных компромиссов.

На дворе 2022 год Мы находим оптимизации в mem*/str* функциях на мажорных платформах в 20%, которые были доступны как лет 10 Да, это патч в glibc. В целом история такая: на x86 достаточно легко переходить из векторного кода в скалярный -- если есть вектор…