[Python-Dev] Optimization of the Year

[Armin Rigo]

Hello,

(Some of my messages seem to get lost and never make it through to the mailing 
list, don't understand why...)

There are a few details and minor bugs (like missing memory checks) that I
don't want to discuss in detail on python-dev.  Here are the fixes, open to
further eyeballing:

  http://arigo.tunes.org/list-r3.diff

But there is something else that the patch does wrong: it never reclaims
memory from the list, unlike the NRESIZE trick which used to realloc with a
smaller size occasionally.  This is very probably bad.  We need to discuss
heuristics for that as well.  I guess the following could do: shrinking the
list only when the ratio ob_size/allocated is below 3/4.

Actually the over-allocation heuristic could also be given a few more
thoughts; it is fine for the list.append() case, but we should check what its
results are for other common patterns.  For example one could argue that a
concatenation "a+b" of two lists of approximately the same length should not
necessarily over-allocate 1/16 of the resulting size.  The following modified
rule could take care of that: list_resize would allocate

   max(17/16 of current size, requested size)

instead of 17/16 of the requested size, as it does now.

Also, the list_sort trickery with empty_ob_item, which I know I am partially
to blame for, seems to leak memory under certain conditions (but that's not
related to the present patch so I'll postpone this investigation).


Armin