Fast(er) binary search in Rust
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, b...
Hasnain says:
Learnt a bunch of cool datastructure tricks from this one.
"The branchless Eytzinger layout is a great option if the data you are searching over is fixed and can be preprocessed to accommodate a faster memory access layout. Because it respects the characteristics of modern CPUs, it is basically one of the fastest ways to search in sorted data when implemented correctly.
Additionally, there are some further ideas like S-trees ([4]) or mixed layout ([2]) that you could try if you’re looking for the best binary search."
Posted on 2023-05-05T03:53:26+0000