Implementation of Type Erasers


(Chris Eidhof) #1

Hello swift-dev,

I was wondering why type erasers (e.g. for AnyIterator) are implemented the
way they are. I would implement AnyIterator like this:

final class MyAnyIterator<A>: IteratorProtocol {
    var nextImpl: () -> A?

    init<I: IteratorProtocol>(iterator: I) where I.Element == A {
        var copy = iterator
        nextImpl = { copy.next() }
    }

    func next() -> A? {
        return nextImpl()
    }
}

Instead, it is implemented in a class which contains a box. The trick with
subclassing and generics to actually erase the type feels like a bit of a
hack, but I figured it would be there for performance reasons. In my
limited testing, I noticed my version is 20% slower when compiling without
optimizations. I didn't really understand why, even after reading through
the SIL. However, when compiling with optimizations, I noticed my version
is 10% faster.

I would like to make a PR to change the stdlib, but before I go through the
hassle, I'd like to hear what the reasons (at the time?) were for the
current solution. Maybe it's just that the optimizer got better?

Thanks!

(Apologies if you receive this mail twice, my first message bounced saying
it was waiting for moderator approval, it didn't seem to get approved)

···

--
Chris Eidhof


(Dmitri Gribenko) #2

Your approach requires adding a new closure property for every method
that is forwarded. Subclassing does not require that.

If you see a case where performance is not good, we would appreciate a
bugreport at https://bugs.swift.org/ . Please attach a self-contained
reproducer. Thank you.

Dmitri

···

On Mon, Sep 5, 2016 at 11:13 AM, Chris Eidhof via swift-dev <swift-dev@swift.org> wrote:

Hello swift-dev,

I was wondering why type erasers (e.g. for AnyIterator) are implemented the
way they are. I would implement AnyIterator like this:

final class MyAnyIterator<A>: IteratorProtocol {
    var nextImpl: () -> A?

    init<I: IteratorProtocol>(iterator: I) where I.Element == A {
        var copy = iterator
        nextImpl = { copy.next() }
    }

    func next() -> A? {
        return nextImpl()
    }
}

Instead, it is implemented in a class which contains a box.

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/


(Chris Eidhof) #3

Thanks! That explains a lot.

In my version, performance only is improved by 10%, so I'm not sure if the
tradeoff is worth it:

In the isolated case of AnyIterator, there's only one method, so the sizeof
is the same (and the performance is worth it). In the case of AnySequence,
it would be a lot more work to write the implementation (and the size would
change a lot). Having two different mechanisms for type erasure seems like
it might confuse things even more.

···

On Mon, Sep 5, 2016 at 9:50 PM, Dmitri Gribenko <gribozavr@gmail.com> wrote:

On Mon, Sep 5, 2016 at 11:13 AM, Chris Eidhof via swift-dev > <swift-dev@swift.org> wrote:
> Hello swift-dev,
>
> I was wondering why type erasers (e.g. for AnyIterator) are implemented
the
> way they are. I would implement AnyIterator like this:
>
> final class MyAnyIterator<A>: IteratorProtocol {
> var nextImpl: () -> A?
>
> init<I: IteratorProtocol>(iterator: I) where I.Element == A {
> var copy = iterator
> nextImpl = { copy.next() }
> }
>
> func next() -> A? {
> return nextImpl()
> }
> }
>
> Instead, it is implemented in a class which contains a box.

Your approach requires adding a new closure property for every method
that is forwarded. Subclassing does not require that.

If you see a case where performance is not good, we would appreciate a
bugreport at https://bugs.swift.org/ . Please attach a self-contained
reproducer. Thank you.

Dmitri

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/

--
Chris Eidhof


(Dave Abrahams) #4

Thanks! That explains a lot.

In my version, performance only is improved by 10%, so I'm not sure if the
tradeoff is worth it:

In the isolated case of AnyIterator, there's only one method, so the sizeof
is the same (and the performance is worth it). In the case of AnySequence,
it would be a lot more work to write the implementation (and the size would
change a lot). Having two different mechanisms for type erasure seems like
it might confuse things even more.

We'll happily take a litte more implementation complexity in exchange
for performance gains. 10% is nothing to sneeze at.

···

on Tue Sep 06 2016, Chris Eidhof <swift-dev-AT-swift.org> wrote:

On Mon, Sep 5, 2016 at 9:50 PM, Dmitri Gribenko <gribozavr@gmail.com> wrote:

On Mon, Sep 5, 2016 at 11:13 AM, Chris Eidhof via swift-dev >> <swift-dev@swift.org> wrote:
> Hello swift-dev,
>
> I was wondering why type erasers (e.g. for AnyIterator) are implemented
the
> way they are. I would implement AnyIterator like this:
>
> final class MyAnyIterator<A>: IteratorProtocol {
> var nextImpl: () -> A?
>
> init<I: IteratorProtocol>(iterator: I) where I.Element == A {
> var copy = iterator
> nextImpl = { copy.next() }
> }
>
> func next() -> A? {
> return nextImpl()
> }
> }
>
> Instead, it is implemented in a class which contains a box.

Your approach requires adding a new closure property for every method
that is forwarded. Subclassing does not require that.

If you see a case where performance is not good, we would appreciate a
bugreport at https://bugs.swift.org/ . Please attach a self-contained
reproducer. Thank you.

Dmitri

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/

--
-Dave


(Chris Eidhof) #5

Hm. I'm not sure if the performance difference is a hard limitation because
of implementation decisions, or if it would be possible to make the current
implementation as fast as the closure-based implementation. I don't
understand enough about the codegen (and about possible optimizations) to
make that decision. Anyone who's willing to help me there?

···

On Thu, Sep 15, 2016 at 5:01 PM, Dave Abrahams via swift-dev < swift-dev@swift.org> wrote:

on Tue Sep 06 2016, Chris Eidhof <swift-dev-AT-swift.org> wrote:

> Thanks! That explains a lot.
>
> In my version, performance only is improved by 10%, so I'm not sure if
the
> tradeoff is worth it:
>
> In the isolated case of AnyIterator, there's only one method, so the
sizeof
> is the same (and the performance is worth it). In the case of
AnySequence,
> it would be a lot more work to write the implementation (and the size
would
> change a lot). Having two different mechanisms for type erasure seems
like
> it might confuse things even more.

We'll happily take a litte more implementation complexity in exchange
for performance gains. 10% is nothing to sneeze at.

> On Mon, Sep 5, 2016 at 9:50 PM, Dmitri Gribenko <gribozavr@gmail.com> > wrote:
>
>> On Mon, Sep 5, 2016 at 11:13 AM, Chris Eidhof via swift-dev > >> <swift-dev@swift.org> wrote:
>> > Hello swift-dev,
>> >
>> > I was wondering why type erasers (e.g. for AnyIterator) are
implemented
>> the
>> > way they are. I would implement AnyIterator like this:
>> >
>> > final class MyAnyIterator<A>: IteratorProtocol {
>> > var nextImpl: () -> A?
>> >
>> > init<I: IteratorProtocol>(iterator: I) where I.Element == A {
>> > var copy = iterator
>> > nextImpl = { copy.next() }
>> > }
>> >
>> > func next() -> A? {
>> > return nextImpl()
>> > }
>> > }
>> >
>> > Instead, it is implemented in a class which contains a box.
>>
>> Your approach requires adding a new closure property for every method
>> that is forwarded. Subclassing does not require that.
>>
>> If you see a case where performance is not good, we would appreciate a
>> bugreport at https://bugs.swift.org/ . Please attach a self-contained
>> reproducer. Thank you.
>>
>> Dmitri
>>
>> --
>> main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
>> (j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/
>>

--
-Dave

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

--
Chris Eidhof


(Chris Eidhof) #6

Oh, also: for AnyIterator it was a pretty clear performance gain (in my
testing). I haven't tested other erasers such as AnySequence, but even if
they're faster, they will have to store more closures (instead of a single
base pointer) and will thus have memory overhead...

···

On Mon, Sep 19, 2016 at 9:43 AM, Chris Eidhof <chris@eidhof.nl> wrote:

Hm. I'm not sure if the performance difference is a hard limitation
because of implementation decisions, or if it would be possible to make the
current implementation as fast as the closure-based implementation. I don't
understand enough about the codegen (and about possible optimizations) to
make that decision. Anyone who's willing to help me there?

On Thu, Sep 15, 2016 at 5:01 PM, Dave Abrahams via swift-dev < > swift-dev@swift.org> wrote:

on Tue Sep 06 2016, Chris Eidhof <swift-dev-AT-swift.org> wrote:

> Thanks! That explains a lot.
>
> In my version, performance only is improved by 10%, so I'm not sure if
the
> tradeoff is worth it:
>
> In the isolated case of AnyIterator, there's only one method, so the
sizeof
> is the same (and the performance is worth it). In the case of
AnySequence,
> it would be a lot more work to write the implementation (and the size
would
> change a lot). Having two different mechanisms for type erasure seems
like
> it might confuse things even more.

We'll happily take a litte more implementation complexity in exchange
for performance gains. 10% is nothing to sneeze at.

> On Mon, Sep 5, 2016 at 9:50 PM, Dmitri Gribenko <gribozavr@gmail.com> >> wrote:
>
>> On Mon, Sep 5, 2016 at 11:13 AM, Chris Eidhof via swift-dev >> >> <swift-dev@swift.org> wrote:
>> > Hello swift-dev,
>> >
>> > I was wondering why type erasers (e.g. for AnyIterator) are
implemented
>> the
>> > way they are. I would implement AnyIterator like this:
>> >
>> > final class MyAnyIterator<A>: IteratorProtocol {
>> > var nextImpl: () -> A?
>> >
>> > init<I: IteratorProtocol>(iterator: I) where I.Element == A {
>> > var copy = iterator
>> > nextImpl = { copy.next() }
>> > }
>> >
>> > func next() -> A? {
>> > return nextImpl()
>> > }
>> > }
>> >
>> > Instead, it is implemented in a class which contains a box.
>>
>> Your approach requires adding a new closure property for every method
>> that is forwarded. Subclassing does not require that.
>>
>> If you see a case where performance is not good, we would appreciate a
>> bugreport at https://bugs.swift.org/ . Please attach a self-contained
>> reproducer. Thank you.
>>
>> Dmitri
>>
>> --
>> main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
>> (j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/
>>

--
-Dave

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

--
Chris Eidhof

--
Chris Eidhof