Первые великие оптимизаторы появились уже на таком низком уровне, как железо. По факту, задача выжимки ресурсов в программировании есть на любом уровне. В этой статье мы разберем оптимизации на уровне CPU такие как NUMA, prefetch, TLB и alignment.

Статья получится немного неоднородной и больше про “высокие материи”, что в принципе намекает на то, что разбор “железной” составляющей скоро подойдет к концу!

Вводная

Как мы рассматривали некогда ранее обращение на RAM – это достаточно дорого. CPU пытается это “скрыть”, чтобы работа казалась куда более быстрой.

Одним из таких механизмов, естественно, является иерархия кэшей!

Но вот не возникало ли у вас вообще вопроса – “А почему память – это в принципе проблема? Почему дорого?”. Все очень просто – доступ к памяти медленный

Тактовая частота например моего ноута – 2,70 ГГц, то есть 2,7 миллиарда циклов/операций в секунду

Доступ к ОЗУ имеет задержку аж в 150–350 циклов! То есть за это время мы могли бы выполнить 200 операций.

Такое положение дел нас в современных реалиях не устраивает, поэтому прибегаем к различным оптимизациями.

Prefetch

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

На всякий случай зафиксируем:

Hardware Prefetcher (блок аппаратной предвыборки) – это механизм процессора, который предсказывает требуемые данные или инструкции и заранее загружает их из медленной оперативной памяти в быстрый кэш.

В этом контексте “механизм” – это аппаратная логика внутри процессора, которая реализует определенное поведение автоматически, без участия программы или ОС. CPU использует несколько аппаратных prefetch-алгоритмов.

Давайте рассмотрим пример!

sl := make([]int, 1024)
for i := range sl {
_ = sl[i]
}

idx := []int{7, 900, 13, 511, 2, 777}
for i := range idx {
_ = sl[idx[i]]
}

// Что будет быстрее?

По идее, должно быть одинаково, но… нет. В первом случае доступ к памяти предсказуемый и линейный, поэтому процессор легко понимает, что после arr[i] почти наверняка потребуется arr[i+1]. В этом случае CPU начинает подгружать следующие cache line ещё до того, как в программе возникнет необходимость пользоваться ими напрямую. А во втором случае – доступ для CPU уже непредсказуемый если idx большой и случайный. Как делать prefetch? Никак!

Вот типичные паттерны в инструкциях, которые CPU может распознать:

Последовательный проход

mov edx, [rdi + rcx*8] ; Прямой проход по слайсу

Адреса растут линейно, поэтому процессор может заранее подтягивать следующие cache lines.

Доступ с постоянным шагом

mov edx, [rdi + rcx*64] ; Прямой проход, но уже с шагом в n > 1

Если шаг стабилен, часть prefetch-механизмов тоже способна это распознать. Шаг должен быть малым.

Обратный последовательный проход

mov edx, [rdi + rcx*8] ; По сути тот же прямой проход
dec rcx ; декремент текущего индекса

Нисходящий поток адресов может быть предсказуемым

И кстати отдельно отмечу, что это одна из главных причин, почему итерация по связному списку медленнее, чем по массиву, хотя теоретически обе O(n).

TLB

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

Локальность памяти — это свойство программ обращаться к данным, которые находятся рядом в памяти или использовались недавно.

Именно на этом предположении основана работа кэшей, prefetch-механизмов и TLB процессора.

Что вообще за виртуальный адрес и зачем он нужен? Суть в том, что операционные системы нынче используют виртуальную память. Программа работает не с реальными адресами RAM, а с виртуальными адресами своего адресного пространства.

Напомню

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

Проще говоря – часть памяти на диске, а часть в RAM.

Вот схема обращения в память:

Схема обращения к памяти с механизмом виртуальной памяти

Сам процесс перевода называется трансляцией адресов(address translation) и выполняется через таблицу страниц(page table).

Зафиксируем:

Address Translation (трансляция адресов) – это механизм, при котором аппаратное обеспечение преобразует виртуальные адреса (логические адреса, используемые программами) в физические адреса (реальные адреса в оперативной памяти RAM).

Таблица страниц(page table) – это специальная структура данных, используемая операционной системой и процессором для преобразования виртуальных адресов памяти, с которыми работают программы, в физические адреса реальной оперативной памяти.

На самом деле page table поддерживается операционной системой. Она хранит незамысловатое соответствие:

virtual page → physical frame

или же

0x00007FF0 → frame 0x1A3

Но здесь возникает проблема.

Page table находится в оперативной памяти. Прикольно, да? Получается парадокс:

Чтобы получить данные из RAM, нужно сначала прочитать page table из RAM

Это означало бы, что каждое обращение к памяти требует нескольких дополнительных обращений к памяти.

Очевидно, такая схема медленная и местами абсурдная!

И тут нам на помощь приходит TLB (Translation Lookaside Buffer, буфер ассоциативной трансляции или буфер трансляции адресов).

TLB – это небольшой кэш переводов виртуальных адресов в физические.

Он хранит недавно использованные вышеуказанные соответствия.

А схема работы с TLB теперь выглядит так:

Схема обращения к памяти при использовании TLB

Если нужная запись находится в TLB, перевод, очевидно, выполняется практически мгновенно!

Но если нужной записи в TLB нет, происходит TLB miss, процессор вынужден выполнить page walk – пройти по таблицам страниц, чтобы найти соответствие.

Page walk может требовать нескольких обращений к памяти, потому что современные системы используют многоуровневые таблицы страниц(в плане вложенности), поэтому TLB miss может стоить десятки, а может и сотни тактов CPU!

А что по размерам?

Сам по себе TLB – достаточно маленький кэш.

Что-то около

L1 TLB ~ 64–128 записей

L2 TLB ~ 512–2048 записей

TLB запись = трансляция для одной page, которая обычно где-то в районе 4 кб

Тогда по минимальной планке получаем 64 записей * 4 кБ = 256 кБ активной памяти без промаха в TLB.

Замечу, что

Если программа активно работает с большим объёмом памяти и постоянно переключается между разными страницами, может возникнуть TLB thrashing (пробуксовка буфера ассоциативной трансляции).

Это ситуация, при которой записи в TLB постоянно вытесняют друг друга.

В результате процессор вынужден регулярно выполнять page walk — обход таблиц страниц, чтобы заново получить перевод виртуального адреса в физический.

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

Вот пример, когда это может произойти:

const N = 4096

matrix := make([]int, N*N) // размер страницы памяти 4 кБ

// плохой вариант
for j := 0; j < N; j++ {
	for i := 0; i < N; i++ {
		_ = matrix[i*N + j]
	}
}
// В этом случае шаг между элементами равен: N * sizeof(int)
// То есть 4096 * 8 = 32768 байт
// Если рабочий набор страниц превышает размер TLB, записи начинают // вытеснять друг друга и возникает TLB thrashing.

// Хороший вариант
for i := 0; i < N; i++ {
	for j := 0; j < N; j++ {
		_ = matrix[i*N + j]
	}
}
/* Теперь доступ происходит последовательно:
page0
page0
page0
page0
...
page1
page1
page1 */
// Количество TLB промахов резко уменьшается.

Мораль на данный момент: старайтесь мыслить в плоскости “А в какой последовательности будет происходить доступ к данным?”

Alignment

Мы уже разобрались, что процессор работает с памятью не по одному байту, а строчками – cache line. Но это не всё, ведь есть ещё одно важное правило, которое влияет на производительность работы с памятью – выравнивание данных (alignment). Думаю, узнали уже эту историю в Go, но давайте разберемся что вообще это и зачем это нужно!

Alignment – это правило, по которому данные в памяти располагаются на адресах, кратных их размеру.

Напомню:

int8 → выравнивание 1 байт

int16 → выравнивание 2 байта

int32 → выравнивание 4 байта

int64 → выравнивание 8 байт

То есть значение типа int64 должно начинаться с адреса, кратного 8 байтам.

А теперь давайте поймем зачем вообще это надо.

Пусть есть структура(я специально не буду учитывать паддинги в Go)

type SomeUltraStructure struct {
  a int64
}

и cache line заполненная на 56 байт.

Тогда всё ок, переменная a поместится например в последние 8 байт, ничего необычного.

А теперь рассмотрим

type SomeNotUltraStructure struct {
  b int8
  a int64
}

56 + 1 = 57, остаются 7 байт, тогда a вылезет за границу этой cache line и войдет в другую. Что мы можем получить из-за этого??? Правильно! Состязание за кэш.

Но это еще не все. CPU будет медленнее считывать т.к. приходится смотреть 2 строки кэша, а не одну + собирать воедино это значение

А такое значение называется misaligned

К слову, на старых CPU такая ситуация могла вызвать исключение процессора!

NUMA

Давайте поговорим немного про архитектуру. Архитектуру памяти :)

До этого момента мы рассматривали оптимизации внутри одного процессора: кэши, prefetch, TLB и выравнивание данных. Однако на ныне на серверах существует ещё один фактор, влияющий на производительность работы с памятью – NUMA.

NUMA (Non-Uniform Memory Access) – это архитектура памяти, в которой время доступа к памяти зависит от того, какой процессор(CPU) обращается к какой области памяти.

Вообще зачем она нужна?

Когда-то на серверах использовалась общая RAM(примерно как у вас на ПК).

Все процессоры имели одинаковое время доступа к памяти.

Однако по мере роста числа ядер такая архитектура стала плохо масштабироваться:

Все процессоры конкурируют за один контроллер памяти
Увеличивается задержка доступа
Падает пропускная способность

Поэтому появилась архитектура NUMA.

В NUMA память распределена между процессорами.

CPU0 → Локальная RAM

CPU1 → Локальная RAM

CPU2 → Локальная RAM

CPU3 → Локальная RAM

Каждый процессор имеет свою локальную память, но может обращаться и к памяти других процессоров.

Но время доступа-то будет разное!

В NUMA существует два типа доступа к памяти.

Local memory

CPU0 → RAM0

Быстрый доступ.

Remote memory

CPU0 → RAM1

Доступ через межпроцессорную шину.

Он может быть в 1,5-3 раза медленнее в зависимости от архитектуры.

Но операционная система будет пытаться уменьшить количество удалённых обращений.

Если потоки активно мигрируют между ядрами или работают с памятью другого NUMA-узла(CPU + RAM), возникает NUMA penalty

Это может приводить к:

Увеличению задержки(локальная: ~80 нс, удаленная ~130 нс)
Уменьшению пропускной способности
Деградации масштабируемости

Особенно это заметно в:

Базах данных
Системах обработки данных
Многопоточных серверных приложениях

Думаю, с аппаратными оптимизациями мы закончили. Осталось совсем немного – разобрать системные вызовы на уровне CPU и можно переходить к полноценным Goшным концепциями. Увидимся в ~~финале~~ следующей статье!

Деконструкция GO: CPU, RAM и что там происходит. Оптимизации на CPU. Часть 1.4