Exponential time increase in garbage collection

[Tim Peters]

[Sean McGrath]
> I have a program that creates lots of small objects (actually some
> large objects that are made up of many sub-objects) and retrieves
> them through a dictionary.
>
> Depending on the machine the program is run on, there comes a point
> where deleting them from the dictionary takes a long time.

Sorry, this is too vague to work with.  Start with which verion of Python
you're using, and try to come up with a self-contained small test case
exhibiting the symptom.

> Plotting the numbers shows a relationship which is distinctly
> exponential in shape.
>
> Machine A:
> Objects	Dictionary Delete Time
> 600		2
> 200		18
> 1000		97
> 1200		344
>
> Machine B:
> Objects	Dictionary Delete Time
> 25		0
> 50		5
> 75		14
> 100		37

If I had any idea what you were doing, this *might* help <wink>.

BTW, why did you mention "garbage collection" in the subject line?  Does the
problem go away if you do gc.disable() at the start?

> The behavior is the same on Windows and Unix.

At the start, you said this happens "depending on the machine".  So what
varies besides Windows-vs-Unix that *does* make a difference?  Also be
specific aobut which flavors of Windows and Unix you're using (different
flavors of WIndows have radically different memory behavior, and ditto
Unix).

> The numbers change but the underlying shape of the graph stays
> the same.
>
> Any lore for dealing with this type of situation greatly appreciated.

If you could try it under current CVS Python, that might be interesting --
pymalloc is enabled by default in the current CVS build, and several times
pymalloc has cured cases where the *platform* malloc/free exhibit
quadratic-time behavior.