Repository navigation
Iterating with step_by(1) is much slower than without #57517
Description
Greetings!
I'd like to report that I get some significant (negative) performance impact when calling step_by(1) on an iterator. I created a repository with a detailed description of the issue and benchmarks to reproduce it: https://github.com/mvlabat/step_by_one
These are the functions I tested:
pub fn iter_default_step(mut arr: Vec<i32>) -> Vec<i32> {
for e in arr.iter_mut() {
*e = e.wrapping_add(3);
}
arr
}
pub fn iter_step(mut arr: Vec<i32>, iter_step: usize) -> Vec<i32> {
for e in arr.iter_mut().step_by(iter_step) {
*e = e.wrapping_add(3);
}
arr
}Calling iter_step(vec![1; LARGE_ENOUGH], 1) computes 1.75x slower than iter_default_step(vec![1; LARGE_ENOUGH])
with const LARGE_ENOUGH: usize = 10_000_000;.
I'm running Macbook Pro 2015 with Intel i5-5257U CPU (2.70GHz).
My rustc version: 1.33.0-nightly (c2d381d39 2019-01-10).
These are the exact benchmark results I got:
running 4 tests
test tests::bench_iter_default_step ... bench: 8,702,963 ns/iter (+/- 1,648,782)
test tests::bench_iter_step_1 ... bench: 15,267,083 ns/iter (+/- 1,236,220)
test tests::bench_iter_step_16 ... bench: 9,053,772 ns/iter (+/- 380,422)
test tests::bench_iter_step_64 ... bench: 8,711,169 ns/iter (+/- 327,562)
In the repository README there are also links to the generated asm code of these two functions.
Activity
nikic commentedon Jan 11, 2019
Godbolt link: https://rust.godbolt.org/z/scU_bY
I've slightly changed the code to actually modify the array (wrapping_add returns the value -- it does not operate in-place).
One bit that stands out especially to me is this:
I would have expected something (possibly jump threading?) to optimize away the
%iter.sroa.13.0phi.vladbat00 commentedon Jan 11, 2019
Yeah, I forgot to use the returned addition value. Changed that in my code already too )
scottmcm commentedon Jan 12, 2019
I wonder if this would be fixed with the change discussed in #52065. Also, try using
.for_each()instead of aforloop; this might just be one of the many places where internal iteration is just faster.Rollup merge of rust-lang#64121 - timvermeulen:iter_step_by_internal,…
nikic commentedon Sep 9, 2019
I don't think #64121 fixes this issue, as it affects internal iteration only, while this one is about external iteration.
timvermeulen commentedon Feb 16, 2020
@nikic You're right, but now it's just a matter of "
for_eachis faster than aforloop forstep_by" which is not at all surprising if you consider thatStepBy::nextbranches based on thefirst_takefield. It's not something we're able to fix in the general case.mlindner commentedon May 18, 2020
There's another example of this coming up here in this thread: https://www.reddit.com/r/learnrust/comments/glxa5r/rust_vs_cpp_speed_in_implementation/
Rust vs C++ example where C++ takes 600-700ms and Rust takes 4300ms.
the8472 commentedon May 23, 2023
Looks like it's fixed on beta and nightly. It hasn't reached stable yet.
https://rust.godbolt.org/z/6qjvoE719
nikic commentedon May 23, 2023
I believe step_by was one of the iterators with improved optimization in LLVM 16. I thought I added a codegen test for that, but apparently not.
We should add a test for this, but probably not the one from OP, but something with simpler IR.