How do Swift's heterogenous value type arrays work?

Question

I'm a C++ programmer just starting out with Swift. I watched Dave Abrahams' WWCD talk "Protocol Orientated Programming in Swift" and I was intrigued by the way that it's possible to create a heterogeneous array of value types constrained by a protocol.

To use the example from the video, given a protocol Drawable and two structs which implement it:

protocol Drawable {
    func draw(renderer: Renderer) // Renderer is another protocol
}

struct Circle : Drawable {
    func draw(renderer: Renderer) {
        // Implementation
    }
}

struct Rectangle : Drawable {
    func draw(renderer: Renderer) {
        // Implementation
    }
}

It's possible to define a Diagram as containing an array of Drawables

struct Diagram : Drawable {
    var elements: [Drawable] = []

    func draw(renderer: Renderer) {
        for e in elements {
            e.draw(renderer);
        }
    }
}

My question is, how exactly does this heterogenous elements array work under the covers? As the various implementations of Drawable can vary in size, I can't see how they can be laid out in an efficient array in memory. Does this mean that such a "protocol array" is actually using per-element heap allocation and dynamic/virtual function calls under the surface?

Answer 1

I was curious about the same, although I did not have time enough to completely get to the bottom of it. Still I think I have gotten some approximation worth of placing here as an answer.

Firstly, there it this article from Jason Bell, which provides some hints at how it all works behind the scenes (not only for Swift but also for Objective-C and other languages).

Secondly, if I take this simple program:

protocol Foo { }

struct Bar: Foo { }

var fooArray = [Foo]()

fooArray.append(Bar())
fooArray.append(Bar())
fooArray.append(Bar())

let arrayElement = fooArray[0]

print(arrayElement)

... and compile it into LLVM IR by doing swiftc -emit-ir unveil.swift > unveil.ir then I can fish out the following IR code that corresponds to a simple fooArray.append(Bar()):

%15 = getelementptr inbounds %P6unveil3Foo_* %3, i32 0, i32 1
store %swift.type* bitcast (i64* getelementptr inbounds ({ i8**, i64, { i64, i8*, i32, i32, i8*, %swift.type** (%swift.type*)*, %swift.type_pattern*, i32, i32, i32 }*, %swift.type* }* @_TMfV6unveil3Bar, i32 0, i32 1) to %swift.type*), %swift.type** %15, align 8
%16 = getelementptr inbounds %P6unveil3Foo_* %3, i32 0, i32 2
store i8** getelementptr inbounds ([0 x i8*]* @_TWPV6unveil3BarS_3FooS_, i32 0, i32 0), i8*** %16, align 8
%17 = getelementptr inbounds %P6unveil3Foo_* %3, i32 0, i32 0
call void @_TFV6unveil3BarCfMS0_FT_S0_()
%18 = bitcast %P6unveil3Foo_* %3 to %swift.opaque*
call void @_TFSa6appendurfRGSaq__Fq_T_(%swift.opaque* noalias nocapture %18, %swift.type* %14, %Sa* nocapture dereferenceable(8) @_Tv6unveil8fooArrayGSaPS_3Foo__)

Here you can find the LLVM IR syntax, but for me above means that Swift arrays are really arrays of pointers.

Also, similarly to IR, I can get to the assembly for the same Swift line, which is:

leaq    __TWPV6unveil3BarS_3FooS_(%rip), %rax
leaq    __TMfV6unveil3Bar(%rip), %rcx
addq    $8, %rcx
movq    %rcx, -56(%rbp)
movq    %rax, -48(%rbp)
callq   __TFV6unveil3BarCfMS0_FT_S0_
leaq    __Tv6unveil8fooArrayGSaPS_3Foo__(%rip), %rdx
leaq    -80(%rbp), %rax
movq    %rax, %rdi
movq    -160(%rbp), %rsi
callq   __TFSa6appendurfRGSaq__Fq_T_

... again, above manipulates the pointers, so that confirms the theory.

And finally, there are SIL headers SILWitnessTable.h and SILWitnessVisitor.h from swift.org to be found at swift/include/swift/SIL/ that suggest the same.

Actually, I guess (and I hope that someone who really knows what he's talking about would weigh in here) that value-types (e.g. structs) and reference-types (read classes) are not so much different under the hood of Swift. Probably the main difference is whether copy-on-write in enforced or not.