Introducton
  
    
    Link to heading
  

Binary search is a very fast algorithm. Due to its exponential nature, it can process gigabytes of sorted data quickly. However, two problems make it somewhat challenging for modern CPUs:

predictability of instruction flow;
predictability of memory access.

At each step, binary search splits the dataset into two parts and jumps to one of those parts based on a midpoint value. It’s difficult for the CPU to predict which parts of the presumably large array will be accessed in the next iteration. As a result, binary search produces many cache misses, which stalls the CPU pipeline, resulting in poor instruction-per-clock performance.

Lobsters is a community-driven platform for sharing and discussing links to articles, tutorials, and projects related to technology and programming. Readers can learn about a wide range of topics, from software development and system administration to cybersecurity and artificial intelligence. With user submissions, comments, and voting, Lobsters provides a platform for collaborative learning and knowledge sharing among technology enthusiasts.

Lobsters

Binary search is a fast algorithm but suffers from predictability issues on modern CPUs. This post explores the Eytzinger layout to improve memory access predictability and introduces a branchless version of the Eytzinger binary search. It also discusses the benefits of using software memory prefetching to further enhance performance.

Fast(er) binary search in Rust

Branchless Eytzinger with memory prefetch