4 ms·
Kinda surprised about iterators not getting optimized so well. Even in higher-level languages, this is a commonly utilized optimization opportunity - e.g. the C
by int_19h 6y ago
Kinda surprised about iterators not getting optimized so well. Even in higher-level languages, this is a commonly utilized optimization opportunity - e.g. the C# compiler will replace a foreach-loop over an array with an identical (but faster) for-loop.
- dpc_pw 6y agoCompiler optimizers are full of surprises going both ways: good and bad. And details like this can probably change from version to version and get affected by compiling options. I would also expect that performance is higher priority than code size, generally, so missed opportunities like this might go unnoticed and unaddressed a long time if they don't show up on performance benchmarks.
- eru 6y agoThe classic example of surprising optimization is perhaps matrix multiplication in Fortran: At some point in history, when you wrote the straightforward, primitive three-nested-loops version of matrix multiplication your code ran much faster than when you tried to implement one of the more sophisticated algorithms. That was because the Fortran compiler recognised the primitive version and replaced it with a special purpose highly optimized matrix multiplication. The compiler couldn't do that with the more sophisticated approaches.
- mmarx 6y ago> The classic example of surprising optimization is perhaps matrix multiplication in Fortran: > At some point in history, when you wrote the straightforward, primitive three-nested-loops version of matrix multiplication your code ran much faster than when you tried to implement one of the more sophisticated algorithms. It might also have been due to Fortran using column-major matrix layout; if you try to implement a sophisticated multiplication algorithm that is optimised for row-major matrices, then that will be slower (indeed, also the row-major three-nested-loops version is already quite a bit slower). Another thing is that the sophisticated algorithms usually have some constant overhead that makes them shine only on sufficiently large matrices.
- gavinray 6y agoThere are tricks/an art to Rust's iterator semantics. One example I know of is that when trying to calculate a dot product, you can improve the generated code and elide the bounds check only by a very particular syntax: // Must slice to equal lengths, and then bounds checks are eliminated! let len = cmp::min(xs.len(), ys.len()); let mut xs = &xs[..len]; let mut ys = &ys[..len]; let mut s = 0.; for i in 0..xs.len() { s += xs[i] * ys[i]; } https://users.rust-lang.org/t/how-to-zip-two-slices-efficiently/2048/10 https://users.rust-lang.org/t/how-to-zip-two-slices-efficien... https://github.com/rustsim/nalgebra/blob/b1b18d17ee64d3fd28b67ac581d28af4d20ec817/src/base/blas.rs#L334-L342 https://github.com/rustsim/nalgebra/blob/b1b18d17ee64d3fd28b...
- bad-apple 6y agoDoes it still elide the bounds check if you replace the first three lines with assert_eq!(xs.len(), ys.len()); ?
- pcwalton 6y agoRust will do that too. We're talking about micro-optimization-level details, not allocation of iterator objects and so forth.
- pornel 6y agoThis isn't a case of a missed optimization. The alternative loop they've used has different semantics: assumes 0 iterations never happen. It's equivalent of changing `while(){}` to `do {} while()`. It's not something an optimizer could safely do when the number of iterations isn't known.