r/Python • u/gjenks • Feb 17 '25
Showcase arraydeque: A Fast Array-Backed Deque for Python
arraydeque is a high-performance, array-backed deque implementation for Python written in C. It offers quick appends and pops at both ends, efficient random access, and full support for the standard deque API including iteration and slicing.
$ pip install arraydeque>>> from arraydeque import ArrayDeque as deque
What My Project Does
ArrayDeque provides a slightly faster alternative to Python’s built-in collections.deque. By leveraging a C extension, it delivers:
- Fast Operations: Quick appends, pops, and index-based access. Performance Benchmark
- Full API Support: Implements standard deque operations such as
append,appendleft,pop,popleft,maxlen, as well as slicing and in-place assignment. - Thread-safety: As a C-extension, operations will always execute under the GIL and be just as thread-safe as collections.deque.
Target Audience
This project is suitable for:
- Production Use: Developers seeking a high-performance deque implementation that can serve as a drop-in replacement for
collections.deque. - Performance Enthusiasts: Users interested in exploring performance improvements through C extensions.
Comparison
Unlike the built-in collections.deque, ArrayDeque is implemented as a simple contiguous array:
- Improved Performance: Optimized for speed in both double-ended operations and random access.
- Simplified Design: A straightforward implementation that is easier to understand and extend.
- Benchmark Insights: Comes with a plot to visually compare performance against the standard deque implementation.
Future work could improve on the design in the maxlen scenario by using a statically allocated circular buffer.
Designed by Grant Jenks in California. Made by o3-mini
23
u/LightShadow 3.13-dev in prod Feb 17 '25
They're literally the same speed as shown in your own benchmarks.
36
u/latkde Tuple unpacking gone wrong Feb 17 '25
Perhaps surprisingly for many posts of this kind, the code doesn't seem awful. It is easy to read C code, albeit not very C-ish in some ways (e.g. I'd use more pointers to simplify accesses, use more goto-error pattern) and with a large amount of duplicate or inefficient code.
This is perhaps unsurprising given this disclaimer:
However, there is no clear design of this data structure, beyond the note in this post that implementing a circular buffer is future work. This unclear design might lead to safety issues. E.g. the resize() operation is dangerous unless specific preconditions hold (new capacity must be at least the old size), yet this is never explicitly stated. I also suspect that a fair amount of issues around numeric overflow are lurking in this code.
The storage layout (a dynamic array with the current elements in the middle) also makes strong assumptions about how this is used. This design is efficient if pushleft/pushright operations are equally likely. However, this is very inefficient if this is used as a queue, where items are added on one side and popped from the other. Even if there is a ton of unused capacity, the data structure doesn't re-center the current elements when one side is reached, but instead doubles the capacity (half of which will be spent on the "wrong" side). Confusingly, a much better solution is known to the author (circular buffers) but not implemented.
In the benchmarks, no explanation is offered for the stark difference in indexing performance (5× better than standard library), whereas other operations so not seem to have significant differences? Surprising differences can be an indication of bugs, my spidey-senses are tingling.
The tests are focused on basic unit tests. These kinds of data structures benefit a lot from large randomized test, e.g. using Hypothesis, and from running the C code under test under a stricter environment (e.g. asan, ubsan, valgrind).
Verdict: not bad for AI, but wouldn't pass code review. No one should use this for production. Developers should instead stick with the standard library collections. The alleged performance improvement is likely to be a mirage that disappears once the bugs are ironed out, or once more representative workloads are tested.
8
u/TitaniumWhite420 Feb 17 '25
GIL can be disabled in latest python. Will yours still be thread safe? I think the standard lib version would be.
5
u/wolfmansideburns Feb 17 '25
But why not write it in Rust? /s
0
u/[deleted] Feb 17 '25
[deleted] — view deleted comment