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

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?

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.