A couple garbage collector questions

[Hannah Schroeter]

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.