Circular references and python

[Tim Peters]

[Neel Krishnaswami, on modern generational gc]

[James Logajan]
> Have the algorithms improved,

Very much so, but also very much more complex.  The best require subtle
platform-dependent HW and/or OS support (e.g., being able to mark pages as
read-only, then intercept the memory errors raised when an attempt is made
to write into them).

> or have clock speeds gotten high enough that the problem has been
> submerged?

Neel means improvement in percentage of total runtime consumed by gc, so
clock rate isn't relevant.

> Aren't there important pathological problem domains (data structures)
> which limit most all GC schemes?  I know in sorting, I have a choice
> of quick-sort [etc; worst case vs expected case]

There are guaranteed real-time GC schemes too, but that's really a different
area.  Python doesn't even guarantee that, e.g., list.append works in
bounded time.  Don't be paranoid unless you *need* to be <0.9 wink>;
Python's reference counting isn't real-time either.

> ...
> On the other hand, if I'm willing to run just a tad slower than
> quick-sort, I can use heap-sort and be assured of N*log(N) complexity
> for all orderings.

It's more like a factor of 2 in this specific case.  By adding a "virtual
recursion depth" counter to quicksort, it's possible to detect bad cases and
switch to (e.g.) heapsort for pathological subfiles, thus giving up only
*truly* "a tad" on quicksort's expected performance, while still
guaranteeing heapsort's worst-case performance.  There are analogues in the
GC world.

> I'll admit I'm not sure what the situation is with GC these days;
> any good (and relatively current) books on the subject?

Paul Wilson's survey paper is very good, and should be available on the web
(sorry, no time to search for it now -- University of Texas is a good clue).

1996's "Garbage Collection:  Algorithms for Automatic Dynamic Memory
Management" (Wiley & Sons), by Richard Jones and Rafael Lins, is the best
recent book that I know of.  It's excellent -- and their pseudo-code looks
an awful lot like Python!

maybe-not-a-coincidence-before-this-is-over-ly y'rs  - tim