Program very slow to finish

[Tim Peters]

[Roeland Rengelink]
> I'm pretty sure this is a problem with the garbage collector, I did some
> measurements showing bad (O(n**2)) performance when collecting large
> numbers of objects at once (as happens when your dicts are deleted at
> the end of your program). I filed a bug report (#477963) on it. See:
>
>
<http://sourceforge.net/tracker/index.php?func=detail&aid=477963&group_id=54
70&atid=105470>
>
> for more details

I expect you're just measuring your platform's cache performance.  Here's
the output from running on a Win98SE box w/ 256MB RAM (I'll leave out the
creation times because they aren't interesting; note too that time.time() on
Windows has poor precision, so the numbers are mostly nonsense for the
smallest dicts):

size:   10000, destruction:  0.00 (usec/elem)
size:   20000, destruction:  2.50 (usec/elem)
size:   50000, destruction:  1.20 (usec/elem)
size:  100000, destruction:  1.10 (usec/elem)
size:  200000, destruction:  1.10 (usec/elem)
size:  400000, destruction:  1.25 (usec/elem)
size:  600000, destruction:  1.37 (usec/elem)
size:  800000, destruction:  1.45 (usec/elem)
size: 1000000, destruction:  1.54 (usec/elem)

So buy more RAM <0.5 wink>.

This is the code that deallocates dicts:

	for (ep = mp->ma_table; fill > 0; ep++) {
		if (ep->me_key) {
			--fill;
			Py_DECREF(ep->me_key);
			Py_XDECREF(ep->me_value);
		}
	}

That is, it's a single scan over the key+value pairs, decrementing the
refcounts on each.  Note that while a left-to-right scan of the container is
cache-friendly, dicts work hard to "randomize" the offsets at which keys are
stored, so the memory pointed to *by* ep->me_key (containing your string
objects) has no useful relation to the order in which you created your
string objects:  you're going to get mountains of cache misses during
deallocation.

It's a mystery why deallocation takes so much longer than allocation when
things go bad (look at it:  the deallocation code is dead simple).  I
tracked down one of those long ago in hideous detail, and it turned out to
be due to the platform free() trashing like mad trying to coalesce adjacent
free'd areas.  I suspect every platform has its own tale of woe to relate
here.