[Python-ideas] Concurrent refcounting research

[Adam Olsen]

On 10/16/07, Jason Orendorff <jason.orendorff at gmail.com> wrote:
> GIL-slayers take note.  Here are two papers about concurrent reference counting:
>
>     An On-The-Fly Reference Counting Garbage Collector for Java
>     Levanoni and Petrank, 2001.
>     http://www.cs.technion.ac.il/~erez/Papers/refcount.ps
>
>     Efficient On-the-Fly Cycle Collection
>     Paz, Bacon, Kolodner, Petrank, and Rajan, 2005.
>     http://www.cs.technion.ac.il/%7Eerez/Papers/CycleCollection.ps
>
> "On-the-fly" means the algorithm is neither "fully concurrent" nor
> "stop the world".  Rather, each thread pauses occasionally to do some
> work.  Instead of a GIL, you have a lock that covers this periodic
> bookkeeping.
>
> The details are awfully complex, but there may be insights worth
> gleaning regardless.

A key assumption of these papers (and presumably most such papers) is
that you have a true tracing GC to fall back on, not one bootstrapped
from reference counts like CPython has.  This means that long-lived or
shared objects can disable reference counting entirely, and not face
the severe contention it would otherwise create.


-- 
Adam Olsen, aka Rhamphoryncus