Tremendous slowdown due to garbage collection

[Rhamphoryncus]

On Apr 12, 6:58 pm, Steve Holden <st... at holdenweb.com> wrote:
> Paul Rubin wrote:
> > Steve Holden <st... at holdenweb.com> writes:
> >> I believe you are making surmises outside your range of competence
> >> there. While your faith in the developers is touching, the garbage
> >> collection scheme is something that has received a lot of attention
> >> with respect to performance under typical workloads over the years.
>
> > Really, Python's cyclic gc is quite crude and should be upgraded to
> > something that doesn't fall into that quadratic behavior.  There was
> > some fairly detailed discussion of this in another thread last time
> > the subject came up.
>
> I'll take your word for it.

I discussed it not too long ago, but I can't seem to find the thread..

Basically, python's gen2 collections are to blame.  You get a full
(gen2) collection a linear number of times for a linear number of
allocations, but the cost of each collection is also linear, giving
you O(n**2) cost.  I think it's fairly clear that it should not be
that expensive.