Data-oriented design и CPU-кэши

Одни и те же ядра на Go и C, на Apple M5 и AMD Zen 4: ступени иерархии кэшей при росте рабочего множества, AoS против SoA и среза указателей, false sharing по расстоянию между счётчиками, ветвления, которые компилятор убирает сам, и те, что остаются, — и аппаратные счётчики perf, которые показывают, почему

Процессор давно не ждёт код — он ждёт данные. Попадание в L1 стоит единицы наносекунд, поход в оперативную память — порядка сотни. Если горячий цикл на каждом шаге уходит в память, ускорять арифметику в нём бесполезно. Data-oriented design переворачивает привычку: думать не «какие у меня объекты», а «как данные лягут в кэш и в каком порядке их прочитает цикл».

Data-oriented design и CPU-кэши

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

Стенд — digital-cookbook/performance/data-oriented. Каждое ядро в нём написано дважды: на Go и на C. C служит проверкой воспроизводимости: эффект, который есть и в Go, и в C, не сводится к особенностям одного компилятора. Причину это ещё не устанавливает — оба компилятора могут упираться в одно и то же ограничение или делать похожие преобразования, — поэтому объяснения ниже опираются на отдельные контроли, машинный код и аппаратные счётчики. Генератор случайных чисел у двух версий один, и стенд сверяет контрольные суммы — языки считают одно и то же.

Два процессора

Ядра запускаются на двух машинах с разной архитектурой:

Mac devproxy
процессор Apple M5 AMD Ryzen 9 7940HS w/ Radeon 780M Graphics
архитектура Go arm64 amd64
линия кэша по системе, байт 128 64
cpu.CacheLinePad, байт 128 64
C Apple clang version 21.0.0 (clang-2100.3.34.2) Debian clang version 19.1.7 (3+b1)
Go go1.27.2 go1.27.2
perf нет 6.12.113

Mac — ноутбук автора, ядра на нём запускаются нативно. devproxy — виртуальная машина в Proxmox с типом процессора host: гостю виден настоящий процессор вместе с блоком аппаратных счётчиков (PMU). Это условие оказалось редким. В виртуалках с обобщённым типом процессора (QEMU по умолчанию, x86-64-v2-AES) и в Docker Desktop на Mac все аппаратные события perf отвечают <not supported>, даже в привилегированном контейнере.

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

Вывод проверки стенда
$ python3 scripts/run-checks.py control
{"variant": "control", "outcome": "match", "detail": "суммы C и Go совпадают: Mac M5 да, devproxy Zen 4 да; другое зерно меняет сумму: Mac M5 да, devproxy Zen 4 да; линия, байт: Mac M5 128, devproxy Zen 4 64; CacheLinePad в x/sys/cpu: Mac M5 128, devproxy Zen 4 64; счётчики в --privileged: да, без него: нет"}

Иерархия кэшей: сколько стоит шаг

Чтобы увидеть ступени, нужен доступ, который процессор не может угадать. Ядро chase выкладывает узлы по одному на 128 байт и связывает их в один случайный цикл (алгоритм Саттоло: перестановка, которая обходит все узлы ровно один раз). Каждый шаг читает адрес следующего узла из текущего — следующий запрос нельзя отправить, пока не вернулся предыдущий, и время шага преимущественно отражает задержку зависимой загрузки. Не только её: в шаг входят вычисление адреса, управление циклом, у Go — проверка границ, и трансляция адреса.

// go/main.go
		steps := param("steps", 1<<22)
		ops = steps
		ns, check = measure(func() uint64 {
			i := uint64(0)
			for s := int64(0); s < steps; s++ {
				i = buf[i]
			}
			return i
		}, ops)

Размер буфера растёт от 16 КБ до 256 МБ; в таблице — время шага относительно 16 КБ. Размер буфера — не то же самое, что объём данных в кэше. Узел стоит через 128 байт, и загрузка трогает одну линию: на M5 (линия 128 байт) затронутые линии покрывают весь буфер, на Zen 4 (линия 64 байта) — одну линию из двух, то есть половину буфера: у буфера 4 МБ затронуто 2 МБ. Регулярный шаг к тому же распределяет адреса по наборам кэша неравномерно. Поэтому таблица показывает, как растёт время шага, но не меряет ёмкость каждого уровня:

размер буфера Mac, C Mac, Go devproxy, C devproxy, Go
16K ×1 ×1 ×1 ×1
32K ×1 ×1 ×1 ×1
256K ×2,9 ×3 ×3,1 ×3
4M ×8 ×8,1 ×12,7 ×11,9
64M ×99,8 ×99,3 ×94,4 ×93,5
256M ×102,6 ×103,7 ×95 ×94,9
Вывод проверки стенда
$ python3 scripts/run-checks.py hierarchy
{"variant": "hierarchy", "outcome": "match", "detail": "32K и 16K — одно плато — Mac M5: C да, Go да; devproxy Zen 4: C да, Go да | задержка растёт до RAM — Mac M5: C да, Go да; devproxy Zen 4: C да, Go да | 256M к 16K, раз — Mac M5: C 50-200, Go 50-200; devproxy Zen 4: C 50-200, Go 50-200 | случайный обход медленнее последовательного больше чем в 10 раз на 128 байт — Mac M5: C да, Go да; devproxy Zen 4: C да, Go да"}

Ступени видны у обоих процессоров и у обоих языков одинаково — это свойство железа, а не кода. 16 и 32 КБ помещаются в L1 и идут с одной скоростью. 256 КБ уже не помещаются в L1 — шаг дорожает в несколько раз. На 4 МБ процессоры расходятся: у M5 общий L2 кластера производительных ядер — 16 МБ (sysctl hw.perflevel0.l2cachesize), и рабочее множество в нём ещё помещается; у Zen 4 L2 — 1 МБ на ядро (по спецификации AMD), и 4 МБ уходят в L3, заметно более медленный. С 64 МБ данные не помещаются никуда, и каждый шаг — поход в память, примерно в сто раз дороже шага по L1.

Сюда же входит трансляция адресов: на 256 МБ случайный шаг почти всегда промахивается и мимо TLB. В виртуальной машине эта трансляция двухуровневая — гостевые таблицы страниц, затем таблицы гипервизора.

Тот же объём, но подряд: случайный шаг дороже последовательного прохода по тем же 128 байтам в 24–53,7 раза на Mac (C — 53,7, Go — 24) и в 23,5–37,1 на devproxy (C — 37,1, Go — 23,5).

Последовательный проход не ждёт каждый адрес: следующий адрес известен заранее, префетчер подтягивает линии впереди, и упор идёт в пропускную способность памяти, а не в задержку. У C разница на Mac больше, чем у Go: clang векторизует последовательную сумму, Go — нет.

Отсюда главный рычаг всей темы — локальность. Пространственная: рядом лежащее читается почти бесплатно, потому что память переносится линиями, а не байтами. Временна́я: недавно прочитанное ещё в кэше. Связный список, дерево указателей, срез указателей на объекты в куче — это ставка на то, что соседние по смыслу данные окажутся соседними в памяти. Иногда она выигрывает, и тогда выигрыш даёт аллокатор, а не код.

AoS против SoA

Частица из восьми полей по 8 байт — ровно 64 байта:

// go/main.go
// particle — восемь полей по 8 байт: ровно 64 байта.
type particle struct{ f [8]float64 }

Массив таких структур (AoS, array of structures) хранит поля одной частицы рядом. Структура массивов (SoA, structure of arrays) — восемь отдельных массивов, по одному на поле. Третий вариант, привычный в Go и Java, — срез указателей на отдельно выделенные объекты. Ядро суммирует одно поле или все восемь:

Mac, C Mac, Go devproxy, C devproxy, Go
одно поле, 2M частиц: AoS к SoA 1,68 1,45 1,88 1,78
все восемь полей, 2M: AoS к SoA 0,99 0,87 0,99 0,9
одно поле, 2048 частиц (в кэше): AoS к SoA 0,99 0,97 0,98 0,99
срез указателей по порядку к AoS 1,21 1,2 2,21 1,35
срез указателей вперемешку к AoS 3,87 3,84 5,33 7,81
Вывод проверки стенда
$ python3 scripts/run-checks.py aos_soa
{"variant": "aos_soa", "outcome": "match", "detail": "одно поле, 2M частиц: SoA быстрее AoS больше чем на 25% — Mac M5: C да, Go да; devproxy Zen 4: C да, Go да | все поля, 2M: SoA не быстрее AoS (отношение < 1.25) — Mac M5: C да, Go да; devproxy Zen 4: C да, Go да | одно поле, 2048 частиц: вровень — Mac M5: C да, Go да; devproxy Zen 4: C да, Go да | срез указателей вперемешку медленнее AoS больше чем в 3 раза — Mac M5: C да, Go да; devproxy Zen 4: C да, Go да | срез указателей по порядку — меньше чем в 3 раза — Mac M5: C да, Go да; devproxy Zen 4: C да, Go да | горячие поля отдельно от холодных, 2M: быстрее частицы целиком больше чем в 1.5 раза — Mac M5: C да, Go да; devproxy Zen 4: C да, Go да"}

Одно поле за пределами кэша — случай, ради которого SoA и придумана. AoS тянет из памяти всю 64-байтную частицу ради 8 байт, SoA — только нужное поле. Аппаратный счётчик это подтверждает: обращений к L2 у AoS в несколько раз больше (ниже, в разделе про perf). Но во времени выигрыш SoA — не восьмикратный, а меньше двух раз. Сумма double — цепочка зависимых сложений: каждое ждёт результата предыдущего, и SoA упирается уже не в память, а в задержку сложения. Сколько даёт раскладка, зависит от того, что ещё ограничивает цикл.

Все восемь полей — SoA не выигрывает: читаются те же байты, только из восьми потоков вместо одного. У Go SoA тут даже медленнее AoS. Машинный код показывает разницу: go build -gcflags=-d=ssa/check_bce/debug=1 сообщает об оставшейся проверке границ на soa[j][i] — по одной на каждое из восьми полей частицы, — а в цикле по aos[i].f[j] проверок нет. Что замедление даёт именно она, а не восемь потоков чтения, — гипотеза: отдельным опытом стенд её не проверял.

В кэше (2048 частиц, 128 КБ) в этом ядре суммирования преимущество SoA не наблюдается: ограничением становится цепочка сложений. Это вывод про конкретное ядро, а не про любые данные в кэше: раскладка влияет на векторизацию и на параллельные записи и при попадании в кэш — раздел о false sharing ниже как раз про небольшие данные.

Срез указателей по порядку отстаёт от AoS ненамного: объекты выделены подряд, и аллокатор положил их подряд. Насколько плотно — зависит от аллокатора: Go кладёт 64-байтные объекты в класс размера ровно 64 байта, а malloc из glibc на devproxy добавляет к каждому блоку служебный заголовок, и объекты лежат реже — вероятная причина заметного отставания C на этом хосте. Вперемешку — в несколько раз медленнее. Но заметно быстрее зависимого обхода из прошлого раздела: адреса всех объектов известны заранее из среза, процессор отправляет много промахов параллельно, а в chase каждый следующий адрес ждёт предыдущий. Порядок обхода, расходящийся с порядком в памяти, в реальном коде получается после сортировки среза указателей, вставок в середину, долгой жизни кучи.

От объектов к данным: горячие и холодные поля

Data-oriented design начинается не с выбора между AoS и SoA, а с вопроса, какие поля читает горячий цикл. Пусть цикл считает, сколько частиц пересечёт границу за шаг: ему нужны координата и скорость — два поля из восьми. Остальные шесть (масса, заряд, другие оси) в этом цикле холодные. Разделение хранения выносит горячие поля в отдельный плотный массив, холодные остаются рядом, в своём:

// go/main.go
// Горячие и холодные поля той же частицы: цикл пересечения границы читает
// только x и vx, остальные шесть полей лежат отдельно и в кэш не попадают.
type hotFields struct{ x, vx float64 }
type coldFields struct{ f [6]float64 }

Цикл по горячему массиву читает 16 байт на частицу вместо 64:

// go/main.go
			hot := make([]hotFields, n)
			cold := make([]coldFields, n)
			for i := range hot {
				hot[i] = hotFields{float64((i * 8) % 1000), float64((i*8 + 1) % 1000)}
				for j := range 6 {
					cold[i].f[j] = float64((i*8 + j + 2) % 1000)
				}
			}
			ns, check = measure(func() uint64 {
				c := uint64(0)
				for i := range hot {
					if hot[i].x+hot[i].vx >= 1000 {
						c++
					}
				}
				return c
			}, ops)
Mac, C Mac, Go devproxy, C devproxy, Go
2M частиц: частица целиком к горячим полям отдельно 4,2 3,48 4,71 2,3
2048 частиц (в кэше): то же 0,99 1,03 1,91 1,1

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

«В кэше» для 2048 частиц значит разное для двух раскладок. Частицы целиком занимают 128 КБ, горячие поля — 32 КБ. У производительных ядер M5 L1 данных — 128 КБ (sysctl hw.perflevel0.l1dcachesize), у Zen 4 — 32 КБ. На Zen 4, значит, горячий массив помещается в L1, а частицы целиком живут уже в L2 — условия размещения у вариантов разные ещё до сравнения кода. На Mac в обоих языках и у Go на devproxy выигрыша почти нет, а C на devproxy быстрее и здесь. Причин две, и стенд их не разделяет: разница L1 и L2 на Zen 4 и то, что плотный массив из двух полей компилятору проще обработать векторно.

Это и есть типичный шаг DOD в живом коде: не переписывать всё в структуру массивов, а найти горячий цикл, выписать поля, которые он трогает, и положить их вместе — отдельно от остального.

False sharing

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

// c/dod.c
// ---- fs: две нити, атомарный инкремент на расстоянии dist байт ----
static uint64_t *fs_a, *fs_b;
static long long fs_iters;
static void *fs_worker(void *p) {
	uint64_t *c = p;
	for (long long i = 0; i < fs_iters; i++) __atomic_fetch_add(c, 1, __ATOMIC_RELAXED);
	return NULL;
}
static uint64_t k_fs(void) {
	*fs_a = 0; *fs_b = 0;
	pthread_t t1, t2;
	pthread_create(&t1, NULL, fs_worker, fs_a);
	pthread_create(&t2, NULL, fs_worker, fs_b);
	pthread_join(t1, NULL);
	pthread_join(t2, NULL);
	return *fs_a + *fs_b;
}
расстояние, байт Mac, C Mac, Go devproxy, C devproxy, Go
8 ×6,96 ×6,65 ×6,73 ×5,47
16 ×7,63 ×7,01 ×6,75 ×5,17
32 ×7,56 ×6,73 ×6,59 ×5,48
64 ×1,02 ×1,01 ×1 ×1
128 ×1,04 ×1,01 ×1 ×1
Вывод проверки стенда
$ python3 scripts/run-checks.py false_sharing
{"variant": "false_sharing", "outcome": "match", "detail": "в 2+ раза медленнее, чем на 256 байтах, при 8 — Mac M5: C да, Go да; devproxy Zen 4: C да, Go да | в 2+ раза медленнее, чем на 256 байтах, при 16 — Mac M5: C да, Go да; devproxy Zen 4: C да, Go да | в 2+ раза медленнее, чем на 256 байтах, при 32 — Mac M5: C да, Go да; devproxy Zen 4: C да, Go да | в 2+ раза медленнее, чем на 256 байтах, при 64 — Mac M5: C нет, Go нет; devproxy Zen 4: C нет, Go нет | в 2+ раза медленнее, чем на 256 байтах, при 128 — Mac M5: C нет, Go нет; devproxy Zen 4: C нет, Go нет"}

На обоих процессорах эффект кратный, пока счётчики ближе 64 байт, и в этом опыте пропадает с 64. Для Zen 4 это ожидаемо: линия 64 байта. Для M5 — нет: sysctl hw.cachelinesize отвечает 128, и Go в golang.org/x/sys/cpu для arm64 берёт паддинг 128 байт. Конфигурация при этом самая строгая из возможных: база выровнена на 256, и при расстоянии 64 оба счётчика лежат в одном выровненном 128-байтном блоке — и всё равно штрафа нет.

Но вывод у этого опыта узкий: в этой конфигурации теста атомарных счётчиков расстояние 64 байта устранило наблюдаемый штраф. Универсального размера паддинга для M5 это не устанавливает. Стенд не фиксирует, на какие ядра попали нити и в каком они кластере — на Mac планировщик выбирает между производительными и энергоэффективными ядрами, и закрепить нить за ядром macOS не даёт; не проверены другие смещения базы и независимые неатомарные записи. Поэтому в коде, который должен работать на любом arm64, паддинг по cpu.CacheLinePad — разумный выбор, а 64 байта ручного паддинга, как в статье о примитивах sync, — то, что этот опыт подтвердил только для двух машин стенда.

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

Предсказание переходов

Классический пример: отсортированный массив обрабатывается быстрее несортированного, потому что условие v >= 128 на отсортированных данных предсказуемо, а на случайных предсказатель ошибается в половине случаев, и каждая ошибка сбрасывает конвейер. Стенд проверяет его в двух видах — сумма с условием и отбор в выходной массив — и для каждого есть вариант без ветвления:

ядро: несортированные к отсортированным Mac, C Mac, Go devproxy, C devproxy, Go
сумма с условием ×0,99 ×1,01 ×1,01 ×1
сумма по маске ×1,01 ×1,05 ×1 ×0,99
отбор в массив с условием ×13,87 ×9,42 ×8,53 ×4,97
отбор без условия ×0,99 ×0,95 ×1,01 ×0,99
Вывод проверки стенда
$ python3 scripts/run-checks.py branch
{"variant": "branch", "outcome": "match", "detail": "сумма с условием: несортированные к отсортированным — Mac M5: C <1.5, Go <1.5; devproxy Zen 4: C <1.5, Go <1.5 | сумма по маске: несортированные к отсортированным — Mac M5: C <1.5, Go <1.5; devproxy Zen 4: C <1.5, Go <1.5 | отбор в массив с условием: несортированные к отсортированным — Mac M5: C >3, Go >3; devproxy Zen 4: C >3, Go >3 | отбор без условия: несортированные к отсортированным — Mac M5: C <1.5, Go <1.5; devproxy Zen 4: C <1.5, Go <1.5 | несортированные: отбор с условием медленнее отбора без условия больше чем в 2 раза — Mac M5: C да, Go да; devproxy Zen 4: C да, Go да | отсортированные: отбор с условием к отбору без условия меньше 1.5 — Mac M5: C да, Go да; devproxy Zen 4: C да, Go да"}

Сумма с условием не замедляется на случайных данных ни в одном языке. Ни clang, ни Go 1.27 не оставили в ней условного перехода. Это проверено по машинному коду, а не по времени: стенд собирает ядра с выводом ассемблера тем же компилятором, что и для замеров, на каждом хосте, и смотрит, есть ли условный переход среди инструкций строки с условием. Go превращает условное прибавление в условную пересылку (CMOVQCC на amd64, CSEL на arm64 в выводе go build -gcflags=-S), clang векторизует цикл целиком, и условие становится векторной маской. Перехода нет — предсказывать нечего, и сортировка ничего не даёт.

Вывод проверки стенда
$ python3 scripts/run-checks.py codegen
{"variant": "codegen", "outcome": "match", "detail": "Mac M5: условный переход на строке условия — C: сумма с условием нет, отбор с условием да, отбор без условия нет; Go: сумма с условием нет, отбор с условием да, отбор без условия нет; сумма в C векторизована — да | devproxy Zen 4: условный переход на строке условия — C: сумма с условием нет, отбор с условием да, отбор без условия нет; Go: сумма с условием нет, отбор с условием да, отбор без условия нет; сумма в C векторизована — да"}

Детектор проверен на обратном случае: в отборе без условия на строке условия переходов нет, хотя в цикле они есть — переход управления циклом детектор не засчитывает.

Отбор в массив — другое дело. Запись по условно растущему индексу компилятор в условную пересылку не превращает, условный переход на строке условия остаётся у обоих компиляторов, и на случайных данных отбор в разы медленнее, чем на отсортированных:

// go/main.go
		case "filter":
			// Отбор байтов >= 128 в выходной срез: запись по условному
			// индексу компилятор в cmov не превращает — ветка остаётся.
			ns, check = measure(func() uint64 {
				k := 0
				for _, v := range data {
					if v >= 128 {
						out[k] = v
						k++
					}
				}
				return uint64(k) + uint64(out[k/2])
			}, ops)

Вариант без ветвления пишет каждый байт и сдвигает индекс только на подходящем — лишняя запись дешевле ошибки предсказания:

// go/main.go
		case "filter_branchless":
			ns, check = measure(func() uint64 {
				k := 0
				for _, v := range data {
					out[k] = v                   // пишем всегда,
					k += int((uint(v) >> 7) & 1) // сдвигаемся только на подходящем
				}
				return uint64(k) + uint64(out[k/2])
			}, ops)

Ему порядок данных безразличен. Прямое сравнение двух вариантов отбора на одних и тех же данных:

отбор с условием к отбору без условия Mac, C Mac, Go devproxy, C devproxy, Go
несортированные данные ×9,1 ×10,5 ×9,89 ×5,59
отсортированные данные ×0,65 ×1,06 ×1,17 ×1,11

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

Осталось ли ветвление после компилятора, устанавливает только машинный код. Счётчик branch-misses отвечает на другой вопрос — ошибается ли предсказатель: у отбора с условием на отсортированных данных промахов почти нет, хотя переход в коде на месте (таблица счётчиков ниже).

Измерять, а не гадать

Всё выше — время. Почему оно такое, показывают аппаратные счётчики: perf stat считает события процессора за время работы программы. Чтобы счётчики относились к ядру, а не к заполнению массивов, стенд запускает каждое ядро дважды — только с подготовкой данных и с подготовкой и прогонами — и делит разность на число операций. Это два отдельных процесса, поэтому результат — оценка вклада ядра после вычитания подготовки, а не точное выделение событий цикла:

perf stat -e cycles,instructions,cache-references,cache-misses,branch-misses -- ./dod-c filter n=4194304 sorted=0
ядро событие C Go
обход 16K, на шаг cache-misses 0,000 0,001
обход 256M, на шаг cache-misses 1,030 1,054
AoS, 2M частиц, на частицу cache-misses 0,004 0,003
SoA, 2M, на частицу cache-misses 0,000 0,001
AoS, 2M, на частицу cache-references 2,024 2,086
SoA, 2M, на частицу cache-references 0,305 0,316
сумма с условием, несортированные, на элемент branch-misses 0,000 0,000
отбор с условием, несортированные, на элемент branch-misses 0,501 0,500
отбор с условием, отсортированные, на элемент branch-misses 0,000 0,000
отбор без условия, несортированные, на элемент branch-misses 0,000 0,000
Вывод проверки стенда
$ python3 scripts/run-checks.py counters
{"variant": "counters", "outcome": "match", "detail": "devproxy — cache-misses на шаг, 16K: C <0.05, Go <0.05; cache-misses на шаг, 256M: C >0.5, Go >0.5; cache-misses на частицу, AoS за кэшем: C <0.1, Go <0.1; cache-references AoS больше SoA в 4+ раза: C да, Go да; branch-misses суммы с условием, несортированные: C <0.05, Go <0.05; то же, отсортированные: C <0.05, Go <0.05; branch-misses суммы по маске: C <0.05, Go <0.05; branch-misses отбора, несортированные: C >0.3, Go >0.3; то же, отсортированные: C <0.05, Go <0.05; branch-misses отбора без условия: C <0.05, Go <0.05; все события считались всё время, без мультиплексирования: C да, Go да"}

Имена perf — обобщённые; на каждом процессоре ядро Linux сопоставляет им своё событие. Для Zen 4 (Linux 6.12, arch/x86/events/amd/core.c и описания событий pmu-events/arch/x86/amdzen4):

имя в perf событие Zen 4 что учитывает
cache-references 0xff60, l2_request_g1.all все запросы к L2 — от промахов L1 данных и инструкций, включая предвыборку в L2
cache-misses 0x0964, l2_cache_req_stat.ic_dc_miss_in_l2 промахи в L2 запросов ядра от промахов L1; запросы предвыборки самого L2 не входят
branch-misses 0x00c3, ex_ret_brn_misp ошибочно предсказанные переходы среди завершённых инструкций

Ни одно из этих событий не считает байты, пришедшие из памяти: это запросы к L2 и их исходы. На другом процессоре те же имена значат другое — на Intel cache-misses относится к последнему уровню кэша.

Что видно в счётчиках:

  • Зависимый обход на 256 МБ даёт около одного промаха на шаг, на 16 КБ — ноль: ступени из первого раздела — это промахи.
  • AoS против SoA: cache-misses почти нулевые у обоих. Это согласуется с работой префетчера — линии потокового обхода приезжают в L2 раньше запроса, а предвыборка в этот счётчик не входит, — но само по себе этого объяснения не доказывает: стенд не снимал события префетчера отдельно. Разницу показывают cache-references — обращения к L2: у AoS их в разы больше, потому что у AoS своя линия у каждой частицы, а у SoA одна линия на восемь. Отсюда практический вывод: низкий cache-misses не значит, что цикл не упирается в память.
  • Ветвления: у суммы с условием промахов предсказания нет ни в C, ни в Go — ветки нет. У отбора на случайных данных — порядка половины промаха на элемент, ровно как у монетки; на отсортированных и без ветвления — ноль.

Ещё одно условие доверия к числам: аппаратных счётчиков мало, и если событий больше, чем счётчиков, perf мультиплексирует их — считает каждое часть времени и досчитывает значение пропорционально. Доля времени работы счётчика выводится в той же строке perf stat -x, и стенд её сохраняет и проверяет: во всех прогонах все пять событий считались всё время. Разбор доли проверен подстановкой строки с долей 1% — она не теряется.

Счётчики есть не везде: на Linux с perf и доступом к PMU (в контейнере — --privileged или CAP_PERFMON; в виртуалке — тип процессора host). Стенд проверяет и обратное: тот же образ без --privileged счётчиков не получает. На macOS аналог — Instruments с шаблоном CPU Counters.

Где это оправдано

Data-oriented design окупается в горячих циклах по большим массивам: обработка частиц и сущностей, колоночные вычисления, разбор и фильтрация потоков, индексы и хеш-таблицы. Признаки того, что пора думать о раскладке: профиль показывает время в цикле, а не в системных вызовах; данные цикла не помещаются в L2; в цикле обход по указателям. Порядок действий — как в стенде: сначала время, потом счётчики, потом раскладка.

Где скорее не оправдано: код, который ждёт сеть или диск, и циклы по десяткам элементов. Для данных в кэше правила нет: для нашего ядра суммирования на малом рабочем множестве преимущество SoA не наблюдается, но раскладка может открыть или закрыть векторизацию и в L1. Паддинг от false sharing — отдельный случай: он про запись из нескольких потоков и нужен и для крошечных данных.

Итоги стенда в одну строку каждый:

  • шаг в память дороже шага по L1 примерно в сто раз; последовательный проход прячет задержку, случайный — нет;
  • SoA и раздельное хранение горячих полей выигрывают, когда цикл читает часть полей большого массива; в ядре суммирования выигрыша нет, когда нужны все поля или данные в кэше;
  • срез указателей быстр, пока порядок обхода совпадает с порядком в памяти;
  • в тесте атомарных счётчиков false sharing на обоих процессорах пропал при 64 байтах между счётчиками — для M5 это наблюдение конфигурации, а не установленный размер паддинга;
  • простое условие в сумме оба компилятора превратили в код без перехода — сортировка для него бесполезна; ветвление, которое осталось, на случайных данных стоит кратного замедления.

Версии

Go 1.27.2 и golang.org/x/sys v0.49.0 на обоих хостах; на Mac — Apple clang 21.0.0, на devproxy — образ golang:1.27.2-trixie с clang 19 и perf 6.12 из Debian 13. Сборка C — clang -O2, Go — go build без флагов.

Обсуждение в Telegram

Присоединиться →