Swift type erasure survey / performance analysis. Build with `swiftc -O -g -whole-module-optimization`

TypeErasureSurvey.swift

// Protocol to use for type erasure.
protocol Summable {
  func sum() -> Int
}

// Concrete model. Type 
extension Int: Summable {
  func sum() -> Int { self }
}

// Generic model. Type erasure doesn't optimize well except by function.
struct X<T: BinaryInteger> { let value: T? }
extension X: Summable {
  func sum() -> Int {
    // set a breakpoint in this function and issue the "disasssemble" command in
    // LLDB to see the code that will be executed for each case.
    Int(value ?? 0)
  }
}

struct Y<T> { let value: T? }
// Concretized generic model (Y<UInt>). Type erasure optimizes well.
extension Y: Summable where T == UInt {
  func sum() -> Int { Int(value ?? 0) }
}

// Instances of each model
let a = X(value: 3), b = 3, c = Y(value: 3 as UInt)

// =============================================================================
// Type erasure techniques.
// =============================================================================

// Used to prevent the compiler from knowing some things at compile-time
let FALSE = CommandLine.arguments.count == 999
// Used to prevent dead code stripping.
var total = 0 

// -----------------------------------------------------------------------------
// Type erasure via existential.  Many nice properties including clean code,
// preserving type safety and value semantics, but optimizes poorly for X<T>
// (see below).  May generate code for box allocation/deallocation.  Always
// generates ARC calls.  Memory footprint of existentials is rather large.

@inline(never)
func invoke1(_ x: Summable) -> Int { x.sum() } 

@inline(never)
func testExistential() {
  print("testExistential")
  let existentials: [Summable] = [a, b, c]
  for e in existentials {
    total += invoke1(e)
    // Element 0 ends up here:
    //
    // x`protocol witness for Summable.sum() in conformance X<A>:
    // ->  0x100002190 <+0>: pushq  %rbp
    //     0x100002191 <+1>: movq   %rsp, %rbp
    //     0x100002194 <+4>: popq   %rbp
    //     0x100002195 <+5>: jmp    0x100001b40               ; x.X.sum() -> Swift.Int at Erasure.swift:14
    //
    // which leads to 426 lines of assembly including calls to
    // - swift_getAssociatedTypeWitness
    // - __chkstk_darwin (many!)
    // - type metadata accessor for Swift.Optional
    // - outlined init with copy of Swift.Optional<A>
    // - swift_getAssociatedConformanceWitness
    // - dispatch thunk of Swift._ExpressibleByBuiltinIntegerLiteral.init(_builtinIntegerLiteral: Builtin.IntLiteral) -> A
    // - dispatch thunk of Swift.ExpressibleByIntegerLiteral.init(integerLiteral: A.IntegerLiteralType) -> A
    // - dispatch thunk of static Swift.BinaryInteger.isSigned.getter : Swift.Bool
    // - dispatch thunk of Swift.BinaryInteger.bitWidth.getter : Swift.Int
    // - dispatch thunk of static Swift.BinaryInteger.isSigned.getter : Swift.Bool
    // - dispatch thunk of static Swift.Comparable.< infix(A, A) -> Swift.Bool
    // - dispatch thunk of static Swift.Equatable.== infix(A, A) -> Swift.Bool
    // - lazy protocol witness table accessor for type SwifDist.Int and conformance Swift.Int : Swift.BinaryInteger
    // ... the list goes on ...

    // Element 1 ends up here:
    //
    // x`protocol witness for Summable.sum() in conformance Int:
    // ->  0x100001b30 <+0>:  pushq  %rbp
    //     0x100001b31 <+1>:  movq   %rsp, %rbp
    //     0x100001b34 <+4>:  movq   (%r13), %rax
    //     0x100001b38 <+8>:  popq   %rbp
    //     0x100001b39 <+9>:  retq   

    // Element 2 ends up here:
    //
    // x`protocol witness for Summable.sum() in conformance <A> Y<A>:
    //     0x1000021a0 <+0>:  pushq  %rbp
    //     0x1000021a1 <+1>:  movq   %rsp, %rbp
    //     0x1000021a4 <+4>:  cmpb   $0x0, 0x8(%r13)
    // ->  0x1000021a9 <+9>:  je     0x1000021af               ; <+15> at Erasure.swift
    //     0x1000021ab <+11>: xorl   %eax, %eax
    //     0x1000021ad <+13>: popq   %rbp
    //     0x1000021ae <+14>: retq   
    //     0x1000021af <+15>: movq   (%r13), %rax
    //     0x1000021b3 <+19>: testq  %rax, %rax
    //     0x1000021b6 <+22>: js     0x1000021ba               ; <+26> [inlined] generic specialization <Swift.Int, Swift.UInt> of (extension in Swift):Swift.SignedInteger< where A: Swift.FixedWidthInteger>.init<A where A1: Swift.BinaryInteger>(A1) -> A at Erasure.swift:20
    //     0x1000021b8 <+24>: popq   %rbp
    //     0x1000021b9 <+25>: retq
  }
}
testExistential()

// -----------------------------------------------------------------------------
// Erase via protocol type.  This method generates no code for lifetime
// management of closure captures, class instances, or existential boxes.
// Unfortunately it optimizes about the same as the above.
extension Summable {
  static func getSum(_ p: UnsafeRawPointer) -> Int {
    p.assumingMemoryBound(to: Self.self).pointee.sum()
  }
}

typealias ProtocolType = Summable.Type
@inline(never)
func invoke4(_ f: ProtocolType, on x: UnsafeRawPointer) -> Int {
  f.getSum(x)
}

func protocolType<S: Summable>(_ s: S) -> ProtocolType {
  FALSE ? Int.self : S.self
}

@inline(never)
func testProtocolType() {
  print("testProtocolType")
  withUnsafePointer(to: a) { ap in
    withUnsafePointer(to: b) { bp in
      withUnsafePointer(to: c) { cp in
        let protocolTypes: [(ProtocolType, UnsafeRawPointer)] = [
          (protocolType(a), .init(ap)),
          (protocolType(b), .init(bp)),
          (protocolType(c), .init(cp))]
        for (f, x) in protocolTypes {
          // Results are similar to the above.
          total += invoke4(f, on: x)
        }
      }
    }
  }
}
testProtocolType()

// -----------------------------------------------------------------------------
// Erase via class type.  This method generates no code for lifetime
// management of closure captures, class instances, or existential boxes.
// Unfortunately it optimizes about the same as the above.
class SummerBase {
  class func getSum(_ p: UnsafeRawPointer) -> Int { fatalError("implement me") }
}
  
class Summer<T: Summable> : SummerBase {
  override class func getSum(_ p: UnsafeRawPointer) -> Int {
    p.assumingMemoryBound(to: T.self).pointee.sum()
  }
}

typealias ClassType = SummerBase.Type
@inline(never)
func invoke5(_ f: ClassType, on x: UnsafeRawPointer) -> Int {
  f.getSum(x)
}

func classType<S: Summable>(_ s: S) -> ClassType {
  FALSE ? Summer<Int>.self : Summer<S>.self
}

@inline(never)
func testClassType() {
  print("testClassType")
  withUnsafePointer(to: a) { ap in
    withUnsafePointer(to: b) { bp in
      withUnsafePointer(to: c) { cp in
        let classTypes: [(ClassType, UnsafeRawPointer)] = [
          (classType(a), .init(ap)),
          (classType(b), .init(bp)),
          (classType(c), .init(cp))]
        for (f, x) in classTypes {
          // Results are similar to the above.
          total += invoke5(f, on: x)
        }
      }
    }
  }
}
testClassType()

// -----------------------------------------------------------------------------
// Erase via class instance. This method _may_ be the worst of all worlds: it
// generates allocations even when the instance could fit inline in an
// existential and generates consequent ARC traffic. Erases value semantics
// unless all operations are nonmutating or you do CoW manually. Invocation
// optimizes about the same as the above.
class AnySummable {
  func sum() -> Int { fatalError("implement me") }
}
  
class SummableBox<T: Summable> : AnySummable {
  let value: T
  init(value: T) { self.value = value }
  override func sum() -> Int {
    value.sum()
  }
}

typealias ClassInstance = AnySummable
@inline(never)
func invoke6(_ s: ClassInstance) -> Int {
  s.sum()
}

func classInstance<S: Summable>(_ s: S) -> ClassInstance {
  FALSE ? SummableBox(value: 0) : SummableBox(value: s)
}

@inline(never)
func testClassInstance() {
  print("testClassInstance")
  let classInstances = [classInstance(a), classInstance(b), classInstance(c)]
  for c in classInstances {
    total += invoke6(c)
  }
}
testClassInstance()

// =============================================================================
// The rest of these methods, based on functions, optimize well, but they have
// other drawbacks.  None of them generalize well to a “table” of multiple
// operations (e.g. if you had another type-erased operation besides "sum()"),
// and all at least generate retain/release calls even when there's no capture
// to manage.  Other downsides noted below.
// =============================================================================

// -----------------------------------------------------------------------------
// Erase via a function that captures the `Summable`.  Incurs allocation for
// captured value
func capturedSum<S: Summable>(_ s: S) -> ()->Int {
  FALSE ? { 0 } : { s.sum() }
}

typealias CapturingFunction = ()->Int
@inline(never)
func invoke2(_ x: CapturingFunction) -> Int {
  return x()
}

@inline(never)
func testCapturingFunction() {
  print("testCapturingFunction")
  let capturingFunctions = [capturedSum(a), capturedSum(b), capturedSum(c)]
  for f in capturingFunctions {
    total += invoke2(f)
  }
}
testCapturingFunction()

// -----------------------------------------------------------------------------
// Erase via a partially applied method. Essentially identical to the above.
func partialApplication<S: Summable>(_ s: S) -> ()->Int {
  FALSE ? { 0 } : s.sum
}

@inline(never)
func testPartialApplication() {
  print("testPartialApplication")
  let partialApplications = [
    partialApplication(a), partialApplication(b), partialApplication(c)]
  for f in partialApplications {
    total += invoke2(f)
  }
}
testPartialApplication()

// -----------------------------------------------------------------------------
// Erase via non-capturing function.  No allocation for captures, but ARC
// calls are generated (code size) and happen (small perf cost) anyway.
typealias NonCapturingFunction = (UnsafeRawPointer)->Int
@inline(never)
func invoke3(_ f: NonCapturingFunction, on x: UnsafeRawPointer) -> Int {
  f(x)
}

func nonCapturingFunction<S: Summable>(_ s: S) -> NonCapturingFunction {
  FALSE ? { _ in  0 } : { p in p.assumingMemoryBound(to: S.self).pointee.sum() }
}

@inline(never)
func testNonCapturingFunction() {
  print("testNonCapturingFunction")
  withUnsafePointer(to: a) { ap in
    withUnsafePointer(to: b) { bp in
      withUnsafePointer(to: c) { cp in
        let nonCapturingFunctions: [(NonCapturingFunction, UnsafeRawPointer)] = [
          (nonCapturingFunction(a), .init(ap)),
          (nonCapturingFunction(b), .init(bp)),
          (nonCapturingFunction(c), .init(cp))]
        for (f, x) in nonCapturingFunctions {
          total += invoke3(f, on: x)
        }
      }
    }
  }
}
testNonCapturingFunction()

print("done. total =", total)