[Python-Dev] Alternative C implementation idea for collections.deque (original) (raw)

Daniel Stutzbach daniel at stutzbachenterprises.com
Thu Nov 15 04:39:47 CET 2007

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:

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

More information about the Python-Dev mailing list