3 ms·
Rust does runtime bounds checks on array access, which the compiler can't elide in non-trivial cases (e.g. binary search), so if you want to write such algorith
by logicchains 4y ago
Rust does runtime bounds checks on array access, which the compiler can't elide in non-trivial cases (e.g. binary search), so if you want to write such algorithms as fast as in C, you need to use a lot of unsafe array indexing.
- bitcharmer 4y agoYou might be referring to slices. Arrays in rust have to have a known length at compile time.
- masklinn 4y agoRustc may still need to do runtime bounds check if it can’t conclude that a dynamically computed index is in-bounds. The length is known statically, but whether the index is in-bounds may not be. The binary search GP talks about is exactly one such case, go on Godbolt, write up a simple binary search (with a static size so you get code), and you’ll see that the compiler checks against the literal array size on every iteration.
- bitcharmer 4y agoI have no idea how I totally missed that from the GP's comment. Thanks for correcting me.
- kaba0 4y agoI would be interested in how big of a difference does it make — these branches will always go one way, so they are trivial to branch predict. Other than very slightly increasing the code size (which can have a big effect if the i cache is no longer sufficient), I fail to see it doing too badly as is.