]> granicus.if.org Git - python/commit
roundupsize() and friends: fiddle over-allocation strategy for list
authorTim Peters <tim.peters@gmail.com>
Sat, 26 May 2001 05:28:40 +0000 (05:28 +0000)
committerTim Peters <tim.peters@gmail.com>
Sat, 26 May 2001 05:28:40 +0000 (05:28 +0000)
commit65b8b8483988cfdb6b23b64b77e94d87c079b9d9
tree20c211327805db397cda9e9358ee558329808f80
parent56a71eee656bb894c64cdd1105abee8813c92735
roundupsize() and friends:  fiddle over-allocation strategy for list
resizing.

Accurate timings are impossible on my Win98SE box, but this is obviously
faster even on this box for reasonable list.append() cases.  I give
credit for this not to the resizing strategy but to getting rid of integer
multiplication and divsion (in favor of shifting) when computing the
rounded-up size.

For unreasonable list.append() cases, Win98SE now displays linear behavior
for one-at-time appends up to a list with about 35 million elements.  Then
it dies with a MemoryError, due to fatally fragmented *address space*
(there's plenty of VM available, but by this point Win9X has broken user
space into many distinct heaps none of which has enough contiguous space
left to resize the list, and for whatever reason Win9x isn't coalescing
the dead heaps).  Before the patch it got a MemoryError for the same
reason, but once the list reached about 2 million elements.

Haven't yet tried on Win2K but have high hopes extreme list.append()
will be much better behaved now (NT & Win2K didn't fragment address space,
but suffered obvious quadratic-time behavior before as lists got large).

For other systems I'm relying on common sense:  replacing integer * and /
by << and >> can't plausibly hurt, the number of function calls hasn't
changed, and the total operation count for reasonably small lists is about
the same (while the operations are cheaper now).
Objects/listobject.c