[Python-Dev] iterzip() (original) (raw)

Tim Peters tim.one@comcast.net
Mon, 29 Apr 2002 19🔞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.