Memahami Biaya Komputasi

Setiap program yang kita jalankan menanggung tiga macam biaya sekaligus: waktu komputasi, penggunaan memori, dan energi. Program pencarian yang memeriksa satu juta elemen satu per satu membuang waktu prosesor dan baterai, sementara program yang menyimpan data secara boros bisa kehabisan memori sebelum pekerjaannya selesai. Performa bukan properti tunggal yang bisa dibeli lewat satu trik, melainkan hasil penjumlahan keputusan-keputusan kecil di banyak lapisan kode. Chapter ini membangun cara pandang yang akan kita pakai sepanjang section: memperlakukan performa sebagai biaya yang bisa dihitung, dibandingkan, dan ditekan.

Empat Level Keputusan Biaya #

Kesalahan paling umum ketika mengoptimasi adalah mencampuradukkan level keputusan. Urutannya dari yang paling berdampak hingga paling kecil: pilihan algoritma, pilihan struktur data, pola akses memori, lalu optimasi mikro. Tabel berikut merangkum keempatnya.

Perhatikan polanya: semakin ke bawah tabel, semakin kecil dampak maksimalnya, tetapi justru level mikro yang paling sering menyita perhatian pemula. Menaikkan algoritma dari O(n) ke O(log n) mengalahkan trik mikro apa pun, sebab perbedaannya tumbuh tanpa batas ketika data membesar. Sebaliknya, menghemat satu operasi penjumlahan di dalam loop hampir tidak pernah terasa karena compiler biasanya sudah melakukannya untuk kita.

Menghitung Biaya Tiga Level dalam Satu Program #

Program berikut mengerjakan satu masalah yang sama — mencari nilai terjauh di satu juta elemen — sambil mencatat biayanya pada tiga level: jumlah perbandingan (algoritma), jumlah byte yang ditempati (struktur data), dan jumlah cache line yang ditarik (akses memori). Semua angka di sini adalah hasil penghitungan, bukan stopwatch, sehingga nilainya persis sama di mesin mana pun:

// Tiga level biaya komputasi untuk masalah yang sama: mencari data
// di satu juta elemen. Semua angka di sini adalah hasil penghitungan,
// bukan pengukuran waktu, sehingga nilainya tetap di mesin mana pun.
#include <iostream>

// ---------- Level 1: algoritma ----------
// Pencarian linear: memeriksa elemen satu per satu sampai ketemu.
long long cariLinear(const int* data, int n, int target, long long& langkah) {
    for (int i = 0; i < n; ++i) {
        ++langkah;                     // satu perbandingan per elemen
        if (data[i] == target) return i;
    }
    return -1;
}

// Pencarian biner: membelah rentang pencarian menjadi dua setiap langkah.
long long cariBiner(const int* data, int n, int target, long long& langkah) {
    int awal = 0, akhir = n - 1;
    while (awal <= akhir) {
        ++langkah;                     // satu perbandingan per pembagian
        int tengah = awal + (akhir - awal) / 2;
        if (data[tengah] == target) return tengah;
        if (data[tengah] < target) awal = tengah + 1;
        else akhir = tengah - 1;
    }
    return -1;
}

// ---------- Level 2: struktur data ----------
// Node senarai berantai membawa satu pointer ekstra per elemen.
struct NodeSenarai {
    int nilai;
    NodeSenarai* berikut;
};

int main() {
    const int N = 1000000;
    static int data[N];                // satu juta int, terurut menaik
    for (int i = 0; i < N; ++i) data[i] = i * 2;
    int target = 1999998;              // elemen terakhir, posisi paling jauh

    long long langkahLinear = 0;
    long long langkahBiner = 0;
    long long posisiL = cariLinear(data, N, target, langkahLinear);
    long long posisiB = cariBiner(data, N, target, langkahBiner);
    std::cout << "== Level algoritma ==\n";
    std::cout << "linear: " << langkahLinear << " perbandingan (indeks "
              << posisiL << ")\n";
    std::cout << "biner : " << langkahBiner << " perbandingan (indeks "
              << posisiB << ")\n";

    std::cout << "== Level struktur data ==\n";
    std::cout << "sizeof(int) = " << sizeof(int) << " byte per elemen array\n";
    std::cout << "sizeof(NodeSenarai) = " << sizeof(NodeSenarai)
              << " byte per node senarai\n";
    std::cout << "satu juta elemen: array " << 1LL * N * sizeof(int)
              << " byte vs senarai " << 1LL * N * sizeof(NodeSenarai)
              << " byte\n";

    std::cout << "== Level akses memori ==\n";
    // Cache line berukuran 64 byte; sizeof(int) = 4 byte,
    // jadi satu cache line memuat 16 int berturut-turut.
    std::cout << "akses urut  1 juta int: "
              << 1LL * N * sizeof(int) / 64 << " pengambilan cache line\n";
    // Akses melompat dengan jarak jauh antar elemen: setiap elemen yang
    // disentuh menarik satu cache line baru yang isinya hampir terbuang.
    std::cout << "akses lompat (1 int per cache line): " << 1LL * N
              << " pengambilan cache line\n";
    return 0;
}

Output yang Dihasilkan:

== Level algoritma ==
linear: 1000000 perbandingan (indeks 999999)
biner : 20 perbandingan (indeks 999999)
== Level struktur data ==
sizeof(int) = 4 byte per elemen array
sizeof(NodeSenarai) = 16 byte per node senarai
satu juta elemen: array 4000000 byte vs senarai 16000000 byte
== Level akses memori ==
akses urut  1 juta int: 62500 pengambilan cache line
akses lompat (1 int per cache line): 1000000 pengambilan cache line

Bedah baris penting:

1. cariLinear: loop memeriksa elemen satu per satu; untuk target di posisi terakhir, pencatat mencatat persis 1.000.000 perbandingan. Ini biaya O(n) yang tumbuh sebanding dengan data.
2. cariBiner: rentang dibelah dua setiap langkah, sehingga satu juta elemen selesai dalam 20 perbandingan. Rasio 1.000.000 berbanding 20 — sekitar 50.000 kali lebih hemat — adalah alasan level algoritma selalu didahulukan.
3. sizeof(NodeSenarai): node senarai membawa int (4 byte) plus pointer (8 byte) plus padding, total 16 byte per elemen. Satu juta node berarti 16.000.000 byte, empat kali lipat array int biasa; lebih sedikit byte berarti lebih sedikit halaman memori dan lebih sedikit cache yang terbuang.
4. Penghitungan cache line: satu cache line berukuran 64 byte dan memuat 16 int berturut-turut. Akses urut menarik 62.500 line untuk satu juta elemen, sedangkan akses melompat menarik satu line per elemen — 1.000.000 pengambilan — dengan isinya hampir semua terbuang.
5. Pola langkah sebagai parameter referensi: pencatat biaya dilewatkan sebagai long long& agar kedua fungsi bisa dibandingkan tanpa variabel global.

Model Biaya Operasi di Bawah Hardware #

Angka di tabel demo mewakili tiga model biaya yang paling sering muncul dalam optimization sehari-hari. Pertama, biaya alokasi: setiap new, malloc, atau pertumbuhan std::vector berarti perjalanan ke allocator, jauh lebih mahal daripada operasi aritmetika dan penuh kejutan latency. Kedua, biaya cache miss: prosesor modern bisa menyelesaikan ratusan instruksi dalam waktu yang dibutuhkan untuk satu pengambilan data dari RAM utama, itulah sebab pola akses memori ikut menentukan kecepatan. Ketiga, biaya branch misprediction: prosesor menebak arah if untuk menjaga pipeline tetap penuh, dan tebakan yang meleset membuang belasan sampai puluhan siklus; ketiganya akan kita ukur dan tekankan di chapter-chapter berikutnya.

Jangan Menebak — Ukur #

Intuisi performa terkenal tidak bisa diandalkan, bahkan di kalangan programmer berpengalaman. Kode yang tampak “berat” bisa ternyata gratis karena compiler memindahkannya keluar loop, sementara kode yang tampak sepele bisa menjadi kemacetan karena pola akses memorinya buruk. Karena itu kebiasaan yang kita bangun di section ini berurutan: hitung dulu apa yang bisa dihitung, ukur apa yang harus diukur, dan baru optimasi setelah data menunjuk lokasi masalahnya.

Penghitungan manual seperti di atas bagus untuk membandingkan dua pendekatan secara adil, tetapi ia tidak menunjukkan bagian mana dari program nyata yang paling menyita waktu. Untuk itu, alat baca biaya program yang berjalan — profiler — menjadi topik chapter berikutnya.

Rujukan resmi: sizeof operator dan isocpp FAQ .