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.
True. But if binary size is anything to go by, an awful lot of bounds checks still end up in the code.
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.
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++.
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.
I believe that in release mode Rust will remove bounds checks.
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:
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.