Какое-то время назад memorysafety.org объявил о конкурсе по повышению производительности rav1d — порта AV1-декодера dav1d на Rust.
Моя фамилия Равид, совсем как название декодера, поэтому я решил, что будет забавно попробовать (хоть я и, вероятно, не смогу участвовать в конкурсе).
Эта статья посвящена двум найденным мной небольшим улучшениям производительности (первый PR, второй PR) и рассказу о том, как я их нашёл.
Я не говорю о навыках или о знаниях, равно как и не пытаюсь внушить миру идею о необходимости оптимизации производительности. Наш мир и без этого поставил во главу угла ускорение всего и вся. Оптимизация производительности кода — это тяжёлый труд из-за того, что речь идёт о задаче, природа которой диктует использование при её решении метода грубой силы — полного перебора вариантов — и ничего с этим не поделаешь.
Статья, которую вы читаете — это, отчасти, рассуждения о том, сколько огорчений мне приносит оптимизация кода. Но я, кроме того, попытаюсь дать здесь практические советы, которые, надеюсь скрасят путь тем, кто идёт дорогами оптимизации.
Привет! Это снова Максим из Яндекс Браузера. Мы с командой продолжаем делиться историями об интересных и неочевидных оптимизациях производительности, которые внедряем в наш браузер. В прошлый раз мы писали о том, как улучшили стабильность GPU‑процесса, воспользовавшись оптимизациями в драйверах видеокарт, сделанными специально для Google Chrome. А сегодня речь пойдёт об ускорении старта нашего браузера на Windows.
лучшие 10 продвинутых хитростей Python, то вы найдёте кучу постов или статей на LinkedIn с обзором тривиальных (но всё же полезных) вещей типа генераторов или кортежей.
Я написал на C# консольный клон Wordle, но попытался сделать двоичный файл максимально крошечным.
Я взял популярную игру Wordle с такими правилами:
Нужно за шесть попыток угадать слово из пяти букв. После ввода каждого варианта цвет букв будет меняться, показывая близость догадки к загаданному слову.
Для каждой попытки уменьшения двоичного файла мы создадим отдельный проект, чтобы удобно было сравнивать предпринятые действия.
В работе с консолью мне помогла игра Console Games - Snake
Проект запускается в новой консоли dotnet.
Зимой 2024 года я восстанавливал IBM PS/1 486-DX2 66Mhz, «Mini-Tower», model 2168. В подростковом возрасте я мечтал о таком компьютере, но не мог себе его позволить. Не могу выразить словами, насколько меня радовала работа над этой машиной.
Как только мне удалось его запустить, я сразу же провёл бенчмарк одного ПО.
Как уместить словарь размером 250 КБ в 64 КБ ОЗУ с возможностью выполнения быстрого поиска? Для справки: даже современные методики сжатия наподобие gzip -9 не могут сжать этот файл до размера меньше 85 КБ.
В 1970-х Дуглас Макилрой столкнулся с этой непростой задачей при реализации проверки правописания для Unix в AT&T. Из-за ограничений компьютера PDP-11 весь словарь должен был умещаться всего в 64 КБ ОЗУ. Кажется, подобную задачу решить невозможно.
Вместо того, чтобы использовать стандартные методики сжатия, Дуглас воспользовался преимуществами свойств данных, разработав алгоритм сжатия, отличавшийся от теоретического минимума сжатия всего на 0,03 бита. И по сей день этот рекорд остаётся непревзойдённым.
История spell в Unix — это не только любопытный исторический факт. Это мастер-класс по проектированию в условиях жёстких ограничений: анализа первооснов задачи, применения математических наблюдений и проектирования изящных решений, работающих в условиях строгого дефицита ресурсов.
Итак, теперь у нас есть первая приблизительная оценка видимости листьев из порталов, хранящаяся в массиве mightsee каждого портала. Вычислять, что именно видно через последовательность порталов, сложно, поэтому мы вместо этих вычислений используем «консервативную» оценку. Она ни за что не скроет лист, который должен оставаться видимым.
«Это просто задача отсечения»
Свет внезапно выключается. Вы сидите в огромном конференц-зале. Кто-то включает проектор. На экране сам Майкл Абраш! Похоже, это знаменитый доклад Quake Postmortem с GDC 1997.
Он говорит о порталах.
Мы берём плоскости отсечения, ограничивающие максимальный объём видимого, и отсекаем их по всё более дальним порталам, пока они не пропадут.
Узнайте, почему большие TypeScript-проекты начинают "захлёбываться" от рекурсивных типов и обилия импортов, и как с помощью правильной структуры монорепы, настройки tsconfig и диагностики ускорить время компиляции и работу IDE. Рассматриваем инструменты, параллельную сборку, оптимизацию рекурсивных типов и прочие техники, которые помогут сохранить ваш проект быстрым и удобным.
Деление — достаточно затратная операция. Например, на CPU Cannon Lake задержки 32-битного деления находятся в интервале 10-15 тактов, а на Zen4 — 9-14 тактов. Задержки 32-битного умножения на обоих CPU составляют 3-4 такта.
Ни в одном из популярных ISA SIMD (SSE, AVX, AVX-512, ARM Neon, ARM SVE) нет целочисленного деления, оно есть только в RISC-V Vector Extension. Однако во всех этих ISA есть деление с плавающей запятой.
В этой статье мы представим два подхода к реализации SIMD-деления 8-битных беззнаковых чисел.
Современное оборудование невероятно быстрое. M1 Max, на котором я пишу эту статью, работает с частотой 3,2 ГГц. То есть 3,2 МИЛЛИАРДА тактов в секунду. Однако Microsoft Teams требуется 3 секунды, чтобы открыть ссылку, и я отказываюсь верить, что для открытия ссылки требуется 9,6 МИЛЛИАРДА тактов. Очевидно, я упрощаю, но смысл остаётся прежним: как так получается, что оборудование становится быстрее, а приложения — только медленнее?
«Потому, что мы выполняем гораздо больше задач». Так считает любитель позднего капитализма. Позвольте объяснить.
Превосходный пример мощи современного «железа» — это видеоигры. Я могу симулировать огромные 3D-среды с физикой и освещением, полученным трассировкой лучей, при этом играть в реальном времени с друзьями из других штатов и даже стран; вполне доступный компьютер потребительского уровня выдаёт 124 миллионов пикселей в секунду1.
[1. 1080p при 60 FPS = 1920 × 1080 × 60 = 124416000]
Можно посмотреть и в обратном направлении: людям удаётся запускать DOOM на почти любом устройстве с процессором: на калькуляторах, iPod, фотокамерах. Невероятно маломощные, зачастую одноразовые устройства обладают достаточными вычислительными ресурсами, чтобы выполнять сверхсовременную на 1993 год игру. Это не особо удивляет, ведь прошло три десятка лет, но показывает, какой путь мы проделали.
Один из моих старых постов о strlcpy недавно вызвал обсуждения на различных форумах. Вероятно, с этим как-то связан выпуск новой версии POSIX. Многие авторы приводили один контраргумент, который я слышал и раньше:
«В общем случае, когда исходная строка умещается в конечный буфер, strlcpy будет обходить строку только один раз, а strlen + memcpy будут обходить её дважды».
Под этим аргументом скрывается допущение о том, что однократный обход строки выполняется быстрее. И, честно говоря, это вполне разумное допущение. Но справедливо ли оно? Об этом мы и поговорим в статье.
Примечание: основная часть изложенного в статье относится к реализации SMT компании Intel, также называемой гипертредингом (hyper-threading). Она основана на научной статье компании, опубликованной в 2002 году.
Я бросил себе вызов: симулировать 1000000 (миллион) частиц на чистом Javascript на телефоне, используя только CPU и добившись 60 FPS.
Поехали.
Задача не особо сложна, если выполнять всю работу на GPU, но правило гласит, что нужно пользоваться только CPU, при этом работая на JS, так что никакого WASM.
В этой части я приведу ещё несколько примеров того, как нам мешает скачивание обновлений внутри приложений.
Пример 1: обновления macOS
Ни для кого не секрет, что обновления macOS огромны. Иногда это раздражает даже дома, но на Южном полюсе ситуация гораздо хуже.
Размер патча минорного обновления macOS обычно имеет размер от 0,5 до 1,5 гигабайтов. Патчи с крупными обновлениями иногда занимают до шести с лишним гигабайтов. Дополнительные инструменты, например Xcode, часто весят несколько гигабайтов.
Пару недель назад я прочитал о запавшем мне в душу челлендже по обработке миллиарда строк, поэтому захотел решить его на Go.
Я немного опоздал, соревнования проводились в январе. И на Java. Меня не особо интересует Java, зато давно интересует оптимизация кода на Go.
Этот челлендж был очень прост: обработать текстовый файл названий метеорологических станций и температур, и для каждой станции вывести минимальное, среднее и максимальное значение. Чтобы упростить задачу, было ещё несколько ограничений, однако я проигнорировал те, что относятся только к Java.
В ноябре 2022 года мы задали себе задачку: можно ли запрограммировать анимацию, воспроизводимую в режиме реального времени как обычный короткий мультик, но с условием, что файл должен быть не больше 8 килобайт. При этом цель считалась бы достигнутой, если бы у нас получилась нормальная графика, анимация, режиссёрская и операторская работа, а ещё подходящая музыка. Да, 8 килобайт — на секундочку, в два с лишним раза меньше этого поста. Мы не представляли, насколько это вообще возможно, так что оставалось только попробовать.
В апреле 2023 года, спустя несколько месяцев работы, мы, наконец, выкатили ленту Барашек и цветок. Можете сами скачать его или проследить на YouTube ход выполнения программы.
Нас многие спрашивали, как нам удалось создать нечто подобное. В статье будут объяснены технические детали и те ограничения, которые пришлось учитывать при проектировании перед выводом этого проекта в продакшен. Кроме того, мы выложили весь исходный код на GitHub.