deque vs list: performance notes

[Courageous]

> As per unusual, I will incorporate this into Stackless
> Python immediately if it is written as clear as you described
> it.

It actually *is* pretty clear, I discovered that I needed to be
very careful with head inserts. I ended up with 3 seperate critical
conditions (and am not sure if there might be some more clever way
of expressing them):

    if ((dlist->vfront < 1) && (dlist->len < (2*dlist->alloclen/3)))
    {
        DlistReposition(dlist);
        dlist->vfront--;
        dlist->items[dlist->vfront]=object;
    }
    else if (dlist->vfront < 1)
    {
        DlistGrow(dlist);
        dlist->vfront--;
        dlist->items[dlist->vfront]=object;
    }
    else
    {
        dlist->vfront--;
        dlist->items[dlist->vfront]=object;
    }

Condition number 1 occurs when the virtual index is underflowing
the actual allocated memory, but there in fact is plenty of memory
to hold the current array. Therefore it is reposition using the
"1/3 rule".

Condition number 2 occurs when the virtual index underflows the
allocated memory, but the memory space is too small. The allocated
region is doubled and then repositioned using the 1/3rd rule.

Condition number 3 occurs normally. The virtual index is
decremented and the item is inserted, cost = 1.

I'm not certain exactly, but I believe that the first two conditions
amortize away over all inserts at the head to O(1)+k.

The rule of 2/3 availabile memory being "enough" was an entirely
arbitrary pick. There has to be some rule, however, otherwise
condition number two will occur on every underflow, resulting in
growth at every insert at the head. Ran into that one by mistake.

Oopsie. :)-



C/