[Python-Dev] deque alternative (was: Linked lists)

[James Y Knight]

On Dec 26, 2005, at 11:07 AM, Martin Blais wrote:
>> Then there's the whole Python list with append() and pop().  It  
>> takes a
>> method resolution and function call, but at least in Python 2.3,  
>> it is a
>> hair faster...
>
> Josiah, that's beside the point, because it is not space-efficient,
> the list is actually an dynamic array/vector, and I would expect an
> efficient array implementation to grow exponentially.  One of the
> reasons we're talking about lists is to avoid exactly this problem...

Okay, now *that* reason is a pretty crazy one. Consider what you're  
saying here.

A list made of cons cells takes at least two words per element. And  
that's if you have an efficient GC mechanism tuned for cons cells,  
like popular common lisps have. In python, a cons cell will take at  
least 8 words (gc_next, gc_prev, gc_refs, padding, ob_refcnt,  
ob_type, and finally, car, and cdr). So a list of 100 elements will  
take _at best_ 200 words, and in python, a ghastly 800 words. Plus,  
in python, the overhead per object in the pyobject memory allocation  
system, which I don't know how to quantify.

An array takes one word per element, plus some header overhead. In  
python, the header overhead will be the same as above, plus around 3  
more words, so around 9 words. So to store an array of 100 elements  
will take around 109 words. Now let's say python did overallocate by  
100%. Then the array would take up 209 words. But it doesn't  
overallocate that much. The real formula is:
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6) + newsize;

So, the list will generally be 1/8th of its size overallocated, or  
112 elements plus 9 words overhead is 121 words. Better than any cons- 
linked list could be, and *insanely better* than a cons-linked list  
would be in python.

James