6 ms·
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 time
by 2102922286 3y ago
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.
- josephg 3y agoI’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.
- eska 3y agoThe 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.
- josephg 3y agoTrue. But if binary size is anything to go by, an awful lot of bounds checks still end up in the code.
- tomsmeding 3y agoDoesn'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.
- josephg 3y agoYeah 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++.
- winstonewert 3y agoRust's large file sizes are due to relying on static linking, not particularly the extra bounds checking.
- rocqua 3y agoI believe that in release mode Rust will remove bounds checks.
- josephg 3y agoNo, 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 https://rust.godbolt.org/z/dhz34KEvj
- xmcqdpt2 3y agoIf 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.
- eklitzke 3y agoRight, 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.
- eklitzke 3y agoI commented on this elsewhere as well, but nowadays you should reach first for AutoFDO rather than PGO.
- berkut 3y agoYeah, 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.