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 _______________________________________________ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
