deque vs list: performance notes

[Courageous]

> I'm against a linked list deque implementation for Python.
> But I'm plus 1 on doing it as an extension of lists.

For what it's worth, I'm implementing a dynarray which
leaves buffer room on both the head and tail as we speak.
Note that this slows down random access ever-so-slightly,
as you have to have a "virtual index" to account for the
actual and current positions of the "beginning" of the list.
However, the cost is very small: an extra add on every
access.

My current algorithm is as follows:

1. Store a "virtual index" into the list, allowing buffer
   room at the head.

2. On an insert at the head, simply decrement the virtual
   index and insert.


3. On an insert operation at the head, if the virtual index
   would go negative on the insert, double the allocation
   space of the array and place the actual used space of
   the array 1/3 of the way into the array.

4. On removal at the head, simply increment the virtual
   index.

5. If the virtual index becomes larger than 2/3 of the
   allocated space, move the actual used space of the
   array 1/3 of the way into the array (this last is to
   avoid an array which would grow infinitely on append
   to tail and removal from head).

6. The growth rate of the array will always be 100%
   increase (as compared to python's 50/500 heuristic,
   IIRC).

7. You'll be able to specify an initial size for the list.

This technique should have the same complexity as python
lists with the additional benefit of O(1) removal/insert
at the head without sacrificing O(1) random access. I'll
do a complete performance test as before, of course.

As per usual, the source will be entered into the public
domain.

C/