Surprising (for me) benchmark results...

Toby Dickenson tdickenson at
Thu May 3 07:15:44 EDT 2001

"Alex Martelli" <aleaxit at> wrote:

>I measured on *large* values of N -- I don't recall the exact
>numbers, but they didn't seem to matter much: allocating by
>the current strategy OR by geometrical growth (say N'=100+1.5N,
>when the current allocation of N items must grow to a new size
>N') produced very similar results, preallocating the whole
>caboodle in advance always gave substantial advantage.
>That was on Windows platforms, and for Python 2.0, by the way.
>Maybe performance behaves otherwise with different allocators.

All win32 platforms, linux, and possibly some other platforms too,
have special provision for malloc of large blocks. realloc is
implemented by remapping VMM pages, rather than copying physical

list.append is definitely O(n*n) in theory, but with a constant factor
small enough that you never see it in practice.

Toby Dickenson
tdickenson at

More information about the Python-list mailing list