[swift-dev] Implementation of Existential Collection (AnySequence and co.)

[Ole Begemann]

On 05.04.2017 00:33, Pavol Vaskovic via swift-dev wrote:
> Hello,
>
> I’ve been familiarizing myself with the implementation details of the `AnySequence` and related types, because I’ve encountered strange performance behavior when using them. I have a few questions as a result. I might also hold incorrect assumptions about how Swift works, so please be gentle and educate me. Also excuse the lengthy URLs at the bottom — I’ll be linking to the sources that are at the tip of the master branch at the moment of this writing, so that the links keep working correctly in the future, too.
>
> ## Performance of Methods Constructed in Initializers
>
> The `_ClosureBasedIterator` is initialized with a closure that is stored in a constant stored property (`let`) and gets forwarded to inside the `func next() -> Element?`. [1][] I also find this pattern very useful in my code, but I wonder about its cost. If this pattern is used on a struct, the direct dispatch should be able to go directly to the underlying implementation, right?
>
> I guess the cost will depend on the type of closure passed in: if it captured any references, the whole struct incurs reference counting penalty. Can the compiler optimize for closures that don’t capture any references and turn this pattern into kind of “compile-time dynamic” constructor, that is equal in performance to the struct that has the same method implemented directly?
> Given this pattern is often used in conjunction with generics, does this pattern affect the compiler’s ability to specialize?
>
> ## `let` vs `var` for closures
>
> What is the performance implication (impact on eligible compiler optimizations) of storing closure in a `var` instead of `let`?
>
> The `_ClosureBasedSequence` stores the escaping closure to `_makeUnderlyingIterator` in a var. [2][]
> Based on the example of `_ClosureBasedIterator` and given that it is never mutated, I believe it should be a `let`.
>
> ## Abstract Base Class with Single Concrete Implementation
>
> What is the purpose of having an internal abstract base `class _AnyIteratorBoxBase`[3][], that is only inherited by the `internal final class _IteratorBox`? [4][] It is used as the type to store the underlying base in the `struct AnyIterator`, but the initializers in `AnyIterator` create only concrete instances of `_IteratorBox` and the remaining occurrence of `_AnyIteratorBoxBase` is as parameter for `internal init` that isn’t used anywhere. My search found no other subclasses of `_AnyIteratorBoxBase`, so I guess this is not an extension point.
This is not an answer to your performance questions, but I believe I can 
explain why the `_AnyIteratorBoxBase` base class is needed.

The purpose of `AnyIterator<Element>` is to hide the specific type of 
the iterator it wraps. Hence it can't have a property whose type is 
generic over the iterator type `I` (because then `AnyIterator` would 
have to be generic over `I` too). Hence `AnyIterator` can't have a 
property `let _box: _IteratorBox<I>` directly.

Here's where the base class comes in. `_AnyIteratorBoxBase` is _not_ 
generic over `I` and thus erases the iterator type. Only the initializer 
must be generic over `I` because it's the only place that needs to 
handle the concrete `_IteratorBox<I>` type.
> If my understanding of how method dispatch works in Swift is correct, this prevents direct dispatch and devolves into table dispatch to the underlying base implementation in `public func next() -> Element?`. Or is the compiler able to devirtualize this given the two public initializers only use the `final class _IteratorBox`?
>
> ## Links
> [1]: https://github.com/apple/swift/blob/29ad714bb77913afb26be7507483f5ff3d167d21/stdlib/public/core/ExistentialCollection.swift.gyb#L107
> [2]: https://github.com/apple/swift/blob/29ad714bb77913afb26be7507483f5ff3d167d21/stdlib/public/core/ExistentialCollection.swift.gyb#L729
> [3]: https://github.com/apple/swift/blob/29ad714bb77913afb26be7507483f5ff3d167d21/stdlib/public/core/ExistentialCollection.swift.gyb#L135
> [4]: https://github.com/apple/swift/blob/29ad714bb77913afb26be7507483f5ff3d167d21/stdlib/public/core/ExistentialCollection.swift.gyb#L148
>
> Best regards
> Pavol Vaskovic
>
>
>
> _______________________________________________
> swift-dev mailing list
> swift-dev at swift.org
> https://lists.swift.org/mailman/listinfo/swift-dev