[Python-Dev] extremely slow exit for program having huge (45G) dict (python 2.5.2) (original) (raw)

Nick Coghlan ncoghlan at gmail.com
Tue Dec 23 02:24:44 CET 2008

Steven D'Aprano wrote:

This behaviour appears to be specific to deleting dicts, not deleting random objects. I haven't yet confirmed that the problem still exists in trunk (I hope to have time tonight or tomorrow), but in my previous tests deleting millions of items stored in a list of tuples completed in a minute or two, while deleting the same items stored as key:item pairs in a dict took 30+ minutes. I say plus because I never had the patience to let it run to completion, it could have been hours for all I know.

There's actually an interesting comment in list_dealloc:

/* Do it backwards, for Christian Tismer.
   There's a simple test case where somehow this reduces
   thrashing when a *very* large list is created and
   immediately deleted. */

The "backwards" the comment is referring to is the fact that it invokes DECREF on the last item in the list first and counts back down to the first item, instead of starting at the first item and incrementing the index each time around the loop.

The revision number on that (13452) indicates that it predates the implementation of PyObject_Malloc and friends, so it was probably avoiding pathological behaviour in platform malloc() implementations by free'ing memory in the reverse order to which it was allocated (assuming the list was built initially starting with the first item).

However, I'm now wondering it if also has the side effect of avoiding the quadratic behaviour Mike has found inside the more recent code to release arenas back to the OS.

I'm working on a simple benchmark that looks for non-linear scaling of the deallocation times - I'll include a case of deallocation of a reversed list along with a normal list and a dictionary.

Cheers, Nick.

-- Nick Coghlan | ncoghlan at gmail.com | Brisbane, Australia

More information about the Python-Dev mailing list