Surprising (for me) benchmark results...

[Toby Dickenson]

"Alex Martelli" <aleaxit at yahoo.com> 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
memory.

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 geminidataloggers.com