IndexPath performance


(Stephan Tolksdorf) #1

Hi,

IndexPath is currently implemented using an [Int] array that is bridged to
an NSIndexPath only on demand. Since IndexPath values are primarily used
together with Objective-C APIs, wouldn't it be better to implement
IndexPath directly as an NSIndexPath wrapper, in order to avoid the
overhead of temporary array instances?

- Stephan


(Tony Parker) #2

Hi Stephan,

Do you have some benchmarks that you could share? That would help us focus performance work in the right area.

I know that 2-item IndexPaths are super common with UIKit collection view and friends, so we may just want to special case those. Unfortunately, NSIndexPath is not abstract, so subclassing it in the same way that we do for a few of the other bridged types (to use native Swift refcounting) is not easy. On the other hand, the ObjC implementation does use tagged pointers, so some NSIndexPaths are really cheap to create.

- Tony

···

On Aug 1, 2016, at 11:44 PM, Stephan Tolksdorf via swift-corelibs-dev <swift-corelibs-dev@swift.org> wrote:

Hi,

IndexPath is currently implemented using an [Int] array that is bridged to an NSIndexPath only on demand. Since IndexPath values are primarily used together with Objective-C APIs, wouldn't it be better to implement IndexPath directly as an NSIndexPath wrapper, in order to avoid the overhead of temporary array instances?

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


(Stephan Tolksdorf) #3

Hi Parker,

I noticed the IndexPath overhead when I investigated why a Swift 3
implementation of UICollectionViewLayout.layoutAttributesForElementsInRect
spent more time in malloc, free and related methods, but I don't have a
benchmark.

Is it important that IndexPath uses native Swift refcounting? It seems to
me that this type is mainly used in ObjC interop code. In native Swift code
I would always try to avoid using a dynamically sized, heap allocated array
as a data structure index. If NSIndexPath can't be bridged to a native
Swift type without introducing additional overhead, then maybe it shouldn't
be bridged at all?

- Stephan

···

On 2 August 2016 at 11:09, Tony Parker <anthony.parker@apple.com> wrote:

Hi Stephan,

Do you have some benchmarks that you could share? That would help us focus
performance work in the right area.

I know that 2-item IndexPaths are super common with UIKit collection view
and friends, so we may just want to special case those. Unfortunately,
NSIndexPath is not abstract, so subclassing it in the same way that we do
for a few of the other bridged types (to use native Swift refcounting) is
not easy. On the other hand, the ObjC implementation does use tagged
pointers, so some NSIndexPaths are really cheap to create.

- Tony

> On Aug 1, 2016, at 11:44 PM, Stephan Tolksdorf via swift-corelibs-dev < > swift-corelibs-dev@swift.org> wrote:
>
> Hi,
>
> IndexPath is currently implemented using an [Int] array that is bridged
to an NSIndexPath only on demand. Since IndexPath values are primarily used
together with Objective-C APIs, wouldn't it be better to implement
IndexPath directly as an NSIndexPath wrapper, in order to avoid the
overhead of temporary array instances?
>
> - Stephan
> _______________________________________________
> swift-corelibs-dev mailing list
> swift-corelibs-dev@swift.org
> https://lists.swift.org/mailman/listinfo/swift-corelibs-dev


(Stephan Tolksdorf) #4

Oh, I'm sorry, Tony, I was too hasty and mistook your last name for your
first name :frowning:

- Stephan

···

On 2 August 2016 at 12:04, Stephan Tolksdorf <st@quanttec.com> wrote:

Hi Parker,

I noticed the IndexPath overhead when I investigated why a Swift 3
implementation of UICollectionViewLayout.layoutAttributesForElementsInRect
spent more time in malloc, free and related methods, but I don't have a
benchmark.

Is it important that IndexPath uses native Swift refcounting? It seems to
me that this type is mainly used in ObjC interop code. In native Swift code
I would always try to avoid using a dynamically sized, heap allocated array
as a data structure index. If NSIndexPath can't be bridged to a native
Swift type without introducing additional overhead, then maybe it shouldn't
be bridged at all?

- Stephan

On 2 August 2016 at 11:09, Tony Parker <anthony.parker@apple.com> wrote:

Hi Stephan,

Do you have some benchmarks that you could share? That would help us
focus performance work in the right area.

I know that 2-item IndexPaths are super common with UIKit collection view
and friends, so we may just want to special case those. Unfortunately,
NSIndexPath is not abstract, so subclassing it in the same way that we do
for a few of the other bridged types (to use native Swift refcounting) is
not easy. On the other hand, the ObjC implementation does use tagged
pointers, so some NSIndexPaths are really cheap to create.

- Tony

> On Aug 1, 2016, at 11:44 PM, Stephan Tolksdorf via swift-corelibs-dev < >> swift-corelibs-dev@swift.org> wrote:
>
> Hi,
>
> IndexPath is currently implemented using an [Int] array that is bridged
to an NSIndexPath only on demand. Since IndexPath values are primarily used
together with Objective-C APIs, wouldn't it be better to implement
IndexPath directly as an NSIndexPath wrapper, in order to avoid the
overhead of temporary array instances?
>
> - Stephan
> _______________________________________________
> swift-corelibs-dev mailing list
> swift-corelibs-dev@swift.org
> https://lists.swift.org/mailman/listinfo/swift-corelibs-dev


(Tony Parker) #5

Hi Stephan,

Hi Parker,

I noticed the IndexPath overhead when I investigated why a Swift 3 implementation of UICollectionViewLayout.layoutAttributesForElementsInRect spent more time in malloc, free and related methods, but I don't have a benchmark.

Is it important that IndexPath uses native Swift refcounting? It seems to me that this type is mainly used in ObjC interop code. In native Swift code I would always try to avoid using a dynamically sized, heap allocated array as a data structure index. If NSIndexPath can't be bridged to a native Swift type without introducing additional overhead, then maybe it shouldn't be bridged at all?

- Stephan

I do think it is likely we could figure out some improvements here, but I’d like to start with a concrete test (and something that is representative of real world use cases). If it’s possible to extract something out of what you’ve already done, that would be really helpful. We can also file a bug on bugs.swift.org as a call for help designing a better perf test suite (we need this for all of the types, frankly).

Once we know we’re measuring the right thing, there are all kinds of interesting things we can do. If (when?) we have ABI stability in Swift 4, we may be able to also change the ObjC Foundation.framework to better cooperate with the Swift side, as we’ll be able to tie the current overlay code to a specific OS instead of having to run back several releases.

Thanks,
- Tony

···

On Aug 2, 2016, at 6:04 PM, Stephan Tolksdorf <st@quanttec.com> wrote:

On 2 August 2016 at 11:09, Tony Parker <anthony.parker@apple.com <mailto:anthony.parker@apple.com>> wrote:
Hi Stephan,

Do you have some benchmarks that you could share? That would help us focus performance work in the right area.

I know that 2-item IndexPaths are super common with UIKit collection view and friends, so we may just want to special case those. Unfortunately, NSIndexPath is not abstract, so subclassing it in the same way that we do for a few of the other bridged types (to use native Swift refcounting) is not easy. On the other hand, the ObjC implementation does use tagged pointers, so some NSIndexPaths are really cheap to create.

- Tony

> On Aug 1, 2016, at 11:44 PM, Stephan Tolksdorf via swift-corelibs-dev <swift-corelibs-dev@swift.org <mailto:swift-corelibs-dev@swift.org>> wrote:
>
> Hi,
>
> IndexPath is currently implemented using an [Int] array that is bridged to an NSIndexPath only on demand. Since IndexPath values are primarily used together with Objective-C APIs, wouldn't it be better to implement IndexPath directly as an NSIndexPath wrapper, in order to avoid the overhead of temporary array instances?
>
> - Stephan
> _______________________________________________
> swift-corelibs-dev mailing list
> swift-corelibs-dev@swift.org <mailto:swift-corelibs-dev@swift.org>
> https://lists.swift.org/mailman/listinfo/swift-corelibs-dev


(Stephan Tolksdorf) #6

Tony,

I understand why you'd ideally want to have a real-world benchmark to guide
performance optimisations, but if you require that for every
performance-related change, you set a very high bar, and that bar will
probably have the effect of biasing performance downwards, since if there
is no existing benchmark, changes that worsen performance might not get
flagged.

The fact that NSIndexPath got the tagged pointer treatment probably
indicates that its implementation has a non-negligible effect on
performance (see also
https://twitter.com/Catfish_Man/status/393249511075639296).

The current IndexPath implementation in terms of an Int array clearly
introduces unnecessary overhead in ObjC interop scenarios, so unless this
implementation of IndexPath has some benefit I don't understand, I'd argue
that it should be replaced with a straightforward wrapper around an
NSIndexPath value.

- Stephan

···

On 2 August 2016 at 12:12, Tony Parker <anthony.parker@apple.com> wrote:

Hi Stephan,

On Aug 2, 2016, at 6:04 PM, Stephan Tolksdorf <st@quanttec.com> wrote:

Hi Parker,

I noticed the IndexPath overhead when I investigated why a Swift 3
implementation of UICollectionViewLayout.layoutAttributesForElementsInRect
spent more time in malloc, free and related methods, but I don't have a
benchmark.

Is it important that IndexPath uses native Swift refcounting? It seems to
me that this type is mainly used in ObjC interop code. In native Swift code
I would always try to avoid using a dynamically sized, heap allocated array
as a data structure index. If NSIndexPath can't be bridged to a native
Swift type without introducing additional overhead, then maybe it shouldn't
be bridged at all?

- Stephan

I do think it is likely we could figure out some improvements here, but
I’d like to start with a concrete test (and something that is
representative of real world use cases). If it’s possible to extract
something out of what you’ve already done, that would be really helpful. We
can also file a bug on bugs.swift.org as a call for help designing a
better perf test suite (we need this for all of the types, frankly).

Once we know we’re measuring the right thing, there are all kinds of
interesting things we can do. If (when?) we have ABI stability in Swift 4,
we may be able to also change the ObjC Foundation.framework to better
cooperate with the Swift side, as we’ll be able to tie the current overlay
code to a specific OS instead of having to run back several releases.

Thanks,
- Tony

On 2 August 2016 at 11:09, Tony Parker <anthony.parker@apple.com> wrote:

Hi Stephan,

Do you have some benchmarks that you could share? That would help us
focus performance work in the right area.

I know that 2-item IndexPaths are super common with UIKit collection view
and friends, so we may just want to special case those. Unfortunately,
NSIndexPath is not abstract, so subclassing it in the same way that we do
for a few of the other bridged types (to use native Swift refcounting) is
not easy. On the other hand, the ObjC implementation does use tagged
pointers, so some NSIndexPaths are really cheap to create.

- Tony

> On Aug 1, 2016, at 11:44 PM, Stephan Tolksdorf via swift-corelibs-dev < >> swift-corelibs-dev@swift.org> wrote:
>
> Hi,
>
> IndexPath is currently implemented using an [Int] array that is bridged
to an NSIndexPath only on demand. Since IndexPath values are primarily used
together with Objective-C APIs, wouldn't it be better to implement
IndexPath directly as an NSIndexPath wrapper, in order to avoid the
overhead of temporary array instances?
>
> - Stephan
> _______________________________________________
> swift-corelibs-dev mailing list
> swift-corelibs-dev@swift.org
> https://lists.swift.org/mailman/listinfo/swift-corelibs-dev


(Lily Ballard) #7

I agree with Stephan, NSIndexPath performance is important and we should
avoid the overhead of allocating/freeing an array for the common case.
Instead of just always wrapping NSIndexPath, maybe we should just switch
the internal representation to something like

enum Indices {
    case one(Int)
    case two(Int, Int)
    // case three?
    case many([Int])
}

Yeah it complicates the methods a bit, and we'd have to have a custom
index instead of just using Array's index, but it avoids heap allocation
for the extremely common case of a 2-element index path (it's so common,
I don't think I've *ever* seen an NSIndexPath that didn't contain
exactly 2 indices).

-Kevin Ballard

···

On Tue, Aug 2, 2016, at 04:24 AM, Stephan Tolksdorf via swift-corelibs-dev wrote:

Tony,

I understand why you'd ideally want to have a real-world benchmark to
guide performance optimisations, but if you require that for every performance-
related change, you set a very high bar, and that bar will probably
have the effect of biasing performance downwards, since if there is no
existing benchmark, changes that worsen performance might not get
flagged.

The fact that NSIndexPath got the tagged pointer treatment probably
indicates that its implementation has a non-negligible effect on
performance (see also
https://twitter.com/Catfish_Man/status/393249511075639296).

The current IndexPath implementation in terms of an Int array clearly
introduces unnecessary overhead in ObjC interop scenarios, so unless
this implementation of IndexPath has some benefit I don't understand,
I'd argue that it should be replaced with a straightforward wrapper
around an NSIndexPath value.

- Stephan

On 2 August 2016 at 12:12, Tony Parker > <anthony.parker@apple.com> wrote:

Hi Stephan,

On Aug 2, 2016, at 6:04 PM, Stephan Tolksdorf <st@quanttec.com> >>> wrote:

Hi Parker,

I noticed the IndexPath overhead when I investigated why a Swift 3
implementation of
UICollectionViewLayout.layoutAttributesForElementsInRect spent more
time in malloc, free and related methods, but I don't have a
benchmark.

Is it important that IndexPath uses native Swift refcounting? It
seems to me that this type is mainly used in ObjC interop code. In
native Swift code I would always try to avoid using a dynamically
sized, heap allocated array as a data structure index. If
NSIndexPath can't be bridged to a native Swift type without
introducing additional overhead, then maybe it shouldn't be bridged
at all?

- Stephan

I do think it is likely we could figure out some improvements here,
but I’d like to start with a concrete test (and something that is
representative of real world use cases). If it’s possible to extract
something out of what you’ve already done, that would be really
helpful. We can also file a bug on bugs.swift.org as a call for help
designing a better perf test suite (we need this for all of the
types, frankly).

Once we know we’re measuring the right thing, there are all kinds of
interesting things we can do. If (when?) we have ABI stability in
Swift 4, we may be able to also change the ObjC Foundation.framework
to better cooperate with the Swift side, as we’ll be able to tie the
current overlay code to a specific OS instead of having to run back
several releases.

Thanks,
- Tony

On 2 August 2016 at 11:09, Tony Parker <anthony.parker@apple.com> >>> wrote:

Hi Stephan,

Do you have some benchmarks that you could share? That would help
us focus performance work in the right area.

I know that 2-item IndexPaths are super common with UIKit
collection view and friends, so we may just want to special case
those. Unfortunately, NSIndexPath is not abstract, so subclassing
it in the same way that we do for a few of the other bridged types
(to use native Swift refcounting) is not easy. On the other hand,
the ObjC implementation does use tagged pointers, so some
NSIndexPaths are really cheap to create.

- Tony

> On Aug 1, 2016, at 11:44 PM, Stephan Tolksdorf via swift-corelibs- >>>> > dev <swift-corelibs-dev@swift.org> wrote:
>
> Hi,
>
> IndexPath is currently implemented using an [Int] array that is
> bridged to an NSIndexPath only on demand. Since IndexPath values
> are primarily used together with Objective-C APIs, wouldn't it
> be better to implement IndexPath directly as an NSIndexPath
> wrapper, in order to avoid the overhead of temporary array
> instances?
>
> - Stephan
> _______________________________________________
> swift-corelibs-dev mailing list swift-corelibs-dev@swift.org
> https://lists.swift.org/mailman/listinfo/swift-corelibs-dev

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


(Lily Ballard) #8

FWIW, if you agree that this approach is reasonable, I would be willing
to write the patch for it.

-Kevin Ballard

···

On Tue, Aug 2, 2016, at 05:46 PM, Kevin Ballard wrote:

I agree with Stephan, NSIndexPath performance is important and we
should avoid the overhead of allocating/freeing an array for the
common case. Instead of just always wrapping NSIndexPath, maybe we
should just switch the internal representation to something like

enum Indices {
    case one(Int)
    case two(Int, Int)
    // case three?
    case many([Int])
}

Yeah it complicates the methods a bit, and we'd have to have a custom
index instead of just using Array's index, but it avoids heap
allocation for the extremely common case of a 2-element index path
(it's so common, I don't think I've *ever* seen an NSIndexPath that
didn't contain exactly 2 indices).

-Kevin Ballard

On Tue, Aug 2, 2016, at 04:24 AM, Stephan Tolksdorf via swift-corelibs- > dev wrote:

Tony,

I understand why you'd ideally want to have a real-world benchmark to
guide performance optimisations, but if you require that for every
performance-related change, you set a very high bar, and that bar
will probably have the effect of biasing performance downwards, since
if there is no existing benchmark, changes that worsen performance
might not get flagged.

The fact that NSIndexPath got the tagged pointer treatment probably
indicates that its implementation has a non-negligible effect on
performance (see also
https://twitter.com/Catfish_Man/status/393249511075639296).

The current IndexPath implementation in terms of an Int array clearly
introduces unnecessary overhead in ObjC interop scenarios, so unless
this implementation of IndexPath has some benefit I don't understand,
I'd argue that it should be replaced with a straightforward wrapper
around an NSIndexPath value.

- Stephan

On 2 August 2016 at 12:12, Tony Parker >> <anthony.parker@apple.com> wrote:

Hi Stephan,

On Aug 2, 2016, at 6:04 PM, Stephan Tolksdorf <st@quanttec.com> >>>> wrote:

Hi Parker,

I noticed the IndexPath overhead when I investigated why a Swift 3
implementation of
UICollectionViewLayout.layoutAttributesForElementsInRect spent more
time in malloc, free and related methods, but I don't have a
benchmark.

Is it important that IndexPath uses native Swift refcounting? It
seems to me that this type is mainly used in ObjC interop code. In
native Swift code I would always try to avoid using a dynamically
sized, heap allocated array as a data structure index. If
NSIndexPath can't be bridged to a native Swift type without
introducing additional overhead, then maybe it shouldn't be bridged
at all?

- Stephan

I do think it is likely we could figure out some improvements here,
but I’d like to start with a concrete test (and something that is
representative of real world use cases). If it’s possible to extract
something out of what you’ve already done, that would be really
helpful. We can also file a bug on bugs.swift.org as a call for help
designing a better perf test suite (we need this for all of the
types, frankly).

Once we know we’re measuring the right thing, there are all kinds of
interesting things we can do. If (when?) we have ABI stability in
Swift 4, we may be able to also change the ObjC Foundation.framework
to better cooperate with the Swift side, as we’ll be able to tie the
current overlay code to a specific OS instead of having to run back
several releases.

Thanks,
- Tony

On 2 August 2016 at 11:09, Tony Parker <anthony.parker@apple.com> >>>> wrote:

Hi Stephan,

Do you have some benchmarks that you could share? That would help
us focus performance work in the right area.

I know that 2-item IndexPaths are super common with UIKit
collection view and friends, so we may just want to special case
those. Unfortunately, NSIndexPath is not abstract, so subclassing
it in the same way that we do for a few of the other bridged
types (to use native Swift refcounting) is not easy. On the other
hand, the ObjC implementation does use tagged pointers, so some
NSIndexPaths are really cheap to create.

- Tony

> On Aug 1, 2016, at 11:44 PM, Stephan Tolksdorf via swift-corelibs- >>>>> > dev <swift-corelibs-dev@swift.org> wrote:
>
> Hi,
>
> IndexPath is currently implemented using an [Int] array that is
> bridged to an NSIndexPath only on demand. Since IndexPath
> values are primarily used together with Objective-C APIs,
> wouldn't it be better to implement IndexPath directly as an
> NSIndexPath wrapper, in order to avoid the overhead of
> temporary array instances?
>
> - Stephan
> _______________________________________________
> swift-corelibs-dev mailing list swift-corelibs-dev@swift.org
> https://lists.swift.org/mailman/listinfo/swift-corelibs-dev

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