core::Zip::next_back() slow for iterators of different lengths

[Dan54]

The following example is a benchmark of core::Zip::next_back() with iterators of very different lengths.

use std::iter::*;
use std::time::Instant;
fn main() {
    let start = Instant::now();
    for _ in 0..10_000 {
        once(0).zip(repeat_n(1, 1_000_000)).next();
    }
    let end = Instant::now();
    println!("next(): {:.2} ns/iter", end.duration_since(start).as_secs_f64() * 100_000f64);

    let start = Instant::now();
    for _ in 0..10_000 {
        once(0).zip(repeat_n(1, 1_000_000)).next_back();
    }
    let end = Instant::now();
    println!("next_back(): {:.2} ns/iter", end.duration_since(start).as_secs_f64() * 100_000f64);
}

It outputs:

next(): 0.02 ns/iter
next_back(): 357483.04 ns/iter

This is caused by Zip::next_back() calling the longer iterator's next_back() until both iterators are the same length. For iterators not implementing TrustedRandomAccessNoCoerce this could be sped up significantly by using advance_back_by() instead.

I'm not sure if this can be optimised for iterators implementing TrustedRandomAccessNoCoerce but not TrustedRandomAccess, as they use the same next_back() implemntation but cannot safely use advance_back_by().

Rust version

rustc 1.90.0 (1159e78c4 2025-09-14)
binary: rustc
commit-hash: 1159e78c4747b02ef996e55082b704c09b970588
commit-date: 2025-09-14
host: x86_64-pc-windows-msvc
release: 1.90.0
LLVM version: 20.1.8

[chenyukang]

even it's not optimized for that scenario, I think it's also safe to apply this change?

rust/library/core/src/iter/traits/double_ended.rs

Lines 138 to 146 in 2f7620a

	fn advance_back_by(&mut self, n: usize) -> Result<(), NonZero<usize>> {
	for i in 0..n {
	if self.next_back().is_none() {
	// SAFETY: `i` is always less than `n`.
	return Err(unsafe { NonZero::new_unchecked(n - i) });
	}
	}
	Ok(())
	}

[Dan54]

A lot of iterators override advance_back_by() or nth_back() to run faster, so it is an optimisation.

TrustedRandomAccess does not require nth_back() to be safe to call after __iterator_get_unchecked(), but I suspect it is safe for all implementors.

[Dan54]

The optimization could be applied to TrustedRandomAccessNoCoerce if the trait's safety requirements were extended to allow calls to advance_back_by(n) and nth_back(n) (with each call counting as n and n + 1 next_back() calls respectively).

TrustedRandomAccessNoCoerce is implemented by the following structs:

• alloc::collections::vec_deque::{Iter<T>, IterMut<T>}
• alloc::vec::IntoIter<T>
• core::array::IntoIter<T, N>
• core::char::{CaseMappingIter, ToLowercase, ToUppercase}
• core::iter::{Cloned<I>, Copied<I>, Enumerate<I>, Fused<I>, Map<I, F>, Skip<I>, Zip<A, B>}
• core::ops::Range<_>
• core::range::IterRange<_>
• core::slice::{Chunks<T>, ChunksExact<T>, ChunksExactMut<T>, ChunksMut<T>, Iter<T>, IterMut<T>, RChunks<T>, RChunksExact<T>, RChunksExactMut<T>, RChunksMut<T>, Windows<T>}
• core::str::Bytes

All of these look safe to me under the above requirement, as their advance_back_by() and nth_back() methods just simulate repeated calls to next_back().