CPU cache hiyerarşisi ve locality of reference nedir? Kodun cache dostu olması performansı nasıl etkiler? False sharing nedir?

CPU, ana bellekten (RAM) yüzlerce kat daha hızlıdır; aradaki farkı kapatmak için küçük ama hızlı L1, L2, L3 cache'ler kullanılır. Cache'ler veriyi cache line (genelde 64 byte) birimleriyle getirir. Programın erişim düzeni ne kadar öngörülebilirse cache o kadar etkili olur; buna locality of reference denir.

Yaklaşık gecikmeler (mertebe olarak)

Locality türleri

• Temporal locality: yakın zamanda erişilen veriye kısa süre içinde tekrar erişilir (döngü sayaçları, sık kullanılan nesneler).
• Spatial locality: erişilen adresin komşularına da erişilir (dizileri sırayla gezmek).

Örnek: satır ve sütun bazlı gezinme

C/Java'da 2D diziler satır öncelikli (row-major) saklanır:

// Hızlı: bellekte ardışık erişim, her cache line tam kullanılır
for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
        sum += a[i][j];

// Yavaş: her erişim N * sizeof(int) byte atlar, sürekli cache miss
for (int j = 0; j < N; j++)
    for (int i = 0; i < N; i++)
        sum += a[i][j];

Büyük N için ikinci döngü birkaç kat yavaş olabilir; Big-O aynı olsa bile.

Pratik sonuçlar

• Dizi (array) tabanlı yapılar, bağlı listelerden genelde çok daha hızlıdır; bağlı liste düğümleri bellekte dağınıktır ve pointer takibi cache miss üretir.
• Oyun motorlarında ve veri işleme sistemlerinde Array of Structs yerine Struct of Arrays düzeni tercih edilir.
• Columnar veritabanları (ClickHouse, Parquet) aynı fikri disk ve bellek seviyesinde uygular.

False sharing

İki thread farklı değişkenleri güncelliyor ama bu değişkenler aynı cache line'da duruyorsa, her yazma diğer çekirdeğin cache line'ını geçersiz kılar (cache coherence, MESI protokolü). Mantıken paylaşım yokken performans çöker.

class Counters {
    volatile long a;   // thread 1 yazar
    volatile long b;   // thread 2 yazar -> muhtemelen aynı 64 byte'lık satırda
}

Çözüm: değişkenleri padding ile ayrı cache line'lara koymak (Java'da @jdk.internal.vm.annotation.Contended; uygulama kodunda -XX:-RestrictContended bayrağı gerekir, C++17'de alignas(std::hardware_destructive_interference_size)) veya her thread'in kendi yerel sayacını tutup sonda birleştirmek.