Fastest Branchless Binary Search

• sb_lower_bound

  10 17 3.9 C++

  Fastest Branchless Binary Search

  Then you'll want to look at 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.

• SaaSHub

  www.saashub.com featured

  SaaSHub - Software Alternatives and Reviews. SaaSHub helps you find the best software and product alternatives

  

• zig

  852 36,205 10.0 Zig

  General-purpose programming language and toolchain for maintaining robust, optimal, and reusable software.

  

  The Zig stdlib does not call out to C++ for binary search. The binary search is currently here: https://github.com/ziglang/zig/blob/master/lib/std/sort.zig#...

• rust

  2,775 100,283 10.0 Rust

  Empowering everyone to build reliable and efficient software.

  

  Integer overflows cause panics in both debug and release mode.

  See line: https://github.com/rust-lang/rust/blob/4d7a80d48697171ed151c...

  Panics require bounds checking, but in this case I can imagine the compiler can rewrite to something like ```(left/2) + (right/2) + (right & left & 1)```, ensuring that it will never overflow. This statement would be an obvious target for improvement.

• Nim

  355 16,707 9.9 Nim

  Nim is a statically typed compiled systems programming language. It combines successful concepts from mature languages like Python, Ada and Modula. Its design focuses on efficiency, expressiveness, and elegance (in that order of priority).

  

  > 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/al...

• tigerbeetle

  62 11,204 9.9 Zig

  The financial transactions database designed for mission critical safety and performance.

  

• branchless-binary-search

  2 10 10.0 C

  Binary search implementation that avoids branch instructions

  I 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/mas...

• amh-code

  8 685 10.0 Jupyter Notebook

  Complete implementations from "Algorithms for Modern Hardware"

  Other fast binary searches https://github.com/sslotin/amh-code/tree/main/binsearch

• ThinkingInSimd

  1 3 2.3 C++

  An essay comparing performance implications of ignoring AVX acceleration

  > 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 will say that if this is the case, there are probably much better versions of binary search out there for primitive types. I made one just screwing around with SIMD that's 3x faster than std::lower_bound until becoming memory bound:

  https://github.com/matthewkolbe/ThinkingInSimd/tree/main/alg...

Suggest a related project