News for hackers. Stuff that matters.

A comment on Beautiful branchless binary search. Parent comment

Re:Beautiful branchless binary search by 2102922286 on Friday April 28, 2023 @03:02AM (#35738345)
This is one area where Profile-Guided Optimization (PGO) can help a lot! With PGO, you run your program on some sample input and it logs info like how many times each side of a branch was taken. From there, you can recompile your code. If the compiler sees that one side of the branch dominates, it can emit code to prioritize that branch. However if the branch counts are approximately even and the branch is hard to predict (n.b. this is technically distinct from having even branch counts), then the compiler can know that the CPU would have trouble predicting the branch, and can emit a cmov instruction instead.
[ Parent | on HN ]
Re:Beautiful branchless binary search by berkut on Friday April 28, 2023 @03:12AM (#35738413)
Yeah, it's mildly annoying there's no (at least to my knowledge?) compiler hint like the '__builtin_expect' ones to tell compilers that the values are very unlikely going to be predictable with enough accuracy to allow the branch predictors to be useful in general, and to use a cmov instead of the traditional branching instructions because of this.
[ Parent | on HN ]
Re:Beautiful branchless binary search by dist1ll on Friday April 28, 2023 @03:21AM (#35738478)
clang has __builtin_unpredictable [0]

[0] https://clang.llvm.org/docs/LanguageExtensions.html#builtin-...

[ Parent | on HN ]
Re:Beautiful branchless binary search by berkut on Friday April 28, 2023 @03:22AM (#35738484)
Oooooh :)

Thanks!

[ Parent | on HN ]
Re:Beautiful branchless binary search by usefulcat on Friday April 28, 2023 @04:57PM (#35747016)
It does, but unfortunately it doesn't always work. For example (note the -march=broadwell option):

https://godbolt.org/z/n1Kz4G7GE

[ Parent | on HN ]
Re:Beautiful branchless binary search by gpderetta on Friday April 28, 2023 @05:11AM (#35739092)
GCC has __builtin_expect_with_probability now. YMMV.
[ Parent | on HN ]
Re:Beautiful branchless binary search by josephg on Friday April 28, 2023 @05:57AM (#35739365)
I’m always surprised by rust’s performance for this reason. The compiler outputs huge binaries, chock full of bounds checks and the like. But performance doesn’t seem to suffer at all from it. On the contrary - I ported some well optimized C to rust and it ran faster.

I can only assume the compiler is marking all the bounds checks as unlikely to fail, and correctly predicted branches must be more or less free in modern CPUs. It’s the only way I can explain it.

[ Parent | on HN ]
Re:Beautiful branchless binary search by eska on Friday April 28, 2023 @07:21AM (#35739914)
The compiler will outright remove bounds checks that are implied by previous bounds checks.

It is a common low level optimization to add a wide boundary check in the beginning to avoid successive smaller bounds checks.

[ Parent | on HN ]
Re:Beautiful branchless binary search by josephg on Friday April 28, 2023 @09:23AM (#35740998)
True. But if binary size is anything to go by, an awful lot of bounds checks still end up in the code.
[ Parent | on HN ]
Re:Beautiful branchless binary search by tomsmeding on Friday April 28, 2023 @09:46AM (#35741226)
Doesn't a rust binary also include a whole lot of standard library? C compilers assume that libc is available, a rust compiler is hardly going to assume that rust's libstd is installed on a random user's machine.
[ Parent | on HN ]
Re:Beautiful branchless binary search by josephg on Saturday April 29, 2023 @07:22AM (#35751925)
Yeah it does, but that’s not enough to explain how large rust programs tend to get. The equivalent C programs, even statically linked, are usually several times smaller than their equivalents in rust.

And the “compile in the standard library” pattern will probably never be changed in rust due to monomorphization. Lots of types in the standard library need to be specialised based on the types of your structs. Even if rust had an ABI for dynamic linking (it doesn’t), structs and functions which take generic type parameters will probably never be able to be loaded from a shared library. Same as C++.

[ Parent | on HN ]
Re:Beautiful branchless binary search by winstonewert on Friday April 28, 2023 @07:11PM (#35748312)
Rust's large file sizes are due to relying on static linking, not particularly the extra bounds checking.
[ Parent | on HN ]
Re:Beautiful branchless binary search by rocqua on Saturday April 29, 2023 @02:55AM (#35750685)
I believe that in release mode Rust will remove bounds checks.
[ Parent | on HN ]
Re:Beautiful branchless binary search by josephg on Saturday April 29, 2023 @03:52AM (#35750975)
No, this is not true. Rust removes integer overflow checks in release mode, but it keeps array bounds checks.

You can see this pretty easily in compiler explorer. This is a simple array lookup compiled in release mode:

https://rust.godbolt.org/z/dhz34KEvj

[ Parent | on HN ]
Re:Beautiful branchless binary search by xmcqdpt2 on Friday April 28, 2023 @09:00AM (#35740748)
If your PGO program ends up in a situation which is the opposite of that you profiled, couldn't you end up with vastly worse performance than a non-optimized program?

I've always felt uncomfortable about PGO for more complex programs because of this.

[ Parent | on HN ]
Re:Beautiful branchless binary search by eklitzke on Friday April 28, 2023 @02:17PM (#35745100)
Right, this is why you should use AutoFDO nowadays not PGO. With AutoFDO you occasionally (e.g. in prod this might be something like record for 1s on average every 300s) record what branches were taken using perf-record from prod binaries, and then feed this back to the compiler.
[ Parent | on HN ]
Re:Beautiful branchless binary search by eklitzke on Friday April 28, 2023 @02:18PM (#35745104)
I commented on this elsewhere as well, but nowadays you should reach first for AutoFDO rather than PGO.
[ Parent | on HN ]