Branch Prediction CPU: Bottleneck Tersembunyi di Kodemu

Ada jawaban Stack Overflow terkenal yang sudah dilihat lebih dari 3 juta kali. Pertanyaannya: kenapa memproses array yang sudah diurutkan lebih cepat daripada yang acak? Kodenya sama persis, yaitu sebuah loop dengan statement if. Bedanya hanya apakah array input sudah terurut. Versi yang terurut berjalan 6x lebih cepat. Penjelasannya, yaitu branch prediction CPU, menunjukkan salah satu faktor performa paling berpengaruh di komputasi modern.

Setiap statement if, setiap kondisi loop, setiap case switch, semuanya adalah cabang (branch) di kodemu. CPU kamu menemui miliaran cabang per detik dan harus memprediksi hasil tiap cabang sebelum tahu jawaban sebenarnya. Kalau prediksinya benar, eksekusi jalan dengan kecepatan penuh. Kalau salah, CPU membuang 10-20 siklus kerja dan mulai dari awal. Memahami mekanisme ini mengubah cara kamu memandang kode yang kritis untuk performa.

Kenapa CPU Perlu Memprediksi

CPU modern menggunakan pipeline: mereka tidak menunggu satu instruksi selesai sebelum memulai instruksi berikutnya. Pipeline CPU tipikal punya 12-20 tahap. Saat satu instruksi dieksekusi, sekitar 15 instruksi berikutnya sudah di-fetch, di-decode, dan disiapkan. Pipelining inilah yang memungkinkan CPU mengeksekusi kira-kira satu instruksi per siklus clock, meski tiap instruksi butuh banyak siklus untuk selesai.

Tapi saat CPU menemui cabang (if x > 0), ada masalah. Instruksi berikutnya bergantung pada apakah cabang diambil atau tidak. CPU belum tahu jawabannya selama beberapa siklus, karena hasil perbandingan perlu merambat melalui pipeline. Ada dua pilihan: menghentikan pipeline dan menunggu (membuang 15+ siklus tanpa hasil), atau menebak arah cabang dan terus bekerja.

CPU selalu menebak. Branch predictor membuat prediksi, dan CPU mengambil serta mengeksekusi instruksi di jalur yang diprediksi. Kalau prediksinya benar, tidak ada yang terbuang. Kalau salah, CPU harus membuang (flush) instruksi yang sudah terlanjur dieksekusi, membuang hasilnya, dan mulai lagi dari jalur yang benar. 'Pipeline flush' ini memakan sekitar 15-20 siklus pada CPU x86 modern, setara dengan 15-20 instruksi kerja yang hilang.

Cara Kerja Branch Predictor

Branch predictor modern itu sangat canggih. Pada dasarnya itu adalah hardware pencocok pola yang belajar dari riwayat setiap instruksi cabang.

Kasus Sederhana: Cabang yang Bias

Banyak cabang yang sangat bias, artinya hampir selalu mengambil arah yang sama. Pengecekan error yang berhasil 99,9% waktu, atau kondisi loop yang benar untuk 999 iterasi dan salah sekali. Branch predictor dengan cepat mempelajari pola seperti ini dan mencapai akurasi hampir sempurna. Cabang yang selalu mengambil arah sama 99% waktu paling banter punya tingkat misprediction 1%.

Pengenalan Pola

Predictor modern tidak berhenti di pelacakan bias sederhana. Mereka mengenali pola yang berulang. Jika sebuah cabang mengikuti pola diambil-diambil-tidak-diambil-diambil-diambil-tidak-diambil... (periode 3), predictor akan mempelajari pola itu dan memprediksinya dengan benar. Prediktor TAGE (TAgged GEometric history length) yang dipakai di CPU Intel dan AMD modern memelihara beberapa tabel riwayat dengan panjang berbeda, sehingga bisa menangkap pola dengan periode dari 2 hingga beberapa ratus.

Cabang yang Berkorelasi

Predictor yang paling canggih juga mempelajari korelasi antar cabang. Jika cabang A yang diambil selalu berarti cabang B (yang muncul lebih belakang di kode) tidak diambil, predictor bisa mempelajari hubungan ini. Teknik ini disebut 'two-level adaptive prediction' dan menangani pola kode seperti:

// These branches are correlated
if (x > 0) {      // Branch A
y = x * 2;
}
// ... some code ...
if (x <= 0) {     // Branch B — always opposite of Branch A
y = -x;
}
// The predictor learns: when A is taken, B is not taken, and vice versa
// Both branches are predicted with near-perfect accuracy

Misteri Array Terurut Terpecahkan

Kembali ke pertanyaan Stack Overflow tadi. Kodenya kurang lebih seperti ini:

int sum = 0;
for (int i = 0; i < arraySize; i++) {
if (data[i] >= 128)    // This is the critical branch
sum += data[i];
}
// With SORTED data [0, 1, 2, ..., 127, 128, 129, ..., 255]:
// Branch pattern: NNNNNN...NNNTTTTTT...TTT
// First half: always NOT taken. Second half: always taken.
// Prediction accuracy: ~99.9% (only mispredicts at the transition)
// With UNSORTED data [random values 0-255]:
// Branch pattern: TNNTTNNTTTNNTNNT... (random)
// Prediction accuracy: ~50% (no pattern to learn)
// Every misprediction costs ~15 cycles

Dengan data yang terurut, cabangnya sangat bisa diprediksi: tidak diambil untuk separuh pertama array, lalu diambil untuk separuh kedua. Predictor dengan cepat mempelajari tiap fase dan hanya meleset di satu titik transisi. Dengan data acak, cabangnya pada dasarnya lemparan koin. Predictor tidak bisa lebih baik dari akurasi ~50%, dan separuh iterasi membuang 15 siklus untuk pipeline flush.

Untuk 100.000 iterasi dengan tingkat misprediction ~50%, itu 50.000 misprediction × 15 siklus = 750.000 siklus terbuang. Di CPU 3 GHz, itu seperempat milidetik, porsi yang cukup besar dari total waktu eksekusi loop sederhana ini.

Berapa Banyak Cabang yang Bisa Ditangani CPU?

Branch predictor punya penyimpanan yang terbatas. Ia melacak riwayat untuk sejumlah lokasi cabang tertentu menggunakan struktur bernama Branch Target Buffer (BTB) dan tabel riwayat terkait. CPU modern bisa melacak puluhan ribu lokasi cabang, tapi codebase besar bisa melampaui batas ini.

Ketika dua instruksi cabang berbeda mengalias ke entri predictor yang sama (karena BTB diindeks dengan hash alamat instruksi), keduanya saling mengganggu prediksi. Ini jarang terjadi di kode biasa, tapi jadi relevan di fungsi yang sangat besar atau saat banyak fungsi kecil masing-masing berisi cabang.

Daniel Lemire sudah mempublikasikan riset bagus yang mengukur kapasitas branch predictor di berbagai CPU. Hasilnya menunjukkan CPU Intel modern (Alder Lake dan setelahnya) bisa memprediksi cabang secara efektif dengan riwayat sampai sekitar 200 cabang ke belakang, artinya predictor mempertimbangkan hasil dari ~200 cabang terakhir saat memprediksi cabang sekarang. CPU AMD punya kapasitas yang mirip. Chip ARM lebih bervariasi, dan chip seri M dari Apple punya branch predictor yang sangat kuat.

Menulis Kode yang Ramah Branch Prediction

Di sebagian besar kode, branch prediction tidak terlalu penting. Predictor-nya sudah cukup bagus, dan cabangnya tidak berada di hot loop. Tapi saat kamu mengoptimalkan jalur yang kritis untuk performa, seperti inner loop, pipeline pemrosesan data, parser, atau codec, perilaku cabang bisa mendominasi waktu eksekusi.

Ganti Cabang dengan Aritmetika

Cabang tercepat adalah cabang yang tidak ada. Banyak pola kondisional bisa diganti dengan aritmetika tanpa cabang (branchless).

// Branching version:
int max_branch(int a, int b) {
if (a > b) return a;
return b;
}
// Branchless version (compiler often does this automatically):
int max_branchless(int a, int b) {
return a ^ ((a ^ b) & -(a < b));
}
// Conditional move — the compiler's favorite trick:
int max_cmov(int a, int b) {
// Most compilers will emit a CMOV instruction for this
return (a > b) ? a : b;
}
// Clamping with branches:
int clamp_branch(int x, int lo, int hi) {
if (x < lo) return lo;
if (x > hi) return hi;
return x;
}
// Clamping branchless:
int clamp_branchless(int x, int lo, int hi) {
// min(max(x, lo), hi)
int t = x > lo ? x : lo;  // CMOV
return t < hi ? t : hi;   // CMOV
}

Compiler modern umumnya cukup pandai mengubah kondisional sederhana menjadi instruksi CMOV (conditional move), yang sama sekali menghindari cabang. Tapi mereka tidak selalu bisa, terutama saat cabang punya efek samping atau saat jalur 'then'-nya mahal. Pola branchless eksplisit membantu di hot loop tempat compiler tidak menghasilkan kode yang optimal.

Urutkan Sebelum Memproses

Kalau kamu mau memfilter data dengan cabang, mengurutkan data dulu membuat cabangnya sangat bisa diprediksi. Kedengarannya kontraintuitif karena sorting punya overhead O(n log n), tapi untuk dataset besar di mana loop pemrosesannya berjalan berkali-kali atau biaya misprediction-nya tinggi, sorting justru terbayar.

Gunakan Lookup Table

Logika kondisional yang kompleks (switch dengan banyak case) bisa diganti dengan lookup table. Alih-alih rantai perbandingan, cukup indeks ke dalam array. Akses array mungkin menyebabkan cache miss, tapi itu biasanya lebih murah daripada deretan cabang yang salah prediksi.

// Branch-heavy version:
char to_hex(int nibble) {
if (nibble < 10)
return '0' + nibble;
else
return 'a' + nibble - 10;
}
// Lookup table version (no branches):
static const char hex_table[] = "0123456789abcdef";
char to_hex_lut(int nibble) {
return hex_table[nibble];
}

Berikan Petunjuk ke Compiler

GCC dan Clang mendukung __builtin_expect untuk memberi tahu compiler arah cabang mana yang kemungkinan besar. Ini tidak langsung mengendalikan branch predictor CPU (yang belajar saat runtime), tapi memengaruhi cara compiler menata kode. Jalur yang umum ditempatkan secara lurus tanpa lompatan, dan itu lebih cepat karena efek instruction cache.

// Tell the compiler that errors are unlikely
if (__builtin_expect(result == NULL, 0)) {
handle_error();
}
// C++20 provides cleaner syntax:
if (result == NULL) [[unlikely]] {
handle_error();
}
// Linux kernel defines macros for this:
#define likely(x)   __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)
if (unlikely(ptr == NULL)) {
panic("null pointer");
}

Mengukur Perilaku Cabang

Kamu bisa mengukur performa branch prediction langsung menggunakan hardware performance counter. Di Linux, perf stat memberimu tingkat misprediction untuk program apa pun.

# Measure branch prediction statistics
$ perf stat -e branches,branch-misses ./my_program
Performance counter stats for './my_program':
1,482,937,256  branches          # 892.7M/sec
3,271,842  branch-misses     # 0.22% of all branches
# 0.22% misprediction rate — excellent.
# Anything under 1% is good.
# Over 5% in a hot loop means branch prediction is hurting you.
# Over 10% means you should consider branchless alternatives.

Untuk micro-benchmark, tool seperti Google Benchmark bisa melacak branch-misses per iterasi, memberi umpan balik yang presisi apakah perubahan kode memperbaiki perilaku cabang. Ini lebih actionable daripada wall-clock time, yang tercampur noise dari aktivitas sistem lain.

Kapan Perlu Peduli (dan Kapan Tidak)

Optimasi branch prediction penting di kategori kode yang sempit tapi krusial: inner loop yang memproses data dalam jumlah besar. Parser, kompresor, pengolahan gambar, komputasi numerik, dan evaluasi query database adalah tempat perilaku cabang mendominasi.

Untuk hal lainnya, seperti business logic, API handler, dan operasi CRUD, branch prediction tidak relevan. Cabang di request router web server kamu bukanlah bottleneck. Jangan menulis ulang rantai if/else yang mudah dibaca menjadi aritmetika branchless yang sulit dibaca di kode yang hanya berjalan sekali per HTTP request. Optimasi di tempat yang ditunjukkan profiler, bukan di tempat yang teori bilang mungkin bermasalah.

Nilai sebenarnya dari memahami branch prediction bukan di optimasi manual, melainkan di memahami kenapa kodemu berperforma seperti itu. Saat profiler menunjukkan bahwa loop sederhana dengan statement if lebih lambat dari perkiraan, misprediction cabang sering kali jadi penjelasannya. Saat mengurutkan data input tiba-tiba mempercepat pemrosesan, branch prediction-lah alasannya. Model mental ini membuatmu bisa mendiagnosis masalah performa yang kalau tidak akan terasa misterius.