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

Beautiful branchless binary search

probablydance.com

Post reply on HN
Print view View original

51–60 of 198 posts

Re: Beautiful branchless binary search

#51

Post by touisteur »

pjmlp wrote: post #48
SleepyMyroslav wrote: post #42

If being branchless is important property of the algorithm then it is better to enforce it. Or at least test for it. If his GCC version will get an update and it will stop producing assembly that he wants no-one will ever know. Which brings us back to regular discussion: C ( and C++ ) does not match hardware anymore. There is no real control over important properties of generated code. Programmers need tools to contr…

The myth that they match has been busted since at very least Pentium came to be. A good read of Michael Abrash books explains that quite well, as does playing around Intel's VTune.

For those looking for it https://www.jagregory.com/abrash-black-book

If some/most of the actual tricks are not up to date (ahem) the whole book is filled with techniques, stories, concepts... It's more than ever a Zen of optimization opus.

Can someone on HN close to him tell Michael Abrash, should he write again, whatever he wants, even gardening or vulkanstuff wrangling, he has guaranteed readers.

Re: Beautiful branchless binary search

#53

Post by tromp »

The setup code to reduce the length to a 2-power can be avoided. I'm curious how well the following code performs in comparison:

    for (size_t length = end - begin; length != 0; length = (length + 1) / 2)
    {
        size_t step = length / 2;
        if (compare(begin[step], value))
            begin += step;
    }   
    return begin;
For odd lengths like 5, this splits the array in an even part of length 2, and an odd part of length 3, and then searches either part with length 3. So again there is some redundancy for non-2-powers.

While this code is simpler, it does require an extra division and increment in each loop iteration, so presumably it performs a little worse.

Re: Beautiful branchless binary search

#54

Post by buybackoff »

Branchless or not in this case, it still touches memory in not so good pattern. I found that a significant speedup of a classic BS could be achieved by switching to vectorized search when the remaining range has a width of 3-4 SIMD lines (or maybe even a little more). The bounds of that range are likely already touched and in cache, then prefetching helps. It has high likelihood of finding the target on a single SIMD compare, then switch to linear search on small data that is already in L1. It gives 30-50% gain on 1K items array of integers, 10-25% on 1M items, depending on data distribution. Here is an example in C#: https://github.com/Spreads/Spreads/blob/main/src/Spreads.Cor...

Re: Beautiful branchless binary search

#55

Post by srcreigh »

vidarh wrote: post #49
srcreigh wrote: post #37

Earlier quoted context omitted.

Trying to figure this out myself. So cache line is 64 bytes. Ignoring pointers you can fit eight 8bit data/key values, or sixteen 4bit data/key values. Pointers are entirely implicit (thx user below) This would save you 3 or 4 memory reads respectively. The odds of this strategy helping past the first few layers seems unlikely. So for 100k elements binary tree, this should be a 21% or 31% performance improvement resp…

You don't store data nodes, or pointers. You store the keys. If you need to store data, just store them at the same index in another array. The pointers are wholly implicit . E.g. assuming you let the index 0 be empty, the left pointer for a node k is at 2k and the right node is at 2k+1. In terms of benefit here, the main benefit appears to be that since you always know where the children will be, you can trade bandw…

That’s what I meant re keys, but ya nice point about pointers. Forgetting details of my data structures classes. updated my post (used to count 1 bit per node for pointers)

Re: Beautiful branchless binary search

#56

Post by SleepyMyroslav »

pjmlp wrote: post #48
SleepyMyroslav wrote: post #42

If being branchless is important property of the algorithm then it is better to enforce it. Or at least test for it. If his GCC version will get an update and it will stop producing assembly that he wants no-one will ever know. Which brings us back to regular discussion: C ( and C++ ) does not match hardware anymore. There is no real control over important properties of generated code. Programmers need tools to contr…

The myth that they match has been busted since at very least Pentium came to be. A good read of Michael Abrash books explains that quite well, as does playing around Intel's VTune.

If that myth has been busted 20 years ago when I have started working close in time with Pentiums then HN crowd never got the memo.

Even right now i have two replies above yours that completely ignore the point of discussed article. Which is that algorithm is 'branchless'.

PS. I agree with comment in this topic from 'mgaunard' that algorithm should have been written as branchless explicitly.

Re: Beautiful branchless binary search

#58

Post by srcreigh »

atq2119 wrote: post #38
srcreigh wrote: post #37

Earlier quoted context omitted.

Trying to figure this out myself. So cache line is 64 bytes. Ignoring pointers you can fit eight 8bit data/key values, or sixteen 4bit data/key values. Pointers are entirely implicit (thx user below) This would save you 3 or 4 memory reads respectively. The odds of this strategy helping past the first few layers seems unlikely. So for 100k elements binary tree, this should be a 21% or 31% performance improvement resp…

The big advantage of the Eytzinger layout actually comes into play when your binary search isn't branch-free. In that case, the CPU will speculate loads reasonably far ahead, and because both choices tend to be in the same cacheline, this prefetch is rarely wasted. In other words, the big win isn't about reducing the number of cacheline fetched, it's about reducing the effective latency of those fetches. That said, u…

I think effective latency and reducing the number of cache lines is probably the exact same thing. The point is instead of fetching 5 cache lines to get to the 5th layer of the tree from memory, you fetch just 2 and access the mega root node via cache.

Re: Beautiful branchless binary search

#59

Post by pjmlp »

SleepyMyroslav wrote: post #56
pjmlp wrote: post #48

Earlier quoted context omitted.

The myth that they match has been busted since at very least Pentium came to be. A good read of Michael Abrash books explains that quite well, as does playing around Intel's VTune.

If that myth has been busted 20 years ago when I have started working close in time with Pentiums then HN crowd never got the memo. Even right now i have two replies above yours that completely ignore the point of discussed article. Which is that algorithm is 'branchless'. PS. I agree with comment in this topic from 'mgaunard' that algorithm should have been written as branchless explicitly.

HN crowd has never got the memo in many subjects, another one is how the game development culture differs from FOSS.

Re: Beautiful branchless binary search

#60

Post by Arnt »

SleepyMyroslav wrote: post #42

If being branchless is important property of the algorithm then it is better to enforce it. Or at least test for it. If his GCC version will get an update and it will stop producing assembly that he wants no-one will ever know. Which brings us back to regular discussion: C ( and C++ ) does not match hardware anymore. There is no real control over important properties of generated code. Programmers need tools to contr…

We lost that control when CPUs became increasingly multilayered and complicated, with 20-step pipelines, enough parallelism to run a hundred instructions at the same time, with micro-ops and microcode, with branch predictors good enough to unroll some loops completely. What programmer today understands the branch prediction logic used on production system? Well enough to understand what difference branchlessness makes?

And it doesn't seem to hurt. I at least have both worked on systems where I can read and write assembly and on one where I can't, and my "need to control" isn't such that the lack of assembly knowledge makes a significant impact on my effectiveness on the latter platform.

Post reply on HN