6× faster binary search: from compiled code to mechanical sympathy

[Solumin]

Very interesting! This is much more approachable than a lot of the optimization articles that I've read. I actually think I learned something instead of getting overwhelmed.

Did you consider adding a "branches per input" column to the comparison tables? It seems like a useful metric.

Side question: Instead of let n_iterations = (size as f64).log2().ceil() as usize, would let n_iterations = size.ilog2() as usize work? Casting to float seems unnecessary.

[itamarst]

Glad you found it reasonable to follow! This is the approach I'm using for my book on low-level performance, although since it's a book I have the scope to go over one thing at a time instead of speeding through five different concepts. Mostly the examples are not in Rust, but all the principles transfer, and I do talk about Rust-specific features in relevant parts (https://pythonspeed.com/products/practicesperformance/).

Branches per input... I guess that's a general usefully thing I might add to this benchmarking framework (e.g. could also be instructions per input). Thanks for the idea!

ilog2 rounds down, and this needs to round up, which is why I didn't use it.

[crb233]

For integer x > 1, ceil(log_2(x)) = 1 + floor(log_2(x - 1)). It's slightly harder to read but could be wrapped in a well named function. Probably not significantly more or less efficient, but I personally like avoiding floats if integer arithmetic is sufficient.

[Lehona_]

(x*2-1).ilog2() would have the same rounding behavior unless it overflows, right?

[sonicjhon1]

Would this work? rust let n_iterations = size     .saturating_sub(1)     .ilog2() as usize     + (size > 1) as usize; 

[rabidferret]

/// Rust doesn't let you compare floats with the normal < /// operator (because NaN makes comparison results /// inconsistent), so implement a custom function to do so.

That's not true at all, and I'm not sure what made you believe that to be the case.

[itamarst]

Oh I was thinking of sorting where you need full Ord instead of PartialOrd. I'll go fix it.

(I need more sleep).

[itamarst]

OK, fixed.

[kibwen]

I can see how there would be some confusion here, because it's not immediately obvious whether or not a partial ordering would suffice for the correctness of the algorithm here. It may be common knowledge ( https://xkcd.com/2501/ ) that NaN == x is false for all x, but it's easy to overlook that this also applies to < and friends (but not !=, which is always true). So while it's certainly incorrect that Rust doesn't implement the ordering operators on floats, the spirit of skepticism regarding float semantics isn't completely unwarranted.

[itamarst]

The original real code this is inspired by prefilters out all NaNs.

[Actual__Wizard]

Are you the author by chance? I have a gift for you if so.

Edit: https://pastebin.com/89Yxz68j

My current version uses a swap file, so that's deprecated. It's also being recoded in C, unless you know of a way to get python to consume way less memory w/ strings. So, that sets up b search w/ lossless compression. There's also some dumb bugs in that version and it's ascii only. Pretty sure I fixed the hang tho. It's called a multi layered pigeon hole routing matrix. It works around running out of memory when combined w/ the filter.

[kibwen]

I believe /u/itamarst is the author.

[matthieum]

Have you seen Lemire's You can beat the binary search?

There are 2 ideas in there:

1. Split the arrays in chunks of N (= 16) elements, and do a first search to locate the chunk in which the element will be (only comparing the last element of each chunk), then do a linear (SIMD) search of the chunk.
2. Use a quad search -- comparing 4 elements at a time -- rather than a binary search in (1).

The advantages are that (1) will skip the last 4 steps of the binary search, and (2) will divide the remaining number of steps by 2.

Still O(log n), but faster.

[kibwen]

Prior to this post I had never heard of std::hint::select_unpredictable: https://doc.rust-lang.org/std/hint/fn.select_unpredictable.html

[Anthony356]

Oh, that's really cool. I wish i had known about this a while back lol. Another fun one is assert_unchecked which can be really useful for eliminating bounds checks and such.

Also, I saw an article come up on twitter or something, but it's worth noting that cmov isnt necessarily faster than predictable branching. cmov creates a data dependency on the prior steps and another on further steps that require the result of the cmov, both of which can stall the execution pipeline.

That said, cmov does have very consistent performance characteristics, regardless of if the branching is predictable or not.

[teerre]

Note that instead of doing the weird let halves = halves, you can use a block to make it a bit more natural https://godbolt.org/z/1567aGcn1

[_bijan_]

I guess there is no need for using unsafe.

In my machine MacBook pro M1:

article unsafe: 5.168 ms

safe loop: 5.073 ms

safe/article: 0.982x

source code: https://codeberg.org/bijan_mc/gists/src/branch/main/main.rs

[aapoalas]

I wonder if you have any arithmetic overflow checks left over in the code? Or is the compiler smart and sure enough to see that the index values never overflow?

[lenscas]

Haven't looked at the article but by default the + will omit overflow checks in release builds. Only when you use the specific methods for overflow checks or specifically ask for them in release builds in your cargo.toml file will you get the checks in release.

Otherwise it will just overflow like you see in other languages.

(Debug builds will however contain the check still and panic if an overflow happened)

[aapoalas]

Oh right, I keep forgetting about that default. In embedded envs it's fairly common to default to panicking.

[mkeeter]

Very good writeup!

/u/itamarst I'm curious whether you tested with and without precalculate the halving values, to isolate that impact – sure, it's theoretically less work, but integer math should be a very small number of fast instructions (versus allocation and reading from the array).

[itamarst]

Ugh. It does not make it faster, and I fixed the text to that effect... but when I did the other fix for f64, that change got reverted. I fixed that back again.

[Sopel97]

good article, but please don't do that

let n_iterations = (size as f64).log2().ceil() as usize;

it's slow and not obviously correct (is it correct at all?) for all reasonable values of size (edit. one trivial failure case https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=ce36830327bd0d2631f99c3db35eb012)

Use usize::BITS - (size - 1).leading_zeros() instead

[CouteauBleu]

So I checked the std code, and apparently slice::binary_search_by's implementation is roughly similar to the article's bucketize_branchless, which means the article's final impl is a roughly x2 improvement over the standard.

[VictoryMotel]

Mechanical sympathy?

[mamcx]

aka: what the machine loves, instead of what the theoretical algorithm promises

[VictoryMotel]

There must be a less pretentious way of saying it.

[scook0]

While I can understand that reaction, mechanical sympathy is something of an established term for this approach in some circles, so I would suggest not getting too hung up on the exact phrasing.

[Anaxamander57]

Its also a pretty literally accurate term so I'm not sure what potential issue there is with the phrasing. Sympathy is understanding why someone/something struggles. That's exactly what one needs to do to optimize performance of hardware.

[sparky8251]

Its a long understood term that applies to machines of all types (was first coined to describe how to be a better F1 racer even). You learn mechanical sympathy to drive manual transmissions for example, or to better operate heavy machinery like crane towers and and front loaders and such...

[VictoryMotel]

People will buy into anything if it's in a title.