Harness yang kita bangun pada chapter Benchmarking memberi mata untuk melihat biaya yang tidak ada dalam model perhitungan sederhana. Salah satu biayanya paling terkenal: instruksi cabang (if, loop, pemanggilan virtual) membuat prosesor harus menebak arah eksekusi sebelum kondisinya selesai dihitung. Tebakan yang tepat hampir gratis, tetapi tebakan yang salah memaksa prosesor membuang pekerjaan yang sedang berjalan dan mengulanginya dari titik cabang. Chapter ini memakai demo klasik untuk melihat biaya itu secara nyata, lalu meninjau dua cara mengatasinya: menyusun kode yang tidak bercabang dan memberi petunjuk kepada compiler.

Pipeline dan Prediksi Cabang #

Prosesor modern mengeksekusi instruksi lewat pipeline: sambil satu instruksi dijalankan, instruksi-instruksi berikutnya sudah diambil dan disiapkan jauh di depan. Ketika instruksi yang disiapkan adalah cabang bersyarat, prosesor belum tahu arahnya — kondisinya baru selesai dihitung belakangan — sehingga unit branch predictor menebak berdasarkan riwayat cabang itu. Bila tebakannya benar, eksekusi spekulatif berjalan tanpa henti dan tebakan terasa gratis; bila salah, seluruh pekerjaan spekulatif dalam antrean dibuang dan pipeline mengulang dari arah yang benar, dengan penalti belasan siklus per kejadian. Prediktor modern mencapai akurasi di atas 95% untuk pola yang beraturan, tetapi pola yang benar-benar acak — seperti data acak — membatasi akurasinya ke sekitar 50%, dan di situlah biayanya terlihat.

Demo Klasik: Array Acak versus Terurut #

Demo ini menjumlahkan elemen bernilai 128 ke atas pada satu juta elemen dengan isi acak, lalu mengulang perhitungan yang sama pada salinan array yang sudah diurutkan. Nilai checksum-nya sama persis — yang berubah hanya urutan data:

cpp 
// Demo klasik branch prediction: menjumlahkan elemen bernilai >= 128 pada
// array acak versus array yang sudah terurut. Checksum dan jumlah elemen
// deterministik; angka durasi bergantung mesin, level optimasi, dan beban
// sistem — karena itu durasi tidak pernah kita jadikan output terverifikasi.
#include <algorithm>
#include <chrono>
#include <iostream>
#include <random>
#include <vector>

long long jumlahBesar(const std::vector<int>& data) {
    long long total = 0;
    for (int x : data) {
        if (x >= 128) total += x;     // cabang yang arahnya ditentukan data
    }
    return total;
}

struct Ukuran {
    long long terbaikUs;              // durasi terbaik (mikrosekon)
    long long checksum;               // hasil perhitungan: penjaga anti-DCE
};

template <class F>
Ukuran ukur(F kerja, int run = 5) {
    for (int i = 0; i < 2; ++i) kerja();          // pemanasan (warm-up)
    long long terbaik = -1;
    long long hasil = 0;
    for (int i = 0; i < run; ++i) {
        auto mulai = std::chrono::steady_clock::now();
        hasil = kerja();                          // hasil disimpan: tidak dihapus
        auto selesai = std::chrono::steady_clock::now();
        auto us = std::chrono::duration_cast<std::chrono::microseconds>(
            selesai - mulai).count();
        if (terbaik < 0 || us < terbaik) terbaik = us;
    }
    return {terbaik, hasil};
}

int main() {
    const std::size_t N = 1000000;
    std::mt19937 gen(42);             // seed tetap: data acak yang bisa diulang
    std::uniform_int_distribution<int> dist(0, 255);
    std::vector<int> acak(N);
    for (int& x : acak) x = dist(gen);

    std::vector<int> urut = acak;     // salinan dengan isi sama, lalu diurutkan
    std::sort(urut.begin(), urut.end());

    int banyakBesar = 0;
    for (int x : acak) {
        if (x >= 128) ++banyakBesar;
    }

    Ukuran uAcak = ukur([&] { return jumlahBesar(acak); });
    Ukuran uUrut = ukur([&] { return jumlahBesar(urut); });

    std::cout << "jumlah elemen      : " << N << '\n';
    std::cout << "elemen >= 128      : " << banyakBesar << '\n';
    std::cout << "checksum acak/urut : " << uAcak.checksum
              << '/' << uUrut.checksum << '\n';
    std::cout << "acak, terbaik      : " << uAcak.terbaikUs << " us\n";
    std::cout << "urut, terbaik      : " << uUrut.terbaikUs << " us\n";
    return 0;
}

Program ini mencetak angka durasi yang berbeda antar eksekusi dan antar mesin, sehingga durasinya tidak kita kunci sebagai output terverifikasi; atribut nondeterministic menandainya secara eksplisit. Pada build -O0 (compiler menerjemahkan if menjadi lompatan sungguhan), perbedaannya dramatis:

bash 
g++ -std=c++23 -Wall -Wextra -O0 urut-vs-acak.cpp -o urut_O0
./urut_O0

Hasil Eksekusi (build -O0, contoh satu eksekusi; angka durasi bervariasi):

text 
jumlah elemen      : 1000000
elemen >= 128      : 500523
checksum acak/urut : 95831136/95831136
acak, terbaik      : 15380 us
urut, terbaik      : 7572 us

Pekerjaan aritmetikanya identik — jumlah elemen yang memenuhi syarat sama, checksum sama — tetapi versi acak butuh dua kali lebih lama. Pada array terurut, cabang if mengambil pola beruntun yang panjang (semua nilai kecil dulu, lalu semua nilai besar), sehingga prediktor belajar dan hampir selalu menebak benar. Pada array acak, keputusan mengikuti dadu: sekitar separuh tebakan meleset, dan setiap kelesatan membayar penalti pipeline.

Ketika Optimizer Mengubah Hasil Demo #

Sekarang kompilasi program yang sama dengan -O2:

bash 
g++ -std=c++23 -Wall -Wextra -O2 urut-vs-acak.cpp -o urut_O2
./urut_O2

Hasil Eksekusi (build -O2, contoh satu eksekusi; angka durasi bervariasi):

text 
jumlah elemen      : 1000000
elemen >= 128      : 500523
checksum acak/urut : 95831136/95831136
acak, terbaik      : 270 us
urut, terbaik      : 289 us

Perbedaannya hilang — kedua versi sama cepatnya. Penjelasannya ada di assembly: pada -O2, GCC tidak menerjemahkan penjumlahan bersyarat ini menjadi lompatan, melainkan menjadi instruksi pemindahan bersyarat (cmov) yang tidak bercabang sama sekali. Berikut isi loop jumlahBesar pada build tersebut:

text 
movslq	(%rax), %rdx
movq	%rdx, %rsi
addq	%rcx, %rdx
cmpl	$127, %esi
cmovg	%rdx, %rcx

cmovg memindahkan kandidat penjumlahan hanya bila flag hasil cmpl menyatakan “lebih besar” — tanpa lompatan, tanpa tebakan, tanpa penalti prediksi. Pelajarannya ganda: efek branch prediction itu nyata, tetapi compiler sering sudah menghapusnya untuk badan cabang yang sederhana. Karena itu ukurlah sebelum mengeluhkan prediksi: pada build -O2 ini, perbedaan yang kita cari sudah dipecahkan compiler untuk kita.

Berpikir Branchless #

Ketika compiler tidak menolong — badan cabang terlalu rumit, atau polanya memang sulit ditebak — kita bisa menyusun kode yang memilih nilai tanpa memilih jalur. Dua gaya klasiknya adalah pernyataan if dan ekspresi ternary; keduanya menghasilkan nilai yang sama:

cpp 
// Dua gaya menentukan nilai minimum dan maksimum: pernyataan if versus
// ekspresi ternary. Hasilnya identik — dan pada build teroptimasi keduanya
// diterjemahkan compiler menjadi instruksi yang sama (branchless).
#include <iostream>
#include <vector>

int minIf(int a, int b) {
    int m = a;
    if (b < a) m = b;          // pernyataan if: menulis ulang m
    return m;
}

int maxIf(int a, int b) {
    int m = a;
    if (b > a) m = b;
    return m;
}

int minTernary(int a, int b) {
    return (b < a) ? b : a;    // ekspresi: nilai dipilih, bukan lompatan
}

int maxTernary(int a, int b) {
    return (b > a) ? b : a;
}

int main() {
    std::vector<int> data = {7, 23, 4, 89, 1, 56, 12, 90, 3, 44};

    int minA = data[0], maxA = data[0];   // jalur if
    int minB = data[0], maxB = data[0];   // jalur ternary
    for (std::size_t i = 1; i < data.size(); ++i) {
        minA = minIf(minA, data[i]);
        maxA = maxIf(maxA, data[i]);
        minB = minTernary(minB, data[i]);
        maxB = maxTernary(maxB, data[i]);
    }

    std::cout << "via if     : min " << minA << ", max " << maxA << '\n';
    std::cout << "via ternary: min " << minB << ", max " << maxB << '\n';
    std::cout << "hasil sama : "
              << (minA == minB && maxA == maxB ? "ya" : "tidak") << '\n';
    return 0;
}

Output yang Dihasilkan:

text 
via if     : min 1, max 90
via ternary: min 1, max 90
hasil sama : ya

Pada build -O2, kedua gaya di atas diterjemahkan menjadi instruksi yang sama persis: cmovle, tanpa lompatan. Jadi perbedaan if versus ternary di sini bukan soal kecepatan melainkan soal gaya — ternary menonjolkan bahwa kita memilih nilai, bukan memilih alur, dan itu membuat maksud branchless terbaca. Untuk badan yang lebih dari sekadar memilih nilai (misalnya memanggil fungsi atau menulis memori), versi branchless bisa jadi lebih lambat karena pekerjaannya dieksekusi selalu, bukan hanya saat diperlukan — biarkan benchmark yang memutuskan.

Petunjuk Cabang dengan [[likely]] dan [[unlikely]] #

Untuk cabang yang compiler tidak bisa dan tidak boleh ubah menjadi branchless, C++20 menyediakan atribut [[likely]] dan [[unlikely]]: petunjuk distribusi cabang yang memengaruhi penataan instruksi (code layout) agar jalur yang sering diambil bebas dari lompatan. Program berikut membuktikan sintaksnya diterima compiler dan hasil perhitungan tidak berubah:

cpp 
// Atribut [[likely]] dan [[unlikely]] (C++20): petunjuk kepada compiler
// tentang cabang mana yang paling sering diambil. Program ini membuktikan
// bahwa sintaksnya diterima compiler dan hasil perhitungan tidak berubah.
#include <iostream>
#include <random>
#include <vector>

// Pembacaan sensor: mayoritas valid, kesalahan jarang.
int proses(int nilai, int& jumlahValid, int& jumlahRusak) {
    if (nilai >= 0) [[likely]] {
        ++jumlahValid;
        return nilai * 2;
    } else [[unlikely]] {
        ++jumlahRusak;
        return 0;
    }
}

int main() {
    std::mt19937 gen(42);                    // seed tetap: urutan bisa diulang
    std::uniform_int_distribution<int> dist(-10, 189);
    std::vector<int> pembacaan(1000);
    for (int& x : pembacaan) x = dist(gen);  // 5% negatif: pembacaan rusak

    int jumlahValid = 0, jumlahRusak = 0, total = 0;
    for (int x : pembacaan) total += proses(x, jumlahValid, jumlahRusak);

    std::cout << "pembacaan valid : " << jumlahValid << '\n';
    std::cout << "pembacaan rusak : " << jumlahRusak << '\n';
    std::cout << "total terolah   : " << total << '\n';
    return 0;
}

Output yang Dihasilkan:

text 
pembacaan valid : 944
pembacaan rusak : 56
total terolah   : 179296

Bedah penggunaannya:

  1. if (nilai >= 0) [[likely]]: atribut diletakkan sebelum blok pernyataan yang dipilih — di sini kita menyatakan jalur pembacaan valid adalah jalur yang biasa terjadi (944 dari 1000).
  2. else [[unlikely]]: jalur pembacaan rusak ditandai jarang, sehingga compiler menaruhnya jauh dari jalur panas dan instruksi jalur panas beruntun di memori.
  3. Hasil tak berubah: atribut adalah petunjuk, bukan perintah — program menghasilkan angka yang sama persis tanpa atribut; yang berubah hanya kemungkinan penataan instruksinya.

Cabang adalah persoalan kontrol alur; ada satu sudut lagi yang belum kita sentuh: memproses banyak data dengan satu instruksi, tanpa iterasi per elemen sama sekali. Pendekatan itu bernama SIMD dan menjadi topik chapter berikutnya.

Rujukan resmi: atribut likely/unlikely dan std::sort .