Slow performance of std::iter::Rev with iterator adapters using std::iter::Iterator::nth()

[koalatux]

The following example shows a benchmark of the iterator adapter step_by(). Once using step_by() directly on the range and once with a redirection via rev().

use test::Bencher;

#[bench]
fn bench_forward_skip(b: &mut Bencher) {
    b.iter(|| (0..10001).step_by(100).sum::<i32>());
}

#[bench]
fn bench_reverse_skip(b: &mut Bencher) {
    b.iter(|| (0..10001).rev().step_by(100).sum::<i32>());
}

Running this benchmark with the current nightly shows these results:

test tests::bench_forward_skip ... bench:         137 ns/iter (+/- 6)
test tests::bench_reverse_skip ... bench:       3,878 ns/iter (+/- 327)

step_by() makes use of nth() of the adapted iterator. A range provides an optimized version of nth(), but by using rev() we get to use the default implementation of nth().

We should Extend std::iter::DoubleEndedIterator to provide a new method maybe nth_back() or rnth() with a default implementation which then can get adapted by rev(). Similar to the already existing next_back(), try_rfold(), rfold() and rfind().

Update:

nth_back() has been merged in #56802. Types which have a specialized nth() and implement DoubleEndedIterator are candidates for a specialized nth_back(). The following list shows these candidates and their implementation status:

• Box (Implement specialized nth_back() for Box and Windows. #59328)
• Bytes (implement specialized nth_back() for Bytes, Fuse and Enumerate #60023)
• Chain (Add custom nth_back for Chain #60492)
• Chunks (Feature/nth back chunks #61048)
• ChunksExact (nth_back for chunks_exact #62064)
• ChunksExactMut (Implement nth_back for ChunksExactMut #63265)
• ChunksMut (squash of all commits for nth_back on ChunksMut #62074)
• &mut DoubleEndedIterator (Add DoubleEndedIterator::nth_back #56802)
• Enumerate (implement specialized nth_back() for Bytes, Fuse and Enumerate #60023)
• Fuse (default fn) (implement specialized nth_back() for Bytes, Fuse and Enumerate #60023)
• Fuse (where FusedIterator) (implement specialized nth_back() for Bytes, Fuse and Enumerate #60023)
• slice::Iter (defined by a macro) (Implement nth_back for slice::{Iter, IterMut} #60772)
• slice::IterMut (defined by a macro) (Implement nth_back for slice::{Iter, IterMut} #60772)
• Range (implement nth_back for Range(Inclusive) #61671)
• RangeInclusive (implement nth_back for Range(Inclusive) #61671)
• RChunks (Implement nth_back for RChunks(Exact)(Mut) #60555)
• RChunksExact (Implement nth_back for RChunks(Exact)(Mut) #60555)
• RChunksExactMut (Implement nth_back for RChunks(Exact)(Mut) #60555)
• RChunksMut (Implement nth_back for RChunks(Exact)(Mut) #60555)
• Rev (Add DoubleEndedIterator::nth_back #56802)
• Skip (Add custom nth_back to Skip #60454)
• Windows (Implement specialized nth_back() for Box and Windows. #59328)
• Zip
• Zip (in ZipImpl default fn)
• Zip (in ZipImpl where TrustedRandomAccess)

[clarfonthey]

I would probably call this nth_back, personally. But I agree that it's a good method to have.

[robsmith11]

I ran into this issue as well I think.

I was expecting vec.iter().rev().skip(n) to be efficient, but it runs 10x slower than vec[0..(vec.len() - n)].iter().rev(), which I would have expected to be similar.

[clarfonthey]

If I get the time later, I'll make a PR to add an nth_back method to DoubleEndedIterator with a few basic overrides. I'll try to get to it by tomorrow at least.

[scottmcm]

With nth_back landed, this is now a fairly-straightforward task to just override nth_back in double-ended iterators that have nth overridden already.

For example, the slice iterator has

rust/src/libcore/slice/mod.rs

Lines 3802 to 3813 in 8ae730a

	#[inline]
	fn nth(&mut self, n: usize) -> Option<Self::Item> {
	let (end, overflow) = self.size.overflowing_add(n);
	if end > self.v.len() || overflow {
	self.v = &[];
	None
	} else {
	let nth = &self.v[n..end];
	self.v = &self.v[n+1..];
	Some(nth)
	}
	}

So it should probably have nth_back in its DEI implementation a few lines later:

rust/src/libcore/slice/mod.rs

Line 3827 in 8ae730a

impl<'a, T> DoubleEndedIterator for Windows<'a, T> {

The general pattern here will be to just do whatever nth is doing from the other end; the differences between next and next_back should give you a good hint about what differences are needed.

[koalatux]

Thanks, I will look into implementing some of the nth_back specializations soon. This sounds a promising task to get familiar with libstd.