This is good!
My one worry is that forcing iteration to use indices is going to add unacceptable overhead.
A side effect of the pitch is that it eliminates a crucial Collection customization point for forward iteration: the possibility to customize the Iterator type. It proposes to instead always use the (non-consuming equivalent of) IndexingIterator.
IndexingIterator tends to perform measurably/significantly worse than a custom iterator type for all but the simplest data structures. (I.e., basically anything that isn't just a contiguous array -- and even for something "simple" like Array, IndexingIterator only works as well as it does because of relatively fragile optimizations, heroically hand-tuned over the years. None of these optimizations translate to, say, collection types with non-inlinable members.)
The problem is that index validity isn't modeled in the type system -- it needs to be verified at runtime. Indices are effectively pointers into the internal structure of the collection value, and they are inherently fragile -- the slightest structural mutation can invalidate them. However, nothing prevents us from continuing to use an invalidated index, or even to apply a valid index from one collection to some completely unrelated other collection instance. Therefore, Collection operations that take indices must always treat them with suspicion, and carefully check validity every single time -- otherwise they risk hazards such as out of bounds accesses.
This means that a for-in loop that relies on indexing will do completely unnecessary index validation work, repeated multiple times during each iteration -- subscript[i] and formIndex(after: &i) will both trigger such checks, even if (as I hope) the language will reject attempts to independently mutate the container during these new-style for borrow and for inout loops.
In contrast, the current (consuming) iterators can safely assume that the underlying container will not be mutated while they are active, so they can shortcut all of these checks.
Beyond eliminating validation steps, we also have the freedom to design iterators that include additional information that optimizes the task at hand but that may not be appropriate to include in a general-purpose index. For instance, iterators in tree-based collections sometimes include direct pointers to every node on the current path, while indices often only carry a single pointer to the "current" node (if that -- node pointers are rather tricky to reliably validate). Or, in the case of something like Set, the iterator can carry state that is cheaper to update than recreating it from scratch in each iteration.
To give a specific example:
let n = 1_000_000
var set = Set(0 ..< n)
let clock = ContinuousClock()
let d = clock.measure {
var c = 0
#if USE_CUSTOM_ITERATOR
var it = set.makeIterator()
while let v = it.next() {
c &+= v
}
#else
var i = set.startIndex
while i < set.endIndex {
c &+= set[i]
set.formIndex(after: &i)
}
#endif
precondition(c == n &* (n - 1) / 2)
}
print(d)
$ swiftc -O foo.swift && ./foo
0.003566333 seconds
$ swiftc -DUSE_CUSTOM_ITERATOR -O foo.swift && ./foo
0.001064959 seconds
Even for something simple like Set, the custom iterator is more than three times faster than equivalent code that's using indices. (This gap feels suspiciously large, to be honest, but even if some of it is due to us not spending enough effort on optimizing performance, it still demonstrates how much easier it is to write a fast iterator than to optimize indices.)
I would therefore be sad if we lost this customization hook. This would be all the more painful if we were planning to switch the default for in syntax to mean a for borrow even for copyable collections/elements -- we'd be inducing a performance regression.
(I expect for borrow would make up a large part of this gap if the Set's Element was a nontrivial type -- not having to retain strong references will be a significant win. But I don't expect for borrow will do much for trivial types.)
As I understand it, the new for borrow/for inout constructs would inherently prevent independent mutations of the underlying container -- this time as a proper, language-level restriction. Can we somehow use this guarantee to introduce a new, non-consuming iterator construct?
