You can beat the binary search
Binary search is a classic and efficient method for finding values in sorted arrays, but it can be outperformed by leveraging modern processor capabilities. The SIMD Quad algorithm combines quaternary interpolation search with SIMD instructions to accelerate searches in arrays of 16-bit integers. This hybrid approach reduces search time by narrowing down blocks quickly and checking multiple elements in parallel.
- ▪Binary search efficiently finds values in sorted arrays by repeatedly halving the search space.
- ▪The SIMD Quad algorithm uses quaternary interpolation to locate a target block and then applies SIMD instructions to check 16 elements at once.
- ▪Modern processors support SIMD operations that allow parallel comparison of multiple 16-bit integers, enabling faster searches than traditional binary search.
- ▪The algorithm performs a linear search on small arrays (<16 elements) and handles leftover elements not in full 16-element blocks.
- ▪Benchmarks test performance across array sizes from 2 to 4096 elements in both cold (cache-miss) and warm (cache-friendly) query modes.
Opening excerpt (first ~120 words) tap to expand
You can beat the binary search We sometimes have to look for a value in a sorted array. The simplest algorithm consists in just going through the values one by one, until we encounter the value, or exhaust the array. We sometimes call this algorithm a linear search. In C++, you can get the desired effect with the std::find function. For large arrays, you can do better with a binary search. Binary search is a classic algorithm that efficiently locates a target value in a sorted array by repeatedly dividing the search interval in half. Starting with the entire array, it compares the target to the middle element: if the target is smaller, it discards the upper half; if larger, it discards the lower half. This process continues until the target is found or the interval is empty.
…
Excerpt limited to ~120 words for fair-use compliance. The full article is at Daniel Lemire's blog.
Discussion
0 commentsMore from Daniel Lemire's blog
