Я создал лексер ассемблера ARM64 (ну, точнее, сгенерировал его из моего собственного генератора парсера, но пост не об этом), обрабатывающий код на Dart вдвое быстрее официального сканера. Этого результата я добился при помощи статистических методик надёжного измерения малых различий в производительности. Затем я провёл его бенчмарк на 104000 файлов и обнаружил, что узким местом был не мой лексер, а ввод-вывод. Это история о том, как я случайно узнал, почему pub.dev хранит пакеты в виде файлов tar.gz.
Подготовка
Я хотел провести бенчмаркинг моего лексера для сравнения его с официальным сканером Dart. В кэше pub на моей машине было 104000 файлов Dart общим объёмом 1,13 ГБ — идеальный тестовый корпус. Я написал бенчмарк, который:
Считывает каждый файл с диска
Выполняет лексинг
По отдельности замеряет время для ввода-вывода и лексинга
Всё очень просто.
Первый сюрприз: лексинг быстр
Вот результаты:
Метрика | Лексер ASM | Официальный Dart |
|---|---|---|
Время лексинга | 2807 мс | 6087 мс |
Пропускная способность лексера | 402 МБ/с | 185 МБ/с |
Мой лексер оказался в 2,17 быстрее. Успех! Но постойте:
Метрика | Лексер ASM | Официальный Dart |
|---|---|---|
Время ввода-выводаtime | 14126 мс | 14606 мс |
Общее время | 16933 мс | 20693 мс |
Общее ускорение | x1,22 | - |
Общее ускорение составило всего x1,22. Ускорение в 2,17 раза, достигнутое моим лексером, было поглощено вводом-выводом. Считывание файлов занимало в пять раз больше времени, чем лексинг.
Второй сюрприз: SSD — не узкое место
В моём MacBook установлен NVMe SSD со скоростью чтения 5-7 ГБ/с. У меня получалось 80 МБ/с, то есть 1,5% от теоретического максимума.
Проблема заключалась не в диске, а в системных вызовах.
При обработке 104000 файлов операционной системе нужно было выполнять:
104000 вызовов
open()104000 вызовов
read()104000 вызовов
close()
То есть больше 300 тысяч системных вызовов. Каждый системный вызов включает в себя:
Переключение контекста из пользовательского пространства в пространство ядра
Учёт ресурсов ядра и проверки разрешений
Переключение контекста обратно в пользовательское пространство
Каждый системный вызов стоит приблизительно 1-5 микросекунд. Если умножить это на 300 тысяч, то мы получим 0,3-1,5 секунды чистого оверхеда ещё до того, как произойдёт дисковый ввод-вывод. Прибавим поиск метаданных файловой системы, обход папок, и становится понятно, куда девается время.
Я попробовал разные решения, но ничего особо не помогло. Отображение файлов в память усугубило ситуацию из-за оверхеда mmap/munmap для каждого файла. Замена чтения файла Dart непосредственными системными вызовами FFI (open/read/close) обеспечило улучшение всего на 5%. Проблема заключалась не в слое ввода-вывода Dart, а в самом количестве системных вызовов.
Гипотеза
В прошлом я несколько раз создавал зеркала pub.dev и заметил, что все пакеты хранятся в виде архивов tar.gz. Я не понимал почему, но моя проблема напомнила мне об этом. Если проблема заключалась в системных вызовах, то решением будет снижение их количества. Что, если вместо 104000 файлов у меня будет 1351 файл (по одному на пакет)?
Я написал скрипт, упаковывающий каждый кэшированный пакет в архив tar.gz:
104000 отдельных файлов -> 1351 архивов tar.gz
1,13 ГБ без сжатия -> 169 МБ со сжатием (коэффициент 6,66)Результаты
Метрика | Отдельные файлы | Архивы tar.gz |
|---|---|---|
Файлы/архивы | 104000 | 1351 |
Данные на диске | 1,13 ГБ | 169 МБ |
Время ввода-вывода | 14525 мс | 339 мс |
Время распаковки | - | 4507 мс |
Время лексинга | 2968 мс | 2867 мс |
Общее время | 17493 мс | 7713 мс |
Ввод-вывод ускорился в 42,85 раза. Чтение 1351 последовательного файла вместо 104000 произвольных файлов снизило время ввода-вывода с 14,5 секунды до 339 миллисекунд.
Общее ускорение составило 2,27 раза. Даже с оверхедом распаковки способ с архивами оказался вдвое быстрее.
Анализируем значения
Ввод-вывод: с 14525 мс до 339 мс
Вот наглядное влияние оверхеда системных вызовов. Снизив количество системных вызовов с 300 тысяч до примерно 4 тысяч (open/read/close для 1351 архива), мы устранили основную часть оверхеда.
Кроме того, последовательное чтение 1351 файла гораздо удобнее для кэша, чем чтение 104000 файлов, разбросанных по файловой системе. Операционная система может эффективно выполнять упреждающую выборку, SSD может выполнять пакетные операции, а страничный кэш остаётся тёплым.
Распаковка: 4507 мс
Распаковка gzip при помощи пакета archive c pub.dev работала со скоростью примерно 250 МБ/с. Теперь она стала новым узким местом. Я не особо трудился над оптимизацией распаковки, возможно, решение на основе FFI с использованием нативной zlib оказажется существенно быстрее. Также могут помочь современные альтернативы наподобие lz4 или zstd.
Коэффициент сжатия: 6,66
Исходный код хорошо сжимается. 1,13 ГБ кода на Dart сжались в 169 МБ. Благодаря этому нужно считывать меньше данных с диска, что помогает даже на быстрых SSD.
Почему на pub.dev используется tar.gz
Этот эксперимент случайным образом объяснил использование на pub.dev такого формата пакетов. При выполнении dart pub get мы скачиваем архивы tar.gz, а не отдельные файлы. Причины этого теперь очевидны:
Меньше HTTP-запросов. По одному запросу на пакет вместо сотен.
Экономия канала. Размер скачиваемых файлов в 6-7 раз меньше.
Ускорение извлечения. Последовательная запись быстрее произвольной.
Снижение оверхеда системных вызовов. И на сервере (нужно передавать меньше файлов), и в клиенте (нужно записывать меньше файлов).
Атомарность. Пакет или полностью скачан, или нет, промежуточные состояния отсутствуют.
Те же самые принципы применимы к npm (tar.gz), Maven (JAR/ZIP), PyPI (wheel/tar.gz) и к практически любому другому менеджеру пакетов.
Более общий вывод
Современные накопители быстры. NVMe SSD могут передавать гигабайты в секунду. Но эта скорость достижима только для последовательного доступа к большим файлам. При работе с тысячами мелких файлов начинает преобладать оверхед системных вызовов.
Это важно для:
Систем сборки. Вы компилируете проект с 10 тысячами файлов исходников? Оверхед файловой системы может превзойти время компиляции.
Обработки логов. У вас есть миллионы маленьких файлов логов? Конкатенируйте их. Именно по этой причине Claude использует JSONL.
Систем резервного копирования. Именно поэтому существуют rsync и tar.
Что бы я сделал иначе
Если бы я продолжил оптимизацию, то:
Использовал бы zstd вместо gzip. Ускорение распаковки в 4-5 с почти такими же коэффициентами сжатия.
Применял бы незапакованные tar для локального кэширования. Даже отсутствие распаковки всё равно снижает количество системных вызовов.
Параллелизировал бы изолированные нагрузки. Одновременная распаковка нескольких архивов несколькими ядрами.
В заключение
Я решил провести бенчмарк лексера и в результате узнал об оверхеде системных вызовов. Лексер был быстрее вдвое, оптимизация ввода-вывода — в 43 раза быстрее.
Приложение: советы читателей
Специфичные для Linux оптимизации
servermeta_net посоветовал два специфичных для Linux решения: отключить speculative execution mitigations (что может повысить производительность в сценариях с большим количеством системных вызовов) и использовать io_uring для асинхронного ввода-вывода. Я прогнал эти бенчмарки в macOS, не поддерживающей support io_uring, но эти возможности Linux кажутся интригующими. Возможно, я опубликую ещё один пост про исследование возможностей оптимизации производительности ввода-вывода в Linux.
king_geedorah подробно объяснил, как io_uring может помочь с этой конкретной рабочей нагрузкой: открыть дескриптор файла папки, извлечь все имена файлов с помощью readdir, затем за раз передать все запросы openat в виде submission queue entry (SQE). Это объединит 104000 последовательных системных вызовов open(), что позволит ядру обрабатывать их конкурентно. Функция io_uring_prep_openat подготавливает такие пакетные операции open. Она больше похожа на примитив «загрузить всю папку в массив дескрипторов файлов», что и нужно в этом случае.
Специфичные для macOS оптимизации
tsanderdev подсказал, что kqueue macOS потенциально может повысить производительность в этом случае. Хоть kqueue и не эквивалентна io_uring Linux (в ней нет пакетного объединения одинаковых системных вызовов через общий кольцевой буфер), она всё равно может обеспечить улучшения по сравнению с синхронным вводом-выводом. Бенчмаркинг я пока не проводил.
Сравнение скорости системных вызовов в macOS и Linux
arter45 отметил, что некоторые системные вызовы macOS может выполнять существенно медленнее Linux, сославшись на Stack Overflow: open() в macOS в четыре раза медленнее, чем в Ubuntu VM. jchw объяснил, что слой VFS Linux агрессивно оптимизирован: он произвольно использует схемы RCU (Read-Copy-Update), чтобы минимизировать конфликты операций с файловой системой, а также применяет агрессивное кэширование dentry. Кроме того, Linux разделяет dentry и общие inodes, а системы BSD/UNIX консолидируют их в структуры vnode. Из этого можно сделать вывод, что мои результаты бенчмаркинга в macOS на самом деле могут преуменьшать проблему оверхеда системных вызовов на этой платформе относительно Linux, или же что пользователи Linux меньше выиграют от решения с tar.gz, потому что у них изначально всё это работает быстрее.
На самом деле проблема в системных вызовах?
ori_b возразил на утверждение о том, что узким местом стал оверхед системных вызовов. На машине с Ryzen вход в режим ядра и выход из него занимает примерно 150 тактов (~50 нс). Даже если переключение режима занимает 1 микросекунду, 300 тысяч системных вызовов займут всего 0,3 секунд из общего времени ввода-вывода (14,5 с). То есть примерно 2%. Вероятно, остальное время тратится на поиск метаданных файловой системы, ресолвинг inode, обход папок и случайные задержки поиска. Даже у NVMe SSD есть ~50-100 микросекунд задержки на каждое произвольное чтение, и 300 тысяч произвольных операций чтения займут основную часть замеренного времени ввода-вывода. То есть более точной формулировкой будет «оверхед на файл», а не «оверхед на системный вызов», потому что затратная часть работы происходит внутри каждого системного вызова, а не в переключении контекста. Также стоит отметить, что ori_b замерял показатели на машине с Linux и Ryzen, где системные вызовы быстрее, чем в macOS (как говорилось выше), что добавляет ещё одну переменную. Пока у меня нет инструментария для анализа того, на что конкретно тратятся эти 14,5 секунды, поэтому я хочу исследовать это в будущем.
Отказываемся от lstat в пользу getdents64
stabbles сообщил, что при сканировании папок можно избежать отдельных вызовов lstat(), использовав поле d_type из getdents64(). В большинстве популярных файловых систем (ext4, XFS, Btrfs) ядро заполняет это поле непосредственно типом файла, поэтому не требуется дополнительный системный вызов для определения того, файл это или папка. Тонкость заключается в том, что некоторые файловые системы возвращают DT_UNKNOWN и в этом случае всё равно нужно вызывать lstat(). В моём случае при сканировании кэша pub это позволит устранить десятки тысяч системных вызовов stat на этапе обхода папок, даже ещё до открытия файла.
Монорепозиторий Go: ускорение в 60 раз благодаря отсутствию дискового ввода-вывода
ghthor поделился похожим опытом оптимизации анализа графа зависимостей в монорепозитории Go. Первоначальное профилирование указало на давление со стороны сборщика мусора, но реальным узким местом оказался ввод-вывод от go list, выполнявшего вызовы stat и чтение с диска для каждого файла. Заменив go list на собственный парсер импорта с использованием стандартной библиотеки Go и на чтение содержимого файлов из блобов git (при помощи git ls-files вместо дисковых вызовов stat), он снизил время анализа с 30-45 секунд до 500 миллисекунд. Это ускорение в 60-90 раз, произошедшее благодаря тому же фундаментальному наблюдению: следует избегать системных вызовов на каждый файл, если можно объединить их или полностью избежать.
packagefs Haiku
smallstepforman рассказал, как Haiku OS решает эту проблему на уровне операционной системы. Пакеты Haiku — это единые упакованные файлы. которые никогда не извлекаются. Вместо этого операционная система использует packagefs — виртуальную файловую систему, представляющую содержимое всех активированных пакетов в виде общего дерева папок. При��ожения видят обычные пути наподобие /usr/local/lib/foo.so, но на самом деле данные считываются из сжатых файлов пакетов в /system/packages. Установка и удаление выполняются мгновенно, поскольку мы просто добавляем или удаляем один файл, а не извлекаем или удаляем тысячи. Это полностью устраняет оверхед системных вызовов на уровне операционной системы, благодаря чему не приходится решать проблему на уровне приложений. Haiku — это опенсорсная операционная система, воссоздающая BeOS, известную своей отзывчивостью и чистой архитектурой. Хоть она и не особо популярна, её архитектура пакетов демонстрирует, что модель «извлекай всё на диск», используемая большинством менеджеров пакетов — это не единственный возможный вариант.
SquashFS для контейнерных сред исполнения
В качестве ещё одной альтернативы stabbles предложил SquashFS со сжатием zstd. Она используется различными контейнерными средами исполнения и популярна в средах HPC, где файловые системы часто имеют высокие задержки. SquashFS можно смонтировать на Linux нативно или через FUSE, что позволит получать доступ к файлам обычным образом, а данные будут сжаты на диске. На вопрос об оверхеде системных вызовов stabbles ответил, что хотя количество системных вызовов остаётся высоким, снижаются задержки, потому что SquashFS обеспечивает близкое хранение файлов, сильно выигрывая от кэша файловой системы. Здесь компромисс отличается от случая с tar.gz: затраты системные вызовы каждого файла сохраняются, но мы получаем локальность файлов и можем использовать стандартные файловые API без явной работы с распаковкой. Один из комментаторов предупредил, что при монтировании образа SquashFS через петлевое устройство необходимо использовать losetup --direct-io=on, чтобы устранить двойное кэширование, что может существенно снизить объём используемой памяти.
SQLite в качестве альтернативы
tsanderdev сообщил, что именно по этой причине SQLite может быть намного быстрее, чем папка с кучей мелких файлов. Я совершенно забыл, что можно использовать SQLite. Хранение содержимого файлов в базе данных SQLite позволит устранить оверхед системных вызовов, обеспечив при этом произвольный доступ к отдельным файлам, что невозможно при работе с tar.gz.
Это также объясняет причины того, почему Apple активно использует SQLite в своих приложениях, по сути, симулируя файловую систему в базах данных SQLite. Если на современном Mac с NVMe для чтения 100 тысяч файлов требуется 14 секунд, представьте, насколько медленнее это происходило бы на старых машинах. Оверхед системных вызовов проявлялся бы ещё сильнее. Применение SQLite вместо файловой системы позволяет полностью избавиться от этих системных вызовов. Эту тему стоит изучить.
Избавляемся от системных вызовов очистки
matthieum предложил популярный трюк, используемый пакетными компиляторами: никогда не вызывать free, close или munmap, вместо этого позволив операционной системе самой собрать все ресурсы после завершения процесса. При однократном пакетном процессе наподобие работы компилятора (или бенчмарка лексера) нет смысла аккуратно освобождать ресурсы, которые операционная система всё равно вернёт себе.
GabrielDosReis упомянул один тонкий момент: в некоторых случаях необходимо вызывать close, или у нас могут закончиться файловые дескрипторы. В macOS лимиты можно проверить следующим образом:
$ launchctl limit maxfiles
maxfiles 256 unlimited
$ sysctl kern.maxfilesperproc
kern.maxfilesperproc: 61440Первое число (256) — это мягкое ограничение на процесс, второе — жёсткое ограничение. kern.maxfilesperproc показывает максимум ядра для каждого процесса. При 104000 файлов отказ от вызовов close исчерпает даже максимальное ограничение. dinosaurdynasty отметил, что используемое по умолчанию нижнее мягкое ограничение — это исторический артефакт системного вызова select(), который может обрабатывать дескрипторы файлов меньше 1024. Современные программы могут просто поднять мягкую границу до жёсткой и не беспокоиться об этом.
Есть и дополнительная оптимизация: использовать процесс-обёртку. Обёртка запускает процесс воркера, выполняющий всю работу. Когда воркер сигнализирует о завершении (через stdout или конвейер), обёртка немедленно завершает выполнение, не ожидая свой отсоединённый дочерний процесс. Дальше все скрипты, ожидающие обёртку, могут продолжить выполнение, а операционная система асинхронно возвращает ресурсы воркера в фоновом режиме. Раньше я не думал о таком решении, но, наверно, стоит его попробовать.
Dwedit отметил, что в Windows похожая оптимизация заключается в вызове CloseHandle из вторичного потока, благодаря чему основной поток остаётся незаблокированным, пока освобождаются дескрипторы.
Стратегии линкеров для быстрого выхода
MaskRay добавил контекст о том, как точно такую же проблему решают линкеры. Линкер mold использует описанный выше процесс-обёртку, выполняя форк дочернего процесса для выполнения всей работы; родительский процесс выполняет выход сразу после того, как дочерний сигнализирует о завершении работы. Это позволяет системам сборки продолжать работу, не дожидаясь очистки ресурсов. Флаг --no-fork отключает такое поведение для отладки. Линкер wild использует тот же паттерн.
lld выбрал другой подход и применяет два целевых хака: async unlink для удаления старых файлов вывода в фоновом потоке и вызов _exit вместо exit для пропуска подпрограмм очистки среды исполнения C (если только не установлен флаг тестирования LLDIN_TEST).
MaskRay отмечает компромисс в решении с процессом-обёрткой: когда в дочернем процессе выполняется высоконагруженная работа, родительский процесс линкера (обычно система сборки) не может точно отслеживать использование ресурсов самой работой. Это важно для систем сборки, отслеживающих потребление памяти или время CPU.
Почему pub.dev на самом деле использует tar.gz
Боб Нистрём из команды Dart сообщил, что моя гипотеза о выборе формата pub.dev была отчасти ошибочной. Снижение количества HTTP-запросов и экономия канала определённо повлияли на решение, как и снижение объёма на сервере. Атомарность тоже важна, однако архивы не полностью решают эту проблему, потому что скачивание и извлечение всё равно могут заканчиваться сбоями. Однако маловероятно, что учитывались преимущества для скорости ввода-вывода (ускорение извлечения, снижение оверхеда системных вызовов): pub извлекает архивы сразу после скачивания, выигрыш от извлечения возникает только при pub get, это одно извлечение — крошечная доля от довольно затратного процесса; к тому же pub никогда не считывает файлы повторно, за исключением pubspec. Полученный мной выигрыш в производительности возникает только при многократном чтении из архивов, но pub работает иначе.
Возникает интересный вопрос: что, если бы pub вообще не распаковывал архивы? Для чистой (не инкрементальной) компиляции большого проекта наподобие Dart Analyzer, содержащего сотни зависимостей, компилятору нужно получать доступ к тысячам файлов во множестве пакетов. Если бы пакеты оставались в формате архива с поддержкой произвольного доступа (наподобие ZIP), то оверхед системных вызовов от открытия и закрытия всех этих файлов потенциально можно было бы снизить. Вместо тысяч разбросанных по файловой системе системных вызовов open/read/close у нас бы было по одному вызову open на один архив пакета, а затем поиск внутри каждого пакета. Непонятно, перевесит ли оверхед распаковки общую экономию на системных вызовах, но этот вопрос стоило бы изучить для систем сборки, в которых часто выполняются чистые сборки с большими деревьями зависимостей.
Использовать dart:io для gzip вместо package:archive
Саймон Байндер указал, что в dart:io уже есть поддержка gzip на основе zlib, поэтому не нужно использовать package:archive для распаковки. Так как dart:io не поддерживает архивы tar, я использовал для всего package:archive и не подумал об отдельном добавлении gzip из dart:io. Использование GZipCodec dart:io с применением package:archive только для извлечения tar может обеспечить повышение производительности. Я попробую это решение, когда попытаюсь лексировать более объёмный корпус.
TAR против ZIP: последовательный и произвольный доступ
vanderZwan сообщил, что файлы ZIP могут обеспечить преимущества произвольного доступа, как в SQLite. Это подчёркивает фундаментальную архитектурную разницу между TAR и ZIP:
TAR был спроектирован в 1979 году для последовательных ленточных накопителей. Метаданные каждого файла хранились в заголовке, идущем непосредственно перед его содержимым, без центрального индекса. Для нахождения конкретного файла нужно было последовательно считывать архив. При сжатии в tar.gz весь поток сжимается вместе, поэтому для доступа к файлу нужно распаковать всё, что идёт перед ним. Этот формат был стандартизирован POSIX (POSIX.1-1988 для ustar, POSIX.1-2001 для pax), он хорошо задокументирован и полностью сохраняет атрибуты файлов Unix.
ZIP был спроектирован в 1989 году, у него есть центральная директория, хранящаяся в конце архива. Эта директория содержит смещения местоположений каждого файла, позволяя выполнять произвольный доступ: достаточно один раз считать центральную директорию, после чего непосредственно искать любой файл. Каждый файл сжимается по отдельности, поэтому можно распаковать только нужный файл. Именно поэтому внутри файлов JAR, OpenDocument и EPUB используется формат ZIP.
Аспект | TAR | ZIP |
|---|---|---|
Произвольный доступ | Нет (только последовательный) | Да (центральная директория) |
Стандартизация | Стандарт POSIX | Спецификация, контролируемая PKWARE |
Разрешения Unix | Полное сохранение | Ограниченная поддержка |
Сжатие | Внешнее (gzip, zstd и так далее) | Встроенное, для каждого файла |
Похоже, не существует широко применяющегося нативного формата Unix, соединяющего в себе произвольный доступ с поддержкой метаданных Unix. TAR обеспечивает последовательный доступ с полной семантикой Unix. ZIP работает с произвольным доступом, но изначально разрабатывался для MS-DOS, поэтому не имеет целостной поддержки разрешений Unix. Нам не хватает чего-то наподобие «ZIP для Unix»: произвольного доступа с сохранением прав владения, разрешений, расширенных атрибутов и ACL.
Больше всего похож на решение dar (Disk ARchive), спроектированный специально в качестве замены tar с современными возможностями. Он хранит индекс каталога в конце архива для извлечения файлов за O(1), сохраняет полные метаданные Unix, в том числе и расширенные атрибуты с ACL, поддерживает сжатие каждого файла по отдельности с выбором алгоритма и может изолировать каталог отдельно для быстрой навигации без всего архива. Однако dar не получил такого широкого распространения, как tar или zip.
В моём бенчмарке лексера произвольный доступ не поможет, потому что я всё равно обрабатываю все файлы. Но в сценариях, требующих доступа к конкретным файлам внутри архива это архитектурное отличие важно.
Блочное сжатие
cb321 сообщил, что есть промежуточное состояние между несжатыми архивами (произвольный доступ, но большой размер) и полностью сжатыми потоками (маленькие, но последовательный доступ). Стандартный gzip сжимает всё в один блок, поэтому для доступа к любому байту нужно выполнить распаковку с начала. BGZF (Blocked GNU Zip Format), разработанный исследователями генома для инструментов наподобие samtools, сжимает данные в независимые блоки по 64 КБ. Каждый блок — это валидный поток gzip, поэтому файл остаётся совместимым со стандартным gunzip, но с индексом можно искать непосредственно любой блок и распаковывать только эту часть. Это позволяет выполнять произвольный доступ к многогигабайтному геному без распаковки терабайтов данных. У Zstd есть похожий формат с возможностью поиска, обладающий более высокими коэффициентами сжатия и ускоренной распаковкой. В случае архивов tar комбинация блочного сжатия с внешним индексом смещений файлов может обеспечить произвольный доступ к отдельным файлам с сохранением преимуществ сжатия.
RE2C: более быстрый подход к генерации лексеров
rurban сообщил, что RE2C генерирует лексеры, которые примерно в десять раз быстрее, чем flex. Главное отличие заключается в архитектуре: flex генерирует табличные лексеры, ищущие переходы в массивах в среде исполнения, а RE2C генерирует лексеры с непосредственным кодированием, в которых конечный автомат кодируется непосредственно в виде условных переходов и сравнений. Это устраняет оверхед табличного поиска и создаёт более быстрый код, с которым проще работать блокам предсказания ветвления CPU.
RE2C также поддерживает computed gotos (флаг -g) — расширение GCC/Clang, компилирующее операторы switch в косвенные переходы через таблицу адресов меток. В случае лексеров со множеством состояний это может существенно снизить количество ошибочных предсказаний ветвления. Также среди оптимизаций можно упомянуть минимизацию DFA и построение автоматов с туннелями.
Мой лексер ассемблера ARM64 на данный момент использует решение на основе таблиц, поэтому интересно было бы исследовать генерацию с непосредственным кодированием. Ещё один вариант — оптимизация на основании профилирования: компиляция лексера в LLVM IR и использование PGO для оптимизации горячих путей исполнения кода на основании реальных паттернов кода Dart. Выигрыш по скорости моего лексера относительно официального сканера Dart частично связан с его простотой: мой лексер чистый, он хранит только стек состояний лексера для нескольких конечных автоматов, а сканер Dart должен конструировать связанный список токенов, обрабатывать восстановление после ошибок и дополнительное управление ресурсами. В будущем я хочу глубже изучить, с чем больше связана разница в производительности: с архитектурой или с набором функций.
Архивы игровых движков: MPQ и CASC
Iggyhopper рассказал, что Blizzard Entertainment решила ту же самую проблему десятки лет назад с помощью формата архивов MPQ (Mo'PaQ, сокращение от Mike O'Brien Pack). MPQ, впервые использованный в Diablo в 1996 году, объединяет игровые ресурсы (текстуры, звуки, модели, данные уровней) в большие архивные файлы со встроенным сжатием, шифрованием и быстрым произвольным доступом посредством индексированием хэш-таблиц. Этот формат применялся в StarCraft, Diablo II, Warcraft III и World of Warcraft. На конференции GDC Austin 2009 сооснователь Blizzard Фрэнк Пирс рассказал, что в WoW содержалось 1,5 миллионов ресурсов, и в последующих расширениях это число только росло. В 2014 году Blizzard заменила MPQ на CASC (Content Addressable Storage Container), использовав его впервые в Warlords of Draenor; в формат были добавлены внутренние проверки целостности и ускоренный патчинг. В нём применён тот же принцип, что и в моём посте: объединение ресурсов в большие архивы позволяет избегать оверхеда обработки каждого файла, из-за которого загрузка миллионов отдельных файлов в игре реального времени была бы очень долгой.
Закон Амдала
fun__friday отметил, что главный вывод из статьи заключается в том. что перед оптимизацией необходимо провести измерения, и сослался на закон Амдала. И мой пост стал наглядной иллюстрацией этого закона: когда на лексинг тратится всего ~17% общего времени исполнения, то даже двукратное ускорение лексинга обеспечит общее ускорение всего в 1,22 раза. Теоретическое максимальное ускорен��е от улучшения лексера ограничено долей времени, затрачиваемого на всё остальное. Сначала измеряйте, потом оптимизируйте.
С точки зрения «бизнеса» имеет смысл делать упор на самых больших узких местах (например, следуя методу критического пути) и тех частях, которые занимают больше всего времени. Однако ПО используют в разных целях, и ускорение одного компонента может обеспечить существенный выигрыш для других потребителей этого компонента. От быстрого лексера выиграет не только этот бенчмарк, но и все использующие его инструменты: форматтеры, линтеры, анализиторы, компиляторы. Я считаю, что наше сообщество разработчиков ПО процветает отчасти и потому, что мы не следуем строго здравому смыслу, определяемому бизнес-оптимизацией.
Ограничения профилирования
Ameisen продолжил тему совета «сначала измеряй» важным тонким моментом: измерение само по себе может быть очень сложным или запутывающим. Здесь можно выделить три сценария. Во-первых, «смерть от тысячи порезов», когда множество мелких неэффективностей по отдельности отображаются в профилировщике в виде шума, но суммарно создают существенный оверхед. Ни одна горячая точка не доминирует, поэтому очевидных изъянов найти нельзя. Во-вторых, косвенные зависимости задач, при которых ускорение одного компонента обеспечивает каскадные преимущества, которые профилировщик с ним не свяжет. Ameisen привёл пример мода ресэмплинга спрайтов, в котором ускоренный алгоритм хэширования н�� только помогал непосредственно потоку рендеринга, но и быстрее заполнял потоки воркеров данными, снижая общие задержки так, что это было незаметно в профиле. В-третьих, профилировщики показывают, источники, но не причины замедления. Классический пример — инвалидация кэша из-за ложного совместного использования: профилировщик указывает на медленный доступ к памяти, но истинная причина (запись другим потоком в ту же линию кэша) остаётся скрытой. Причина замедления и то, что замедлилось, не совпадают, но в профиле отобразится только последнее. В ещё одном комментарии Ameisen привёл конкретные примеры: а) конкурентные воркеры, работавшие на 30% медленнее, потому что их выходным данным требовалась собственная линия кэша, но её не было (ложное совместное использование), б) поток рендеринга, получивший ускорение на 20% благодаря устранению защитного ветвления, которое приводило к незадокументированному сбросу конвейера CPU, когда за ним следовала заблокированная команда. Ни та, ни другая проблема не проявлялась в профиле.
