11 ms·
Fastest branchless binary search
- foldr 3y ago>gcc has __builtin_expect_with_probability(cond, 0, 0.5) but it does nothing (tested v10). ↩ I wonder what could possibly be the use of this builtin. Branch prediction varies enough between different processors that it seems unlikely that anything useful could be done with a fine-grained probability estimate.
- twoodfin 3y agoPresumably it’s not about matching the dynamic branch prediction estimate but rather exploiting static (or profile-provided) information to assist other optimizations. Inlining seems like a natural application: Inlining is perhaps the most critical optimization to get right, and getting it right is a complex balance of frequency of use vs. added code bloat and associated further optimization cost. Having more than one bit of branch-likelihood as input to these decisions could easily be helpful.
- foldr 3y agoGood point. That's the only plausible explanation in this thread, I think. However, if you're at the level of performance tuning where you want to optimize inlining beyond the compiler defaults, I would have thought that it would make more sense to just experiment with forcing certain functions to be inlined or not.
- gpderetta 3y agoI think it is used for code layout: typically you want to make the most often taken branch as fallthrough as it can be slightly faster even when perfectly predicted. I also tried (and failed) to use expect with probability to generate a cmov, but in retrospect it is obvious: the parameter is not the prediction probability, but the taken/not-taken probability, and even a branch that goes either way with 50% probability can still be predicted perfectly (for example a branch that switches every other iteration), so the parameter can't be used to decide between predication and prediction. edit: what we really need is an [[unpredictable]] attribute.
- twoodfin 3y agoIndeed: A branch taken 50% of the time can be readily predicted 100% of the time if it follows a pattern the CPU can infer. Why you have to be careful choosing realistic input data if you are microbenchmarking at this level for a real purpose.
- pixelesque 3y agoclang has one: https://clang.llvm.org/docs/LanguageExtensions.html#builtin-unpredictable https://clang.llvm.org/docs/LanguageExtensions.html#builtin-...
- ot 3y agoWhich also does not affect cmov conversion. Every time this comes up I bring up this long-standing LLVM bug: https://bugs.llvm.org/show_bug.cgi?id=40027 https://bugs.llvm.org/show_bug.cgi?id=40027
- dzaima 3y ago__builtin_unpredictable is gonna be fixed in LLVM/clang 17: https://github.com/llvm/llvm-project/commit/09515f2c20111628ce81ad5f40e12e5f6af5ed2f https://github.com/llvm/llvm-project/commit/09515f2c20111628... (also, bugs.llvm.org is old; the more up-to-date (but still open) issue is https://github.com/llvm/llvm-project/issues/39374 https://github.com/llvm/llvm-project/issues/39374)
- ot 3y agoAmazing, finally!!!
- foldr 3y ago>typically you want to make the most often taken branch as fallthrough as it can be slightly faster even when perfectly predicted. Sure, but that application doesn't require a fine-grained probability estimate.
- wongarsu 3y agoAt least when I last read it a couple years ago, Intel's optimization manual recommends certain code layouts. For example in the absence of better information a conditional jump backwards would be predicted as true (because that's what loops look like) while a jump forward is seen as less likely to happen (error conditions and else branches look like that). Not sure how consistent this is across architectures, and how useful it still is. But at least it used to be a thing
- kragen 3y agopretty common but not, as i thought, universal since stretch https://en.wikipedia.org/wiki/Branch_predictor#Static_branch_prediction https://en.wikipedia.org/wiki/Branch_predictor#Static_branch... but the only simpler approach is 'predict not taken' which in a sense is what a cortex-m0 does
- Pannoniae 3y agoRead https://en.algorithmica.org/hpc/pipelining/branching/ https://en.algorithmica.org/hpc/pipelining/branching/ and the following chapter. TL;DR: you can generate different, and more efficient code if you know how much it is going to be mispredicted.
- gpderetta 3y agoThe built-in doesn't provide misprediction information to the compiler.
- foldr 3y agoNothing in that link shows how a compiler could make use of a fine-grained probability estimate in a practical way to guide optimizations. I'm perfectly aware of the general concept of branch prediction and the annotations that certain architectures have in their instruction sets.
- bjourne 3y agoThere are ARM processors where bits in the branch instructions encode whether they should be predicted as taken or not. So on such architectures such hints can be useful. On x86-64, however, they are afaik completely useless (from an optimization perspective).
- shmageggy 3y ago> If only there was a clean fast bare-metal language to write all this in.. The author includes a footnotes for "BUT RUST.." and "BUT ZIG..", but how about Nim? Looks like there is a native library implementation of `lowerBound` https://github.com/nim-lang/Nim/blob/version-2-0/lib/pure/algorithm.nim#L221 https://github.com/nim-lang/Nim/blob/version-2-0/lib/pure/al... Yes, it's not a "bare-metal" language, but it compiles to one (or two), so it would be interesting to see what it compiles to here. Also, what's wrong with C?
- matklad 3y ago> BUT ZIG.. There’s no binary search implementation in Zig that I could find, rather it calls to C++. Zig’s binary search is here, it’s an unoptimized textbook version: https://github.com/ziglang/zig/blob/b835fd90cef1447904d3b009c9662ba4c0ea77d4/lib/std/sort.zig#L400 https://github.com/ziglang/zig/blob/b835fd90cef1447904d3b009... At TigerBeetle, we have our own branchless implementation here: https://github.com/tigerbeetle/tigerbeetle/blob/e996abcf71540747bd57fa2ffb1814ee3e2acff8/src/lsm/binary_search.zig#L53 https://github.com/tigerbeetle/tigerbeetle/blob/e996abcf7154...
- josephg 3y agoRust's binary search is here. Also a pretty textbook version of the function: https://github.com/rust-lang/rust/blob/4d7a80d48697171ed151c4667b74fc7d784c1836/library/core/src/slice/mod.rs#L2769-L2809 https://github.com/rust-lang/rust/blob/4d7a80d48697171ed151c... How much faster is the branchless version in practice? I make heavy use of binary search in some code I maintain, and I wonder if it would make much of a difference to switch to a more efficient version of the function.
- abhishekjha 3y agoI don't know much about Rust data types or Rust in general but does it not have any integer overflow? I see (left+right)/2. Is it like python with unbounded precision?
- deleted 3y ago
- anonymoushn 3y agoThe Zig stdlib does not call out to C++ for binary search. The binary search is currently here: https://github.com/ziglang/zig/blob/b835fd90cef1447904d3b009c9662ba4c0ea77d4/lib/std/sort.zig#L400 https://github.com/ziglang/zig/blob/b835fd90cef1447904d3b009... (edit: fixed link to not decay, thanks)
- djoldman 3y agoInteresting that the results don't hold up with a more complicated comp comparison function: > For somewhat realistic scenarios of binary searching with a slower comp() function I’ve thought of searching through ids, phone numbers, accounts and keywords. I’ve thus settled on testing searching 8-byte strings. > ... > In this case std::lower_bound is very slightly but consistently faster than sb_lower_bound. To always get the best performance it is possible for libraries to use sb_lower_bound whenever directly working on primitive types and std::lower_bound otherwise. I would like to see the analysis here.
- twoodfin 3y agoI can’t find any assertion in the post about the content of any of the input data sets or search keys, other than that they’re “unpredictable”. I assume purely random, but if these 8-byte strings were anything but pure information, modern branch predictors can sniff their way to better performance than cmov pretty easily.
- pclmulqdq 3y agoI believe this happens because branch prediction lets you pipeline multiple simultaneous comparisons, and rewind whenever the branch predictor is wrong (about half the time for truly random data and inputs). The CMOV approach blocks after each comparison function due to the data dependency. On average, you're doing two comparisons at a time with branches, and one with CMOV, so when comparison time is greater than branch prediction penalty, you would expect a crossover to occur.
- gpderetta 3y agoSwitching to an N-way search (for N>2) could help extract the lost parallelism. At the cost of touching more cachelines though, so it is not necessarily a win.
- pclmulqdq 3y agoYou're also wasting a lot of work doing that. If you go two levels deep, you now do 2 comparisons per iteration (caching the result from the previous level), but you are guaranteed to waste one of those. The CPU with branch predictor is doing about 1.5 comparisons per iteration (worst case) thanks to the 50% mispredict rate, although this depends a lot on how long the comparison takes: a very long comparison function will converge to 1 comparison per iteration. Only if you replicate the speculation for yourself - which will necessarily have to be a lot worse than a CPU branch predictor to be fast and branchless - do you have any hope of an efficiency gain.
- LoganDark 3y agoDoes anyone know where the "BUT RUST" link was supposed to lead? It seems to be already out of date due to being unversioned, I can't tell whether it's supposed to lead to the middle of the `starts_with` doc comment or not.
- quietbritishjim 3y agoLooking at the archive.org captures just before [1] and just after [2] the article was published, it looks like it was meant to be this line of code, now on line 2779 [3]: let mid = left + size / 2; [1] https://web.archive.org/web/20230602210213/https://doc.rust-lang.org/src/core/slice/mod.rs.html https://web.archive.org/web/20230602210213/https://doc.rust-... [2] https://web.archive.org/web/20230709221353/https://doc.rust-lang.org/src/core/slice/mod.rs.html https://web.archive.org/web/20230709221353/https://doc.rust-... [3] https://doc.rust-lang.org/src/core/slice/mod.rs.html#2779 https://doc.rust-lang.org/src/core/slice/mod.rs.html#2779
- LoganDark 3y agoAlright, and as a versioned link that'll be: https://github.com/rust-lang/rust/blob/7d8386f05cedf33c7475cbb44f84178df5919202/library/core/src/slice/mod.rs#L2781 https://github.com/rust-lang/rust/blob/7d8386f05cedf33c7475c... Thank you!
- veber-alex 3y agoYou can get versioned link directly into rustdoc: https://doc.rust-lang.org/1.71.1/src/core/slice/mod.rs.html#2779 https://doc.rust-lang.org/1.71.1/src/core/slice/mod.rs.html#...
- LoganDark 3y agoI couldn't find any direct references to this anywhere, believe me I spent a long 30 minutes looking... >.< But thank you anyway <3
- 3y ago
- deleted 3y ago[deleted]
- hajrice 3y agoI wish all blog posts started the way his does: "You’re a busy person so I’ll first jump right to it. Here it is, the fastest general (and simple) binary search C++ implementation:"
- w0mbat 3y agoIs that still lower_bound? Maybe I am misreading the code but it looks like this returns any match, not the earliest match (when there are dupes). It’s common to have multiple matches even in a unique list if the comparison function is say looking for a certain string prefix to do autocomplete, but we want the earliest in the list.
- klysm 3y agoI guess it’s good to have the option of not caring if you want even more speed
- deleted 3y ago[deleted]
- shultays 3y agoMy lower_bound is a bit better then template <class ForwardIt, class T, class Compare> constexpr ForwardIt super_optimized_lower_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp) { return first; } It doesn't really work like for some cases std::lower_bound but it is super fast
- commandlinefan 3y agoOr, less contentiously - if you know you don't care/don't need to disambiguate dups, look how much efficiency you're losing on a case that isn't important. The most common argument against optimization is "just use the existing code", but the "existing code" _always_ attempts to handle special edge cases that probably don't apply in your case. We programmers waste a lot of end-user time saving a bit of programmer time.
- jfk13 3y agoOn the other hand, assuming it's OK to ignore the special edge cases (or not even thinking of them) can come back to bite you (or your users) when eventually one of them does show up in a situation you didn't anticipate.
- andyg_blog 3y agoThis is not a valid drop in replacement for lower_bound. Accessing iterators as front[index] is only for random access iterators like vector has. The author may have realized this if they benchmarked on other containers.A forward iterator must be advanced and then dereferenced.
- fn-mote 3y agoCan you do binary search without random access? I would not expect so. Am I missing a point that someone could explain?
- andyg_blog 3y agoThe C++ standard measures the time complexity of lower_bound and binary_search by the number of comparisons performed. So yes, it's possible on e.g., a linked list like std::list (by this definition)
- kccqzy 3y agoObserve that you can restrict your code to only call std::advance on the iterator. So definitely you could do binary search without random access, and you would actually iterate over all elements, but you just skip the comparison function for the majority of elements.
- commonlisp94 3y agoGood point. I don't think anyone actually uses it for containers that only support forward iteration. But the author did declare the signature with ForwardIterator.
- mhdm 3y agoFor a proper/sane forward iterator, front[index] is the same thing as *(front + index) and front + index achieves the same as std::advance(front, index) (just not in place). Or are you pointing out how first[length] and first += length + rem would technically result in advancing a forward iterator through to first + length twice? (Trivially fixed with a middle = first + length temporary variable btw).
- jezze 3y agoWouldnt it be faster to do length & 1 instead of length % 2 and also length >> 1 instead of length / 2? But maybe the compiler does this behind the scenes?
- edg-l 3y agoCheck out https://en.algorithmica.org/hpc/data-structures/binary-search/ https://en.algorithmica.org/hpc/data-structures/binary-searc...
- funkychicken 3y agoIt looks like the unpredictable attribute now influences the cmov conversion pass (as of June 1st, so probably in clang 17/18) https://reviews.llvm.org/D118118 https://reviews.llvm.org/D118118
- sixthDot 3y agohttps://probablydance.com/2023/04/27/beautiful-branchless-binary-search/ https://probablydance.com/2023/04/27/beautiful-branchless-bi...
- commonlisp94 3y agolower_bound and upper_bound are typically implemented in terms of partition_point, which is much more general than this version of lower_bound taking an element.
- Aardwolf 3y agoEven more reason to use this if you don't need the more general case and its associated performance cost
- commonlisp94 3y agoPartition point is even simpler and can be optimized the same way. > if you don't need the more general case and its associated performance cost In C++ the "more general case" typically doesn't have a performance cost.
- victor106 3y agoAnyone knows if Java already does this optimization?
- ectospheno 3y agoEvery post like this makes me update my junior engineer watchlist. Then I have to go patiently explain why mucking about in the code to save one instruction because you read a blog post is a horrible idea. Easily half of all silly junior code is pointless optimization. Having said that, I did enjoy the post.
- sph 3y agoWhat kind of junior engineers are you hiring that prematurely rewrite a hot loop to use branchless assembly logic? The junior employees I have had to deal with tended to build towering abstractions that no one really needed, rather than optimising hot loops.
- ectospheno 3y agoYes, I would say that is the other half.
- sesuximo 3y agoI’m too lazy to try it, but putting __builtin_unpredictable around the implementation of comp might make std::lower_bound less branchy
- JonChesterfield 3y agoBranches on a comparison function, doesn't count it as simple functions end up as a conditional move. Branches in a loop back edge, doesn't count it as there's a branch predictor. I was hoping for a binary search without branches in it. Not really what we got.
- 3cats-in-a-coat 3y agoEvery time I see people trying to eliminate branches, I wonder, do we realize that having long pipelines where a branch misprediction stalls the pipeline is not actually a necessary part of architecture? The pipeline is long because we do lots of analysis and translation on the fly, just in time, which could easily be done in most cases ahead of time, as it's not a very stateful algorithm. This is how Transmeta Crusoe CPUs worked. Imagine NOT caring that you have a branch. After all, if you think about it, all operations are branches. Down to bitwise operations and summing two numbers. It's branching in the ALU, carry bits and what not. You can't compute absolutely anything without looking at the state of one or more bits, and making a decision that changes the outcome. But the reason those branches don't hurt performance is that they're not branches on the main pipeline. These local branches have a very short (or non-existent) "pipeline". And the main pipeline is therefore not affected, despite the actual state of the system is.
- robertlagrant 3y ago> After all, if you think about it, all operations are branches Isn't this definition the crux of it? If you redefine everything as a Branch™, even things that are not branches, then you can definitely precompute some Branch™es. But the sort of non-Branch™ branch elimination is talking about actually branching computation routes in code due to an if/else statement or similar, is it not? That would still be useful to do in your world of Branch™es, just only the Branch™es that try and compute the results of more than one future at the same time (i.e. branches).
- deleted 3y ago[deleted]
- dragontamer 3y ago> The pipeline is long because we do lots of analysis and translation on the fly, just in time, which could easily be done in most cases ahead of time, as it's not a very stateful algorithm. You're going down the wrong path, again, as Intel did with Itanium. We have pipelines because CPUs are performing Tomasulo's algorithm at runtime, because there are 10 pipelines in practice (for Intel systems), and all can be run in parallel. Multiply can be issued on pipeline0, pipeline1, or pipeline5. If there are 3 multiply instructions, all three pipelines (p0, p1, and p5) all get issued a multiply on _THIS_ clock tick. ---------- The analysis must be dynamic because instructions such as "mov" can take a variable amount of time: loading data from L1 cache is 4-clock ticks, L2 cache is 40 clock ticks, L3 cache is ~150 clock ticks, and RAM is 400+ clock ticks. That means a "lazy" strategy, where you analyze the state of the pipeline "as late as possible" before making a decision wins out. If you do pre-analysis (ie: what Intel's compiler was supposed to do with Itanium), you pretty much lose out on all variable-time instructions (ex: cache vs RAM). If you know for certain that you have no memory-operations, then you probably should use a GPU instead of a CPU. --------- theLoop: mov ebx, eax[ecx] ; y = array[x] add ebx, edx ; y += z add ecx, 4 cmp ecx, jnz theLoop How long should you schedule the "add" instruction in the above assembly code? If you got a dynamic system just analyzing your pipelines and "lazily" issuing the instructions, you "perform it when its ready" (ie: after the mov instruction is complete, as you need ebx / variable-y to have been finished reading from RAM before progressing). "add ecx, 4" can actually be done right now in parallel. You split ecx into two registers (ecx-old and ecx-new). You issue "mov ebx, eax[ecx-old]", and then you can execute future instructions with ecx-new. If the next loop is branch predicted (as would be the case in binary search, since you almost always loop), the pipeline/branch prediction stuff works together and you can execute mov ebx, eax[ecx0], mov ebx, eax[ecx1], mov ebx, eax[ecx2], mov ebx, eax[ecx3]... all in parallel (!!!!), as ecx3 gets branch predicted and multiple loops start running in parallel.. Its not hard, its not very difficult analysis, its low power. Everyone does this parallel computation now. If you go static / compiled ahead-of-time, you can't do this kind of thing anymore. So you lose out in speed compared to regular CPUs that have OoO analysis going on. ---------- Furthermore, most code with branches can seemingly be replaced with branchless code (ex: cmov instructions, min instruction, max instruction, etc. etc.) So instead of magic compilers trying to solve an unsolvable problem (how do you schedule memory load/stores to keep the processor busy even though you don't know how long any memory operation takes...)... you write a magic compiler that solves a very easy to solve problem. (IE: convert the branchy-if statement into a branchless max or branchless cmov instruction instead). -------- EDIT: I added "theLoop:" to the assembly above, because I realized that "branches" can be beneficial in the face of OoO / Tomasulo's algorithm. "Executing future loops" before the 1st loop is done is very beneficial.
- postalrat 3y agoHow can you call it branchless if it has "while (length > 0) {"
- dehrmann 3y agoI took a stab at the same problem a while ago. Since the upper bound of iterations is based on the input length, if you write your search in a way that extra iterations don't change the result, you can use a switch fallthrough to "unroll" the loop and not have to branch. https://github.com/ehrmann/branchless-binary-search/blob/master/src/bbsearch.c https://github.com/ehrmann/branchless-binary-search/blob/mas...
- fsckboy 3y agothe article covers that right at the top: “branchless” because the if compiles down to a conditional move instruction rather than a branch/conditional jump.
- Const-me 3y agoThat particular branch is well-predicted for long arrays. You probably only gonna have a single misprediction for the complete binary search function, the performance consequence of that branch is negligible. People (and compilers, too) don’t write branchless code just for the sake of it, they do because it helps with performance.
- kragen 3y agosometimes branchless code also stops timing side channel attacks, but it's not enough by itself
- einpoklum 3y agoBecause that's a branch that's "always" taken, except for once - which, speed-wise, is very close to always taken, i.e. not a branch. The author counts the branching inside the loop, which is often taken and often not taken.
- postalrat 3y ago
- tgv 3y agoIf the compiler doesn't optimize the if(cmp(...)) first += length + rem; perhaps a sign operation could be used when cmp returns a number. Something along the lines of: first += (length + rem) * ((sign(cmp(...)) + 1) / 2) Has anyone tried that? DDG isn't very helpful.
- WinLychee 3y agoOther fast binary searches https://github.com/sslotin/amh-code/tree/main/binsearch https://github.com/sslotin/amh-code/tree/main/binsearch
- notorandit 3y agoBranchless? You need at least 1 branch to exit the loop.
- ant6n 3y agoDo you tho? You could unroll the loop ceil(log2(MAX_SIZE)) times.
- amluto 3y agoOh, C++, the language where templates are extremely powerful but their usability is so poor that code like this is kind of idiomatic and even compiles: template <class ForwardIt, class T, class Compare> constexpr ForwardIt sb_lower_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp) { auto length = last - first; This looks generic, it compiles by itself, it contains a fancy word “ForwardIt”, and it works if you try it with a vector or an array. But you can’t actually subtract forward iterators, and binary searching a range of forward iterators is quite silly. Rust would have required using the correct trait. Maybe C++ will improve the situation in the long run.
- bjourne 3y agoOn my Cascade Lake processor "-mllvm -x86-cmov-converter=false" almost halves the performance of the binary search: | Benchmark | gcc | clang | clang -cmov | |-----------|------|-------|-------------| | slow u32 | 23.4 | 46.7 | 45.8 | | fast u32 | 18.1 | 19.8 | 31.4 | The numbers are nanoseconds/bsearch on a 100mb uint32 array. Seem to me that clang (15.0.7) is just much worse at optimizing this particular piece of code than gcc (13.2.1). You can see the assembly here https://godbolt.org/z/cbx5Kdjs6 https://godbolt.org/z/cbx5Kdjs6. The gcc assembly looks way cleaner to me.
- mhdm 3y agoThen you'll want to look at https://mhdm.dev/posts/sb_lower_bound/#prefetching https://mhdm.dev/posts/sb_lower_bound/#prefetching 100mb is large enough that the branchy version turns out to have a slight advantage, more due to quirks of x86 (speculative execution) rather than being better.
- bjourne 3y agoSo I spent too much time benchmarking: | Entries | gcc | gcc+pref. | clang | clang+pref. | clang -cmov | clang -cmov+pref. | |---------|-----|-----------|-------|-------------|-------------|-------------------| | 0.5 | 210 | 88 | 213 | 191 | 109 | 93 | | 1.0 | 231 | 107 | 235 | 211 | 134 | 112 | | 2.0 | 289 | 168 | 306 | 275 | 231 | 179 | | 5.0 | 369 | 231 | 389 | 343 | 338 | 239 | | 10 | 413 | 268 | 437 | 384 | 410 | 276 | | 25 | 469 | 311 | 490 | 435 | 506 | 318 | | 50 | 515 | 346 | 537 | 478 | 586 | 356 | | 100 | 564 | 387 | 588 | 522 | 670 | 399 | Entries are in millions and times in ns per bsearch call. Prefetching does all the difference, but perhaps not for the right reason. On my machine (broadwell) the two prefetches that you suggested makes gcc emit the cmovb that clang with -cmov uses. The second one is enough to make it prefer cmovb but not the first one. Maybe a hand-hacked assembly loop based on the code gcc emits but without the prefetches would run even faster.
- alain94040 3y agoI don't get it. The problem with binary search and branches is not the branches themselves, it's the fact that until you have done the comparison, you don't know which memory location in the array to fetch next. It doesn't matter if you use branches or anything else, the question is what do you want the processor to do? There is a data dependency: until I read the middle index, I can't tell if I want to search the data in the upper section or the lower section. I can speculate and issue reads to both. That would fix the dependency, but create more memory traffic. Is this the right trade-off? What do you want? Removing branches is not it.
- returningfory2 3y agoIf the array is fully in L1 cache, isn't the cost of the branch mis-predict much greater than the memory fetches?
- alain94040 3y agoFull array in L1 is not a typical scenario for binary search. Binary search is usually for large data sets, that are in DRAM.
- thefifthsetpin 3y agoBinary search reduces the search space exponentially as it proceeds, so actually quite a lot of the total comparisons can hit L1d cache. (Maybe half of them for a ~250GB dataset.) Of course, you could keep a cacheable partial index of your huge dataset to accelerate the early part of your search as well.
- Bognar 3y agoSounds like we're just reinventing B-trees.
- thefifthsetpin 3y agoYep. I considered phrasing my answer that way.
- 1letterunixname 3y agoIt's not branchless if there are are any Jcc other than JMP because that's an opportunity for a branch prediction miss and a pipeline stall.
- MrYellowP 3y agoI am confused. > Same function interface as std::lower_bound, but 2x faster, and shorter. “branchless” because the if compiles down to a conditional move instruction rather than a branch/conditional jump. Assembly programmers did "fastest branchless binary searches" using cmov decades ago and we didn't need to think about the compiler at all. I know, because I was one of them. Optimizing branches away was and still is a nice pastime. This is not new, or original, and I don't understand what's noteworthy about it. "Elitist", you say? Well ... yeah! At least I know what I'm doing, unlike people who solely rely on and blindly trust the compiler to do their work for them.
- fl0ki 3y agoPro tip, the footer link https://doc.rust-lang.org/src/core/slice/mod.rs.html#2520 https://doc.rust-lang.org/src/core/slice/mod.rs.html#2520 is not a permalink because it doesn't include a commit ID. It looks like it's already linking to the wrong thing now (and the article is only two months old), and I don't know what the right thing was meant to be. I suggest using GitHub permalinks in future, pinned to specific commits.
- up2isomorphism 3y agoLearn assembly: you will get these “tricks” automatically. To be honest it is way more efficient to read these long posts.