Support fixed-size Deque

[comyar]

Currently, Deque can be initialized with a minimumCapacity and Deque's internal storage will grow capacity as the number of elements in the Deque increases. It is not possible today to limit the maximum capacity of Deque.

This limitation prevents the usage of Deque as a traditional ring buffer/circular buffer which is backed by fixed-size, contiguous memory. Ideally, Deque would allow a user to provide a capacity or eagerCapacity which results in the Deque's storage eagerly allocating contiguous memory for its elements and enforcing the capacity restriction. This is a relatively common use case for high-performance systems which utilize fixed-size queues.

[lorentey]

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:

1. The collection value is initialized with a specified minimum capacity
2. 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.
3. 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.

[lorentey]

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. 🤔