Iterator::nth doesn't compose well

[timvermeulen]

Iterators like iter::{Flatten, FlatMap, Chain} that chain multiple iterators together aren't able to implement Iterator::nth in terms of the nth method on their inner iterators, because when nth returns None, there's no way to know how many elements are "left".

This can lead to surprisingly bad performance when the inner iterator has an efficient nth implementation. For example, (0..100_000).chain(0..100_000).nth(50_000) has O(n) performance, even though it never reaches the second iterator.

I don't really know if this is worth fixing, but if it is, a way to fix it could be to add a method similar to nth to Iterator that returns Result<Self::Item, usize>. The Err case represents the "remaining" n (there's probably a better way to phrase that).

I don't have any interesting benchmarks, but I can confirm that implementing what I've temporarily called try_nth for ops::Range and iter::Chain makes (0..100_000).chain(0..100_000).nth(50_000) run in constant time. So returning Result<Self::Item, usize> indeed composes better. But again, this may not be worth fixing. 🙂

[Mark-Simulacrum]

I'm not sure if we can get away with it (depending on the guarantees nth exposes), but it's possible this is simply a lack of specialization. Presumably chain could forward TrustedLen/ExactSizeIterator and the like such that we'd be able to "skip" within it as needed.

[Stargateur]

That more chain that doesn't compose very well ?

[timvermeulen]

@Mark-Simulacrum That's a great point, an ExactSizeIterator bound would indeed allow a better implementation. Do note that this isn't quite as powerful as always being able to forward to nth, though, because some types could conceivably implement nth more efficiently than the default implementation without implementing ExactSizeIterator.

[cuviper]

I don't really know if this is worth fixing, but if it is, a way to fix it could be to add a method similar to nth to Iterator that returns Result<Self::Item, usize>. The Err case represents the "remaining" n (there's probably a better way to phrase that).

Would iter::empty().try_nth(0) return Err(0) or Err(1)?

This is an extension of the general off-by-one confusion of nth, which needs careful documentation.

[timvermeulen]

@cuviper It would return Err(0). It's indeed very important to be wary of off-by-one errors, and I believe this is the more natural choice, because:

• Having the invariant that n is always non-zero seems inconsistent with the parameter of nth being zero-indexed.
• The combinators that would benefit from this can pass this same n to try_nth of the next iterator, rather than having to do integer arithmetic.
• It matches the final value of n in the current default implementation of nth.

[timvermeulen]

@Mark-Simulacrum Note that a chain of more than two iterators wouldn't be able to benefit from that specialization because Chain itself doesn't implement ExactSizeIterator, so only try_nth would help there. Or e.g. a Chain nested inside a Flatten.

[timvermeulen]

This is no longer relevant now that Iterator::advance_by has been merged.