[Python-Dev] iterzip()

Guido van Rossum guido@python.org
Mon, 29 Apr 2002 14:22:25 -0400


> The cause on Win98SE is clear enough with a little instrumentation:  in the
> justzip case, listobject.c's ins1 ends up *copying* the memory much more
> often, presumably due to that there's a new tuple allocation after every
> append (preventing realloc from growing into that space).  justpush copies
> the memory at sizes (skipping some tiny ones, and where this is a count of
> the number of elements in the list, not the number of bytes (multiply by 4
> to get the latter)):
> 
>     247 639 959 2047 45055 163839
> 
> and that's all.  justzip copies the memory at sizes:
> 
>     247 639 959 2047 45055 53247 57343 65535 81919 98303 122879 163839
>     196607 229375 262143 294911 360447 393215 458751 589823 622591
>     688127 720895 753663 786431 819199 851967 884735 917503 950271
> 
> Copying 3-4MB multiple times at the end ain't cheap.
> 
> justpush does relatively worse if the order in which they're called is
> swapped, as then justzip and the custom tuple free list conspire to leave
> memory in a more-fragmented state.

This suggests that zip() can be sped up considerably by using a hint
for the input sequence sizes.  If they all respond properly to
PySequence_Length(), zip can preallocate the result list to the
correct size.  It shouldn't believe the numbers fully, but using them
as a hint for initial allocation makes a lot of sense, and should
greatly reduce the inefficiency.

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