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

111–120 of 198 posts

Re: Beautiful branchless binary search

#111

Post by msla »

mgaunard wrote: post #71
mgaunard wrote: post #29

It's funny how people struggle so much to write branchless code. The code is clearly not branchless as written, and relies on non-trivial optimizations for it to happen. Just write it correctly to begin with.

Modded down, I guess the average hackernews web dev can't do branchless either. It's easy, just run all the instructions from all branches, and select the output you want based on conditionals.

> and select the output you want based on conditionals.

I thought you said it would be branchless.

Re: Beautiful branchless binary search

#112

Post by Paul-Craft »

2102922286 wrote: post #12
vkazanov wrote: post #8

Earlier quoted context omitted.

I don't think it is the instruction that makes the difference. Cmov is a branch either way. Branches can be unpredictable and slow, no matter what instructions, (or tables, or whatever) are used to introduce the branch at question. It is predictable nature of branching in this algo that makes the difference. Which makes me wonder... EDIT: the cmov vs explicit branching story is a bit more complicated than just branch…

Cmov doesn't branch. A branch refers specifically to the program counter ending up in more than one possible place after an instruction has executed. It is this behavior that mucks with the CPU state and slows everything down. It's true that the cmov instruction uses the CPU flags register (which I'm sure the CPU designers at Intel hate), but that doesn't mean that it branches. You can achieve the same effect as cmov…

Thank you for this comment! I was sitting here, metaphorically scratching my head, trying to figure out how the hell you can call this branchless when there's clearly an `if` in there:

        for (step /= 2; step != 0; step /= 2) {
        if (compare(begin[step], value))
            begin += step;
        }
Your comment, especially this part, made it click for me:

> You can achieve the same effect as cmov by using bitwise operations and a subtraction, though it'd just be a few cycles slower--but it would be even more clear that it doesn't branch.

BTW, I hate how the author doesn't use braces with this `if` statement. Many a production bug, including one in OSX, as I recall, have occurred because someone didn't want to type a couple extra characters.

Re: Beautiful branchless binary search

#113

Post by ptspts »

otikik wrote: post #80

My C++ is incredibly rusty. Don't all major compilers provide an `asm` declaration? It seems that would have been handy in order to overcome Clang's unwillingness to use CMOV.

Most modern C++ compilers provide inline assembly. However, the syntax is compiler-specific and target-specific. Also it's (almost) impossible to use generic types with such inline assembly.

Re: Beautiful branchless binary search

#115

Post by kccqzy »

abainbridge wrote: post #79

How does the benchmarking work here? I always find this kind of micro-benchmarking hard. I feel like I want to see results with and without a preceding cache flush. And with/without clearing of the branch predictor state. Other things I find hard are: 1) ensuring that the CPU is running at full(ish) speed and isn't in a slower-clocked power saving mode for some of the test, 2) effects of code and data alignment can b…

According to Intel, for accurate benchmarking you should write a Linux kernel module. And remember to disable preemption and disable interrupts.

https://www.intel.com/content/dam/www/public/us/en/documents...

Re: Beautiful branchless binary search

#116

Post by shultays »

What is the reason for different compilers not optimizing that (if (cond ...) begin += step;) as cmov?

Sometimes I feel like I am putting too much trust in compilers. I recently started reading the manual of Agner Fog. Any other recommended resources?

Re: Beautiful branchless binary search

#117

Post by vlovich123 »

2102922286 wrote: post #11

A cool related algorithm is https://algorithmica.org/en/eytzinger In addition to being branchless, it also has better cache properties than a standard binary search tree. If you're doing a binary search in an array, you start in the middle, and then jump all the way to the midway point of one half, and so on. As a result, there's a lot of distance between each read that you do in the array. Thus, each read is putting…

IIRC it really only works well if you have a rarely mutated structure that's read-heavy. Otherwise every time you try to mutate the array, you have to rebuild the layout & it's typically heavier than just sorting (i.e. you have to sort + regenerate the layout). It's a neat concept for sure.

Re: Beautiful branchless binary search

#118

Post by secondcoming »

Paul-Craft wrote: post #112
2102922286 wrote: post #12

Earlier quoted context omitted.

Cmov doesn't branch. A branch refers specifically to the program counter ending up in more than one possible place after an instruction has executed. It is this behavior that mucks with the CPU state and slows everything down. It's true that the cmov instruction uses the CPU flags register (which I'm sure the CPU designers at Intel hate), but that doesn't mean that it branches. You can achieve the same effect as cmov…

Thank you for this comment! I was sitting here, metaphorically scratching my head, trying to figure out how the hell you can call this branchless when there's clearly an `if` in there: for (step /= 2; step != 0; step /= 2) { if (compare(begin[step], value)) begin += step; } Your comment, especially this part, made it click for me: > You can achieve the same effect as cmov by using bitwise operations and a subtraction…

Most topics I've read/viewed on branchless stuff seems to boil down to doing arithmetic with bools. So your code above can be thought of as:

   bool b = compare(begin[step], value);
   begin += (step * b);

Re: Beautiful branchless binary search

#119

Post by compiler-guy »

spc476 wrote: post #62
Dwedit wrote: post #41

Earlier quoted context omitted.

I just had it pointed out to me that CMOV can be simulated with subtraction and bitwise operators. Specifically, subtraction, arithmetic shift right, and AND. `((A-B) ASR 31) AND C`. Your result is C if `A - B = 0`.

In C, shifting signed integers is undefined behavior.

Although it can bite you if you don’t know what you are doing, signed-integer shifting is not necessarily undefined behavior. Roughly, for positive signed integers, if the operation doesn’t overflow then the result is defined. For negative signed numbers, right shifts are implementation defined, but almost all modern systems define the result in the expected manner.

https://en.cppreference.com/w/cpp/language/operator_arithmet...

Re: Beautiful branchless binary search

#120

Post by cmrdporcupine »

This is a great article I can't wait to dig into (and the comments here) as soon as I can unshift my brain from the gear it's in.

One thing I noticed is the author doesn't compare against linear search for reference. I am personally very curious at what container size either lower_bound or branchless_lower_bound start to outperform a linear scan on modern hardware with modern L1 cache sizes etc.

In the thing I've been playing with -- very unscientifically with a vector of up to 16 sorted u8s:

On x86_64, an SSE optimized vector scan like this: https://github.com/armon/libart/blob/master/src/art.c#L426 is slightly faster than linear scan, which is in turn slighty faster than binary search (the latter two are very close)

However on M1 Mac, simple binary search outperforms a NEON SIMD optimized search which in turn is basically tied with linear scan. Sometimes. The NEON algorithm is trickier than the SSE because NEON lacks an equivalent of SSE's _mm_movemask_epi8

Post reply on HN