Debugging pakai binary search: buang setengah kemungkinan tiap langkah

Bug muncul di versi sekarang, tapi nggak ada di versi 3 minggu lalu. Ada 200 commit di antaranya. Cara amatir: baca satu-satu dari atas. Cara benar: bagi dua, terus bagi dua lagi. 200 commit jadi ~8 langkah. 1000 commit jadi 10 langkah.

Ini bukan trik Git. Ini cara berpikir: setiap pertanyaan yang jawabannya cuma "ya/tidak" memotong ruang masalah jadi separuh.

Prinsipnya

Binary search cuma sah kalau ada predikat monoton — semua keadaan sebelum titik X "bagus", semua sesudahnya "rusak". Satu titik balik, nggak bolak-balik.

Kalau bug-nya hilang-muncul acak (flaky), predikatnya nggak monoton. Bisect bakal nunjuk commit random dan bohong. Itu pitfall nomor satu.

Terapan 1: `git bisect` — commit mana yang bikin rusak

git bisect start
git bisect bad                # HEAD sekarang rusak
git bisect good v1.4.0        # tag yang lo tau masih waras
# git checkout sendiri ke commit tengah, lo tes manual, lalu:
git bisect good   # atau
git bisect bad
# ulangi sampai Git bilang: "<sha> is the first bad commit"
git bisect reset

Versi yang lebih enak — biar skrip yang ngetes:

git bisect start HEAD v1.4.0
git bisect run npm test -- --grep "checkout"

Aturan exit code: 0 = bagus, 1–127 = rusak, 125 = skip (commit nggak bisa dites, misal build-nya error). Skip itu penting — tanpa itu lo kejebak di commit yang emang nggak bisa dijalankan.

Kalau tes lo agak flaky, jangan percaya satu run. Bikin wrapper yang jalanin tesnya 3x dan baru bilang "bagus" kalau ketiganya lolos. Lebih lambat, tapi hasilnya nggak ngawur.

Terapan 2: bagi dua kode, bukan commit

Nggak ada Git history bersih? Potong jalur eksekusinya.

Rusak di halaman checkout. Ada 6 langkah dari klik sampai render. Kasih console.log/log di tengah (langkah 3): datanya sudah salah di situ atau belum? Kalau sudah salah → bug di langkah 1–3. Kalau masih benar → langkah 4–6. Tiga iterasi, ketemu.

Versi lebih rapi: matikan separuh fitur flag, separuh middleware, separuh query. Prinsipnya sama — bagi dua, jangan telusuri berurutan.

Terapan 3: bagi dua konfigurasi & data

Config: 40 environment variable bikin beda antar staging dan lokal. Setengahnya dikosongkan. Masih rusak? Berarti biang keroknya di setengah yang lain. 40 variabel → ~6 percobaan.
Data: import CSV gagal di baris ke-90.000. Jangan baca 90.000 baris. Ambil 45.000 pertama — gagal? Masalah di paruh atas. Nggak? Paruh bawah. Log2(90.000) ≈ 17 langkah, bukan 90.000.
Input request: body JSON 3KB bikin 500. Hapus separuh field, ulangi. Cepat ketemu field yang bikin meledak.

Checklist

[ ] Definisikan dulu predikat "bagus/rusak" yang bisa dijalankan mesin. Kalau nggak bisa, belum siap bisect.
[ ] Pastikan kedua ujung terverifikasi: yang lama beneran bagus, yang sekarang beneran rusak. Salah satu keliru = hasil ngawur.
[ ] Build harus reproducible. Dependency yang narik versi beda tiap install bikin bisect nunjuk commit yang salah.
[ ] Simpan git bisect log sebelum reset — dokumentasi buat postmortem.
[ ] Flaky? Jalanin N kali, atau --grep tes yang paling deterministik.

Satu hal yang bisa langsung dipakai

Hari ini, coba ini di repo yang lo pegang:

git bisect start HEAD $(git describe --tags --abbrev=0)

Lihat berapa commit di antaranya. Kalau lebih dari ~20, itulah alasan git bisect run lebih cepat daripada git log -p yang lo scroll manual sambil ngopi.

Takeaway

Debugging berurutan itu O(n). Bagi dua itu O(log n). Kalau lo masih baca commit satu-satu, lo bukan teliti — lo cuma lambat.

Catatan kecil yang lucu: algoritma binary search yang dipakai buat nyari bug ini sendiri pernah punya bug. (low + high) / 2 bisa overflow integer. Joshua Bloch nulis soal ini di 2006, dan bug-nya udah hidup ~9 tahun di java.util.Arrays.binarySearch. Alat bagus tetap bisa rusak — makanya tetap verifikasi ujung-ujungnya.