> If resizing of lists is too slow, then we should reconsider the 9/8 factor
> and/or look to tweak the resizing code.

The thing is that the performance is platform specific. On systems with a
fast memory allocator, especially on Linux, the difference is negligible.
However, with a slow memory allocator, especially a slow realloc(), e.g. on
Windows or Solaris, this can substantially hurt the performance, up to a
quadratically increasing runtime in the worst case.

The length hint was implemented specifically to work around this problem.

Stefan

 
It's not the actual allocation (typically), it's the copying that's the problem.

As far as data goes - preallocation can make 4x difference (on PyPy, although the dominant operation is not different on CPython) on ''.join(some-iterable). It depends grossly on the sizes of the list, so you can't claim that there is a precise speedup of a constant factor, however, there are cases where it *can* be significant (as in the copying is by far the dominating operation), most notable giant templates with iterators written in C.
">

(original) (raw)

On Mon, Jul 16, 2012 at 11:02 AM, Stefan Behnel <stefan_ml@behnel.de> wrote:

Mark Shannon, 16.07.2012 10:37:

> If resizing of lists is too slow, then we should reconsider the 9/8 factor
> and/or look to tweak the resizing code.

The thing is that the performance is platform specific. On systems with a
fast memory allocator, especially on Linux, the difference is negligible.
However, with a slow memory allocator, especially a slow realloc(), e.g. on
Windows or Solaris, this can substantially hurt the performance, up to a
quadratically increasing runtime in the worst case.

The length hint was implemented specifically to work around this problem.

Stefan

It's not the actual allocation (typically), it's the copying that's the problem.

As far as data goes - preallocation can make 4x difference (on PyPy, although the dominant operation is not different on CPython) on ''.join(some-iterable). It depends grossly on the sizes of the list, so you can't claim that there is a precise speedup of a constant factor, however, there are cases where it \*can\* be significant (as in the copying is by far the dominating operation), most notable giant templates with iterators written in C.

Speaking of which - I find this bikeshed disgusting. The purpose of the PEP is to codify whatever is already written in code in CPython. If you guys don't want it, we'll just implement it anyway and try to follow the CPython current implementation from 2.7.

Cheers,
fijal