swift for-loop compilation iterator dynamic-dispatch

Why is indexingIterator.next() using dynamic dispatch?

Why is for-in slower than while in swift debugging mode? I wrote this. Thanks for people who answer to me, I could have learned Seqeunce and IteratorProtocol.

So I implemented custom type ( School below code ) which conformed Sequence. And I checked Xcode-time profile.

But I can't find anything protocol witness

But If only use range and for-in , time profiler show protocol witness.

why is indexingIterator.next() using dynamic method but not in School ? I thought that even struct conformed protocol, if variable in struct type use method of protocol, this method will be static method. If I am wrong, Could you please tell me what is wrong?

⬇️School code

struct SchoolIterator: IteratorProtocol {
    
    private var schoolList: School
    var idx = 0
    init(_ school: School) {
        self.schoolList = school
    }
    
    mutating  func next() -> String? {
        defer { idx += 1 }
        guard schoolList.count-1 >= idx
            else { return nil }
        
        return schoolList[idx]
    }
}

struct School: Sequence {
    fileprivate var list = Array(repeating: "school", count: 100000)
    var count: Int { return list.count }
    
    subscript(_ idx: Int ) -> String? {
        guard idx <= count-1
            else { return nil }
        return list[idx]
    }
    func makeIterator() -> SchoolIterator {
        return SchoolIterator(self)
    }
}
var schools = School()
for school in schools {
    print(school)
}

Solution

Your for loop translates to:

var schools = School()
var iterator = schools.makeIterator()
while let school = iterator.next() {
    print(school)
}

Notice how nothing here is a protocol. schools is of type School, iterator is of type SchoolIterator, everything that next does (like accessing schoolList.count, or the subscript of schoolList) deals with structs too. The key point is that the compiler can figure out exactly which member you mean, because its (compile-time) type is a struct. There is no need to look up witness tables.

Compare that to, e.g.

func f<S: Sequence>(_ s: S) {
    for thing in s {
        ...
    }
/*
    var iterator: S.Iterator = s.makeIterator()
    while let thing = iterator.next() {
        ...
    }
*/
}

f(School())
f(1..<100)

How would the compiler dispatch the calls to iterator.next()? I've deliberately added the type annotation to make it clear what's happening - this time, the compiler doesn't know which next you mean. Is it IndexingIterator.next()? Or SchoolIterator.next()? Or SomeOtherIterator.next()? Keep in mind that I can call f with any kind of Sequence! That's why it needs to look up the witness table of the actual type of S.Iterator at runtime - it is impossible to figure out which next to call.

As for why for i in 0..<100 uses dynamic dispatch, well, on first sight, there seems to be all structs:

let range: Range<Int> = 0..<100
var iterator: IndexingIterator<Range<Int>> = range.makeIterator()
while let i = iterator.next() {
    ...
}

However, iterator.next actually does something like this:

public mutating func next() -> Elements.Element? { if _position == _elements.endIndex { return nil } let element = _elements[_position] _elements.formIndex(after: &_position) return element }

_elements is defined like this:

public struct IndexingIterator<Elements: Collection> {
  
  internal let _elements: Elements

_elements could be any kind of Collection, so again, we don't know which member _elements[_position] or _elements.formIndex refers to at compile time. Is it Array.formIndex? Or Set.formIndex? We only know at runtime, when we know what Elements is.