Use internal iteration in FromIterator and Extend implementations.

[Stebalien]

Internal iterators (e.g., Iterator::fold(...)) often optimize better (e.g., in Zip, FlatMap, etc...) as they don't need to repeatedly check the entire state of the iterator every iteration. Given that FromIterator and Extend implementations consume the entire iterator, they could use internal iterators and take advantage of this fact.

@bluss?

^{(I have no benchmarks or code and don't really have time to do anything but suggest that someone else look into this ATM, sorry.)}

[bluss]

I benchmarked this at some point (in connection to #37306), and sure enough, stuff like .chain() can benefit greatly if .fold() is used in FromIterator (because since chain is a TrustedLen if its parts are).

The nature of the optimization is that it can make a really big difference in its best case (think byte at a time, while checking different chain iterator flags per byte versus memcpy).

I kind of consider it too weird if we have a better loop than the for loop, but the pragmatic thing would be to use whatever is faster internally and work towards a Rust where the for loop is never a worse alternative.

[Stebalien]

I wonder if we could make for loops use internal iteration when possible or if that would be way too magical... (I feel dirty even suggesting this). Alternatively, in the distant future, we may be able to use the iterator's internal iterator implementation as a hint to some amazing equivalence proving optimizer.

[steveklabnik]

Triage: I'm not aware of any movement on this issue. @bluss's comment seems to indicate that this is an improvement if we could make it happen.

[Stebalien]

This looks like it has been implemented. At least in Vec, HashMap, BTreeMap, and String.