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

81–90 of 198 posts

Re: Beautiful branchless binary search

#81

Post by krona »

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…

Running within a linux cset shield is a fairly standard practice.

For benchmarks reporting times in the range of nanoseconds a common approach is a linear regression of varying batch sizes; I'm not sure gtest does this.

But generally, don't trust any result without a (non-parametric) confidence interval, since the confounding factors like OS jitter, CPU frequency, temperature etc. can't be easily controlled, although some CPU features can be disabled.

Re: Beautiful branchless binary search

#82

Post by account42 »

contravariant wrote: post #73
zelphirkalt wrote: post #44

Earlier quoted context omitted.

Isn't that like storing a heap inside an array, with indices and values like this: 0: top of heap, 1: left of top, 2: right of top, 3: left of left of top ... ?

It is, but so is storing a sorted array.

It's still misleading to call this a binary search when that is commonly understood as an algorithm operating on a sorted range which is not just an arbitrary datastructure but something that already exists in many situations. If you just need fast lower_bound lookup for a set that you control and which has no other uses then sure this is nice, but more commonly you only care if an element is in the set and in that case if you can control the data structure then there are many more options.

Re: Beautiful branchless binary search

#83

Post by leroy-is-here »

rowanG077 wrote: post #76
Aissen wrote: post #65

Earlier quoted context omitted.

You don't really want branchless in security. The requirement is constant-time and side-channel resistance. The branchless algorithm is an implementation detail.

Constant-time is not possible with branching code. If it's possible your code runs through different paths then your time is not constant. Or if you disagree with me show me branching ASM code that has exactly the same perf counters independent of input.

It’s possible to design an algorithm which branches and is also constant time. If, for all inputs, the instruction length (# of instructions executed) is the same even for different branch paths, then they must all run in the same time. This, of course, isn’t accounting for different (microscopic) execution times of individual instructions, but constant time isn’t really a measure of clock time anyway.

Re: Beautiful branchless binary search

#84

Post by account42 »

skrebbel wrote: post #22
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.

I agree with GP that this particular implementation is somewhat off-putting. I think it's because of recommended amounts which makes this feel less of a donation and more like a business transaction. It doesn't help that the amounts are ridiculously high for a single article.

Re: Beautiful branchless binary search

#85

Post by eska »

account42 wrote: post #82
contravariant wrote: post #73

Earlier quoted context omitted.

It is, but so is storing a sorted array.

It's still misleading to call this a binary search when that is commonly understood as an algorithm operating on a sorted range which is not just an arbitrary datastructure but something that already exists in many situations. If you just need fast lower_bound lookup for a set that you control and which has no other uses then sure this is nice, but more commonly you only care if an element is in the set and in that c…

I agree with you.

Algorithms don’t exist in a bubble, but are always accompanied with a data structure.

A heap sorted array is different from a linearly sorted array. Binary search is only defined for the latter.

Re: Beautiful branchless binary search

#86

Post by eska »

josephg wrote: post #78
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…

I’m always surprised by rust’s performance for this reason. The compiler outputs huge binaries, chock full of bounds checks and the like. But performance doesn’t seem to suffer at all from it. On the contrary - I ported some well optimized C to rust and it ran faster. I can only assume the compiler is marking all the bounds checks as unlikely to fail, and correctly predicted branches must be more or less free in mode…

The compiler will outright remove bounds checks that are implied by previous bounds checks.

It is a common low level optimization to add a wide boundary check in the beginning to avoid successive smaller bounds checks.

Re: Beautiful branchless binary search

#87

Post by jove_ »

coppsilgold wrote: post #26
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.

Size also matters for this problem. The effect of it is to slash your processor's cache size. If your problem is small enough that it fits in the cache anyway you won't see the effects. That said, unless the cache is hot, it shouldn't make a difference in the first place. Moreover I'm pretty confident in guessing that with a cold cache, the difference between the algorithms would vanish.

Re: Beautiful branchless binary search

#88

Post by mihaic »

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…

Thinking about cache-optimality, I'm wondering if anyone is using a hybrid: the first levels are in this way (index K branches to 2K and 2K+1 if 1-based), but the end levels are consecutive to then can be loaded in a single cacheline anyway.

Re: Beautiful branchless binary search

#89

Post by martincmartin »

WithinReason wrote: post #61
vidarh wrote: post #49

Earlier quoted context omitted.

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…

So binary search should actually not be binary but... octary?

Yes, these are the same issues faced by databases on spinning rust disks. The solution was to figure out how many keys fit in a disk block / cache line, let's call it k, then have a k-ary tree instead of a binary tree. This is called a B-tree.

https://en.wikipedia.org/wiki/B-tree

With caching on modern CPUs, as opposed to databases on disks, there are multiple levels of caching and you may not know the size of the caches. And the caches can be shared with other work you're doing, or other processes are doing, so the effective size can be smaller. So there's some benefit to algorithms that are independent of cache size.

Re: Beautiful branchless binary search

#90

Post by blondin »

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…

are you going to have a printed version of your book?
Post reply on HN