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_skipzips two iterators and then skips a good portion followed by conditionally taking 100 elements -
skip_zipuses skip on the individual iterators and then does the same -
slice_zipslices 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?
