Ketika p95/p99 endpoint Rust tiba-tiba naik, CPU ikut tinggi, tetapi query database tetap stabil, godaan pertama biasanya adalah menyalahkan jaringan, ORM, atau lock contention. Namun pada beberapa kasus, sumber latensi justru ada di jalur komputasi yang terlihat “murah”: binary search pada data terurut di memori.

Artikel ini membahas studi kasus debug latensi binary search pada backend Rust, dengan akar masalah di branch misprediction dan pola akses memori yang tidak ramah cache. Fokusnya bukan sekadar “binary search itu O(log n)”, melainkan mengapa kompleksitas asimtotik yang bagus tetap bisa kalah di CPU modern, bagaimana membuktikannya lewat profiling dan perf counter, serta kapan pendekatan branchless layak dicoba.

Gejala Nyata di Produksi

Skenarionya sederhana tetapi realistis:

  • Endpoint baca mengalami kenaikan p95 dan p99 secara tiba-tiba.
  • CPU usage naik, kadang hanya pada sebagian instance.
  • Latency query database normal; slow query log tidak menunjukkan anomali.
  • Error rate tetap rendah, sehingga masalahnya tampak seperti “sekadar lebih lambat”.
  • Deploy terakhir tidak mengubah query SQL, tetapi ada perubahan pada struktur data in-memory atau volume data yang dicari.

Ini pola yang penting. Jika database normal tetapi CPU aplikasi naik, kemungkinan besar bottleneck bergeser ke hot path di aplikasi: parsing, serialisasi, hashing, locking, atau pencarian data. Pada kasus ini, pelakunya adalah pencarian berulang pada koleksi terurut yang cukup besar.

Mengapa Binary Search Bisa Jadi Biang Latensi

Secara teori, binary search sangat efisien: O(log n). Untuk data terurut, itu pilihan alami. Masalahnya, CPU modern tidak hanya peduli pada jumlah perbandingan. Ia juga sangat peduli pada:

  • Prediktabilitas branch untuk pipeline eksekusi.
  • Lokalitas memori agar data cepat diambil dari cache, bukan dari level cache lebih rendah atau RAM.
  • Instruction-level parallelism yang bisa hilang jika alur kontrol terlalu sulit diprediksi.

Pada binary search klasik, setiap iterasi biasanya memuat satu keputusan cabang:

if key < mid_value { ... } else if key > mid_value { ... }

Untuk distribusi input yang bervariasi, arah branch ini sering sulit diprediksi CPU. Ketika prediksi salah, pipeline harus dibatalkan dan diisi ulang. Itulah branch misprediction. Selain itu, binary search melompat-lompat ke lokasi memori yang berjauhan. Walaupun jumlah langkahnya sedikit, pola aksesnya bisa buruk bagi cache.

Intinya: pada CPU modern, O(log n) tidak otomatis berarti cepat jika setiap langkah memicu branch yang sulit diprediksi dan akses memori yang tersebar.

Mechanical Sympathy: Menghubungkan Algoritma dengan Perilaku CPU

Mechanical sympathy berarti menulis sistem dengan memahami bagaimana hardware benar-benar bekerja. Pada konteks ini, binary search klasik memiliki dua sifat yang sering merugikan:

1. Branch yang Sulit Diprediksi

Jika nilai pencarian datang dari request yang beragam, pola hasil perbandingan di setiap level binary search cenderung acak dari sudut pandang branch predictor. CPU sangat bagus pada branch yang berulang dengan pola stabil, tetapi tidak pada keputusan yang terlihat acak.

2. Lompatan Memori yang Menyebar

Pencarian dimulai di tengah array, lalu seperempat, lalu tiga perempat, dan seterusnya. Ini efektif untuk mengecilkan ruang pencarian, tetapi tidak optimal untuk prefetcher dan cache locality. Jika struktur datanya besar atau elemen yang dibandingkan mahal dibaca, biaya memori menjadi signifikan.

Gabungan dua faktor itu sering menjelaskan gejala “CPU tinggi, DB normal, throughput turun” pada endpoint yang tampaknya hanya melakukan lookup sederhana.

Kasus Backend Rust: Dari Dugaan ke Hipotesis Teknis

Misalkan endpoint memuat data referensi terurut di memori saat startup, lalu setiap request melakukan banyak lookup ke koleksi tersebut. Dalam Rust, implementasi awal bisa terlihat wajar:

fn find_index(sorted: &[u64], key: u64) -> Option<usize> {
    sorted.binary_search(&key).ok()
}

Secara API, ini benar dan idiomatis. Masalahnya bukan pada Rust atau fungsi standarnya, melainkan pada kecocokan pola akses dengan beban produksi. Jika fungsi ini dipanggil berkali-kali per request, pada himpunan data besar, dan input kunci sulit diprediksi, total biaya mikroarsitekturalnya bisa menumpuk menjadi latensi p95/p99 yang nyata.

Kesalahan umum di tahap ini adalah langsung mengganti algoritma tanpa bukti. Yang dibutuhkan adalah investigasi yang bisa diulang.

Langkah Investigasi yang Bisa Diulang

1. Konfirmasi bahwa bottleneck bukan DB atau I/O

Mulai dari metrik level layanan:

  • Bandingkan latency endpoint dengan latency query DB.
  • Lihat CPU user time vs iowait.
  • Periksa apakah peningkatan latensi berkorelasi dengan volume request atau ukuran data yang dicari.

Jika DB stabil dan CPU user naik, fokuskan ke compute path.

2. Profiling CPU di proses Rust

Gunakan profiler yang dapat menunjukkan fungsi terpanas. Tujuannya bukan mencari “angka sakti”, tetapi memastikan lookup memang dominan.

Contoh alur umum di Linux:

perf record -F 99 -g -- ./server-binary
perf report
# atau buat flamegraph dari hasil perf

Pada lingkungan nyata, lebih aman melakukan profiling di canary, replika trafik, atau jendela observasi singkat untuk mengurangi risiko.

3. Baca flamegraph dengan benar

Jika flamegraph menunjukkan waktu banyak di fungsi pencarian atau pembanding, jangan berhenti pada nama fungsi. Tanyakan:

  • Apakah fungsi itu dipanggil sangat sering?
  • Apakah biaya utamanya di branch, akses memori, atau pembandingan elemen?
  • Apakah ada inlining yang membuat hotspot tersebar di beberapa frame?

Binary search kadang tidak tampak dramatis dari sudut jumlah instruksi, tetapi tetap mahal karena stall CPU.

4. Lihat perf counter, bukan hanya call stack

Untuk hipotesis branch misprediction dan cache behavior, call stack saja tidak cukup. Anda perlu melihat counter perangkat keras yang relevan. Nama event dan ketersediaannya bisa berbeda antar CPU, tetapi secara umum carilah:

  • branches dan branch-misses
  • cache-references dan cache-misses
  • indikator stalls atau backend bound jika tool yang dipakai mendukung

Contoh umum:

perf stat -e branches,branch-misses,cache-references,cache-misses ./server-binary

Lebih baik lagi jika Anda dapat membandingkan dua build atau dua varian implementasi dengan workload yang sama. Yang dicari bukan angka absolut universal, tetapi perbedaan relatif yang konsisten.

5. Buat benchmark mikro, lalu uji lagi di beban yang realistis

Benchmark mikro berguna untuk mengisolasi lookup. Tetapi benchmark mikro sering menipu jika:

  • dataset terlalu kecil sehingga seluruh array muat di cache,
  • pola kunci pencarian terlalu berulang sehingga branch predictor “belajar”,
  • loop benchmark terlalu sintetik dibanding distribusi request nyata.

Karena itu, lakukan dua tahap:

  1. Mikrobenchmark untuk membandingkan implementasi pencarian.
  2. Load test realistis dengan distribusi key, concurrency, dan ukuran data mendekati produksi.

Di Rust, Anda bisa memakai benchmark harness pilihan tim Anda, tetapi yang paling penting adalah kualitas skenario, bukan nama tool-nya.

Binary Search Biasa vs Pendekatan Branchless

Binary search biasa

Pendekatan klasik menggunakan percabangan eksplisit. Keunggulannya:

  • Sederhana, mudah dibaca, mudah diverifikasi.
  • Biasanya sudah cukup baik untuk banyak kasus.
  • Tidak memaksa trik yang mungkin memperumit pemeliharaan.

Kekurangannya:

  • Rentan terhadap branch misprediction pada input yang sulit diprediksi.
  • Tetap memiliki pola akses memori yang kurang ramah cache.

Pendekatan branchless

Secara konseptual, pendekatan branchless berusaha mengganti percabangan yang sulit diprediksi dengan operasi yang lebih mudah dipipeline oleh CPU, misalnya melalui perhitungan indeks berbasis hasil komparasi alih-alih if/else langsung. Tujuannya adalah mengurangi penalti branch misprediction.

Perlu ditekankan: branchless bukan berarti tanpa keputusan logis. Logikanya tetap ada, tetapi diekspresikan dengan cara yang lebih ramah bagi eksekusi spekulatif dan pipeline CPU.

Contoh konseptual yang disederhanakan:

fn lower_bound_branchless(sorted: &[u64], key: u64) -> usize {
    let mut base = 0usize;
    let mut len = sorted.len();

    while len > 1 {
        let half = len / 2;
        let mid = base + half;
        let go_right = (sorted[mid] < key) as usize;
        base = base + go_right * half;
        len -= half;
    }

    base + ((base < sorted.len() && sorted[base] < key) as usize)
}

Contoh di atas bersifat ilustratif, bukan drop-in replacement universal. Implementasi branchless yang aman, benar, dan efektif perlu diuji sangat hati-hati, terutama untuk kasus batas seperti array kosong, elemen duplikat, dan kebutuhan exact match vs lower_bound.

Poin penting: pendekatan branchless dapat membantu mengurangi penalti branch, tetapi tidak menghilangkan masalah akses memori acak. Karena itu hasilnya tidak selalu spektakuler, dan kadang tidak membantu sama sekali.

Kapan Branchless Membantu, dan Kapan Tidak

Cenderung membantu jika

  • Lookup sangat sering dan berada di jalur panas endpoint.
  • Distribusi key pencarian cukup acak sehingga branch predictor sering salah.
  • Ukuran data cukup besar sehingga biaya branch menjadi signifikan pada akumulasi panggilan.
  • Benchmark realistis menunjukkan penurunan branch-miss yang konsisten.

Sering tidak banyak membantu jika

  • Dataset kecil dan sering muat di cache level tinggi.
  • Pola key berulang sehingga branch predictor bekerja baik.
  • Bottleneck utama justru ada di parsing, alokasi, lock contention, atau serialisasi.
  • Biaya pembandingan elemen jauh lebih mahal daripada branch itu sendiri.

Bahkan bisa merugikan jika

  • Kode menjadi terlalu rumit dan sulit diverifikasi.
  • Kompiler sudah menghasilkan kode yang cukup baik untuk kasus Anda.
  • Optimasi mikro mengorbankan maintainability tanpa dampak p95/p99 yang nyata.

Karena itu, keputusan optimasi harus berbasis data, bukan asumsi bahwa branchless selalu lebih cepat.

Validasi Hipotesis: Dari Eksperimen ke Patch

Setelah profiler dan perf counter mengarah ke binary search, langkah berikutnya adalah menguji hipotesis secara terkendali:

  1. Buat varian implementasi lookup: baseline dan kandidat branchless.
  2. Pastikan keduanya mengembalikan hasil yang identik pada test fungsional.
  3. Jalankan benchmark mikro dengan dataset dan distribusi key yang bervariasi.
  4. Jalankan load test realistis untuk mengukur dampak pada p95/p99 dan CPU.
  5. Bandingkan perf counter antar varian, terutama branch-miss dan cache-miss.

Jika branchless menurunkan branch-miss tetapi p95 produksi tidak berubah, berarti branch bukan bottleneck dominan atau efeknya tertutup biaya lain. Itu tetap temuan yang berguna: hipotesis tidak terbukti cukup kuat untuk konteks sistem Anda.

Alternatif patch selain branchless

Dalam beberapa sistem, perbaikan terbaik bukan mengutak-atik binary search, melainkan mengubah representasi data:

  • Layout data lebih padat agar cache locality membaik.
  • Batching lookup untuk mengurangi overhead per request.
  • Index tambahan jika ada subset key yang sangat sering diakses.
  • Pengelompokan data berdasarkan pola akses agar prefetching lebih efektif.
  • Mengurangi jumlah lookup dengan memoization per request jika aman.

Ini penting karena masalah performa jarang murni “algoritma salah”; sering kali masalahnya adalah kecocokan buruk antara pola akses dan hardware.

Contoh Strategi Patch yang Aman di Rust

Jika tim memutuskan mencoba optimasi, lakukan dengan guardrail yang jelas:

1. Bungkus implementasi di fungsi sempit

Jangan sebarkan logika branchless ke banyak tempat. Simpan dalam fungsi utilitas yang mudah diuji.

fn lookup_id(sorted_ids: &[u64], key: u64) -> Option<usize> {
    // Bisa diarahkan ke baseline atau implementasi alternatif via feature flag.
    sorted_ids.binary_search(&key).ok()
}

2. Tambahkan test korektness yang kuat

  • Array kosong
  • Satu elemen
  • Elemen pertama/terakhir
  • Key tidak ditemukan
  • Nilai duplikat bila relevan
  • Dataset acak dengan pembanding terhadap implementasi referensi

3. Gunakan feature flag atau runtime switch

Ini memudahkan canary dan rollback cepat jika hasil produksi tidak sesuai ekspektasi.

4. Dokumentasikan alasan optimasi

Kode yang tampak “aneh” tanpa konteks sering dihapus pada refactor berikutnya. Tambahkan komentar singkat yang menjelaskan bahwa ini adalah optimasi untuk branch prediction/cache behavior, beserta tautan ke benchmark internal tim.

Verifikasi Pasca-Rilis

Optimasi performa belum selesai saat patch di-merge. Pastikan ada verifikasi setelah rilis:

  • Bandingkan p50, p95, p99 sebelum dan sesudah deploy.
  • Amati CPU usage, saturation, dan throughput.
  • Periksa apakah hasil hanya membaik pada sebagian traffic pattern.
  • Bandingkan error rate dan correctness metric jika ada.
  • Jika memungkinkan, lihat lagi perf counter pada canary atau host uji.

Jangan puas hanya karena benchmark lokal membaik. Target sebenarnya adalah latensi endpoint di sistem nyata.

Kesalahan Umum Saat Debug Kasus Ini

  • Terlalu cepat menyalahkan database padahal gejalanya menunjukkan CPU-bound.
  • Mengandalkan benchmark mikro saja tanpa workload produksi.
  • Menganggap O(log n) pasti cukup cepat tanpa mempertimbangkan branch dan cache.
  • Mengoptimasi sebelum profiling, lalu sulit membuktikan manfaatnya.
  • Mengabaikan maintainability saat menulis branchless code yang sulit diverifikasi.

Checklist Pencegahan Regresi Performa

  • Identifikasi dan dokumentasikan hot path endpoint kritis.
  • Tambahkan benchmark untuk jalur lookup yang sensitif.
  • Gunakan dataset benchmark yang mencerminkan ukuran dan distribusi key produksi.
  • Bandingkan implementasi baru terhadap baseline, bukan angka absolut saja.
  • Awasi metrik p95/p99, CPU, dan throughput setelah setiap perubahan signifikan pada struktur data.
  • Jika ada optimasi nontrivial, lindungi dengan feature flag untuk rollout bertahap.
  • Simpan flamegraph atau hasil perf sebagai artefak pembanding sebelum/sesudah.
  • Pastikan test korektness mencakup edge case dan properti hasil yang identik.
  • Jangan mengasumsikan optimasi mikro akan selalu menang di semua hardware.
  • Tinjau ulang apakah masalah lebih tepat diselesaikan dengan perubahan layout data, bukan hanya algoritma pencarian.

Penutup

Debug latensi binary search di backend Rust adalah contoh klasik bahwa performa dunia nyata tidak cukup dijelaskan oleh kompleksitas algoritma. Ketika p95/p99 naik, CPU tinggi, dan DB normal, binary search pada data terurut bisa menjadi tersangka serius jika dipanggil sangat sering di jalur panas.

Akar masalahnya sering terletak pada branch misprediction dan akses memori yang tidak ramah cache. Pendekatan branchless kadang membantu, tetapi bukan obat universal. Cara yang benar adalah menggabungkan profiling, perf counter, benchmark mikro, load test realistis, dan verifikasi pasca-rilis. Dengan begitu, Anda tidak hanya menebak-nebak, tetapi benar-benar membuktikan penyebab dan dampak perbaikannya.