Re:Binary Search: A new implementation that is up to 25% faster
by thomasahle on Monday July 20, 2020 @03:46AM
(#23895625)
If you have some sort of chip that can do B comparisons in parallel, you can search in log(N)/log(B) time.
[ Parent
| on HN ]
Re:Binary Search: A new implementation that is up to 25% faster
by BeeOnRope on Monday July 20, 2020 @10:16AM
(#23898071)
Any modern chip with SIMD can do comparisons in parallel. For example, almost recent Intel chip can do 16x 32-bit comparisons in a single cycle.
The bottleneck is not usually the comparison itself, however, but the data movement needed to gather all the elements to be compared. This cannot be vectorized efficiently since SIMD gathers tend to be inefficient.
The story is probably different on GPUs.