[Python-Dev] Windows Low Fragementation Heap yields speedup of ~15%

[Tim Peters]

[Tim Peters]
>> grow the list to its final size once, at the start (overestimating if
>> you don't know for sure).  Then instead of appending, keep an index to
>> the next free slot, same as you'd do in C.  Then the list guts never
>> move, so if that doesn't yield the same kind of speedup without using
>> LFH, list copying wasn't actually the culprit to begin with.

[Evan Jones]
> If this *does* improve the performance of his application by 15%, that
> would strongly argue for an addition to the list API similar to Java's
> ArrayList.ensureCapacity or the STL's vector<T>::reserve. Since the
> list implementation already maintains separate ints for the list array
> size and the list occupied size, this would really just expose this
> implementation detail to Python. I don't like revealing the
> implementation in this fashion, but if it does make a significant
> performance difference, it could be worth it.

That's a happy thought!  It was first suggested for Python in 1991
<wink>, but before Python 2.4 the list implementation didn't have
separate members for current size and capacity, so "can't get there
from here" was the only response.  It still wouldn't be trivial,
because nothing in listobject.c now believes the allocated size ever
needs to be preserved, and all len()-changing list operations ensure
that "not too much" overallocation remains (see list_resize() in
listobject.c for details).

But let's see whether it would help first.