At runtime, how does Swift know which implementation to use?

Question

protocol A {
    func f()
}

struct S1 : A {
    func f() {
        print("S1")
    }
}

struct S2 : A {
    func f() {
        print("S2")
    }
}

let array: [A] = [S1(), S2()]

for s: A in array {
    s.f()
}

// "S1\n" "S2\n"

If this was an inheritance hierarchy, I would expect Swift to use a v-table to look up the correct implementation. However, the concrete types in array could be anything that implements A, along with any number of other protocols, so how would the Swift runtime know the structure of the object if it was also using v-tables?

Kidding

Swift uses a "Protocol Witness Table" to do this – this WWDC talk explains it pretty well: developer.apple.com/videos/play/wwdc2016-416/?time=1474 – Fabrianna

Awesome, and funnily enough, I was already planning to watch that video today. :) – Kidding

Was about to reply, but yes, watch that talk :) – Iveyivie

Answer 1

The Swift runtime uses a Protocol Witness Table which holds pointers to each type's implementations of the protocol methods.

Mike Ash explains it best in his article Exploring Swift Memory Layout, Part II:

The last one, at offset 32 is a "protocol witness table" for the underlying type and the protocol, which contains pointers to the type's implementations of the protocol methods. This is how the compiler is able to invoke methods, such as p(), on a value of protocol type without knowing the underlying type at runtime.

I would also watch the WWDC video Understanding Swift Performance as suggested in the comments by Hamish.

Saskatchewan