[Python-Dev] collections module

[Guido van Rossum]

> Shouldn't you malloc() in the case of prepending, and do the copying 
> yourself? realloc can only avoid copying if it can append a free block.
> For the list, we know
> a) realloc is unlikely to find a new block, anyway, as it is pymalloc,
>     which never extends a small block.

Not for large lists.  pymalloc passes large objects off to real malloc.

> b) even if realloc would be able to extend the block, we still would
>     have to copy the data.

For really large lists, you'd risk running out of memory due to the
malloc(1GB), while realloc(1GB) very likely just extends (since such a
large block effectively becomes in a memory segment of its own).

> I don't know whether the overallocation would make similar-sized room
> at both ends, or whether it would take the current operation into
> account. For the specific case of queues, we may find that doing
> *just* the copying might be sufficient, with no need to go to the
> allocator.

Hm.  An idea: don't bother overallocating when inserting in the front,
but do keep the free space in the front if possible.  Then recommend
that queus are implemented using append(x) and pop(0), rather than
using insert(0, x) and pop().

--Guido van Rossum (home page: http://www.python.org/~guido/)