RFC: Deque: should it have a capacity?

Deque documents

They also lack a capacity property -- the size of the
storage buffer at any given point is an unstable implementation detail that
should not affect application logic.

I find this somewhat unconvincing because Deques are often used for buffering and in many cases we want to prevent holding onto a (temporarily) ballooned Deque. For example in SwiftNIO we have code which does:

self.buffers.removeAll(keepingCapacity: self.buffers.capacity < 16) // don't grow too much

and the idea is that we want to hold onto self.buffers (a deque) but only if its underlying storage buffer is 16 elements or less at the moment. This occurred to me when I was reimplementing CircularBuffer on top of Deque.

5 Likes

That’s a good reason to provide a capacity. :thinking:

But what if we instead made Deque automatically shrink its storage on removals instead? (And provided an init(minimumCapacity:persistent:) initializer, like OrderedSet.)

If you have a good idea of the expected working size of the set, calling this initializer with persistent set to true can sometimes improve performance by eliminating churn due to repeated rehashings when the set temporarily shrinks below its regular size.

  • Parameter minimumCapacity: The minimum number of elements that the newly created set should be able to store without reallocating its storage.

  • Parameter persistent: If set to true, prevent removals from shrinking storage below the specified capacity. By default, removals are allowed to shrink storage below any previously reserved capacity.

Terms of Service

Privacy Policy

Cookie Policy