11–20 of 155 posts
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)
Does 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.
let mid = left + size / 2;
[2] https://web.archive.org/web/20230709221353/https://doc.rust-...
[3] https://doc.rust-lang.org/src/core/slice/mod.rs.html#2779
Interesting 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…
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.
>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.
I 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% probabilit…
Why you have to be careful choosing realistic input data if you are microbenchmarking at this level for a real purpose.
>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.
I 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% probabilit…
>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.
Not sure how consistent this is across architectures, and how useful it still is. But at least it used to be a thing
Interesting 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…
Does 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.
Looking 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-... [2] https://web.archive.org/web/20230709221353/https://doc.rust-... [3] https://doc.rust-lang.org/src/core/slice/mod.rs.html#2779
Thank you!
Earlier quoted context omitted.
I 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% probabilit…
clang has one: https://clang.llvm.org/docs/LanguageExtensions.html#builtin-...
Earlier quoted context omitted.
Looking 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-... [2] https://web.archive.org/web/20230709221353/https://doc.rust-... [3] https://doc.rust-lang.org/src/core/slice/mod.rs.html#2779
Alright, and as a versioned link that'll be: https://github.com/rust-lang/rust/blob/7d8386f05cedf33c7475c... Thank you!
https://doc.rust-lang.org/1.71.1/src/core/slice/mod.rs.html#...