[Python-Dev] iterzip()

Tim Peters tim.one@comcast.net
Mon, 29 Apr 2002 19:18:52 -0400


Let me channel Neil here.  "The list" does move out of the "frequently
collected" generation (gen0) the first time that gets collected, and works
its way into the least frequently collected generation (gen2).  The time for
futile attempts to collect the first- and second-most (gen1) frequently
collected generations doesn't grow as the program goes on.  After things get
going, they just contain tuples, and those move from gen0 into gen1 into
gen2 at the same rate they're created.  The quadratic time is due to gen2
collections:  gen2 holds "the list", and an ever-increasing number of
tuples.  gen0 never holds more than about 700 tuples, and gen1 never more
than about 8500.

This is easy to see by adding

import gc
gc.set_debug(gc.DEBUG_STATS)

at the top of the test case.  Here's a snippet from near the end of a run,
taken at a time when gen1 and gen2 collections are about to trigger:

...
gc: collecting generation 0...
gc: objects in each generation: 701 4907 736679
gc: done.
gc: collecting generation 0...
gc: objects in each generation: 701 5608 736679
gc: done.
gc: collecting generation 0...
gc: objects in each generation: 701 6309 736679
gc: done.
gc: collecting generation 0...
gc: objects in each generation: 701 7010 736679
gc: done.
gc: collecting generation 1...
gc: objects in each generation: 0 8412 736679
gc: done.
gc: collecting generation 2...
gc: objects in each generation: 0 0 745792
...

If you try this, you'll get a good gut feel for what's happening:  the
output whizzes by until hitting a gen2 collection, then there's a pause, and
the gen2 pause gets longer and longer as the program goes on.

So the primary benefit in bad cases from auto-adjusting would come from
auto-adjusting the gen2 threshold.  That's the only generation that can grow
without bound.  Before an object moves into gen2, it can get futilely
scanned just twice (once in a gen0 collection, and again in a gen1
collection).  Boosting the gen0 threshold wouldn't have much effect.