Rust'ta 6 kat hızlı toplu ikili arama: dallanma tahmini optimizasyonu
scikit-learn'ün ikili arama kodu Rust'ta dallanma tahmini optimizasyonuyla 6 kat hızlandırıldı; CPU mekanik sempatisi üzerine teknik inceleme.
Quansight'ta çalışan bir mühendis, scikit-learn'ün gradyan histogram boosting algoritmasında kullanılan ikili arama adımını Rust ile yeniden yazarak 6 kat hızlandırdı. Optimizasyonun temelinde 'mekanik sempati' yatıyor: CPU'nun dallanma tahmincisiyle savaşmak yerine onunla uyumlu çalışan kod yazmak.
Standart ikili arama, float değerleri 255 kovaya (bucket) eşit dağıtmak için kullanılıyor, ancak veriler eşit dağıldığında hangi dalın seçileceği CPU için öngörülemez hale geliyor. Donanım sayaçlarıyla yapılan ölçümler, 1 milyon değerlik veri setinde yaklaşık 27 milyon dallanma talimatının %16,6'sının yanlış tahmin edildiğini gösteriyor.
Çözüm, while döngüsünü sabit sayıda yinelemeye (kova sayısının log2'si) çevirmek ve if/else bloklarını dallanmasız (branchless) koda dönüştürmek. Bu yaklaşım, komut düzeyinde paralellik ve SIMD gibi düşük seviye donanım kavramlarını pratik bir performans kazanımına dönüştürüyor; sayısal Python uzantıları yazan mühendisler için doğrudan uygulanabilir bir ders sunuyor.