Program bisa kehilangan faktor sepuluh kecepatannya tanpa satu pun instruksi tambahan — cukup karena data diakses dengan urutan yang tidak ramah cache. Prosesor modern tidak pernah membaca satu byte dari RAM; ia menarik satu blok sekaligus yang disebut cache line, dan CPU jauh lebih cepat daripada RAM utama sehingga setiap “perjalanan jauh” berarti menunggu ratusan siklus. Cache locality adalah prinsip menyusun dan mengakses data agar data yang dipakai berdekatan, baik dalam waktu (temporal locality) maupun dalam alamat (spatial locality). Chapter ini menghitung biaya cache secara teoretis, lalu membuktikan dampaknya dengan pengukuran nyata di platform uji (Debian, g++ 14.2, CPU 2 core).

Hierarki Memori dan Cache Line 64 Byte #

Data yang dipegang prosesor bertingkat dari yang paling cepat dan paling kecil: register, cache L1 (biasanya puluhan KB, beberapa siklus), cache L2 (satu sampai beberapa MB, belasan siklus), cache L3 (puluhan MB, puluhan siklus), lalu RAM utama (ratusan siklus atau lebih). Angka pastinya berbeda antar prosesor, tetapi rasio bahannya stabil: setiap tingkat di bawahnya berukuran lebih besar dan lebih lambat satu orde magnitude. Satuan pemindahan antar tingkat ini adalah cache line, dan di hampir semua hardware x86 serta ARM modern besarnya 64 byte.

Konsekuensi cache line 64 byte mudah dihitung: membaca satu int berarti menarik 64 byte, dan 60 byte sisanya ikut datang gratis — terpakai bila elemen berikutnya yang kita baca memang bertetangga, terbuang bila tidak. Di situlah bedanya akses berurutan versus melompat: akses berurutan memanfaatkan seluruh isi line dan hardware prefetcher ikut menarik line berikutnya lebih awal, sedangkan akses melompat membayar satu perjalanan penuh untuk setiap elemen.

Menghitung Cache Line: Traversal Baris vs Kolom #

Matriks dua dimensi di C++ sebenarnya satu blok memori yang disusun baris-demi-baris (row-major): elemen [baris][kolom] berada di alamat baris * jumlah_kolom + kolom. Program berikut menghitung biaya cache dua arah pemindaian untuk matriks 1024 x 1024:

cpp 
// Menghitung biaya cache secara teoretis untuk dua cara memindai
// matriks berurutan C++ (row-major). Semua angka hasil penghitungan,
// bukan pengukuran waktu, sehingga nilainya tetap di mesin mana pun.
#include <iostream>
#include <new>

constexpr int N = 1024;                                  // matriks 1024 x 1024
constexpr int CACHE_LINE = 64;
constexpr int INT_PER_LINE = CACHE_LINE / sizeof(int);   // 16 int per line

int main() {
    std::cout << "matriks " << N << "x" << N << " int = "
              << 1LL * N * N * sizeof(int) << " byte (4 MB)\n";
    std::cout << "satu cache line = " << CACHE_LINE << " byte = "
              << INT_PER_LINE << " int berurutan\n";

    // Traversal baris: menyapu memori berurutan, tiap line terpakai penuh.
    std::cout << "traversal baris : "
              << 1LL * N * N / INT_PER_LINE
              << " pengambilan line, 64 byte per line terpakai\n";

    // Traversal kolom: jarak antar elemen = 1024 x 4 = 4096 byte,
    // jauh melewati batas satu line, dan matrix 4 MB jauh melebihi
    // kapasitas cache L1/L2 sehingga line lama sudah tergusur.
    std::cout << "traversal kolom : "
              << 1LL * N * N
              << " pengambilan line (hanya 4 byte per line terpakai)\n";
    std::cout << "efisiensi line kolom: 4 dari 64 byte\n";

    // Alignment eksplisit: menjamin satu objek menempati satu line sendiri.
    struct PenghitungSejajar {
        alignas(CACHE_LINE) long nilai;
    };
    std::cout << "sizeof(PenghitungSejajar) = " << sizeof(PenghitungSejajar)
              << " byte\n";
    std::cout << "hardware_destructive_interference_size = "
              << std::hardware_destructive_interference_size << '\n';
    return 0;
}

Output yang Dihasilkan:

text 
matriks 1024x1024 int = 4194304 byte (4 MB)
satu cache line = 64 byte = 16 int berurutan
traversal baris : 65536 pengambilan line, 64 byte per line terpakai
traversal kolom : 1048576 pengambilan line (hanya 4 byte per line terpakai)
efisiensi line kolom: 4 dari 64 byte
sizeof(PenghitungSejajar) = 64 byte
hardware_destructive_interference_size = 64

Bedah baris penting:

  1. Ukuran data 4 MB: jauh melebihi cache L1/L2 tipikal, sehingga line yang jarang disentuh akan tergusur sebelum dipakai lagi — syarat agar perhitungan kasar ini valid.
  2. Traversal baris: menyapu 4 MB berurutan membutuhkan 4.194.304 / 64 = 65.536 pengambilan line, dan seluruh 64 byte setiap line terpakai. Ini jumlah minimum teoretis.
  3. Traversal kolom: jarak dua elemen berurutan dalam satu kolom adalah 1024 × 4 = 4096 byte, jauh melewati satu line; setiap elemen menarik line baru yang hanya menyumbang 4 byte. Totalnya 1.048.576 pengambilan — 16 kali lebih banyak perjalanan memori untuk pekerjaan yang persis sama.
  4. alignas(64): menjamin struct menempati satu cache line sendiri; sizeof menjadi tepat 64 byte meski anggotanya hanya satu long. Konstanta hardware_destructive_interference_size (64 di platform ini) adalah cara standar C++ menanyakan jarak anti-false-sharing ke compiler.

Angka 16 kali itu masih angka penghitungan. Pertanyaannya: apakah perbedaan itu terlihat di stopwatch?

Melihat Dampaknya Secara Nyata #

Program berikut menjumlahkan seluruh elemen matriks 3000 x 3000 (36 MB) dua kali — sekali memindai baris-demi-baris, sekali kolom-demi-kolom — dengan isi dan jumlah operasi identik:

cpp Pengukuran durasi traversal matriks — angka milidetik bervariasi antar eksekusi dan antar mesin 
#include <chrono>
#include <iostream>
#include <vector>

int main() {
    const int N = 3000;
    std::vector<int> m(static_cast<std::size_t>(N) * N, 1);
    auto mulai = std::chrono::steady_clock::now();
    long long totalBaris = 0;
    for (int baris = 0; baris < N; ++baris)
        for (int kolom = 0; kolom < N; ++kolom)
            totalBaris += m[static_cast<std::size_t>(baris) * N + kolom];
    auto tengah = std::chrono::steady_clock::now();
    long long totalKolom = 0;
    for (int kolom = 0; kolom < N; ++kolom)
        for (int baris = 0; baris < N; ++baris)
            totalKolom += m[static_cast<std::size_t>(baris) * N + kolom];
    auto selesai = std::chrono::steady_clock::now();
    auto d1 = std::chrono::duration_cast<std::chrono::milliseconds>(tengah - mulai).count();
    auto d2 = std::chrono::duration_cast<std::chrono::milliseconds>(selesai - tengah).count();
    std::cout << "baris: " << d1 << " ms, kolom: " << d2
              << " ms, total: " << totalBaris << '/' << totalKolom << '\n';
    return 0;
}

Hasil Eksekusi (satu run nyata di platform uji; jalankan beberapa kali dan angkanya akan bergetar, arah perbedaannya tidak):

text 
baris: 2 ms, kolom: 51 ms, total: 9000000/9000000

Kedua loop menghasilkan jumlah yang sama persis dan mengerjakan 9 juta penjumlahan, tetapi traversal kolom memakan waktu sekitar 25 kali lebih lama. Kode yang “hanya” menukar posisi dua loop ternyata mengubah pola akses memori secara fundamental. Perhatikan juga traversal baris cepat tidak wajar untuk 9 juta elemen: compiler -O2 memvektorisasi loop berurutan menjadi instruksi SIMD, memperlebar lagi jurangnya — keuntungan locality dan vektorisasi saling menguatkan.

Locality sebagai Prinsip Desain #

Dari sini kita menarik tiga kebiasaan desain. Pertama, utamakan struktur yang menyimpan data terkait berdekatan: std::vector dan std::array menang dari senarai berantai dan pointer bolak-balik, karena tiap node senarai memaksa perjalanan memori sendiri. Kedua, pindai data mengikuti tata letak memorinya: loop terluar untuk baris, loop terdalam untuk kolom pada array C++ standar. Ketiga, saat struct punya banyak field tetapi hot loop hanya memakai beberapa, pisahkan field yang panas — idiom yang disebut struct of arrays, dan akan kita bangun utuh pada chapter Data-oriented Design.

Sebelum sampai ke desain data besar-besaran, ada lapisan yang lebih mendasar: bagaimana satu struct disusun byte demi byte di memori, dan mengapa urutan member bisa mengubah ukurannya. Topik itu menjadi isi chapter berikutnya.

Rujukan resmi: alignas dan hardware interference size .