deque vs list: performance notes

[Christian Tismer]

Courageous wrote:
> 
> > 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):

God are you quick. Do you have a copy of G-man's time machine? :-)

>     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. :)-

Tja. You touched hardcore stuff, so problems come for free :-)

But I'm quite confident that your "thirds" approachis fine.

ciao - chris

-- 
Christian Tismer             :^)   <mailto:tismer at appliedbiometrics.com>
Applied Biometrics GmbH      :     Have a break! Take a ride on Python's
Kaunstr. 26                  :    *Starship* http://starship.python.net
14163 Berlin                 :     PGP key -> http://wwwkeys.pgp.net
PGP Fingerprint       E182 71C7 1A9D 66E9 9D15  D3CC D4D7 93E2 1FAE F6DF
     where do you want to jump today?   http://www.stackless.com