[Python-Dev] collections module

Martin v. Loewis martin at v.loewis.de
Sat Jan 10 07:24:38 EST 2004


Tim Peters wrote:
> The overallocation strategy gets more complicated, though, and less
> effective for prepending.  If you run out of room when prepending, it's not
> enough just to ask realloc() for more memory, you also have to memmove() the
> entire vector, to "make room at the left end".  In previous lives I've found
> that "appending at the right" is as efficient as it is in practice largely
> because most non-trivial C realloc() calls end up extending the vector
> in-place, not needing to copy anything.  The O() behavior is the same if
> each boost in size has to move everything that already existed, but the
> constant factor goes up more than just measurably <wink>.

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.
b) even if realloc would be able to extend the block, we still would
    have to copy the data.

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.

Regards,
Martin




More information about the Python-Dev mailing list