Локальность памяти и производительность

Хотя память часто рассматривается как единый однородный пул хранения, ее физическая организация и способ доступа к ней ЦП оказывают глубокое влияние на производительность приложений. Понимание локальности памяти является ключом к написанию высокопроизводительного кода, который эффективно использует иерархию кэша ЦП.

Иерархия кеша ЦП

Современный мобильный ЦП работает намного быстрее, чем основная ОЗУ системы (DRAM). Чтобы преодолеть этот разрыв в производительности, процессоры используют несколько уровней небольшой, чрезвычайно быстрой памяти, называемой кэшем.

• Кеш L1 (уровень 1). Самый маленький и быстрый (около 1 нс). На процессоре с частотой 3 ГГц это примерно три такта.
• Кэш L2 (второй уровень). Больше и немного медленнее (3–5 нс или 10–15 циклов).
• Кэш L3 (уровень 3). Самый большой кэш (~10–20 нс или ~30–60 циклов).
• Основная память (DRAM). Самая большая и медленная (более 100 нс или более 300 циклов).

Контекстуализация задержки: стоимость остановки

Чтобы понять влияние этих чисел, рассмотрим современный суперскалярный ЦП, который может выполнять от 4 до 8 инструкций за тактовый цикл.

Если ЦП пропустит все кеши и будет ждать 100 нс (300 циклов) для чтения DRAM:

• Потерянные циклы: около 300.
• "Потерянные" инструкции. От 1200 до 2400 инструкций, которые могли бы быть выполнены,если бы данные уже находились в локальном регистре или кеше L1.

Когда у вашего кода плохая локальность памяти, ЦП не обязательно занят сложной математикой; он часто «зависает», бездействуя в течение тысяч эквивалентов инструкций в ожидании подсистемы памяти.

Количество инструкций за такт (IPC)

Ключевой показатель эффективности – количество инструкций за такт (IPC). IPC – это среднее количество инструкций, которые ЦП успешно выполняет за один такт.

• Высокое значение IPC (например, 3,0–5,0). ЦП работает с высокой эффективностью, вероятно, находя большую часть данных в кэшах L1/L2 или регистрах.
• Низкое значение IPC (например, < 0,5). Производительность ЦП сильно ограничена. Даже если системные мониторы показывают, что ЦП загружен на 100 %, на самом деле он в основном ожидает ответа от памяти. Это состояние называется остановкой памяти.

Локальность памяти – основной фактор, определяющий, будет ли цикл с интенсивным использованием данных выполняться с высоким IPC или приведет к серии задержек.

Строки кеша

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

TLB (буфер ассоциативной трансляции)

Android использует виртуальную память. Каждый доступ к памяти требует преобразования виртуального адреса в физический. TLB – это специализированный кеш, в котором хранятся недавние преобразования. Если происходит промах, ядро должно пройтись по таблицам страниц в основной памяти. Это относительно ресурсоемкая операция по сравнению с попаданием в TLB.

Профиль оборудования: Pixel 10 Pro Fold

Для выполнения следующих упражнений мы использовали устройство Pixel 10 Pro Fold. Это устройство оснащено системой на кристалле Google Tensor G5.

Опрос оборудования

Чтобы понять, как работает подсистема памяти, сначала изучим конфигурацию ЦП и параметры кеша.

# Check CPU architecture and core parts
adb shell cat /proc/cpuinfo | grep 'CPU part' | sort -u
# Output:
# CPU part  : 0xd8b
# CPU part  : 0xd8c
# CPU part  : 0xd90

# Check cache line size
adb shell getconf -a | grep CACHE_LINESIZE
# Output:
# LEVEL1_ICACHE_LINESIZE             64
# LEVEL1_DCACHE_LINESIZE             64

Декодирование частей ЦП

Значения CPU part в /proc/cpuinfo – это шестнадцатеричные идентификаторы ядер процессоров ARM. Для системы на кристалле Laguna в Pixel 10 Pro Fold это:

• 0xd8b: ARM Cortex-A520 (энергоэффективные ядра)
• 0xd90: ARM Cortex-A720 (производительные ядра)
• 0xd8c: ARM Cortex-X4 (основное ядро)

Конфигурация 4 + 3 + 1 часто встречается в современных однокристальных системах для мобильных устройств, где у разных кластеров могут быть разные размеры кеша и задержки.

Типы населенных пунктов

Эффективная разработка программного обеспечения опирается на два основных типа локальности:

1. Пространственная локальность. Если происходит обращение к определенной ячейке памяти, то, скорее всего, вскоре произойдет обращение и к соседним ячейкам. Последовательный обход массива – классический пример. Поскольку ЦП загружает всю строку кеша, доступ к следующему элементу в массиве практически не требует ресурсов, если он уже находится в строке кеша.
2. Временная локальность. Если к ячейке памяти обращаются, то, скорее всего, к ней скоро обратятся снова. Хорошие алгоритмы повторно используют данные, пока они ещё "горячие" в кеше.

Практическое упражнение: измерение локальности с помощью simpleperf

В этом упражнении мы будем использовать simpleperf для мониторинга счетчиков производительности оборудования при выполнении двух разных обходов матрицы размером 256 МБ.

1. Обход по строкам. Доступ к элементам матрицы в том порядке, в котором они хранятся в памяти. Это позволяет эффективно использовать кэш и пространственную локальность.
2. Обход по столбцам. Переход по памяти для доступа к элементам по столбцам. Это часто приводит к промахам в кеше и TLB, что заставляет ЦП простаивать.

1. Запуск с Simpleperf

Отправьте двоичный файл, убедитесь, что он исполняемый, и используйте simpleperf stat, чтобы измерить события кеша и TLB. Суффикс :u используется для измерения событий в пользовательском пространстве. Для выполнения этих команд на большинстве устройств adb root требуется доступ к аппаратным счетчикам PMU.

adb root
adb shell "chmod +x /data/local/tmp/LocalityLab"

Профиль Row-major:

adb shell "simpleperf stat -e cpu-cycles:u,instructions:u,cache-misses:u,L1-dcache-load-misses:u,dTLB-load-misses:u /data/local/tmp/LocalityLab row"

Профиль Column-major:

adb shell "simpleperf stat -e cpu-cycles:u,instructions:u,cache-misses:u,L1-dcache-load-misses:u,dTLB-load-misses:u /data/local/tmp/LocalityLab col"

2. Примеры измерений (Pixel 10 Pro Fold)

Ниже приведены результаты, полученные на устройстве Pixel 10 Pro Fold.

3. Анализ результатов

• Падение IPC. В тесте с построчным обходом ЦП достигает IPC 4, 40, что указывает на эффективное выполнение нескольких инструкций за цикл. В тесте с обходом по столбцам IPC падает до 0, 16. Это означает, что 96 % времени ЦП простаивает, ожидая поступления данных из DRAM.
• Узкое место TLB. Самая большая разница наблюдается в dTLB-load-misses. Последовательный доступ (по строкам) остается в пределах одних и тех же страниц памяти, что приводит к очень небольшому количеству промахов TLB. Переход между столбцами (по столбцам) заставляет ЦП постоянно ссылаться на новые страницы, перегружая TLB и заставляя выполнять дорогостоящие обходы таблицы страниц.
• Эффективность кеша. При обходе по столбцам генерируется в 16 раз больше промахов кеша L1, что заставляет ЦП постоянно извлекать данные из гораздо более медленного L3 или DRAM.

Наблюдение. Хотя в обоих случаях выполнялась одна и та же логическая операция с одними и теми же данными, обход по столбцам был более чем в 80 раз медленнее. Эта огромная разница полностью обусловлена тем, как шаблон доступа взаимодействует с физической реальностью подсистемы памяти процессора.

Поиск указателей в структурах данных Java и Kotlin

Хотя тест производительности двумерной матрицы демонстрирует пространственную локальность в смежных нативных массивах, большая часть кода приложений для Android и фреймворков написана на Java и Kotlin. В управляемых языках переменные объектов и элементы коллекций не хранят объекты в строке, а хранят ссылки (указатели) на объекты, размещенные в куче ART.

Стоимость графов вложенных ссылок

Рассмотрим распространенный шаблон в приложениях Android и системных службах: обход вложенных коллекций, таких как ArrayList объектов состояния, каждый из которых содержит ArrayMap или ArraySet прослушивателей или подключений, каждый из которых указывает на другую запись состояния.

Хотя ArrayList, ArrayMap и ArraySet хранят свои внутренние массивы Object[] непрерывно, каждый элемент в этом Object[] по-прежнему является ссылкой на кучу. Для разыменования цепочки, например process.services.valueAt(i).connections.valueAt(j).client, требуется пять последовательных зависимых загрузок памяти:

1. Загрузите Object[] подложкуservices.
2. Загрузите заголовок и поля объекта ServiceRecord.
3. Загрузите Object[] подложкуconnections.
4. Загрузите объект ConnectionRecord.
5. Загрузите целевое поле ProcessRecord.

Поскольку адрес памяти каждой загрузки зависит от значения, возвращенного предыдущей загрузкой, механизм внеочередного выполнения ЦП и аппаратный предварительный выборщик не могут их перекрывать. Если эти объекты были выделены в разное время или перемещены в разные регионы во время сборки мусора, каждый переход рискует привести к промаху кэша L1 или L2.

Упакованные примитивы (ArrayList<Integer>, HashMap<Long, Boolean>) и универсальные лямбда-выражения усугубляют эти накладные расходы: каждый поиск элемента требует дополнительного разыменования указателя для распаковки значения, а универсальные обратные вызовы Consumer<T> вставляют заглушки проверки типов во время выполнения (CheckCast), которые увеличивают нагрузку на кеш инструкций (L1-icache).

Диагностика поиска по указателям с помощью simpleperf

В реальных рабочих нагрузках Java и Kotlin (например, при обходе графов ссылок на процессы, сервисы и поставщики в system_serverOomAdjuster) IPC редко падает до 0,16, как при синтетическом сканировании 256 МБ по столбцам, поскольку часть рабочего набора помещается в кеш L2 или L3. Вместо этого ищите в simpleperf следующую характерную сигнатуру:

• Низкий IPC (примерно от 0,6 до 0,9). Значительно ниже ширины суперскалярного выхода ЦП.
• Высокая задержка памяти на бэкенде (raw-stall-backend-mem). Часто от 35 до 45 % всех циклов ЦП тратится на ожидание заполнения кеша данных.
• Повышенные показатели L1-dcache-load-misses и L1-icache-load-misses. Высокая частота отсутствия совпадений в кеше данных в сочетании с отсутствием совпадений в кеше инструкций, когда циклы обхода переходят между виртуальными методами и общими заглушками лямбда-выражений.

Вы можете измерить эти счетчики в запущенном процессе с помощью simpleperf stat:

adb shell simpleperf stat \
  -e cpu-cycles:u,instructions:u,raw-stall-backend-mem:u,L1-dcache-load-misses:u,L1-icache-load-misses:u \
  -p $(pidof system_server) --duration 10

Улучшение локальности в управляемом коде

• Замените упакованные коллекции примитивными массивами или коллекциями AndroidX. Используйте примитивы IntArray, LongArray, SparseIntArray или androidx.collection (IntList, LongLongMap, ScatterMap), чтобы исключить объекты-оболочки и сохранить значения непрерывными в пределах одного выделенного массива.
• Упростите часто используемые пути обхода. Если часто используемый цикл многократно проходит три или четыре перехода по графу объектов, чтобы прочитать один логический или целочисленный флаг, поднимите или кэшируйте это состояние в плоский массив или битовую маску, индексированную плотным идентификатором.
• Избегайте захвата или общих лямбда-выражений в узких внутренних циклах. Используйте стандартные индексированные циклы for по спискам RandomAccess вместо forEach или цепочек итераторов, чтобы избежать выделения итераторов, мегаморфной диспетчеризации и накладных расходов на проверку типов во время выполнения.

← Потоки | ↑ Вверх | Привязки сервисов →