A couple garbage collector questions
Hannah Schroeter
hannah at schlund.de
Tue Apr 10 10:23:58 EDT 2001
Hello!
In article <mailman.986492109.7560.python-list at python.org>,
Skip Montanaro <skip at pobox.com> wrote:
> >>> Reference-counting exacts very heavy performance costs, no matter
> >>> what you back it up with.
> Hannah> Correct. *Except* if the compiler does heavy optimization of
> Hannah> reference count updates (i.e. if you can prove that some basic
> Hannah> block just increases the RC, later decreases it, having a net
> Hannah> effect of +- 0, you can drop both RC updates, and so on).
>This is unlikely to happen in practice. A basic block consists of a
>straightline piece of code containing no branches. There's no reason to
>increment a reference count and decrement it within the same basic block,
>since the object's reference count can't be decremented to zero by some
>other piece of code.
Example:
tmp := a
a := b
b := tmp
A simplistic interpreter may do this:
if (tmp)
tmp->rc --
if (a)
a->rc ++
tmp = a
if (a)
a->rc --
if (b)
b->rc ++
a = b
if (b)
b->rc --
if (tmp)
tmp->rc ++
b = tmp
A well done compiler could do this (slightly SSA):
tmp0 = tmp
a0 = a
b0 = b
if (tmp0)
tmp0->rc --
if (a0)
a0->rc ++
tmp1 = a0
if (a0)
a0->rc --
if (b0)
b0->rc ++
a1 = b0
if (b0)
b0->rc --
if (tmp1)
tmp1->rc ++
b1 = tmp1
a = a1
b = b1
tmp = tmp1
Now some copy propagation: tmp1 = a0, a1 = b0, b1 = tmp1 = a0
tmp0 = tmp
a0 = a
b0 = b
if (tmp0)
tmp0->rc --
if (a0)
a0->rc ++
-- removed: dead: tmp1 = a0
if (a0)
a0->rc --
if (b0)
b0->rc ++
-- removed: dead: a1 = b0
if (b0)
b0->rc --
if (a0)
a0->rc ++
-- removed: dead: b1 = a0
a = b0
b = a0
tmp = a0
Now you see that all RC manipulation has been moved together.
As the conditionals don't influence each other, we can permute them
and coalesce them for matching conditions:
tmp0 = tmp
a0 = a
b0 = b
if (tmp0)
tmp0->rc --
if (a0)
a0->rc ++
-- removed: cancelled by following conditional: if (a0): a0->rc --
-- removed: cancels out with previous conditional: if (a0): a0->rc ++
-- removed: cancels out w/ following if: if (b0) b0->rc ++
-- removed: cancels out w/ previous if: if (b0) b0->rc --
a = b0
b = a0
tmp = a0
Oh, from originally 6 RC manipulations, there are only 2 remaining.
If we can prove that tmp was void before and dead afterwards,
(i.e. it's used only here, or can be made thus by valid variable renaming)
the last tmp = a0 reference becomes dead (-> remove the if (a0): a0->rc++),
and the if (tmp0) condition is constant false.
Resulting code:
a0 = a
b0 = b
a = b0
b = a0
or: (copy propagation on b0)
a0 = a
a = b
b = a0
I.e. in principle the original instruction sequence, but completely
w/o RC manipulation.
IF a compiler does that to reference counting, *then* RC can be more
efficient than GC. If a compiler/interpreter is simplistic,
RC ist most probably slower than good current GC techniques.
If you possibly do interprocedural dataflow analysis on reference-counts,
you can gain even more. This will probably be necessary to gain
good (comparable or better than current GC techniques) perfomance
in programs that use small procedures/functions (which is encouraged
e.g. by OO programming).
Kind regards,
Hannah.
More information about the Python-list
mailing list