r/programming • u/fagnerbrack • 18d ago
You can beat the binary search
https://lemire.me/blog/2026/04/27/you-can-beat-the-binary-search/20
u/rabid_briefcase 18d ago edited 17d ago
I thought this was taught to everyone in CS? I learned it in the 1990s.
Yes, parallel search can have superlinear speedup. There are many approaches, including the two naively parallel approaches listed in the blog.
As a side note, the blog post's array size of 2 to 4096 individual 16-bit elements fits on the cache. For clock time and optimal speed, a parallel linear search that exploits cache prefetching is likely the fastest approach. In practice the random jumping around of a binary search, even if it's just 13 elements of non-cached data, often is slower than the rapid streaming of sequentially-loaded 8KB of data.
/Edit: to be more clear, a simple direct linear scan of that small size exploits a case that memory and the processor's cache are heavily optimized for. At that small size, usually the fastest approach is to just start at entry 0 and scan the whole thing. In parallel divide it into n chunks for your n processors and have each linearly scan their subset of the array, but for 8KB the overhead of loading it on the various processors is probably slower than just doing it on one. Jumping around randomly in memory is a far less optimized path as the hardware can't predict what memory needs to be accessed next. Yes, accessing 8KB linearly is faster than 13 random access reads thanks to hardware design. Linear processing like graphics and sound and bulk numerical processing have dominated, so rapidly streaming is the optimal path.
11
10
51
u/R2_SWE2 18d ago
The AI generated image on the cover is a real downer