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

21–30 of 198 posts

Re: Beautiful branchless binary search

#21

Post by 2102922286 »

vkazanov wrote: post #18
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…

Sure, it doesn't change the PC. But it can introduce a branch indirectly, I.e. when there is a jump to an address MOVed by cmov. Either way, it seems that the wisdom has change since the last time I wrote and read assembly. Cmov used to be slow. It seems that the current answer is "it depends".

If what you're saying is (roughly)

        cmovne  rax, rdx
        jmp     rax
that is, a cmov followed by an indirect jump to the address contained in rax, "jmp rax" is _always_ an indirect jump. It doesn't matter whether rax was set via a conditional move instruction or not.

Re: Beautiful branchless binary search

#22

Post by skrebbel »

heywhatupboys wrote: post #17

I'm all for supporting OSS, but the author having a tip button with "recommended" tips of 20 $ and 1,000 $ for people and business respectively is so laughable it took away from an otherwise good blog posts. Commercialisation of OSS 2.0 should be discouraged to this extend

I bet it’s just for kicks, you’re reading way too much into this. This is just someone’s personal website and they’re experimenting with a donate button.

Re: Beautiful branchless binary search

#23

Post by 2102922286 »

kevingadd wrote: post #19
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…

The main problem with branches in an algorithm like this is that they create a dependency, where not only do the future instructions depend on the possibly-mispredicted outcome of the previous instruction and need to get thrown out, but you may have started executing the wrong instructions. A cmov doesn't affect the instruction pointer, so that 'executing the wrong instructions' condition is gone, but it still affect…

For the given assembly from the blog post

    loop:
        lea (%rdx,%rax,4),%rcx
        cmp (%rcx),%esi
        cmovg %rcx,%rdx
        shr %rax
        jne loop
Here's a simulated CPU trace on Intel skylake: https://uica.uops.info/tmp/2de9d862d05d482ebed576d7e3923b93_...

Note that this tracer makes the assumption that all memory loads are in cache (otherwise the memory lookup will dominate). So bear that in mind for this code, especially since memory reads will likely dominate the cost of a binary search.

Regardless, it appears that the cost of conditional move is not the source of bottleneck.

Re: Beautiful branchless binary search

#24

Post by Dwedit »

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…

For the case of comparing integers, and you want to know if A - B >= 0, you can take A - B, Arithmetic Shift Right 31 bits, then you have 0 if Greater Than or Equal and -1 if Less Than. From there you can just AND that with your displacement.

Note that it's not a comparison on A and B, it's a comparison on A - B, which must not overflow.

Re: Beautiful branchless binary search

#25

Post by jeffreygoesto »

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…

Do they publish if getting the tree/array in shape initially or inserting an element is significantly different in speed to the plain sorted layout? The method is a nice read optimization and you'd need to check if it amortizes when sun together with the tree creation.

Re: Beautiful branchless binary search

#26

Post by coppsilgold »

cmovq wrote: post #15

> Those spikes for std::lower_bound are on powers of two, where it is somehow much slower. I looked into it a little bit but can’t come up with an easy explanation It’s been a long time since I looked into this, if I recall correctly binary search with close to power of 2 sized data is slower because of some interaction with the caches which causes the data to constantly have to be reloaded from memory.

Cache associativity, conflict miss. When too many memory addresses which are far apart map to the same cache lines while being used and reused in quick succession, causing cache evictions.

Scott Meyers had a very good talk which contained this information: https://youtu.be/WDIkqP4JbkE?t=3614>

This is an effect of access pattern rather than size, but some access patterns are dictated by size.

Re: Beautiful branchless binary search

#27

Post by pizza234 »

Some information on the CMOV can be found on the Intel Optimization Reference Manual (https://cdrdv2-public.intel.com/671488/248966-046A-software-...).

Torvalds was famously critical of it (https://yarchive.net/comp/linux/cmov.html); part of the criticism is now moot though, due to low latencies on modern processors (it seems 1 cycle or less, although the instruction consumes internal flags).

His idea seems to be still applicable and consistent with Intel's recommendation: make branches predictable, and only after, use CMOV for the remaining ones. His fundametnal assumption is that "even if you were to know that something is unpredictable, it's going to be very rare.".

Re: Beautiful branchless binary search

#28

Post by jeffreygoesto »

2102922286 wrote: post #23
kevingadd wrote: post #19

Earlier quoted context omitted.

The main problem with branches in an algorithm like this is that they create a dependency, where not only do the future instructions depend on the possibly-mispredicted outcome of the previous instruction and need to get thrown out, but you may have started executing the wrong instructions. A cmov doesn't affect the instruction pointer, so that 'executing the wrong instructions' condition is gone, but it still affect…

For the given assembly from the blog post loop: lea (%rdx,%rax,4),%rcx cmp (%rcx),%esi cmovg %rcx,%rdx shr %rax jne loop Here's a simulated CPU trace on Intel skylake: https://uica.uops.info/tmp/2de9d862d05d482ebed576d7e3923b93_... Note that this tracer makes the assumption that all memory loads are in cache (otherwise the memory lookup will dominate). So bear that in mind for this code, especially since memory reads…

How do you get such am image please?

Re: Beautiful branchless binary search

#30

Post by 2102922286 »

pizza234 wrote: post #27

Some information on the CMOV can be found on the Intel Optimization Reference Manual ( https://cdrdv2-public.intel.com/671488/248966-046A-software-... ). Torvalds was famously critical of it ( https://yarchive.net/comp/linux/cmov.html); part of the criticism is now moot though, due to low latencies on modern processors (it seems 1 cycle or less, although the instruction consumes internal flags). His idea seems to be…

This is one area where Profile-Guided Optimization (PGO) can help a lot! With PGO, you run your program on some sample input and it logs info like how many times each side of a branch was taken. From there, you can recompile your code. If the compiler sees that one side of the branch dominates, it can emit code to prioritize that branch. However if the branch counts are approximately even and the branch is hard to predict (n.b. this is technically distinct from having even branch counts), then the compiler can know that the CPU would have trouble predicting the branch, and can emit a cmov instruction instead.
Post reply on HN