Comments (2)
My initial instinct is that this feature would not be a good fit with the Deque
we have, i.e., one that implements copy-on-write value semantics.
The headlining feature of Swift’s collection types is that they implement value semantics with the copy-on-write optimization. This means that any operation that mutates a collection can (and does) implicitly and automatically reallocate storage. Automatic resizing goes hand in hand with that — I think disabling resizing but not copy-on-write would be weirdly inconsistent.
Deque
follows the patterns set by the standard Array
type -- it is essentially an Array
that can efficiently grow/shrink at both ends. Like Array
, Deque
intentionally has dynamic capacity: it allows its storage buffer to grow as needed to accommodate insertions. Additionally, both of these types automatically (and implicitly!) allocate a copy of their storage whenever an instance is mutated while there are outstanding copies:
var a = Deque(minimumCapacity: 100)
let b = a
a.append(42) // This will allocate a second buffer to avoid changing `b`.
Neither this behavior, nor the dynamic resizing prevent the use of Deque
as a fixed-size ring buffer (or the use of Array
as a fixed-size stack), though -- as long as the following conditions hold:
- The collection value is initialized with a specified minimum capacity
- The collection value is held in a stored property of a class type (or in a global variable), and its value is never copied out of that variable.
- The client never inserts more items than the initial capacity of the collection value.
The first requirement avoids the initial ramp-up of exponentially growing allocations until we reach the stable working size.
The second requirement is the routine way for Swift code to avoid spurious copy-on-write copies in high-performance contexts.
The third requirement is a client-driven, rather unusual addition -- but if avoiding allocation spikes is for some reason necessary, it is relatively straightforward to enforce a maximum count by e.g. embedding Deque in a custom wrapper type.
Questions:
- Why do you need to guarantee that the Deque never grows beyond a particular maximum? (E.g., are heap allocations a particular concern?)
- What do you expect to happen when a new item is appended to a Deque that is already at capacity?
Fixed size Array
and Deque
variants would be very desirable additions once Swift matures enough to support backing them with inline storage, i.e., without a heap allocation. I don't expect this to become possible in the immediate future though. (I imagine it would require the language to support FixedArray<Int, 256>
, where the size of the array is encoded directly in its type.)
Rather, I expect we'll soon implement noncopyable variants of Array
and Deque
that would support holding noncopyable items. These variants would not implement the implicit copy-on-write behavior (as they wouldn't be able to copy the contents of their storage), but since they would still be backed by a heap allocation, I still expect them to be dynamically (and implicitly) resizable -- they would still grow their storage size as needed.
from swift-collections.
If pressed, it would be possible to expose a fixed-capacity deque variant as a new class type, possibly even rewriting the existing Deque
to use it as its internal storage type. 🤔
from swift-collections.
Related Issues (20)
- Incorrect CustomStringConvertible implementations HOT 3
- Update `OrderedCollection` package to use iOS 11 HOT 1
- API-NUMPY-METADATA HOT 2
- `Deque` lacks `capacity` HOT 2
- OrderedDictionary decoding. HOT 1
- OrderedDictionary insert(at:) HOT 1
- OrderedDictionary `updateValue` autoclosure for insertion index
- Failed to resolve dependencies Dependencies could not be resolved because no versions HOT 1
- Ship Sendable annotations in 1.0.6 HOT 1
- `Heap` documentation does not explain what a heap is
- `Heap.insert(contentsOf:)` is quasilinear instead of linear complexity
- OrderedSet `append(contentsOf:)` with insertion check result/results
- OrderedDictionary.values and OrderedSet Performance Problems when SwiftUI.List is paired with SwiftUI.NavigationStack HOT 6
- Ship release 1.0.6 HOT 11
- Ship release 1.1.0 HOT 19
- BitArray's bitwise operations should allow operating on slices HOT 2
- Version 1.1.0 fails to compile HOT 11
- Add Privacy Manifest HOT 7
- The bundle at path Payload/MyApp.app/Frameworks/_CollectionsUtilities.framework has an invalid CFBundleIdentifier '_CollectionsUtilities' HOT 13
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from swift-collections.