[Swift 3?] Add ContiguousArray -> Array non-copying initialiser


(Karl) #1

https://github.com/apple/swift/pull/3819

···

As I understand it, Array may be backed by contiguous storage (if native) or it may be backed by some exotic NSArray subclass. We provide a related type with stronger backing guarantees: ContiguousArray (and indeed, in my algorithmic code, I can see a total execution time halve by switching from one to the other -- which may be a bug, but in any case there are differences which is why we have the type in the first place).

Unfortunately, there is no way to vend a ContiguousArray as a regular Array. If you wish to make use of the stronger guarantees of ContiguousArray in your algorithm, everybody who uses those results must also use ContiguousArray or else you will have to copy the data.

I know it's late for Swift 3. I literally only noticed this today, otherwise I would have mentioned it earlier.

It seems like a reasonably large hole with a simple fix. Going from ContiguousArray to Array is a kind-of upcasting conversion and should be allowed -- it seems like that's almost the whole point of the type.


(Dmitri Gribenko) #2

Hi Karl,

Converting a ContiguousArray to Array using Array's initializer is
O(1). Are you seeing something different?

Array.init:

https://github.com/apple/swift/blob/f8f6d61d195185f54aeba425dd0db8be4c5d163f/stdlib/public/core/Arrays.swift.gyb#L1037

ContiguousArray._copyToContiguousArray():

https://github.com/apple/swift/blob/f8f6d61d195185f54aeba425dd0db8be4c5d163f/stdlib/public/core/Arrays.swift.gyb#L1430

Dmitri

···

On Wed, Jul 27, 2016 at 11:08 PM, Karl via swift-evolution <swift-evolution@swift.org> wrote:

It seems like a reasonably large hole with a simple fix. Going from
ContiguousArray to Array is a kind-of upcasting conversion and should be
allowed -- it seems like that's almost the whole point of the type.

--
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>*/


(Karl) #3

I didn't know that normally-copying initialiser was non-copying for ContiguousArray. That's the kind of thing we should really document somewhere (or it should be it's own function because it guarantees non-copying behaviour).

If you're using CA explicitly, it's because you want those subtle performance guarantees.

Karl

···

Sent from my new Email (https://itunes.apple.com/app/apple-store/id922793622?pt=814382&mt=8&ct=my_new_email)

On Jul 28, 2016 at 10:32 AM, <Dmitri Gribenko (mailto:gribozavr@gmail.com)> wrote:

On Wed, Jul 27, 2016 at 11:08 PM, Karl via swift-evolution > <swift-evolution@swift.org (mailto:swift-evolution@swift.org)> wrote:
> It seems like a reasonably large hole with a simple fix. Going from
> ContiguousArray to Array is a kind-of upcasting conversion and should be
> allowed -- it seems like that's almost the whole point of the type.

Hi Karl,

Converting a ContiguousArray to Array using Array's initializer is
O(1). Are you seeing something different?

Array.init:

https://github.com/apple/swift/blob/f8f6d61d195185f54aeba425dd0db8be4c5d163f/stdlib/public/core/Arrays.swift.gyb#L1037

ContiguousArray._copyToContiguousArray():

https://github.com/apple/swift/blob/f8f6d61d195185f54aeba425dd0db8be4c5d163f/stdlib/public/core/Arrays.swift.gyb#L1430

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 (mailto:gribozavr@gmail.com)>*/


(Dmitri Gribenko) #4

I didn't know that normally-copying initialiser was non-copying for
ContiguousArray. That's the kind of thing we should really document
somewhere

We would welcome a patch for the docs!

(or it should be it's own function because it guarantees
non-copying behaviour).

It should be the same function, so that you get this optimization even
when working from generic code, when the type of the initializer's
argument is erased to Sequence.

Dmitri

···

On Thu, Jul 28, 2016 at 11:01 AM, Karl Wagner <razielim@gmail.com> wrote:

--
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>*/