Сжатие указателей в Oilpan
Это абсолютно глупо иметь 64-битные указатели, когда я компилирую программу, использующую менее 4 гигабайт оперативной памяти. Когда такие значения указателей оказываются внутри структуры, они не только занимают половину памяти, но и фактически используют лишь половину кеша.
Менее истинные слова (почти) никогда не были сказаны. Мы также видим, что поставщики процессоров фактически не поставляют 64-битные процессоры, а производители Android выбирают только 39-битное адресное пространство для ускорения обхода таблиц страниц в ядре. V8, работающий в Chrome, также изолирует сайты в отдельные процессы, что дополнительно снижает требования к фактическому адресу памяти, необходимому для одной вкладки. Однако ничего из этого не является полностью новым, именно поэтому мы запустили сжатие указателей для V8 в 2020 году и увидели значительные улучшения в использовании памяти в Интернете. С библиотекой Oilpan у нас под контролем есть еще один строительный блок веба. Oilpan — это сборщик мусора на основе трассировки для C++, который, среди прочего, используется для размещения модели объектов документа в Blink и поэтому является интересной целью для оптимизации памяти.
Основная информация
Сжатие указателей — это механизм для уменьшения размера указателей на 64-битных платформах. Указатели в Oilpan инкапсулированы в умный указатель, называемый Member. В не сжатой структуре кучи ссылки Member указывают непосредственно на объекты в куче, то есть на каждую ссылку используется 8 байт памяти. В таком случае куча может быть распределена по всему адресному пространству, так как каждый указатель содержит всю необходимую информацию для ссылки на объект.
В сжатой структуре кучи ссылки Member являются лишь смещениями внутри сегмента кучи, который представляет собой непрерывный участок памяти. Комбинация базового указателя (base), указывающего на начало сегмента кучи, и Member образует полный указатель, очень похожий на сегментированную адресацию. Размер сегмента кучи ограничен доступными битами для смещения. Например, сегмент кучи объемом 4 ГБ требует 32-битное смещение.
Удобно, что кучи Oilpan уже находятся в таком сегменте кучи объемом 4 ГБ на 64-битных платформах, что позволяет ссылаться на метаданные сборки мусора, просто выравнивая любой действительный указатель на ближайшую границу в 4 ГБ.
Oilpan также поддерживает несколько куч в одном процессе, например, для поддержки веб-воркеров с их собственными кучами C++ в Blink. Проблема, возникающая в этом случае, заключается в том, как сопоставить кучи с потенциально множеством сегментов кучи. Поскольку кучи привязаны к нативным потокам в Blink, решение в данном случае заключается в ссылке на сегменты кучи через локальный для потока базовый указатель. В зависимости от того, как V8 и его встроенные компоненты компилируются, модель локального хранилища потока (TLS) может быть ограничена для ускорения загрузки базы из памяти. Тем не менее, для поддержки Android требуется наиболее универсальный режим TLS, так как на этой платформе рендер (и, следовательно, V8) загружаются через dlopen. Такие ограничения делают использование TLS непрактичным с точки зрения производительности1. Для обеспечения наилучшей производительности, Oilpan, аналогично V8, выделяет все кучи в один сегмент при использовании сжатия указателей. Хотя это сокращает доступную общую память, мы считаем, что это приемлемо, учитывая, что сжатие указателей уже направлено на уменьшение размера памяти. Если единственный сегмент кучи объемом 4 ГБ оказывается слишком строгим ограничением, текущая схема сжатия позволяет увеличить размер сегмента до 16 ГБ без жертв производительности.
Реализация в Oilpan
Требования
До сих пор мы говорили о тривиальной схеме кодирования, где полный указатель формируется путем добавления базы к смещению, которое хранится в указателе Member. К сожалению, фактически реализованная схема не так проста, так как Oilpan требует, чтобы Member мог принимать одно из следующих значений:
- Действительный указатель кучи на объект;
- C++
nullptr(или аналог); - Сентинельное значение, которое должно быть известно на этапе компиляции. Сентинельное значение, например, может использоваться для сигнализации об удаленных значениях в хэш-таблицах, которые также поддерживают
nullptrв качестве записей.
Проблемная часть вокруг nullptr и сентинеля — это отсутствие явных типов для их отлова на стороне вызывающего:
void* ptr = member.get();
if (ptr == nullptr) { /* ... * }
Так как нет явного типа для хранения возможно сжатого значения nullptr, для сравнения с константой требуется фактическая декомпрессия.
Имея в виду это использование, мы искали схему, которая бы прозрачно обрабатывала случаи 1-3. Поскольку последовательности сжатия и декомпрессии будут инланинизированы везде, где используется Member, также желательны следующие свойства:
- Быстрая и компактная последовательность инструкций для минимизации промахов icache.
- Безветвленная последовательность инструкций для избежания использования предсказателя ветвлений.
Поскольку ожидается, что чтения будут значительно преобладать над записями, мы допускаем асимметричную схему, где предпочтение отдается быстрой декомпрессии.
Сжатие и декомпрессия
Для краткости это описание охватывает только финальную схему сжатия. Подробности о том, как мы пришли к ней, и рассмотренные альтернативы можно найти в нашем документе о проектировании.
Основная идея сегодняшней реализованной схемы — это отделение регулярных указателей кучи от nullptr и сентинеля с использованием выравнивания области памяти. Фактически, область кучи выделена с выравниванием таким образом, что наименее значащий бит старшего полуслова всегда установлен. Мы обозначаем старшую и младшую половину (по 32 бита каждая) как U31...U0 и L31...L0 соответственно.
| старшая половина | младшая половина | |
|---|---|---|
| указатель кучи | U31...U11 | L31...L3000 |
nullptr | 0...0 | 0...000 |
| сентинель | 0...0 | 0...010 |
Сжатие создает сжатое значение простым сдвигом вправо и обрезкой старшей половины значения. Таким образом, бит выравнивания (который теперь становится самым значащим битом сжатого значения) сигнализирует о действительности указателя кучи.
| C++ | Ассемблер x64 |
|---|---|
| ```cpp | ```asm \ |
| uint32_t Compress(void* ptr) { | mov rax, rdi \ |
| return ((uintptr_t)ptr) >> 1; | shr rax \ |
| } | ``` \ |
| ``` |
Кодирование для сжатых значений выглядит следующим образом:
| сжатое значение | |
|---|---|
| указатель кучи | 1L31...L200 |
nullptr | 0...00 |
| сентинель | 0...01 |
Заметьте, это позволяет определить, представляет ли сжатое значение указатель кучи, nullptr или сентинельное значение, что важно для избежания ненужных декомпрессий в пользовательском коде (см. ниже).
Идея декомпрессии заключается в использовании специально создавленного базового указателя, у которого наименее значимые 32 бита установлены в 1.
| старшая половина | младшая половина | |
|---|---|---|
| база | U31...U11 | 1...1 |
Операция декомпрессии сначала выполняет знаковое расширение сжатого значения, затем сдвигает влево для восстановления знака. Результирующее промежуточное значение кодируется следующим образом
| старшая половина | младшая половина | |
|---|---|---|
| указатель кучи | 1...1 | L31...L3000 |
nullptr | 0...0 | 0...000 |
| sentinel | 0...0 | 0...010 |
Наконец, декомпрессированный указатель - это просто результат побитового И между этим промежуточным значением и базовым указателем.
| C++ | x64 assembly |
|---|---|
| ```cpp | ```asm \ |
| void* Decompress(uint32_t compressed) { | movsxd rax, edi \ |
| uintptr_t intermediate = | add rax, rax \ |
| (uintptr_t)((int32_t)compressed) <<1; | and rax, qword ptr \ |
| return (void*)(intermediate & base); | [rip + base] \ |
| } | ``` \ |
| ``` |
Полученная схема обрабатывает случаи 1-3. прозрачно через асимметричную схему без ветвлений. Сжатие занимает 3 байта, если не считать начальное перемещение регистра, так как вызов все равно будет встроенным. Декомпрессия занимает 13 байт, включая начальное расширение знака регистра.
Выбранные детали
Предыдущий раздел объяснил используемую схему сжатия. Компактная схема сжатия необходима для достижения высокой производительности. Схема сжатия, описанная выше, все же привела к заметным регрессиям в Speedometer. Следующие абзацы объясняют несколько дополнительных аспектов, необходимых для улучшения производительности Oilpan до приемлемого уровня.
Оптимизация загрузки базового значения "клетки"
Технически, с точки зрения C++, глобальный базовый указатель не может быть константой, поскольку он инициализируется во время выполнения после main(), всякий раз, когда Oilpan инициализируется встроенным приложением. Наличие этой глобальной переменной изменяемой будет препятствовать важной оптимизации распространения констант, например, компилятор не сможет доказать, что случайный вызов не модифицирует базу и должен будет загружать ее дважды:
| C++ | x64 assembly |
|---|---|
| ```cpp | ```asm \ |
| void foo(GCed*); | baz(Member<GCed>): \ |
| void bar(GCed*); | movsxd rbx, edi \ |
| add rbx, rbx \ | |
| void baz(Member<GCed> m) { | mov rdi, qword ptr \ |
| foo(m.get()); | [rip + base] \ |
| bar(m.get()); | and rdi, rbx \ |
| } | call foo(GCed*) \ |
| ``` | and rbx, qword ptr \ |
| [rip + base] # extra load \ | |
| mov rdi, rbx \ | |
| jmp bar(GCed*) \ | |
| ``` |
С некоторыми дополнительными атрибутами мы научили clang рассматривать глобальную базу как константу и таким образом действительно выполнять только одну загрузку в рамках контекста.
Полное избегание декомпрессии
Самая быстрая последовательность инструкций - это nop! С учетом этого, для многих операций с указателями можно легко избежать избыточного сжатия и декомпрессии. Например, нам не нужно декомпрессировать Member, чтобы проверить, равен ли он nullptr. Нам не нужно декомпрессировать и сжимать при создании или присваивании Member из другого Member. Сравнение указателей сохраняется при сжатии, поэтому мы можем избегать преобразований и для них. Абстракция Member прекрасно подходит для этого.
Хеширование можно ускорить сжатиями указателей. Декомпрессия для расчета хеша избыточна, поскольку фиксированная база не увеличивает энтропию хеша. Вместо этого можно использовать более простую функцию хеширования для 32-битных целых чисел. В Blink есть множество хеш-таблиц, которые используют Member в качестве ключа; 32-битное хеширование привело к более быстрым коллекциям!
Помощь clang там, где он не оптимизирует
При анализе сгенерированного кода мы обнаружили еще одно интересное место, где компилятор не выполнил достаточно оптимизаций:
| C++ | x64 assembly |
|---|---|
| ```cpp | ```asm \ |
| extern const uint64_t base; | Assign(unsigned int): \ |
| extern std::atomic_bool enabled; | mov dword ptr [rdi], esi \ |
| mov rdi, qword ptr \ | |
| void Assign(uint32_t ptr) { | [rip + base] \ |
| ptr_ = ptr | mov al, byte ptr \ |
| WriteBarrier(Decompress(ptr)); | [rip + enabled] \ |
| } | test al, 1 \ |
| jne .LBB4_2 # очень редкое \ | |
| void WriteBarrier(void* ptr) { | ret \ |
| if (LIKELY( | .LBB4_2: \ |
| !enabled.load(relaxed))) | movsxd rax, esi \ |
| return; | add rax, rax \ |
| SlowPath(ptr); | and rdi, rax \ |
| } | jmp SlowPath(void*) \ |
| ``` | ``` |
Сгенерированный код выполняет загрузку базы в горячем базовом блоке, даже несмотря на то, что переменная не используется в нем и могла бы быть тривиально перенесена в следующий базовый блок, где вызывается SlowPath() и фактически используется декомпрессированный указатель. Компилятор консервативно решил не менять порядок неатомарной загрузки с атомарной релаксированной загрузкой, хотя это было бы полностью законно с точки зрения правил языка. Мы вручную переместили декомпрессию ниже атомарного считывания, чтобы сделать присвоение с write-barrier как можно более эффективным.
Улучшение упаковки структур в Blink
Трудно оценить эффект от уменьшения размера указателя Oilpan вдвое. По сути, это должно улучшить использование памяти для «упакованных» структур данных, таких как контейнеры для таких указателей. Локальные измерения показали улучшение примерно на 16% памяти Oilpan. Однако исследование показало, что для некоторых типов мы не уменьшили их фактический размер, а только увеличили внутренние отступы между полями.
Чтобы минимизировать такие отступы, мы написали плагин для clang, который автоматически идентифицировал такие классы с мусоросборкой, для которых изменение порядка полей уменьшило бы общий размер класса. Поскольку таких случаев было много в кодовой базе Blink, мы применили изменение порядка для наиболее используемых классов, см. документ проектирования.
Неудачная попытка: ограничение размера heap cage
Не каждая оптимизация дала хорошие результаты. В попытке еще больше оптимизировать сжатие, мы ограничили heap cage до 2 ГБ. Мы убедились, что самый значимый бит нижнего полуслова базы cage равен 1, что позволило полностью избежать сдвига. Сжатие стало бы простым усечением, а декомпрессия — простым считыванием и побитовым И.
Учитывая, что память Oilpan в Blink render среднем занимает менее 10 МБ, мы предположили, что можно смело переходить на более быструю схему и ограничить размер cage. К сожалению, после доставки оптимизации мы начали получать ошибки нехватки памяти в некоторых редких сценариях работы. Мы решили откатить эту оптимизацию.
Результаты и перспективы
Сжатие указателей в Oilpan было включено по умолчанию в Chrome 106. Мы наблюдали значительное улучшение использования памяти:
| Память Blink | P50 | P99 |
|---|---|---|
| Windows | -21% (-1.37MB) | -33% (-59MB) |
| Android | -6% (-0.1MB) | -8% (-3.9MB) |
Приведенные данные представляют собой 50-й и 99-й перцентили памяти Blink, выделенной с помощью Oilpan, по всему парку2. В предоставленных данных показана дельта между стабильными версиями Chrome 105 и 106. Абсолютные числа в мегабайтах дают представление о нижней границе, которую пользователи могут ожидать. Реальные улучшения, как правило, немного выше из-за косвенных эффектов на общую загрузку памяти Chrome. Большее относительное улучшение предполагает, что упаковка данных в таких случаях лучше, что является индикатором большего использования памяти в коллекциях (например, векторах), которые имеют хорошую упаковку. Улучшенная упаковка структур появилась в Chrome 108 и показала дополнительное улучшение на 4% памяти Blink в среднем.
Поскольку Oilpan повсеместно используется в Blink, стоимость производительности может быть оценена на Speedometer2. Начальный прототип, основанный на версии с локальными потоками, показал регрессию на 15%. С учетом всех вышеупомянутых оптимизаций мы не обнаружили заметной регрессии.
Сканирование стека консервативным методом
В Oilpan стек сканируется консервативным методом для нахождения указателей на куче. С сжатыми указателями это означает, что мы должны обрабатывать каждую половину слова как потенциальный указатель. Более того, во время сжатия компилятор может решить записать промежуточное значение в стек, что означает, что сканер должен учитывать все возможные промежуточные значения (в нашей схеме сжатия единственное возможное промежуточное значение — это усеченное, но еще не смещенное значение). Сканирование промежуточных значений увеличило количество ложных срабатываний (т.е. половинные слова, которые выглядят как сжатые указатели), что снизило улучшение памяти примерно на 3% (без учета этого факторa предполагаемое улучшение памяти составило бы 24%).
Другое сжатие
В прошлом мы наблюдали значительные улучшения, применяя сжатие в V8 JavaScript и Oilpan. Мы считаем, что эту парадигму можно применить к другим умным указателям в Chrome (например, base::scoped_refptr), которые уже указывают на другие области кучи. Первоначальные эксперименты показали обнадеживающие результаты.
Исследования также показали, что большая часть памяти фактически удерживается через виртуальные таблицы. В этом же духе мы включили ABI относительных виртуальных таблиц на Android64, что сжимает виртуальные таблицы, позволяя нам сохранять больше памяти и одновременно улучшать время загрузки.
Footnotes
-
Заинтересованные читатели могут обратиться к
ThreadStorage::Current()в Blink, чтобы увидеть результат компиляции доступа к TLS в различных режимах. ↩ -
Данные собираются с использованием фреймворка анализа пользовательских метрик Chrome. ↩