3 ms·
> The key thing with bounds checks is to hoist them out of inner loops. The compiler can't always hoist the check on its own, because program behavior might de
by zozbot234 6y ago
> The key thing with bounds checks is to hoist them out of inner loops.
The compiler can't always hoist the check on its own, because program behavior might depend on the bounds check occurring in the loop. But you can write an assert!() outside the loop to hoist it explicitly, and verify that the bounds checks are optimized away - or use unsafe unchecked access when they aren't.
- IshKebab 6y agoHow do you write the assert? I've not heard of that before. Oh you mean `assert!(array.len() > 100); for i in 0..100 { array[I]; }` I don't think that guarantees that bounds checks will be hoisted. It's just a strong hint. I mean in this case it will almost certainly work, but in more complexes cases it might not and the compiler is still free to emit bounds checks without telling you. It would be nice if there was an explicit way of forcing an error if the bounds check was not hoisted. Similar story for lots of other optimisations - autovectorisation, tail call optimization, etc. Some game developer made a good point that sometimes fast is correct, i.e. it's actually a bug if autovectorisation or whatever doesn't happen, so you really need a way to guarantee it.
- nicoburns 6y agoIn Rust, the way to force removal of bounds checks is to use iterators rather than a for loop.
- IshKebab 6y agoI don't think that forces their removal either. It just happens to help the compiler enough that it can remove them automatically most of the time. As far as I know the only way to guarantee that bounds checks are not used in a block of code is to use `unsafe`.
- dexterlemmer 6y agoIterators do indeed not force the removal of bounds check, but that's simply because they don't exist to remove in the first place. That's because iterators actually do use `unsafe` internally. They are a safe abstraction. // This is unidiomatic. Don't do this. for i in 0..100 { // Oops! Array indexing. Here's a nasty bounds check! array[i] * 2 } // Very unidiomatic. Never do this! Not even as an // optimization. You should properly use safe abstractions // in stead. for i in 1..100 { // Oh, NOOOO! This isn't supposed to be C! unsafe { array.get_unchecked(i) * 2 } } // This is still unidiomatic unless you want to use // it to explicitly show your code has side-effects. // However, we're completely rid of the bounds check and // yet it's perfectly safe perfectly safe. // The only way this could be unsafe is if rustbelt's // formal proofs, reviews, audits // and (probably) MLOC of thoroughly tested and // possibly fuzzed code using this in practice // have all somehow missed an unsoundness bug // in one of the more used safe abstractions in the // core library for years. for a in array { // Look, Ma! No indexing, therefore no bounds check! // Internally `get_unchecked` is (conceptually) used // but it's perfectly safe! a * 2 } // This is idiomatic Rust. Again, there's no bounds check // to start with, since the save abstraction knows // exactly how many elements are in the array and // that the borrow checker will ensure nobody can // possibly invalidate its indexing. // Ditto what was said above that the safe abstraction // is pretty much guaranteed to be sound. a.iter().map(|a| a * 2).collect()
- deleted 6y ago[deleted]
- deleted 6y ago[deleted]