[Python-Dev] Alternative C implementation idea for collections.deque

[Daniel Stutzbach]

Many years ago I implemented a deque type in C (for use in C programs)
using a single dynamically sized array as the underling type, along
with an extra integer to designate where the "start" of the list is.
Somehow, I had always imagined that Python's implementation worked the
same way, but was just looking at the code and found that it uses
doubly-linked lists of 62-item blocks.

I just wanted to toss my approach out there to see if it might offer
better performance and/or simpler code (my pure-C implementation is
only 80 lines of code).  If there's interest, I'd be happy to work it
up into a patch.  I could also do some performance tests if others
have specific use cases they'd like to see tested.  I see the
advantages as follows:

- __getitem__ would take O(1) time instead of O(n)
- Dirt simple implementation

Compared to the existing code, memory allocation/deallocation is less
frequent but more expensive when necessary, working out to O(1)
amortized time (same as the current implementation).

The basic idea is to use a single dynamically sized array (much like
Python's list type).  An extra integer points to the start of the
deque within the array, and the data implicitly wraps around the end
of the list back to the beginning.  Here's the basic data structure:

struct deque
{
    PyObject **obs;
    int max_len;        /* Number of objects we can store in the deque
before having to reallocate */
    int len;                /* Number of objects currently in the deque */
    int start;              /* Where in obs the objects starts */
}

When len == max_len and the user adds an element, we reallocate obs.
Much like Python's list type, this can be done in such a way that
memory allocation takes O(1) amortized time (e.g., by doubling
max_len)..

The start of the list is always obs[start] and the last element of the
list is at obs[(start + len - 1) % max_len].  The nth element of the
list is obs[(start + n) % max_len].

I think an example would be helpful.  For illustrative purposes,
suppose we start with max_len=4.  Each line is followed by a picture
of the data structure's contents:

>>> x = deque()
{obs = {NULL, NULL, NULL, NULL}, max_len = 4, len = 0, start = 0}
>>> x.extend((1,2,3,4))
{obs = {1, 2, 3, 4}, max_len = 4, len = 4, start = 0}
>>> x.popleft()
{obs = {NULL, 2, 3, 4}, max_len = 4, len = 3, start = 1}
>>> x.append(5)
{obs = {5, 2, 3, 4}, max_len = 4, len = 4, start = 1}
>>> x.popleft()
{obs = {5, NULL, 3, 4}, max_len = 4, len = 3, start = 2}
>>> x.pop()
{obs = {NULL, NULL, 3, 4}, max_len = 4, len = 2, start = 2}

Comments?  Thoughts?  Would a patch be welcome?

-- 
Daniel Stutzbach, Ph.D.             President, Stutzbach Enterprises LLC