Hacker News Reader

Comment by kllrnohj | Hacker News Reader

Can you point to any such bounds check in C that an optimizer cannot eliminate but it can eliminate the equivalent one in Rust?

I'm sure it's possible to construct such a thing, but I cannot imagine it ever being common enough to show up on any sort of head to head comparison.

View on HN

I would guess all the aliasing stuff will get you. In C it's very difficult for the compiler to know whether two pointers are aliased, if we change X maybe Y changes too (because actually X and Y were the same). In Rust if we can write to it then it isn't aliased, and if we can't write to it then nobody can change it, thus changing X definitely can't change Y and the emitted machine code is sometimes simpler as a result, doing what you naively expected rather than what the C needs to do just in case you're crazy and there is an alias.

Now, in modern C you can say you don't have aliasing, but you're probably wrong and so there's a high risk when you do that you now get "impossible" bugs because you swore to the optimiser that if X changes, Y is unaffected, then created a situation where that wasn't true and now your program has no defined meaning, which is going to be tricky to debug. So, on the whole C programmers do not use this, indeed in places like the Linux kernel they even turn off the C standard's very minimal aliasing rules (which forbid aliasing objects of different types), they just don't trust themselves.

But the compiler doesn't need to care in that case because it's not bounds checking those pointers in the first place in C. So that's not going to give you slow C code from bounds checking that the optimizer failed to eliminate.

Like yeah there's aliasing changes, but in "idiomatic" C/C++ how is that getting you bounds checking that's not being optimized away fairly consistently?

Wait, previously you were talking about bounds checks which can't be optimised out, now you seem to be saying in C you wouldn't bother writing any bounds checks, which is a quite different claim.

I think what they're saying is that C compilers don't care about aliasing here because it's not actually bounds checking the pointers, it's just a numeric comparison between two random arguments. It's much easier for an optimizing compiler to eliminate a duplicated boolean check between two numbers this way because passing numbers from one function to the next has no aliasing concerns.

This is a misunderstanding of what's useful about aliasing information. A lot of C code can't be autovectorized because it can't tell that accesses to two arrays don't alias, for example. Similarly it often can't reorder / eliminate redundant updates to arrays because it can't tell they're not aliased. These aren't related to bounds checking specifically but they are things that can improve performance in Rust over C (theoretically, anyway; in practice LLVM is still very much tuned for C so it doesn't take advantage of a lot of this stuff yet, but it likely will in the future).

there's almost no bounds checking in rust code before the optimizer even looks at it because we use iterators and not goofy manually indexed for loops that are begging you to make a typo that crashes your code :)

Yeah but idiomatic modern C++ is also using iterators and even before that there's no bounds checking to eliminate in the first place since operator[] is unchecked so the optimizer can't be struggling to eliminate it since it's not there.

The question isn't "does Rust have bad bounds checking optimizations" but rather "what is this mythical heavily-bounds-checked C code that the compiler can't optimize away?"

No the claim is always that Rust "must" be slower than C/C++ because it has pervasive bounds checking for array indexing.

Then people insist on wanting to replace every x[i] in prod with x.get_unchecked(i) only to learn that, not only was that indexing not slowing the code down (the branch is perfectly predictable in a correct program!), but actually any difference is so in the noise that the random perturbation is worse (or that the asserts were actually adding extra facts for more profitable optimizations in llvm).

There is definitely specific hot loops with weird access patterns where it can be high impact but those are the exception, not the rule, as the Android team demonstrated.

Trivially, anything using the Iterator trait.

I don't know that I've ever actually manually indexed an array over years of using Rust.

In the HPC / offline graphics / simulation world, there's lots of things like sparse arrays / grids, where you index into compacted grids and iterators wouldn't be that practical in that scenario (i.e. one single item, although for things like filtering with surrounding cells they can still be useful sometimes), and bounds checks do make a bit of a difference there (it's definitely measureable above the noise threshold), and due to the random nature of the data, the branch predictors don't help avoid the overhead.

Sure, I know there's paradigms where manual indexing is important. GP asked for an example where bounds-checking could be eliminated in Rust, so I gave the first one I thought of.

I don't think your answer is relevant to the question:

> Can you point to any such bounds check in C

Reply on news.ycombinator.com