Move `collections.deque` to a growable ring buffer for fast random access

[matthiasgoergens]

Feature or enhancement

Proposal:

See the faster-cpython issue.

At the moment, collections.deque is implemented via a linked list of 64-element arrays. That means it can quickly access elements at the beginning and end, and has only a modest amount of space overhead.

However, collections.deque also offers indexing via my_deque[index] but that takes linear time.

Inspired by Rust's VecDeque, I have implemented a double-ended queue implemented with a growable ring buffer.

The new implementation is simpler, and I ran a few simple benchmarks. Most notable, random access is now O(1), and slicing can be done in O(k) where k is the length of the resulting slice. Just like lists.

• Accessing the ends (append either side, pop either side) is about as fast as before.
• Deleting an arbitrary element in the middle, inserting an element in the middle and rotation etc are still O(n), but the constant factors are better: the main bulk of the work is essentially just memmove.

One downside: just like with lists, my prototype grows the allocated space geometrically, so the worst case append-time is linear, but it's amortised constant. (There are well-known ways to make both lists and my deque prototype have O(1) append, but if they aren't worth it for lists, they probably aren't worth it for the deque. They come with a constant factor overhead.)

The new implementation should be cache friendlier, because it's just one big array, not a linked list. But I haven't devised a benchmark to investigate the impact of that, yet.

Inserting into a ring-deque with a fixed maximum length is still O(1) worst case (not just amortised), like in the original implementation. That's what the ring-buffer buys us.

Has this already been discussed elsewhere?

No response given

Links to previous discussion of this feature:

No response

Linked PRs

• gh-141335: Deque as a Growable Ring Buffer #141337

[terryjreedy]

@rhettinger

[dg-pb]

What would be very useful is to see benchmarks that:
a) Compare amortised performance
b) Expose "performance hits" of rebalancing in relation to amortised performance

I think performance is the key here.

And hopefully slicing will not be discarded easily.
The issue of the past, as far as I remember, was that there was no unilateral decision on what object should be returned when slicing.
Which path did you take?
If deque is returned and maxlen is set, what is the maxlen of the slice?

[matthiasgoergens]

@dg-pb I went with slices returning a copy of the items in a deque with the same maxlen in O(number of items in the resulting slice). Mostly to mirror what slicing of tuples and strings is already doing.

I also considered returning:

• a special view object in O(1) time,
• or a list
• or a deque with unlimited maximum

I have no strong preference for any of the four options, nor would I mind yet another suggestion.

I can upload some performance measurements. For the subscription, the performance can be made to look arbitrarily good, because we are moving from O(n) to O(1). (And slicing wasn't supported at all, apart from indirectly via conversion to list first.) But for all the other operations, it might be a fair comparison.

I grew our ring-buffer as powers of two, because that makes index arithmetic particularly trivial: it's just bit-mask and a logical &. As an alternative design, we can go with the same growth factors as list (assuming they differ?). Presumably they are optimised to conserve memory, but we'd take a slight performance hit on the index calculations.

[JelleZijlstra]

I don't find O(n) indexing a very compelling argument: we have other data structures that have O(n) indexing, and a deque just might not be the right tool to use when you need indexing. What are some use cases where this is useful?

The PR not only changes the internal representation of a deque, it also adds slicing. Similarly, what's the use case for slicing a deque? Why do we need this feature?

The strongest argument for merging this PR would be if it improves performance for common and recommended deque operations, such as adding and removing from either end.

[dg-pb]

What are some use cases where this is useful?

To me this is a big pain point.
There have been numerous times where I would have swapped list for deque if it had slicing and O(1) random access.

I don't know about the others, but for me this is a reoccurring thought.

Use case: alternative backend for SortedList - double ended insertion cost has both average performance benefit and smoother, more predictable performance.

[serhiy-storchaka]

I proposed something similar (not a ring buffer, but a two layer collection with linear index buffer growable from both sides) 9.5 years ago, but it was rejected because it had the same downside as this proposition -- the complexity of adding to deque changed from constant to amortized constant.

• O(1) deque indexing #71234

[matthiasgoergens]

the complexity of adding to deque changed from constant to amortized constant.

Interesting! It's good enough for lists, so I wonder why it wouldn't be good enough for deques.

Btw, as far as I can tell, one important difference is that as long as the deque doesn't grow overall (either because of a maxlen or because of balanced inserts and deletes), the new implementation stays O(1) in the steady state in the worst case, not just amortised.

[rhettinger]

Thank for you the suggestion, but I will decline. As Jelle says, we already have structures with O(n) indexing. Further, indexing by position doesn't make sense in the typical use cases for queues when the positions of values shift over time. The only reason we have indexing at all is to support rapid access to the endpoints (where the position does have meaning).