6× faster binary search: from compiled code to mechanical sympathy
Summary
This article demonstrates hardware-aware optimizations to speed up a binary search used in data bucketing. It starts with a Rust-based compiled extension approach, then introduces branchless and precomputed strategies to reduce branch mispredictions, achieving up to 6x speedups. It also covers unsafe code, auto-vectorization, and the tradeoffs of SIMD and portability, ending with recommended readings.