Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Fastest branchless binary search

mhdm.dev

Post reply on HN
Print view View original

151–155 of 155 posts

Re: Fastest branchless binary search

#151

Post by gpderetta »

pclmulqdq wrote: post #140
gpderetta wrote: post #111

Earlier quoted context omitted.

You do additional comparisons at each recursion depth, but you have a shallower recursion depth though. I think you break-even already at 4-way search.

I think that only helps if you assume exactly 1.5 comparisons per level with a branch predictor, and I think that will be hard to hit: you basically need the comparison function to be very short to have that (shorter than the mispredict penalty). Then, you are doing 3 comparisons per two levels vs 3 comparisons for 2 levels. If you were to extend this logic to do 3 levels at a time, you would be doing 7 comparisons t…

Ok, I have been nerd sniped. I need to get near a compiler and a profiler ASAP.

Re: Fastest branchless binary search

#153

Post by hinkley »

eesmith wrote: post #107
hinkley wrote: post #91

Earlier quoted context omitted.

The comments have a higher density of opinions and experience.

But does it have a higher density of good opinions and experience? ;)

Do you want to fish in a lake that doesn’t have many fish but they’re all large, or in a lake that has lots of fish?

Re: Fastest branchless binary search

#154

Post by eesmith »

hinkley wrote: post #153
eesmith wrote: post #107

Earlier quoted context omitted.

But does it have a higher density of good opinions and experience? ;)

Do you want to fish in a lake that doesn’t have many fish but they’re all large, or in a lake that has lots of fish?

Could you explain the metaphor? Are you asking me if I'm a sport fisherman who wants the largest fish, or a commercial fisherman who wants a large haul?

It probably doesn't help that, I don't fish. What I know comes originally from Alan Dean Foster's serialization of "The Last Starfighter", at https://archive.org/details/laststarfighter0000fost_f6k9/pag... :

> There weren’t many fish to be had in the small desert lake nearby. That didn’t worry Mr Boone. As any true fisherman knows, catching fish has nothing to do with fishing. The catching is an adjunct, a corollary to the actual art of fishing, which consists of killing time on a small boat as simply as possible, utilizing only the minimal amount of energy necessary to maintain life while simultaneously consuming as much cold beer and snacks as the body will tolerate.

Re: Fastest branchless binary search

#155

Post by bjourne »

mhdm wrote: post #132
bjourne wrote: post #102

On my Cascade Lake processor "-mllvm -x86-cmov-converter=false" almost halves the performance of the binary search: | Benchmark | gcc | clang | clang -cmov | |-----------|------|-------|-------------| | slow u32 | 23.4 | 46.7 | 45.8 | | fast u32 | 18.1 | 19.8 | 31.4 | The numbers are nanoseconds/bsearch on a 100mb uint32 array. Seem to me that clang (15.0.7) is just much worse at optimizing this particular piece of c…

Then you'll want to look at https://mhdm.dev/posts/sb_lower_bound/#prefetching 100mb is large enough that the branchy version turns out to have a slight advantage, more due to quirks of x86 (speculative execution) rather than being better.

So I spent too much time benchmarking:

    | Entries | gcc | gcc+pref. | clang | clang+pref. | clang -cmov | clang -cmov+pref. |
    |---------|-----|-----------|-------|-------------|-------------|-------------------|
    | 0.5     | 210 | 88        | 213   | 191         | 109         | 93                |
    | 1.0     | 231 | 107       | 235   | 211         | 134         | 112               |
    | 2.0     | 289 | 168       | 306   | 275         | 231         | 179               |
    | 5.0     | 369 | 231       | 389   | 343         | 338         | 239               |
    | 10      | 413 | 268       | 437   | 384         | 410         | 276               |
    | 25      | 469 | 311       | 490   | 435         | 506         | 318               |
    | 50      | 515 | 346       | 537   | 478         | 586         | 356               |
    | 100     | 564 | 387       | 588   | 522         | 670         | 399               |
Entries are in millions and times in ns per bsearch call. Prefetching does all the difference, but perhaps not for the right reason. On my machine (broadwell) the two prefetches that you suggested makes gcc emit the cmovb that clang with -cmov uses. The second one is enough to make it prefer cmovb but not the first one. Maybe a hand-hacked assembly loop based on the code gcc emits but without the prefetches would run even faster.
Post reply on HN