Experimental chill

2022-08-29 23:01:42 А вот и блог в армах про 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 Открыть/Комментировать

2022-08-27 19:34:00 Рубрика: интересные компиляторы

Поговорим просто про сложение. На 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 Открыть/Комментировать

2022-08-20 18:06:55 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, все дела.

Приятная для чтения статья, много всяких примеров можно придумать в голове Открыть/Комментировать

2022-08-11 20:02:04 Забавный рисёрч вышёл от нас про 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, потому что кто-то да умный найдётся как написать красиво и элегантно (или не очень, как уж пойдёт). Перформанс и корректность можно померить в отличие от красоты кода. Хорошо, что эти вещи иногда коррелируют.

В статье вот пример с тем, что есть решение посортировать -> выдать ответ или положить в кучу, но зато выйти из цикла пораньше. В реальности я бы выбрал второе, если мне был бы важен перформанс или первое, если бы я хотел элегантности. Как правильнее -- непонятно, зато понятно, как улучшить решение в С раз.

Просто красиво, как использовать -- пока непонятно Открыть/Комментировать

2022-08-08 13:13:46 Далёкая память

В датацентрах давным давно уже проблемы с тем, чтобы закупать память -- она очень дорогая. Мы по сравнению с 2011 годом в Борге хоть и видим увеличение утилизации на 5-20%, но медианная утилизация остаётся на уровне 60% [1].

Из-за этого в статьях прошлых лет (года с 2018) сильно развивалось понятие далёкой памяти -- давайте мы абстрагируем память ещё, теперь будем забирать данные с помощью сети из других машин. Самые известные -- Hydra [2], мы на OSDI'22 в Google вышли с Carbink [3]. Обе статьи решают нужные нам задачи:

* Можем достигать лучшей утилизации и уменьшить простой
* Приложения могут аллоцировать больше памяти, чем одна машина

Проблемы очевидны: забирать по сети намного тяжелее, отказоустойчивость не так просто сделать (хранить память на SSD не подходит из-за ещё более медленных восстановлений), модель _памяти_ становится не очень ясной.

Для того, чтобы достигнуть репликации фактора два, можно реплицировать на три узла. Память дорогая и так делать не стоит. Поэтому лучше взять Erasure Coding: в самом простом случае это выглядит как поделить данные пополам, взять xor, теперь у нас есть 3 части, при выпадении любой, можно восстановить все данные. В итоге занимаем x1.5 места, но фактор репликации можно достигнуть любой. За Erasure Codes стоит большая теория, но основная идея, что мы делим данные на N несколько частей, считаем M дополнительных через линейное преобразование. При выпадении любых M, мы можем посчитать обратное линейное преобразование. Математика говорит, что матрицы существуют при почти всех разумных N и M, которые обладают таким свойством. Обычно выбирают что-то из пар (3,2), (4,3), (12,9).

Проблема в том, что когда вы аллоцируете память, её поделить даже на 3, 4 или 12 частей тяжело, так как аллокации объектов не очень большие и erasure codes начинают тормозить. Мы в Google вышли со статьёй о TCMalloc, где мы храним такие объекты в так называемых spans, много мелких объектов хранятся в одном чанке в пару мегабайт. Мы решили делать так же -- мы будем синхронизировать spans объектов (а также erasure codes на множество spans, что мы назвали spanset), а не каждый кусок. Это разгружает сеть, так как объекты в erasure codes находятся внутри спанов, а не разделены. Если ничего не выпало, из одного узла возьмутся данные, в худшем случае при падении узлов читать надо всё.

Изменения происходят в background тредах, если память становится холодной, она помещается в span, инвалидируется по сети, замещается. Узлы, которые отвечают за саму память, время от времени делают compaction, чтобы удалить ненужные spans. Если приложение memory intensive, это увеличивает нагрузку на сеть.

Использовать spans в пару мегабайт имеет лишние ненужные байты. В Carbink мы в итоге насчитали, что используем на 35% больше памяти, чем в Hydra, но зато сильно уменьшили 50 и 99 квантили (в ~1.2-1.5 раз) доступа и throughput.

В статье много интересных деталей -- например, как помечать биты в указателях, как брать RCU lock на указатели, которые приходят по сети и тд.

Меня, конечно, больше интересует вопрос о том, когда это можно ждать в датацентрах? Ну, в худшем случае никогда, в лучшем через 2-3 года, когда software и hardware stack будет к этому готов, потому что использование памяти по сети требует

* Писать немного кода, чтобы использовать такие указатели, прозрачно через аллокатор пока тяжело это сделать. Это кстати не особо большая проблема, сервисы обычно имеют понятное использование больших буфферов
* Perf будет страдать, надо будет аккуратно выбирать пользователей для этого, которым важен throughput, инфраструктура типа MapReduce/Spanner может подойти
* Можно сжимать холодую память в этой далёкой памяти, как делает, скажем, zswap, экономить ещё

Хорошая статья о том, как можно увеличивать утилизацию памяти, когда вы очень большие, ну и мы наконец-то поделились, что думаем о far memory и инвестируем research туда :)

[1] Borg: the next generation
[2] Hydra : Resilient and Highly Available Remote Memory
[3] Carbink: Fault-Tolerant Far Memory Открыть/Комментировать

2022-08-03 02:23:21 В C++, вы можете создавать объекты в классе и объекты, которые задекларированы последними, могут принимать себе параметры предыдущих.

state_ зависит от dep_ в примере. При деструкторе state_ разрушится, потом dep_ разрушится. Всё хорошо. Объекты разрушаются в обратном порядке. Так учили ... всегда и везде, да? :)

Так вот, при default move операторе мы сначала делаем move на dep_, потом на state_ и между move мы получаем state_ с вероятно некорректной зависимостью (вектора или умные указатели вызывают деструктор при move dep_).

Бабах, пруф https://gcc.godbolt.org/z/xG14Wj3E7

Фикс: писать свой move оператор, где вы сначала делаете move на state_, потом на dep_, то есть в обратном порядке.

Скажите же, очень легко написать = default здесь, думая, что язык сам делает всё правильно?

Пойду попишу на расте, что ли Открыть/Комментировать

2022-08-03 02:23:14 Опять наврал, но на этот раз, пусть будет, #челоперф, продуктивность людей тоже сильно влияет

Забавно наблюдать за собой в карьерном плане. В последние 3 дня я был очень тревожным, прям до невозможности, я заболел и была температура.

Выписал от чего такая тревожность возникла, помимо всяких личных мелких проблем, которые не вызывают такой уровень, выписал парочку:

1. Я разломал прод.

2. Я почему-то начал бояться, что не вывезу одну задачу. И если честно, я её реально не вывожу. Она важная, а я не знаю как её решить уже несколько месяцев, хотя я придумал идею аж два года назад. Страшно увидеть, что идея не работает :)

Казалось бы, мелочи, кто не ломал, и бывают сложные задачи. Притворяться, что у меня идеальная карьера не хочется и это, как бэээ, не правда. Успецкий мужицкий патриархальный успех с промо каждые 6 месяцев приправленный L7 до 28 лет и хатой в центре Лондона это не про меня. И меня, кстати, скорёжило недавно от вопроса, мол, когда следующее промо. Почему это логично меня спросить, что я как будто, должен этого хотеть, я не знаю. Всё само придёт, я просто это знаю, я не оптимизирую свою карьеру очень сильно, и никому не советую, это опасный риск.

Короче, я просто херовенько переживаю неудачи. Помогают народные методы, как

* Поговорить с менеджером
* Притормозить
* Взять отпуск
* Пописать код на Rust
* Починить прод, который сломал, хотя бы откатить
* Покушать вкусной еды

Ну и дальше ковырять, почему задача кажется невыполнимой. Потом возникают всякие интересные особенности

* Мне очень комфортно работать в командах 2-3 человека. Проект/задача включает в себя 5 человек, кто-то да работает не так, как хочу, не делает чего-то. Мне не хватает ни сил, ни желания руководить этим хаосом, когда люди не очень стабильны. Среди 5 людей очень часто кто-то не очень стабилен.
* Люблю близкое общение. Меня похвалили за менторство джунов. В команде на много людей работаю плохо. Check
* Когда у меня отнимают код и заставляют писать много псевдотехнических доков/рисовать презентации, хочется прям выбросить ноутбук и не приходить на работу. Check

Поболтали, поняли, что на самом деле брать много людей пока не надо. Можно расти работая близко с парой людей над проектами. Хочешь Individual Contributor Track -- пожалуйста, дорога посложнее, зато ты счастливее.

Да, счастливее. Буквально за полдня температура снизилась, завтра отдохну до конца и пойду снова херачить, может, дам проекту провалиться. It's fine. Пусть горит, я знаю как ещё в ста местах принести пользы. Пока бизнес позволяет это, это нормально.

Я давно замечаю, что люди самые продуктивные, когда всё в порядке с ментальным ощущением себя в мире. Никаких "через себя", "да ты что не мужик/слабый". Да, мир сложнее, и это утопия, если все такими будут. Тем не менее, искать пути сделать себя спокойнее по жизни важны. Расту, учусь, как ладить с собой.

А теперь учу как разломать прод: Открыть/Комментировать

2022-07-29 14:51:39 Ваш PlayStation 5 умножает числа на три в два раза медленнее, чем ваш ноутбук

После релиза Arm машин я попал в дофаминовую яму из которой я стараюсь выходить всякой рутиной, где я помогал разным проектам (в том числе и всякими оптимизациями в Arm). За последнее время я решил перечитать много литературы, писал много документов и мало кода. It's fine, sometimes there are weeks when you understand completely nothing. Две истории, одна стратегическая, другая практическая, но они связаны.

Я понял, что когда делаю свою работу, я очень мало времени уделяю тулингу в перформансе. Скажем, я делаю процентов 20 анализа данных, что медленно, почему медленно, процентов 40 как это соптимизировать, остальные 40 на то, а как эту историю можно обобщить. Скажем, я недавно писал, как одна доп кешлиния в AMD не выучивается процессором, что она не так уж и важна, дальше вопрос, а в чем различия AMD и Intel, если уж посмотреть глобально. Бенчмарки делались на Intel долго, интересно, есть ли пробелы у AMD, можно ли унифицировать, чтобы всем было хорошо. Нашёл ещё одну историю, но она сильно другая:

На x86 умножение на 3 устроено через старую иструкцию LEA (Load Effective Address). Если коротко, эта иструкция умеет вычислять выражения REG1+X*REG2+Y, где X -- 0, 1, 2, 4, 8, а Y не очень большая константа. В итоге чтобы умножить на 3 надо взять REG1==REG2, X = 2. То есть это сумма X и (X << 1), вполне логично и legacy, которое мы за собой оставили. Инструкции mul/imul работают дольше.

Посмотрев на таблицу инструкций я нашёл, что AMD Zen 2 имеет latency 2, когда как абсолютно все Intel latency 1. Proof.

Нашёл пару мест в коде и поправил на что-то более унифицированное, выиграл немного.

Я назвал этот пост ваш PlayStation 5 умножает числа на 3 в два раза медленнее, чем ваш ноутбук для лайков и хайпа. Вопрос, который мне задали несколько раз:

$AUTHOR_NAME, как ты эту херню находишь?

Я скачал все таблицы инструкций и просто подиффал самую большую разницу. И просто сидел изучал, что из этого выходит. И да, что-то вышло. Есть ещё пару различий

* pclmuldqd -- Zen2-3 имеет latency 4, Intel 7. Это означает, что CRC чексуммы надо вычислять по-другому, Erasure кодеки работают медленнее, нашёл CRC вычисление, сравнил, действительно медленнее
* Ещё некоторый SIMD Memory load, но паттерн доступа к памяти проявился и тогда

OH MY GOD, ИСТОРИЯ ПРО КЕШЛИНИЮ MAKES SOME SENSE. Конечно, не сразу, конечно, чтобы её найти съесть много всего, внимательно смотреть. Главный вопрос, который я себе задаю -- а может ли это быть важно? И да, очень часто можно найти на скейле любую историю.

Но я понял, что тулингом/анализом надо заниматься плотно, может быть, даже 50%, ты открываешь интересные инсайты про те или иные истории.

Большой человек из Netflix (а сейчас из Intel) не зря занимался визуализацией через flame graphs, это тулинг, позволяющий что-то понять, мультипликативный фактор новых открытий и понимания. В Google мы семплируем весь прод каждый день, чтобы открыть понимание, происходит ли что-то (а что-то вообще происходит?).

В ближ время хочу заняться двумя вещами в тулинге: иллюстрация всех ассемблерных инструкций, а также хочу написать свой сжимающий кодек отсортированных с random access и поиском, работа Lemire про FastPFor мне кажется слишком простой, а я слишком много знаю про эту тему. Посмотрим, насколько я загорюсь. Сил не хватает, автор походу постарел, гореть чем-то почему-то стало тяжелее за последний год.

След статья про распределённые системы, обещаю :) Открыть/Комментировать

2022-07-19 18:18:27 https://github.com/carbon-language/carbon-lang

Выложили мои коллеги из Google новый язык, совершенно в проекте не участвовал, но очень интересно приживется ли такой язык и нужен ли он обществу

Идея: есть С++, его все не любят. Есть Rust, его как-то все настойчиво любят, но у него приоритеты больше по safety и отсутствия багов. Из-за этого страдает перф

Carbon хочется втиснуться посерединке. Он все ещё небезопасный, зато с коробочными санитайзерами. Такой же быстрый, как и С++, но с модулями, без исключений, c дженериками, без ABI совместимости, с тулингом от LLVM, *с тулзой для миграции с С++* (почти рабочей ).

Можете называть его форком С++, можете называть его неудачной попыткой в Rust. Мне будет интересно, приживется или нет. Может он умрет через полгода, а, может, и будет процветать. Деталей сам знаю мало, пошел читать Открыть/Комментировать

2022-07-16 11:51:27 https://www.meetup.com/clickhouse-london-user-group/events/286891586/

Буду выступать на митапе ClickHouse в среду 20 июля в Лондоне, расскажу про оптимизации Arm для CH, и в целом про Arm чуть чуть

(Опять меня легко купили на рекламу ClickHouse)

Приходите, если можете Открыть/Комментировать