Ложное разделение: счётчики в одной кеш-линии

Что болело

Параллельный сборщик статистики: N потоков, каждый инкрементит свой счётчик в массиве uint64_t cnt[N]. По логике - идеальное распараллеливание, потоки не трогают чужие ячейки. На деле на восьми потоках было медленнее, чем на двух, и это первый признак, что потоки всё-таки дерутся за общий ресурс, которого я не вижу в коде.

perf c2c

Когда потоки конкурируют за память, которой в коде не делят, это почти всегда ложное разделение - разные данные в одной кеш-линии. Прибор ровно под это - perf c2c, он ловит передачи модифицированной линии между ядрами (HITM, hit-modified):

$ perf c2c record ./collect && perf c2c report --stdio
  Shared Data Cache Line Table
  #        Total      Tot  ----- HITM -----
  # Index  records    Hitm  LclHitm  RmtHitm   Cacheline
       0    284113   96.4%    14201M        0   0x55a1c0004a00
  Shared Cache Line Distribution
    Off   Node  PID    cpu  code addr      symbol
   0x00     0  2041     1   collect+0x41   cnt[0]
   0x08     0  2042     3   collect+0x41   cnt[1]
   0x10     0  2043     5   collect+0x41   cnt[2]

Одна кеш-линия по адресу cnt[0], 96 % всех HITM, и в её распределении видно восемь разных PID по смещениям 0x00, 0x08, 0x10… Восемь счётчиков uint64_t по 8 байт лежат подряд и укладываются ровно в одну 64-байтную линию. Каждый инкремент любого из них делает линию грязной у одного ядра, и остальным семи приходится тащить её к себе по шине заново - это и есть ложное разделение.

Выравнивание

Лечится раскладыванием счётчиков по разным линиям. Самый прямой способ - обернуть счётчик в структуру размером с кеш-линию и выровнять её:

#define CACHELINE 64

struct counter {
    _Alignas(CACHELINE) uint64_t v;
    char pad[CACHELINE - sizeof(uint64_t)];
};
static struct counter cnt[NTHREAD];   /* теперь каждый в своей линии */

Паддинг нужен не только для выравнивания начала, но и чтобы следующий счётчик не заполз в хвост этой же линии; без pad компилятор поставил бы соседа вплотную. 64 байта - это размер линии на этом x86; на aarch64-стенде он тоже 64, но закладываться вслепую нельзя - размер берут из /sys/.../cache/index0/coherency_line_size, а не из головы. Цена - память: восемь счётчиков вместо 64 байт занимают 512, но счётчиков тут десятки, не миллионы.

Числа

Стенд: x86-64, 8 ядер / 32 ГиБ, линия 64 байта, ядро 6.6, gcc 13.2, -O2, пять прогонов, медиана; счётчики инкрементятся 2 млрд раз суммарно.

На двух потоках разница почти нулевая - линию делят двое, драка редкая. Вся беда вылезает с ростом потоков: плотная раскладка на восьми не ускорилась, а замедлилась (отрицательное масштабирование), выровненная дала ожидаемый рост. HITM упали на три с лишним порядка.

Где я ошибся

Моя ошибка была в том, что я добавил потоков, увидел замедление и полез искать ложку в планировщике и привязке к ядрам. Отрицательное масштабирование от числа потоков при независимых по виду данных - это почти диагноз ложного разделения, и начинать надо было с perf c2c, а не с taskset. Правило: если потоки формально ничего не делят, а скорость падает с их числом, ищи общую кеш-линию, прежде чем винить ядро.