I recenly wrote some naive code that used Vec indices to access data. I assumed using iterators would speed up the generated code, but the opposite happened. I think I found cause and made a testcase.
My code did a binary search to find a start position and then generally only a few iterations to find some matches. I process the resutls from two equal-length vectors. I can represent it using the following tests:
-
zip_skip
zips two iterators and then skips a good portion followed by conditionally taking 100 elements -
skip_zip
uses skip on the individual iterators and then does the same -
slice_zip
slices the vectors before creating the iterators
#[bench]
fn zip_skip(b: &mut Bencher) {
let v: Vec<_> = (0..100_000).collect();
let t: Vec<_> = (0..100_000).collect();
b.iter(|| {
let s = v.iter().zip(t.iter()).skip(10000)
.take_while(|t| *t.0 < 10100)
.map(|(a, b)| *a + *b)
.sum::<u64>();
assert_eq!(s, 2009900);
});
}
#[bench]
fn skip_zip(b: &mut Bencher) {
let v: Vec<_> = (0..100_000).collect();
let t: Vec<_> = (0..100_000).collect();
b.iter(|| {
let s = v.iter().skip(10000).zip(t.iter().skip(10000))
.take_while(|t| *t.0 < 10100)
.map(|(a, b)| *a + *b)
.sum::<u64>();
assert_eq!(s, 2009900);
});
}
#[bench]
fn slice_zip(b: &mut Bencher) {
let v: Vec<_> = (0..100_000).collect();
let t: Vec<_> = (0..100_000).collect();
b.iter(|| {
let s = v[10_000..].iter().zip(t[10_000..].iter())
.take_while(|t| *t.0 < 10100)
.map(|(a, b)| *a + *b)
.sum::<u64>();
assert_eq!(s, 2009900);
});
}
Running this benchmark gives the following results:
running 3 tests
test tests::skip_zip ... bench: 127 ns/iter (+/- 15)
test tests::slice_zip ... bench: 59 ns/iter (+/- 2)
test tests::zip_skip ... bench: 5,059 ns/iter (+/- 330)
The summing in the main map
probably not contributing a lot means we benchmark mainly the costs of the iterator? There is a huge difference in the zip_skip
approach which to me is the one you would naturally write.
Does the skip on the zipped iterators indeed call next 10K times, while the iter().skip does the skip in a single step like the slice? Should I have known this?