zip() function troubles

[Chris Mellon]

On 31 Jul 2007 12:57:13 -0700, Paul Rubin
<"http://phr.cx"@nospam.invalid> wrote:
> "Chris Mellon" <arkanes at gmail.com> writes:
> > Better hand in your computer, then. You're never going to find a
> > situation where the environment won't affect the running time of your
> > algorithms.
>
> The environment may affect the running time by an additive or linear
> multiplicative constant but it should never turn an O(n) algorithm
> into an O(n**2) one.
>

Hardly true. When you start to factor real world issues like memory
allocations (and all the complexities thereof) and cache misses into
algorithmic performance an algorithm certainly can change from O(n) to
O(n**2). This is one reason why real world performance is tested and
compared using benchmarks and not Big O notation.

> > For the record, the python GC is generational. This is a case of a
> > default heuristic giving pathological behavior in a corner case, not
> > anything broken about the design of the python GC.
>
> No, it is broken, per discussion on a
> comp.compilers/comp.lang.functional thread this week.  The notion of
> using a generational collector was to collect less and less frequently
> for older and older generations (e.g. doubling the amount of
> allocation between generations) but the usual solution is apparently
> to increase the heap size by some multiplicative factor when GC fails
> to free enough memory.
> --

The issue at hand has nothing to do with the generational nature of
the Python GC. It's caused by a heuristic that aggressively attempts
to reclaim objects when there are large numbers of allocations without
releases. This is a tuneable GC parameter.