Understanding Swift Performance - Apple WWDC 2016

By: Swift Language

52   2   5215

Uploaded on 06/28/2016

In this advanced session, find out how structs, classes, protocols, and generics are implemented in Swift. Learn about their relative costs in different dimensions of performance. See how to apply this information to speed up your code. Learn more about Swift at https://swiftlang.eu

Comments (6):

By anonymous    2017-09-20

Protocol-typed values are represented using an 'existential container' (see this great WWDC talk on them; or on Youtube), which consists of a value-buffer of fixed size in order to store the value (if the value size exceeds this, it'll heap allocate), a pointer to the protocol witness table in order to lookup method implementations and a pointer to the value witness table in order to manage the lifetime of the value.

Unspecialised generics use pretty much the same format (I go into this in slightly more depth in this Q&A) – when they're called, pointers to the protocol and value witness tables are passed to the function, and the value itself is stored locally inside the function using a value-buffer, which will heap allocate for values larger than that buffer.

Therefore, because of the sheer similarity in how these are implemented, we can draw the conclusion that not being able to talk in terms of protocols with associated types or Self constraints outside of generics is just a current limitation of the language. There's no real technical reason why it's not possible, it just hasn't been implemented (yet).

Here's an excerpt from the Generics Manifesto on "Generalized existentials", which discusses how this could work in practice:

The restrictions on existential types came from an implementation limitation, but it is reasonable to allow a value of protocol type even when the protocol has Self constraints or associated types. For example, consider IteratorProtocol again and how it could be used as an existential:

protocol IteratorProtocol {
  associatedtype Element
  mutating func next() -> Element?
}

let it: IteratorProtocol = ...
it.next()   // if this is permitted, it could return an "Any?", i.e., the existential that wraps the actual element

Additionally, it is reasonable to want to constrain the associated types of an existential, e.g., "a Sequence whose element type is String" could be expressed by putting a where clause into protocol<...> or Any<...> (per "Renaming protocol<...> to Any<...>"):

let strings: Any<Sequence where .Iterator.Element == String> = ["a", "b", "c"]

The leading . indicates that we're talking about the dynamic type, i.e., the Self type that's conforming to the Sequence protocol. There's no reason why we cannot support arbitrary where clauses within the Any<...>.

And from being able to type a value as a protocol with an associated type, it's but a short step to allow for type-casting to that given type, and thus allow something like your first extension to compile.

Original Thread

By anonymous    2017-09-20

This is indeed correct behaviour as overload resolution takes place at compile time (it would be a pretty expensive operation to take place at runtime). Therefore from within test(value:), the only thing the compiler knows about value is that it's of some type that conforms to DispatchType – thus the only overload it can dispatch to is func doBar<D : DispatchType>(value: D).

Things would be different if generic functions were always specialised by the compiler, because then a specialised implementation of test(value:) would know the concrete type of value and thus be able to pick the appropriate overload. However, specialisation of generic functions is currently only an optimisation (as without inlining, it can add significant bloat to your code), so this doesn't change the observed behaviour.

One solution in order to allow for polymorphism is to leverage the protocol witness table (see this great WWDC talk on them) by adding doBar() as a protocol requirement, and implementing the specialised implementations of it in the respective classes that conform to the protocol, with the general implementation being a part of the protocol extension.

This will allow for the dynamic dispatch of doBar(), thus allowing it to be called from test(value:) and having the correct implementation called.

protocol DispatchType {
    func doBar()
}

extension DispatchType {
    func doBar() {
        print("general function called")
    }
}

class DispatchType1: DispatchType {
    func doBar() {
        print("DispatchType1 called")
    }
}

class DispatchType2: DispatchType {
    func doBar() {
        print("DispatchType2 called")
    }
}

func test<D : DispatchType>(value: D) {
    value.doBar()
}

let d1 = DispatchType1()
let d2 = DispatchType2()

test(value: d1)    // "DispatchType1 called"
test(value: d2)    // "DispatchType2 called"

Original Thread

By anonymous    2017-09-20

There are two main problems with what you're trying to do here.

1. Overload resolution favours supertypes over optional promotion

You've declared your == overload for Item! parameters rather than Item parameters. By doing so, the type checker is weighing more in favour of statically dispatching to NSObject's overload for ==, as it appears that the type checker favours subclass to superclass conversions over optional promotion (I haven't been able to find a source to confirm this though).

Usually, you shouldn't need to define your own overload to handle optionals. By conforming a given type to Equatable, you'll automatically get an == overload which handles equality checking between optional instances of that type.

A simpler example that demonstrates the favouring of a superclass overload over an optional subclass overload would be:

// custom operator just for testing.
infix operator <===>

class Foo {}
class Bar : Foo {}

func <===>(lhs: Foo, rhs: Foo) {
    print("Foo's overload")
}

func <===>(lhs: Bar?, rhs: Bar?) {
    print("Bar's overload")
}

let b = Bar()

b <===> b // Foo's overload

If the Bar? overload is changed to Bar – that overload will be called instead.

Therefore you should change your overload to take Item parameters instead. You'll now be able to use that overload to compare two Item instances for equality. However, this won't fully solve your problem due to the next issue.

2. Subclasses can't directly re-implement protocol requirements

Item doesn't directly conform to Equatable. Instead, it inherits from NSObject, which already conforms to Equatable. Its implementation of == just forwards onto isEqual(_:) – which by default compares memory addresses (i.e checks to see if the two instances are the exact same instance).

What this means is that if you overload == for Item, that overload is not able to be dynamically dispatched to. This is because Item doesn't get its own protocol witness table for conformance to Equatable – it instead relies on NSObject's PWT, which will dispatch to its == overload, simply invoking isEqual(_:).

(Protocol witness tables are the mechanism used in order to achieve dynamic dispatch with protocols – see this WWDC talk on them for more info.)

This will therefore prevent your overload from being called in generic contexts, including the aforementioned free == overload for optionals – explaining why it doesn't work when you attempt to compare Item? instances.

This behaviour can be seen in the following example:

class Foo : Equatable {}
class Bar : Foo {}

func ==(lhs: Foo, rhs: Foo) -> Bool { // gets added to Foo's protocol witness table.
    print("Foo's overload")           // for conformance to Equatable.
    return true
}

func ==(lhs: Bar, rhs: Bar) -> Bool { // Bar doesn't have a PWT for conformance to
    print("Foo's overload")           // Equatable (as Foo already has), so cannot 
    return true                       // dynamically dispatch to this overload.
}

func areEqual<T : Equatable>(lhs: T, rhs: T) -> Bool {
    return lhs == rhs // dynamically dispatched via the protocol witness table.
}

let b = Bar()

areEqual(lhs: b, rhs: b) // Foo's overload

So, even if you were to change your overload such that it takes an Item input, if == was ever called from a generic context on an Item instance, your overload won't get called. NSObject's overload will.

This behaviour is somewhat non-obvious, and has been filed as a bug – SR-1729. The reasoning behind it, as explained by Jordan Rose is:

[...] The subclass does not get to provide new members to satisfy the conformance. This is important because a protocol can be added to a base class in one module and a subclass created in another module.

Which makes sense, as the module in which the subclass resides would have to be recompiled in order to allow it to satisfy the conformance – which would likely result in problematic behaviour.

It's worth noting however that this limitation is only really problematic with operator requirements, as other protocol requirements can usually be overridden by subclasses. In such cases, the overriding implementations are added to the subclass' vtable, allowing for dynamic dispatch to take place as expected. However, it's currently not possible to achieve this with operators without the use of a helper method (such as isEqual(_:)).

The Solution

The solution therefore is to override NSObject's isEqual(_:) method and hash property rather than overloading == (see this Q&A for how to go about this). This will ensure that your equality implementation will always be called, regardless of the context – as your override will be added to the class' vtable, allowing for dynamic dispatch.

The reasoning behind overriding hash as well as isEqual(_:) is that you need to maintain the promise that if two objects compare equal, their hashes must be the same. All sorts of weirdness can occur otherwise, if an Item is ever hashed.

Obviously, the solution for non-NSObject derived classes would be to define your own isEqual(_:) method, and have subclasses override it (and then just have the == overload chain to it).

Original Thread

Recommended Books

    Popular Videos 286

    Submit Your Video

    If you have some great dev videos to share, please fill out this form.