4 ms·
In Rust, an assert can turn multiple bounds checks on array indexing into just a single bounds check. Maybe it's something along those lines here too.
by FreeFull 7y ago
In Rust, an assert can turn multiple bounds checks on array indexing into just a single bounds check. Maybe it's something along those lines here too.
- drewm1980 7y agoInteresting! Do have a link to an example?
- FreeFull 7y agoGiven the following code (and with optimisations on): pub fn no_assert(input: &mut [u8]) { for i in 0..10 { input[i] += input[i+1]; } } pub fn with_assert(input: &mut [u8]) { assert!(input.len() >= 11); for i in 0..10 { input[i] += input[i+1]; } } The no_assert function ends up doing a bounds check for every iteration, and the with_assert function only does a single check.
- tudelo 7y agoStill that assert has to be checked at some point right? I would assume that maybe the compiler could do this optimization without having to be told.
- FreeFull 7y agoIn practice a small function like this would be inlined, which gives room for further optimisations. At any point, if the compiler knows that all accesses are in bounds, it can remove the bounds checks. The trick is actually having it figure that out.
- deleted 7y ago[deleted]
- kzrdude 7y agoI believe the compiler can't do that, since the bounds check panic is a side effect that can be observed - the message tells which index that failed the check! For that reason, non-elided checks will not be reordered. However, I believe a future Rust RFC could turn that around and validate the idea that in some cases such things could change execution order, even if it has noticeable side effects. (No idea if it's technically feasible!)
- josephg 7y agoInteresting! Godbolt if anyone is interested: https://godbolt.org/z/1QlLyG https://godbolt.org/z/1QlLyG Both loops get entirely unrolled. Its 5 instructions for each iteration in the first example, and only 3 in the second example. (To say nothing of the fact that conditional jumps are (usually?) much more expensive than add/mov instructions)
- lalaithion 7y agohttps://gist.github.com/kvark/f067ba974446f7c5ce5bd544fe370186#assert-conditions-beforehand https://gist.github.com/kvark/f067ba974446f7c5ce5bd544fe3701...
- bt848 7y agoGo and C++ (when using checked accessors like std::vector::at) can do the same thing. A precondition that satisfies all bounds checks will also eliminate them. You could do this as a post-compile optimization for any language under certain conditions.
- haasted 7y agoI’m interested in how this works in Go, which doesn’t have a built-in assert statement. Do you have somewhere I can read up on it?
- bt848 7y agoThe form of "assert" is not important. It is isomorphic with if (a>b) {exit}. The compiler can assume that thereafter a<=b. until one of them is modified.