rust-lang / rust-lang/rust

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

Open
#147,704 3 comments 1 reaction 0 assignees View on GitHub

Nobody has claimed this yet.

A-iterators C-optimization T-libs
Dominant language
Rust
Stars
119k
Forks
16.1k
PR merge metrics
PR metrics pending

Description

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

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start at the core::Zip::next_back() implementation and inspect how it handles iterators with different lengths, including the TrustedRandomAccessNoCoerce distinction and advance_back_by(). Reproduce the supplied benchmark first, then verify that the optimized behavior preserves correctness and improves the reported next_back() timing.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
performance
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.