Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[SR-3631] Introduce ContiguouslyStored protocol and kill ArraySlice type #46216

Closed
dabrahams opened this issue Jan 13, 2017 · 14 comments
Closed
Labels
affects ABI Flag: Affects ABI good first issue Good for newcomers improvement standard library Area: Standard library umbrella swift evolution implemented Flag → feature: A feature that was approved through the Swift evolution process and implemented

Comments

@dabrahams
Copy link
Collaborator

Previous ID SR-3631
Radar rdar://problem/30541077
Original Reporter @dabrahams
Type Improvement

Attachment: Download

Additional Detail from JIRA
Votes 0
Component/s Standard Library
Labels Improvement, AffectsABI, StarterProposal
Assignee None
Priority Medium

md5: 0b822da3966dafcaf6527038fc805b6a

relates to:

  • SR-3633 Support for segmented data structures
  • SR-3087 No way to arbitrarily initialise an Array's storage

Issue Description:

Sketch:

protocol ContiguouslyStored : RandomAccessCollection {
  func withUnsafeBufferPointer<R>(...) -> R
  mutating func withUnsafeMutableBufferPointer<R>(...) -> R
}

extension Slice : ContiguouslyStored where Base : ContiguouslyStored {
  func withUnsafeBufferPointer<R>(...) -> R { ... }
  mutating func withUnsafeMutableBufferPointer<R>(...) -> R { ... }
}

typealias ArraySlice<T> = Slice<Array<T>>

(This is related to https://bugs.swift.org/browse/SR-3633)

@swift-ci
Copy link
Collaborator

Comment by Daryle Walker (JIRA)

Whether or not a type uses contiguous storage has nothing to do with how its elements are accessed by normal developers. For instance, a multi-dimensional array would have packed storage, but can't qualify for Sequence or its derivatives (since it's a non-linear container). So ContiguouslyStored should be a base protocol, and not inherit from any of the collection protocols.

As of this writing, I recently posted the same idea. But I had a ContiguousBlock protocol for .withUnsafeBufferPointer (with an Element associated type) for immutable visitation, and a derived MutableContiguousBlock adding .withUnsafeMutableBufferPointer for mutable visitation.

@swift-ci
Copy link
Collaborator

Comment by Daryle Walker (JIRA)

I just attached my version of this idea.

@dabrahams
Copy link
Collaborator Author

CTMacUser (JIRA User) I disagree. If there is storage for a contiguous array of elements, there is inherently a random-access collection. A dense multi-dimensional array should not be-a RandomAccessCollection of all its elements, but it could have such a collection, and probably does. At the same level of abstraction where that collection would be exposed, so too could unsafe access to its contiguous storage be exposed.

@swift-ci
Copy link
Collaborator

swift-ci commented Feb 5, 2017

Comment by Daryle Walker (JIRA)

And the implication from contiguous arrays of elements to random-access collections is already present; Unsafe[Mutable]BufferPointer IS-A RandomAccessCollection already. Copying that connection up to the Contiguous* protocol is an over-specification, the two methods look self-contained and don't need anything from the Collection interface.

@dabrahams
Copy link
Collaborator Author

It's not overspecification; it's good old-fashioned concept clustering. We don't make every concept minimal for good reasons.

@dabrahams
Copy link
Collaborator Author

I should add that there are no interesting generic algorithms that can operate on a "has contiguous memory" protocol without further semantic constraints. An Int has contiguous memory; what are you going to do with it? Now if you know the type has the semantics of a collection and the contiguous memory is expressed as its elements, a generic algorithm can meaningfully take advantage of that.

@swift-ci
Copy link
Collaborator

swift-ci commented Feb 5, 2017

Comment by Daryle Walker (JIRA)

Unsafe[Mutable]BufferPointer already provides both contiguous memory and collection semantics. The generic algorithm can be called within withUnsafe[Mutable]BufferPointer; that's the reason for their existence, after all. Adding Collection to Contiguous* just adds a second path for the same concept.

Side Note: I was just pondering why we don't replace these methods with two properties. But that wouldn't be compatible with the array changing size between calls. The current function-based interface avoids us making the user invalidate any cached copies of the buffers. I know some interfaces have "lazy" variants; I don't know enough about how lazy evaluation works to know if that technique could help making this interface property-based instead.

@dabrahams
Copy link
Collaborator Author

1. The point is that algorithms that are sure of themselves should be able to (generically) get an unsafe buffer to any contiguously stored collection. That collection should not necessarily be forced to expose an unsafe primary interface to all users.

  1. That's not why they aren't properties' it has to do with being able to guarantee the lifetime of the underlying storage

@airspeedswift
Copy link
Member

This kind of more in depth conversation is better had on he evolution list rather than on this Jira via comments. This jira will become a proposal pitch soon at which point we can have this debate there.

@airspeedswift
Copy link
Member

@swift-ci create

@dabrahams
Copy link
Collaborator Author

@karwa
Copy link
Contributor

karwa commented Mar 24, 2017

Do you imagine UnsafeRawBufferPointer would also conform to that protocol, vending a typed buffer of UInt8s?

At the memory-binding level it may be false, but at the Collection level, for generic algorithms, it's sometimes useful to think of a raw-buffer simply as some contiguously-stored bytes (and since there is no Byte type, that means UInt8s).

For example, let's say I have a simple slicing structure which buffers some streaming data and queries a predicate when to break. It's nice if I can handle generic data-frames which are contiguous collections of T, handling raw-byte streaming and buffering as well as typed buffers with the same implementation (the reason it has to be contiguous is so that we can pass-through slices that are entirely contained within the frame without copying - could also be solved in other ways, I suppose...).

Additionally, it would be nice if we could implement Sequence's hidden "_copyContents" optimisations using this, so any 3rd-party Sequence which declares that it is contiguously-stored automatically gets those optimisations when copying its contents in to an Array or buffer.

@glessard
Copy link
Contributor

glessard commented Jun 4, 2021

`ContiguouslyStored` was merged in #21092
`ArraySlice` seems likely to stick around. Should this be closed?

@swift-ci swift-ci transferred this issue from apple/swift-issues Apr 25, 2022
@AnthonyLatsis AnthonyLatsis added good first issue Good for newcomers swift evolution implemented Flag → feature: A feature that was approved through the Swift evolution process and implemented and removed StarterProposal labels Nov 11, 2022
@AnthonyLatsis
Copy link
Collaborator

Closing this as partially implemented. If anyone wishes to revisit the ArraySlice part, please open a new issue and start a discussion on the forums.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
affects ABI Flag: Affects ABI good first issue Good for newcomers improvement standard library Area: Standard library umbrella swift evolution implemented Flag → feature: A feature that was approved through the Swift evolution process and implemented
Projects
None yet
Development

No branches or pull requests

6 participants