Allow Pre-Stepping in Step-By?

[Emerentius]

step_by has to special case the first element and this behaviour can act as a performance block because of the necessary branch in next as seen with integer ranges. This branch can be removed, by always taking the next element and also stepping ahead in one go but that changes the semantics when the iterator has side-effects.
step_by will be stabilized with the next release and I fear that the need to preserve semantics may lock us into a sub-optimally performing step_by or some other lacking solution. I propose that we amend a note to step_by, allowing us to use the "always take and step ahead" semantics for optimization for now. In the future, when we have this issue figured out, we can then limit the cases where pre-stepping is allowed. The general case should not use it.

One example where preserving semantics causes inefficiency is RangeFrom iterators. When pre-stepping, a RangeFrom will overflow its start member one iteration earlier and will therefore, in debug mode, panic one iteration earlier. That may cause a panic in a program that doesn't actually use any elements after the overflow, i.e. a program without any user error. If we have to preserve these semantics, RangeFrom can not be optimized for step_by.
(RangeFrom reserves the right to change overflow behaviour so we could "fix" this particular one by allowing overflow in debug mode)

Furthermore, if range iterators need to pre-step for performance reasons, then the currently still unstable Step trait's step* methods must be limited to be side-effect free or the pre-stepping optimization would be invalid.

[oli-obk]

Nominated for discussion by @rust-lang/libs because of upcoming stabilization being a blocker for perf improvements due to semantic changes being required

@Emerentius I think discussion would be aided by a PR that makes this change and shows some performance numbers

[SimonSapin]

1.28 is in beta, so if we make a change it may need to be backported.

I’m having a little hard time following what is being proposed exactly. Could you give some code examples and the behavior before/after the change?

Is the change "only" in documentation of semantics, in terms of what implementations of a trait are allowed or not allowed to do? Is that the Iterator trait, the Step trait, both? Could you provide wording that would go into those docs?

[Emerentius]

I'm not proposing any code changes right now, only a note in the docs giving us some freedom for future changes.

The semantics of step_by are (next), (skip, next), (skip, next), …. Parenthesised actions are grouped, i.e. done together.
In Rust, that is next(), nth(), nth()…. That necessitates a branch because of the first element. With side-effect free iterators you can switch this to a branchless (next, skip), (next, skip), …. That's what I've been calling the pre-stepping semantics.
We don't (yet?) have a function for (next, skip) except for a combination of next and nth.

The concrete performance problem I have in mind are still ranges (#51557, #43064, #31155). Their problems are not entirely due to StepBy but its branching is part of the issue. For now, StepBy<Range> and StepBy<RangeInclusive> are specialized to use the branchless pre-stepping. It's hacky, but it covers the most common cases. RangeFrom can't be specialized because it would make a correct program crash in an edge case if the current semantics have to be conserved. I'd rather not have to tell people to never use (start..).step_by() without for_each or another iter consumer.

The problem therefore is, what if we need to be able to pre-step for performance reasons in the presence of side-effects? With RangeFrom, that means an integer overflow, but in the future the question extends to any implementor of the Step trait. User iterators could also gain from this, but I have no examples currently.
We shouldn't pre-step in general precisely because of an iterator's possible side-effects, but we may need some way for iterators to opt into it. Special casing only ranges seems questionable.

I just want to keep our options open for now but change no actual code. We can sort this out without a stabilization countdown over our heads. Also, I don't have much time right now.

[alexcrichton]

@Emerentius could you expand on the proposed documentation change? What do you think should be added to the documentation to future-proof ourselves?

[scottmcm]

Right now, the following code

    (0..10)
        .inspect(|x| print!("({}) ", x))
        .step_by(2)
        .take(3)
        .for_each(|x| println!("{}", x));

prints

(0) 0
(1) (2) 2
(3) (4) 4

I believe the request is to allow it the freedom to instead print

(0) (1) 0
(2) (3) 2
(4) (5) 4

Which I think can be optimized better for ranges (one addition instead of two) and could be argued is a more pure translation of "step by two", but has the obvious downside of potentially reading more things from the source iterator (if it doesn't get exhausted).

[alexcrichton]

Ah ok, thanks @scottmcm! That makes total sense to me and I'd personally be down for such an implementation

[Emerentius]

Yes, that's what I was trying to say. It's a bit difficult to express concisely in terms of existing iterator methods. Here's my attempt at the note to be added:

---

Note: StepBy behaves like the sequence next(), nth(step-1), nth(step-1), …, but is also free to behave like the sequence advance_n_and_return_first(step), advance_n_and_return_first(step), …
Which way is used may change for some iterators for performance reasons. The second way will advance the iterator earlier and may consume more items.

advance_n_and_return_first is the equivalent of:

fn advance_n_and_return_first<I>(iter: &mut I, total_step: usize) -> Option<I::Item>
where
    I: Iterator,
{
    let next = iter.next();
    if total_step > 1 {
        iter.nth(step-2);
    }
    next
}

[alexcrichton]

Sounds like a great clause to me to add!

(I'd personally be down for a PR to change the behavior as well)

[Emerentius]

PR is merged and backported