4 ms·
If you have some sort of chip that can do B comparisons in parallel, you can search in log(N)/log(B) time.
by thomasahle 6y ago
If you have some sort of chip that can do B comparisons in parallel, you can search in log(N)/log(B) time.
- BeeOnRope 6y agoAny 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.