Re:Binary Search: A new implementation that is up to 25% faster
by pbiggar on Monday July 20, 2020 @05:46AM
(#23896271)
This is really cool!
About a decade ago I did research on sorting and searching, which was the same type of work going on here (https://github.com/pbiggar/sorting-branches-caching). I found it was extremely difficult to accurately say whether one algorithm is faster than another in the general case. I found a bunch of speed improvements that probably only apply in processors with very long pipelines (like the P4)).
Execution speed is probably the right metric here, but it makes it hard to understand _why_ it's faster.
PS. Looking at "boundless interpolated search" (https://github.com/scandum/binary_search/blob/master/binary-...), it seems it's missing a `++checks`. I initially thought this could be the cause of a misreporting it as being faster, but I see the benchmark is run-time based so that wouldn't cause it unless the incrementing itself is the bottleneck.
About a decade ago I did research on sorting and searching, which was the same type of work going on here (https://github.com/pbiggar/sorting-branches-caching). I found it was extremely difficult to accurately say whether one algorithm is faster than another in the general case. I found a bunch of speed improvements that probably only apply in processors with very long pipelines (like the P4)).
Execution speed is probably the right metric here, but it makes it hard to understand _why_ it's faster.
PS. Looking at "boundless interpolated search" (https://github.com/scandum/binary_search/blob/master/binary-...), it seems it's missing a `++checks`. I initially thought this could be the cause of a misreporting it as being faster, but I see the benchmark is run-time based so that wouldn't cause it unless the incrementing itself is the bottleneck.