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

31–40 of 198 posts

Re: Beautiful branchless binary search

#31

Post by 2102922286 »

jeffreygoesto wrote: post #28
2102922286 wrote: post #23

Earlier quoted context omitted.

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?

https://uops.info/uiCA.html it's really cool!!

Re: Beautiful branchless binary search

#32

Post by kevingadd »

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…

Wow, the dispatch queue is so deep! The trace makes a lot of sense, thanks for sharing it. I must have been unclear if it sounded like I was saying cmov was a bottleneck - my argument is just that it's not going to be especially faster than a branch in the general case.

Great point that memory reads are going to dominate a binary search - at that point the CPU will be spending a lot more time waiting for memory than it is spending executing your branches or cmovs.

Re: Beautiful branchless binary search

#33

Post by rowanG077 »

berkut wrote: post #3
rowanG077 wrote: post #2

Nice algorithm. I don't agree that it is branchless however. Cmov is a branching instruction for sure. And it doesn't really matter whether a branch can be well predicted. The reason you mainly want branchless code is for security reasons where a timing sidechannel could reveal information. Calling this algorithm branchless devalues the term into something meaningless. Edit: Everybody in the comments is focusing on p…

> "The reason you mainly want branchless code is for security reasons where a timing sidechannel could reveal information." Erm, that likely depends on the industry you're in? In HPC, branchless algorithms are often needed to use wide architectures (SIMD / GPUs) to their full capacity...

It's a requirement thing. For security the requirement is code needs to be branchless. In HPC the requirement is high performance, the branchless algorithm is an implementation detail. In fact branchless code is often much slower then the branching version.

Re: Beautiful branchless binary search

#34

Post by secondcoming »

latency-guy2 wrote: post #13
secondcoming wrote: post #7

Earlier quoted context omitted.

> The reason you mainly want branchless code is for security reasons That just isn’t true.

Which part isn't true? I think the qualifier 'mainly' definitely weakens the statement, but I'm struggling to think of how it could certainly be false statement. This is certainly true for at minimum DDoS attacks, and I would absolutely consider that a security risk.

Branchless algos are all over the place outside of security.

Re: Beautiful branchless binary search

#35

Post by latency-guy2 »

secondcoming wrote: post #34
latency-guy2 wrote: post #13

Earlier quoted context omitted.

Which part isn't true? I think the qualifier 'mainly' definitely weakens the statement, but I'm struggling to think of how it could certainly be false statement. This is certainly true for at minimum DDoS attacks, and I would absolutely consider that a security risk.

Branchless algos are all over the place outside of security.

Don't care, there's a quote in the OP that this discussion is being limited to.

Re: Beautiful branchless binary search

#36

Post by berkut »

2102922286 wrote: post #30
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 pr…

Yeah, it's mildly annoying there's no (at least to my knowledge?) compiler hint like the '__builtin_expect' ones to tell compilers that the values are very unlikely going to be predictable with enough accuracy to allow the branch predictors to be useful in general, and to use a cmov instead of the traditional branching instructions because of this.

Re: Beautiful branchless binary search

#37

Post by srcreigh »

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…

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 respectively. That’s 17 vs 14 and 17 vs 13 reads.

And this would not help much for string data values unless the strings are at most 8 characters long :-)

This same thinking can be used to optimize database queries. Given several table and index layouts how many 8kb disk reads will be needed in each case. Wish I could get a job doing that kind of design work!

Re: Beautiful branchless binary search

#38

Post by atq2119 »

srcreigh wrote: post #37
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…

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, using a similar layout with higher fan-out and SIMD ops doesn't benefit from this effect and is probably still better.

Re: Beautiful branchless binary search

#39

Post by dist1ll »

berkut wrote: post #36
2102922286 wrote: post #30

Earlier quoted context omitted.

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 pr…

Yeah, it's mildly annoying there's no (at least to my knowledge?) compiler hint like the '__builtin_expect' ones to tell compilers that the values are very unlikely going to be predictable with enough accuracy to allow the branch predictors to be useful in general, and to use a cmov instead of the traditional branching instructions because of this.

clang has __builtin_unpredictable [0]

[0] https://clang.llvm.org/docs/LanguageExtensions.html#builtin-...

Re: Beautiful branchless binary search

#40

Post by berkut »

dist1ll wrote: post #39
berkut wrote: post #36

Earlier quoted context omitted.

Yeah, it's mildly annoying there's no (at least to my knowledge?) compiler hint like the '__builtin_expect' ones to tell compilers that the values are very unlikely going to be predictable with enough accuracy to allow the branch predictors to be useful in general, and to use a cmov instead of the traditional branching instructions because of this.

clang has __builtin_unpredictable [0] [0] https://clang.llvm.org/docs/LanguageExtensions.html#builtin-...

Oooooh :)

Thanks!

Post reply on HN