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

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

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

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

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

• Кэш L1 (уровень 1) : самый маленький и самый быстрый (~1 нс). На процессоре с частотой 3 ГГц это примерно 3 тактовых цикла.
• Кэш L2 (уровень 2) : больше по размеру и немного медленнее (~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% загрузка процессора, на самом деле он большую часть времени тратит на ожидание доступа к памяти — состояние, известное как задержка доступа к памяти .

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

Строки кэша

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

TLB (буфер резервного перевода)

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

---

Характеристики оборудования: Pixel 10 Pro Fold

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

Проверка оборудования

Для понимания работы подсистемы памяти мы сначала рассмотрим конфигурацию процессора и параметры кэша.

Примечание: Для выполнения следующих команд требуются права root ( adb root ).

# 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. Для SoC Laguna, используемого в Pixel 10 Pro Fold, они соответствуют следующим значениям:

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

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

---

Типы местности

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

1. Пространственная локальность : если происходит обращение к ячейке памяти, то вскоре, вероятно, произойдет обращение к соседним ячейкам памяти. Классическим примером является последовательный обход массива. Поскольку процессор загружает всю кэш-линию целиком, доступ к следующему элементу массива практически «бесплатен», если он уже находится в кэш-линии.
2. Временная локальность : если происходит обращение к определенному участку памяти, то, вероятно, вскоре к нему снова обратятся. Хорошие алгоритмы повторно используют данные, пока они еще находятся в «активном» состоянии в кэше.

---

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

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

1. Обход по строкам : обращается к элементам матрицы в том порядке, в котором они хранятся в памяти. Это выгодно с точки зрения кэширования и использует принцип пространственной локальности.
2. Обход по столбцам : осуществляется переход по памяти для доступа к элементам по столбцам. Часто при этом не удается получить доступ к кэшу и TLB, что приводит к зависанию процессора.

Примечание: для работы simpleperf на вашем устройстве должна быть запущена userdebug или eng сборка.

1. Запустите с помощью Simpleperf

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

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

Профиль, строка-основа:

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"

Основной раздел профиля:

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:

Метрическая система	Главный ряд (дружественный)	Главный столбец (недружелюбный)	Разница
Время выполнения	0,83 секунды	68,3 секунды	примерно в 82 раза медленнее
Инструкции	5,27 миллиарда	10,20 миллиарда	примерно в 1,9 раза больше
Циклы ЦП	1,20 миллиарда	62,18 миллиарда	~52 раза больше
Количество инструкций за цикл (IPC)	4.40	0,16	Эффективность снижена в 27 раз.
Промахи кэша данных L1	210 миллионов	3,369 миллионов	В 16 раз больше промахов
Промахи при загрузке dTLB	0,13 миллиона	2,888 миллионов	В 22 000 раз больше промахов

Примечание: В этом упражнении мы явно отключили автоматическую векторизацию SIMD с помощью #pragma clang loop vectorize(disable) . Это гарантирует, что измеренная нами разница в производительности обусловлена ​​исключительно узкими местами подсистемы памяти (кэш и TLB), а не разницей в пропускной способности инструкций SIMD и скалярных инструкций.

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

• Сбой IPC : В построчном тесте процессор достигает показателя IPC 4,40, что указывает на эффективное выполнение нескольких инструкций за цикл. В столбцовом тесте показатель IPC падает до 0,16. Это означает, что процессор простаивает 96% времени , ожидая поступления данных из DRAM.
• Узкое место TLB : Наиболее существенное различие заключается в промахах при загрузке dTLB . Последовательный доступ (построчный) остается в пределах одних и тех же страниц памяти, что приводит к очень небольшому количеству промахов TLB. Переходы между столбцами (столбцовый) заставляют процессор постоянно обращаться к новым страницам, перегружая TLB и вынуждая выполнять дорогостоящие обходы таблицы страниц.
• Эффективность кэша : Поколоночный обход кэша приводит к увеличению количества промахов в кэше L1 в 16 раз, заставляя процессор постоянно получать данные из гораздо более медленного кэша 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. Загрузите базовые services Object[] .
2. Загрузите заголовок и поля объекта ServiceRecord .
3. Загрузите массив Object[] для connections .
4. Загрузите объект ConnectionRecord .
5. Загрузите целевое поле ProcessRecord .

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

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

Диагностика проблемы "следования указателя" с помощью simpleperf

В реальных рабочих нагрузках Java и Kotlin (например, при обходе графов ссылок на процессы, сервисы и поставщиков с помощью OomAdjuster из system_server ) отслеживание указателей редко снижает 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 или цепочек итераторов, чтобы избежать выделения памяти итераторам, мегаморфной диспетчеризации и накладных расходов на проверку типов во время выполнения.

---

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