Cache lines и false sharing: когда параллелизм замедляет код

Два thread. Каждый пишет в свою переменную. Нет shared state. Нет mutex. Нет contention — по крайней мере, так кажется из кода. Параллельная версия в три раза медленнее однопоточной.

Cache lines: единица transfer

Data не двигается между RAM и cache по одному байту. Единица — cache line (64 байта на x86 и большинстве ARM, 128 байт на некоторых Apple Silicon и ARM server cores).

Читаешь байт на адресе X — CPU грузит байты X до X+63 в cache, все сразу. Поэтому sequential access так быстр: первый read грузит 8 doubles за раз; следующие 7 — бесплатные L1-хиты.

MESI протокол

В multi-core системе каждое ядро имеет свой L1/L2 cache. Чтобы данные были согласованы, hardware использует MESI протокол: каждая cache line находится в одном из четырёх состояний:

• M (Modified) — только у этого core, изменена (dirty).
• E (Exclusive) — только у этого core, не изменена.
• S (Shared) — у нескольких cores, read-only.
• I (Invalid) — копия устарела, нужно re-fetch.

Когда core A пишет в line, MESI отправляет invalidation всем cores, у которых есть копия. Их line переходит в состояние I. При следующем обращении они должны re-fetch.

False sharing

False sharing случается, когда два thread пишут в разные переменные, случайно находящиеся в одной cache line.

struct Counters {
    int64_t thread0_count;  // байты 0–7
    int64_t thread1_count;  // байты 8–15
    // обе переменные в одной 64-байтной cache line
};

Thread 0 пишет thread0_count, thread 1 пишет thread1_count. С точки зрения кода — нет shared state. С точки зрения MESI — каждая запись invalidates cache другого thread. Line ping-pong-ит между cores:

T=0: Core 0 пишет → line в M (Core 0)
T=1: Core 1 пишет → Core 0's copy становится I → Core 1 re-fetch → 30–50 циклов
T=2: Core 0 пишет снова → Core 1's copy становится I → Core 0 re-fetch → ещё 30–50 циклов
...

Параллельная работа становится serialized ожиданием cache coherency.

Фикс: padding до 64 байт.

struct Counters {
    alignas(64) int64_t thread0_count;  // занимает собственную cache line
    alignas(64) int64_t thread1_count;  // занимает собственную cache line
};

Или padding вручную:

struct Counter {
    int64_t value;
    char padding[56];  // 8 + 56 = 64 байта ровно
};

Struct layout и struct splitting

Cache line behaviour влияет не только на multi-threading. Struct layout критичен и для single-threaded hot loops.

Рассмотрим:

struct Entity {
    float x, y, z;       // 12 байт — горячие, нужны каждый кадр
    char name[64];        // 64 байта — холодные, нужны редко
    float health;         // 4 байта — горячие
    // total: 80 байт = 2 cache lines
};

Hot loop, обрабатывающий 10 000 entity каждый кадр, читает только x, y, z, health — 16 байт. Но загружает 80 байт (2 cache lines) per entity, потому что name засоряет cache.

Struct splitting (field shuffling): разделяй горячие и холодные поля.

struct EntityHot {
    float x, y, z, health;  // 16 байт — 4 элемента per cache line
};
struct EntityCold {
    char name[64];           // редко нужен
};
EntityHot hot_data[N];  // dense array
EntityCold cold_data[N]; // accessed by index

Теперь hot loop грузит 4 EntityHot per cache line вместо 1 Entity per 2 lines. Cache pressure в 8x ниже.