The Zig stdlib does not call out to C++ for binary search. The binary search is currently here: https://github.com/ziglang/zig/blob/b835fd90cef1447904d3b009... (edit: fixed link to not decay, thanks)
Thanks, updated the footnote.
Fastest branchless binary search
131–140 of 155 posts
Re: Fastest branchless binary search
#132On 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 c…
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.
Re: Fastest branchless binary search
#133I 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.
Re: Fastest branchless binary search
#134This 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.
For 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).
Re: Fastest branchless binary search
#135Earlier quoted context omitted.
It looks like CompCert explicitly does not attempt to prevent UB from resulting in unpredictable behavior; all it guarantees is that "the observable behavior of [the compiled code] C improves on one of the allowed observable behaviors of [the source program] S ", where "improving on" allows for arbitrary behavior on UB [0]: > Third, the compiler is allowed to improve the behavior of the source program. Here, to impro…
You have to scroll down a bit, but see here[1]. Also searching [site:regehr.org compcert] will find more. CompCert C makes it impossible to reproduce at least some UB bugs: For CompCert, the high-level correctness theorems I proved are all of the first kind above: if the source program goes wrong, nothing is guaranteed about the behavior of the compiled code. It happens, however, that the stepwise simulation lemmas I…
Apart from compiler bugs, this issue with "time-traveling UB" shouldn't really occur in practice with any side effects other than volatile accesses. As noted by Martin Uecker [0],
> In portable C code I/O is performed using function calls of the standard library. A compiler can generally not assume that a function returns to the caller, because the function could call ‘exit’, ‘abort’, ‘longjmp’, or enter an infinite loop. For this reason, it is never allowed for a compiler to use any information derived from an operation with potential UB that comes after a function call in a way that could affect observable behavior before the function call. Consequently, observable behavior that is accessed via function calls (i.e. all except volatile accesses) can not be affected by time-traveling optimizations even when using the abstract interpretation. In principle, a compiler could use special knowledge about C library functions and use the fact those functions always return to the caller, but we are not aware of any compiler which does this (and it hardly seems worthwhile).
I believe LLVM has a "mustreturn" attribute expressing this, but as noted, no standard C library messes with any such attributes for functions that cause observable behavior.
So time-traveling UB really only affects programs which use volatile accesses for MMIO, and it might eventually be banned entirely from the C standard if the linked proposal N3128 goes through. I'd say that even "some C bugs" is a overstatement outside of embedded programming, given the rarity of MMIO in a hosted environment.
[0] https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3128.pdf
Re: Fastest branchless binary search
#136How can you call it branchless if it has "while (length > 0) {"
This is literally addressed in the article: More branchless, more better? Short answer: no. This section can be skipped but here’s the long answer: For n elements where 2k 0) loop. So it’s possible to write a “fully branchless” version that doesn’t have the length check by using a switch with intentional fall-through. size_t length = last - first; size_t rem; switch(std::bit_width(length)) { case 64: rem = length % 2…
TBH I had to read that part two times before realizing that it was describing an an unrolled loop.
Re: Fastest branchless binary search
#137Earlier quoted context omitted.
> 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…
I have little experience in hardware related performance optimizations, so excuse me if some of the things you wrote went over my head. But this sentence: > 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. Are you implying that in JIT compiled languages I c…
JITs can do a lot of things but in practice its a better mental model to just assume that the equivalent AOT code is faster and the JIT is merely recouping performance lost to the inefficiencies of interpretation or weird semantics (javascript being the implication)
Re: Fastest branchless binary search
#138Interesting 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…
> 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...
Re: Fastest branchless binary search
#139Earlier quoted context omitted.
Full array in L1 is not a typical scenario for binary search. Binary search is usually for large data sets, that are in DRAM.
Binary 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.
Sounds like we're just reinventing B-trees.
Re: Fastest branchless binary search
#140Earlier quoted context omitted.
You'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…
You do additional comparisons at each recursion depth, but you have a shallower recursion depth though. I think you break-even already at 4-way search.
I think that only helps if you assume exactly 1.5 comparisons per level with a branch predictor, and I think that will be hard to hit: you basically need the comparison function to be very short to have that (shorter than the mispredict penalty). Then, you are doing 3 comparisons per two levels vs 3 comparisons for 2 levels. If you were to extend this logic to do 3 levels at a time, you would be doing 7 comparisons to do the same amount of work that the branch predictor does in expected <4.5 comparisons.