Процессор давно не ждёт код — он ждёт данные. Попадание в L1 стоит единицы наносекунд, поход в оперативную память — порядка сотни. Если горячий цикл на каждом шаге уходит в память, ускорять арифметику в нём бесполезно. Data-oriented design переворачивает привычку: думать не «какие у меня объекты», а «как данные лягут в кэш и в каком порядке их прочитает цикл».
Тема продолжает статью про управление памятью в разных языках: там — аллокации и сборка мусора, здесь — что происходит с уже размещёнными данными на пути через кэши. Как найти горячий цикл, которому всё это нужно, разобрано в статье о профилировании.
Стенд — 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
Присоединиться →