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

[matthiasgoergens]

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 prototyped 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).

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

The prototype is on my github, but it's not polished and still has plenty of bugs. If there's interest, I'll publish the benchmarks and make a more polished PR.

[matthiasgoergens]

In related news, I'm also working on a similar prototype for the ordered dict.

There the storage overhead of the existing linked list solution is quite substantial, because each item is its own node with forward and backward links. But the code is more complicated, and thus more complicated to port.

Preliminary results there are encouraging. (And it's the same trade-off amortised costs going down, but we do the occasional rebuild.)

[Deric-W]

In related news, I'm also working on a similar prototype for the ordered dict.

With a possible use case of OrderedDict being LRU caches (at least me and the docs use it that way) it is important that its move_to_end method experiences no slowdowns, which might not be the case when using the O(n) operations of the ring buffer.
I am not that familiar with the current implementation, but with a linked list it is probably a O(1) operation assuming the list nodes are referenced directly by the dictionary.

Could you keep that in mind when testing your new implementation?

[dg-pb]

offers indexing via my_deque[index] but that takes linear time

OT. Then, maybe with new approach it would be more natural / convenient to implement slicing?

I'll publish the benchmarks

Would be very interesting to see some of these.

[matthiasgoergens]

Then, maybe with new approach it would be more natural / convenient to implement slicing?

That should be quite doable, though I'm not completely sure what's involved there, but it should be only slightly more complicated than slicing a list. What's involved there?

Would be very interesting to see some of these.

Which reminds me, I really need to get back to this little project.

[dg-pb]

What's involved there?

I think there are other, non-technical reasons why it isn't implemented.

But just curious whether it would be easier with what you are proposing or not as I am hopeful that one day it will happen.

[matthiasgoergens]

With a possible use case of OrderedDict being LRU caches (at least me and the docs use it that way) it is important that its move_to_end method experiences no slowdowns, which might not be the case when using the O(n) operations of the ring buffer.

My implementation is amortised O(1), just like eg appending to lists, or almost anything in Python that could trigger a GC. However, it's not worst case O(1). You could get that at the price of worse constant factors (and that the kind of trade-off that the ordered dict is currently making, but with different implementation details).

[matthiasgoergens]

But just curious whether it would be easier with what you are proposing or not as I am hopeful that one day it will happen.

Would you want to have a copy or a view? From what I can tell, the shallow copy (like lists) wouldn't be much harder to add to the existing linked list based implementation than to mine, but perhaps it's distasteful to some? If you want a view, then my implementation might be easier.

[Eclips4]

My implementation is amortised O(1), just like eg appending to lists, or almost anything in Python that could trigger a GC.

Sorry, I didn’t quite understand the point about the GC. Did you perhaps mean reallocations instead?
When we exceed the current capacity while appending to a list, the list is reallocated and its capacity grows.

[matthiasgoergens]

When we exceed the current capacity while appending to a list, the list is reallocated and its capacity grows.

Yes. And that takes O(n) time for that specific insert, but on average inserts still only take O(1), because the reallocation happens rarely enough. Amortised analysis is one way to formalise this observation.

[dg-pb]

the shallow copy (like lists)

If this was to happen, my best guess is that it would be in line with list.

[Deric-W]

My implementation is amortised O(1), just like eg appending to lists, or almost anything in Python that could trigger a GC.

I am not that familiar with the internals of OrderedDict, but I am sure that the kind of operations used by move_to_end require extracting an element from somewhere in a queue and adding it to the front (or back).
This is O(1) for linked lists but O(n) for a ring buffer since elements have to be moved by the extraction operation (like in a Python list) while adding or removing elements from the front (or back) is still O(1).

I am happy to be proven wrong, just do a little benchmarking when working on the internals of OrderedDict.

[matthiasgoergens]

am not that familiar with the internals of OrderedDict, but I am sure that the kind of operations used by move_to_end require extracting an element from somewhere in a queue and adding it to the front (or back).
This is O(1) for linked lists but O(n) for a ring buffer since elements have to be moved by the extraction operation (like in a Python list) while adding or removing elements from the front (or back) is still O(1).

You are right for a naive implementation. However when you have 'tombstones', like dicts already do, you can do this in amortised O(1): put a tombstone in the original place of the item, and add it at the end. You can already do this in amortised constant time with vanilla dicts right now and could have done this since 3.6 when dicts became ordered by insertion.

The big change would be to also allow this for moving items to the front. There are a few smaller changes to make these operations have better constant factors than delete-followed-by-append/prepend, but it's still amortised constant in either case.

The last time we discussed this implementation of ordered dicts, the controversy was over the amortising.

[isaacl]

Indexing into a deque feels unintended, and maybe shouldn't even be in the API?

Your change would presumably need to at least match deque's primary use case, which is add/remove from head/tail, in an arbitrary series of ops. It might be hard to prove that.

[dg-pb]

Personally, I like "functional" types.

Although modifying deque with extra efficient operations might not be worthwhile if it damages its primary usage, but might be more than desirable if it doesn't.

For example, O(1) random access deque could be used for sortedcontainers.SortedList storage for double-ended insertion, which would increase its performance. In short, having such would open possibilities to more efficient algorithms that can build upon it.

Also, https://en.cppreference.com/w/cpp/container/deque.html is O(1) random access. It is not like Python is lower level language than C++ to persist being more primitive.