Pole a cache: optimalizace přístupu O(1)

# Optimalizace polí pro minimalizaci cache missů

Sekvenční přístup k prvkům pole je 7–10krát rychlejší než náhodný díky vlastnostem funkce cache paměti. Jedna cache linka o 64 bajtech načte 16 sekvenčních int, což minimalizuje promyhy při správném vzoru procházení. Profilování perf stat odhaluje problém: 450k cache-misses na 1M instrukcí ukazuje na neoptimální využití polí i v jednoduchých úlohách zpracování paketů.

Vliv kroku přístupu na výkon

Krok přístupu určuje efektivitu načítání cache linek. Při kroku 1 se všech 64 bajtů využije naplno, prefetcher rozpozná vzor a urychlí načítání.

int sum = 0;
for (int i = 0; i < 8; i++) {
    sum += array[i];
}

Takový sekvenční přístup vyžaduje 107 taktů na 8 prvků (13,4 taktu/prvek). Náhodný přístup přes indexy zvyšuje náklady na 800 taktů (100 taktů/prvek).

Benchmark na poli 1M prvků:

• Krok 1: 1,2 ms (100% využití linek)
• Krok 2: 1,3 ms (50% využití)
• Krok 4: 1,5 ms
• Krok 8: 2,1 ms
• Krok 16: 3,8 ms (6,25% využití)
• Krok 64: 8,5 ms

Doporučení: krok ≤8 prvků pro přijatelný výkon. Nástroj lmbench lat_mem_rd potvrzuje: malé kroky (128–512 bajtů) drží data v L1 (3–4 ns), velké (64 KB) vyhodí do DRAM (100+ ns).

Vícedimenzionální pole: pořadí procházení je klíčové

C používá row-major pořadí: prvky řádku jsou v paměti sousední. Procházení po řádcích zajišťuje sekvenční přístup, po sloupcích — krok 16+ bajtů.

int matrix[4][4] = {
    {0, 1, 2, 3},
    {4, 5, 6, 7},
    {8, 9, 10, 11},
    {12, 13, 14, 15}
};

Pro matici 1024×1024 trvá procházení po řádcích 12 ms, po sloupcích — 45 ms (3,75× pomalejší).

Optimalizace násobení matic

Naivní ijk-pořadí:

for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        for (int k = 0; k < N; k++) {
            C[i][j] += A[i][k] * B[k][j];
        }
    }
}

Problém: B[k][j] se čte po sloupcích (krok N=1024, 4096 bajtů). Pořadí ikj to opraví:

for (int i = 0; i < N; i++) {
    for (int k = 0; k < N; k++) {
        int r = A[i][k];
        for (int j = 0; j < N; j++) {
            C[i][j] += r * B[k][j];
        }
    }
}

Výsledek pro 512×512: ijk — 2450 ms, ikj — 680 ms (3,6× zrychlení).

Pro velké matice — tiling s BLOCK_SIZE=64:

for (int ii = 0; ii < N; ii += BLOCK_SIZE) {
    for (int jj = 0; jj < N; jj += BLOCK_SIZE) {
        for (int kk = 0; kk < N; kk += BLOCK_SIZE) {
            for (int i = ii; i < min(ii + BLOCK_SIZE, N); i++) {
                for (int k = kk; k < min(kk + BLOCK_SIZE, N); k++) {
                    int r = A[i][k];
                    for (int j = jj; j < min(jj + BLOCK_SIZE, N); j++) {
                        C[i][j] += r * B[k][j];
                    }
                }
            }
        }
    }
}

Bloky se vejdou do L1, data se znovu využijí. Pro 1024×1024: 1800 ms (10× rychlejší než naivní).

AoS vs SoA: organizace dat

Array of Structures (AoS) grupuje pole částice, ale cache linka obsahuje nepotřebná data (37,5% využití).

typedef struct {
    float x, y, z;
    float vx, vy, vz;
    float mass;
    int id;
} particle_t;

Structure of Arrays (SoA) rozděluje podle typů:

typedef struct {
    float x[1000], y[1000], z[1000];
    float vx[1000], vy[1000], vz[1000];
    float mass[1000];
    int id[1000];
} particles_t;

Aktualizace pozic v SoA využívá cache linky na 100 %. Benchmark 1M částic, 1000 iterací: AoS — 2850 ms, SoA — 1200 ms (2,4× zrychlení).

Co je důležité

• Sekvenční přístup k poli minimalizuje cache promyhy 7+krát oproti náhodnému
• Krok přístupu ≤8 prvků zajišťuje >90% využití cache linek
• Row-major pořadí v C vyžaduje procházení po řádcích; sloupcový přístup zpomalí 3–4×
• Změna pořadí cyklů v maticových operacích dá 3–4× zrychlení
• SoA překonává AoS při SIMD-zpracování a častém přístupu k podmnožině polí

— Editorial Team