Implementation of Existential Collection (AnySequence and co.)

palimondo · April 4, 2017, 10:33pm

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.

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]: swift/ExistentialCollection.swift.gyb at 29ad714bb77913afb26be7507483f5ff3d167d21 · apple/swift · GitHub
[2]: swift/ExistentialCollection.swift.gyb at 29ad714bb77913afb26be7507483f5ff3d167d21 · apple/swift · GitHub
[3]: swift/ExistentialCollection.swift.gyb at 29ad714bb77913afb26be7507483f5ff3d167d21 · apple/swift · GitHub
[4]: swift/ExistentialCollection.swift.gyb at 29ad714bb77913afb26be7507483f5ff3d167d21 · apple/swift · GitHub

Best regards
Pavol Vaskovic

ole · April 5, 2017, 9:59am

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` 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` type.

···

On 05.04.2017 00:33, Pavol Vaskovic via swift-dev wrote:

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@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev

palimondo · April 5, 2017, 12:56pm

Thanks Ole! This explanation of type erasure makes total sense. I have overlooked they are generic over different axis.

But I think I have confirmed the performance implications of this design and created [SR-4499] Iterating over elements from existential collections is super slow · Issue #47076 · apple/swift · GitHub to track the issue.
As is, all elements that get vended through this are being created using virtual dispatch on generic protocol - super slow.

If I recall correctly, there is alternative approach to type erasure using closures, but its possible it has similar performance characteristics?
Does this show a need for a different approach to type erasure in Swift? Some language or compiler support?

Best regards
Pavol Vaskovic

···

On Wednesday, 5 April 2017 at 11:59, Ole Begemann wrote:

On 05.04.2017 00:33, Pavol Vaskovic via swift-dev wrote:
> ## 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` 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` type.

palimondo · April 5, 2017, 1:22pm

Why exactly isn’t `AnyIterator` implemented like this?

public struct AnyIterator<Element> : IteratorProtocol, Sequence {
let _next: () -> Element?
public init(_ base: I) where I.Element == Element {
var _base = base
_next = { return _base.next() }
}
public init(_ next: @escaping () -> Element?) {
_next = next
}
public func next() -> Element? {
return _next()
}
}

It seems to me this is using the same "Methods Constructed in Initializers” pattern I was asking about Re: `_ClosureBasedIterator`.

Best regards
Pavol Vaskovic

···

On Wednesday, 5 April 2017 at 14:56, Pavol Vaskovic wrote:

Thanks Ole! This explanation of type erasure makes total sense. I have overlooked they are generic over different axis.

But I think I have confirmed the performance implications of this design and created [SR-4499] Iterating over elements from existential collections is super slow · Issue #47076 · apple/swift · GitHub to track the issue.
As is, all elements that get vended through this are being created using virtual dispatch on generic protocol - super slow.

If I recall correctly, there is alternative approach to type erasure using closures, but its possible it has similar performance characteristics?

ole · April 5, 2017, 2:00pm

One reason to favor the class-based approach to type erasure is that the closure-based approach requires more storage if the protocol you're implementing has multiple methods — the closure-based approach requires storage for one closure per method vs. storage for a single reference in the class-based approach.

This argument doesn't really apply to AnyIterator since IteratorProtocol only defines a single method, though. I'm not sure why the standard library prefers the class-based approach.

···

On 05.04.2017 15:22, Pavol Vaskovic via swift-dev wrote:

On Wednesday, 5 April 2017 at 14:56, Pavol Vaskovic wrote:

Thanks Ole! This explanation of type erasure makes total sense. I have overlooked they are generic over different axis.
But I think I have confirmed the performance implications of this design and created [SR-4499] Iterating over elements from existential collections is super slow · Issue #47076 · apple/swift · GitHub to track the issue.
As is, all elements that get vended through this are being created using virtual dispatch on generic protocol - super slow.
If I recall correctly, there is alternative approach to type erasure using closures, but its possible it has similar performance characteristics?

Why exactly isn’t `AnyIterator` implemented like this?

public struct AnyIterator<Element> : IteratorProtocol, Sequence {
let _next: () -> Element?
public init(_ base: I) where I.Element == Element {
var _base = base
_next = { return _base.next() }
}
public init(_ next: @escaping () -> Element?) {
_next = next
}
public func next() -> Element? {
return _next()
}

It seems to me this is using the same "Methods Constructed in Initializers” pattern I was asking about Re: `_ClosureBasedIterator`.

rintaro · April 5, 2017, 2:04pm

Just FYI

Implementation of Type Erasers
https://lists.swift.org/pipermail/swift-dev/Week-of-Mon-20160905/002852.html

···

2017-04-05 22:22 GMT+09:00 Pavol Vaskovic via swift-dev <swift-dev@swift.org >:

On Wednesday, 5 April 2017 at 14:56, Pavol Vaskovic wrote:
> Thanks Ole! This explanation of type erasure makes total sense. I have
overlooked they are generic over different axis.
>
> But I think I have confirmed the performance implications of this design
and created [SR-4499] Iterating over elements from existential collections is super slow · Issue #47076 · apple/swift · GitHub to track the issue.
> As is, all elements that get vended through this are being created using
virtual dispatch on generic protocol - super slow.
>
> If I recall correctly, there is alternative approach to type erasure
using closures, but its possible it has similar performance characteristics?
Why exactly isn’t `AnyIterator` implemented like this?

public struct AnyIterator<Element> : IteratorProtocol, Sequence {
let _next: () -> Element?
public init(_ base: I) where I.Element == Element {
var _base = base
_next = { return _base.next() }
}
public init(_ next: @escaping () -> Element?) {
_next = next
}
public func next() -> Element? {
return _next()
}
}

It seems to me this is using the same "Methods Constructed in
Initializers” pattern I was asking about Re: `_ClosureBasedIterator`.

Best regards
Pavol Vaskovic

_______________________________________________
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev

palimondo · April 5, 2017, 4:56pm

Thanks for that link!

This looks like a followup to Chris’s question, so I’m pinging Dmitri to chime in on this.

Bug report: [SR-4499] Iterating over elements from existential collections is super slow · Issue #47076 · apple/swift · GitHub

For a reproducer, see the benchmark for `run_SuffixAnySequence` - that is utterly dominated by wending elements from the underlying sequence using generic witness table. There is no specialization occurring at all. As I’ve reasoned in my original e-mail, this is understandable - semantics of _AnyIteratorBox used in AnyIterator’s `next` method require virtual dispatch.

Closure based approach to type erasure should’t have such a semantic barrier for optimization - the limit would probably just be currently conservative optimization?

Best regards
Pavol Vaskovic

···

On Wednesday, 5 April 2017 at 16:04, rintaro ishizaki wrote:

Just FYI

Implementation of Type Erasers
[swift-dev] Implementation of Type Erasers

palimondo · April 8, 2017, 8:45pm

Jordan Rose says in the comment on SR-4499 that Dmitri no longer works on
Swift. Who owns that part of code now?

Also, who is able to answer my original questions from this thread?

--Pavol

···

On Wed, 5 Apr 2017 at 18:56, Pavol Vaskovic <pali@pali.sk> wrote:

On Wednesday, 5 April 2017 at 16:04, rintaro ishizaki wrote:
> Just FYI
>
> Implementation of Type Erasers
>
[swift-dev] Implementation of Type Erasers

Thanks for that link!

This looks like a followup to Chris’s question, so I’m pinging Dmitri to
chime in on this.

Bug report: [SR-4499] Iterating over elements from existential collections is super slow · Issue #47076 · apple/swift · GitHub

For a reproducer, see the benchmark for `run_SuffixAnySequence` - that is
utterly dominated by wending elements from the underlying sequence using
generic witness table. There is no specialization occurring at all. As I’ve
reasoned in my original e-mail, this is understandable - semantics of
_AnyIteratorBox used in AnyIterator’s `next` method require virtual
dispatch.

Closure based approach to type erasure should’t have such a semantic
barrier for optimization - the limit would probably just be currently
conservative optimization?

Best regards
Pavol Vaskovic

Luke_Larson · April 8, 2017, 9:11pm

David Abrahams is the code owner for the Swift standard library.

Luke

···

On Apr 8, 2017, at 1:45 PM, Pavol Vaskovic via swift-dev <swift-dev@swift.org> wrote:

Jordan Rose says in the comment on SR-4499 that Dmitri no longer works on Swift. Who owns that part of code now?

Also, who is able to answer my original questions from this thread?

--Pavol

On Wed, 5 Apr 2017 at 18:56, Pavol Vaskovic <pali@pali.sk <mailto:pali@pali.sk>> wrote:
On Wednesday, 5 April 2017 at 16:04, rintaro ishizaki wrote:
> Just FYI
>
> Implementation of Type Erasers
> [swift-dev] Implementation of Type Erasers

Thanks for that link!

This looks like a followup to Chris’s question, so I’m pinging Dmitri to chime in on this.

Bug report: [SR-4499] Iterating over elements from existential collections is super slow · Issue #47076 · apple/swift · GitHub

For a reproducer, see the benchmark for `run_SuffixAnySequence` - that is utterly dominated by wending elements from the underlying sequence using generic witness table. There is no specialization occurring at all. As I’ve reasoned in my original e-mail, this is understandable - semantics of _AnyIteratorBox used in AnyIterator’s `next` method require virtual dispatch.

Closure based approach to type erasure should’t have such a semantic barrier for optimization - the limit would probably just be currently conservative optimization?

Best regards
Pavol Vaskovic
_______________________________________________
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev