[fpc-devel] Improving Ref Counting

[DrDiettrich]

Jamie McCracken wrote:

> Rather than continuing the GC stuff which seems fruitless I thought it
> might be better to improve what we have with ref counting (whilst taking
> a leaf out of the GC book as well).

A reasonable attempt.


> 2) Have a single linked list that contains references to all managed
> objects (ansi strings, variants etc)

A pointer to the next object could be part of every managed object.

> 3) Each managed object also has a single linked list that contains
> addresses of all pointers that reference it.

Now you replace an simple reference counter by a list of pointers?
What a waste of memory and runtime :-(

Consider what will happen with every assignment to a (managed) string
variable.

> 5) dec ref count means removing the pointer's address from that list.
> When that list is empty the object is freed. (a check for eliminating
> circular refs should also be done if applicable)

A check for circular references is just what GC never has to do. That's
why GC can execute in linear time. It also cannot be determined when a
check for circular references is required, as soon as more than one
object has to be managed. This means that this check must be run very
often, with low probability that it will find discardable object
clusters.


> 6) Whenever an exception is thrown, wait until its either handled or
> fully propagated and then perform some garbage collection. (traverse the
> single linked list of all managed objects and for each object check
> whether anything that references it is still valid and delete if
> appropriate).

This requires that it's known which objects are in/valid - how that?


Your ideas are not bad at all, so let me refine your model:
{Notes: 
"object" in the following text means *managed* object.
A "client" object contains a reference to a "server" object.
}


1) Every object is accompanied by a list of references to other objects.
This list is required for the maintenance of the reference lists. The
list can become part of the RTTI, as a list of offsets to reference
fields in the objects of the same type.

2) All objects include an pointer to the next object. (Your 2).

3) Every object has a list of client objects (it is the list header). 
A reference (list record) consists of an pointer to the referenced
object, and of an pointer to the next reference to the same (server)
object. (Your 3)

4) Subroutines include a list of references to managed objects. This
list is used to determine which references become invalid, after normal
or abnormal exit from a subroutine. (Your 6)
This list can be optimized by allocating all such variables in a
contiguous stack area, to eliminate linked-list management overhead.
Subroutine parameters must be managed similarly, but they can't be
reordered. The lists are static, part of the subroutine signature.


Now let's replace (3) by this:

5) Non-local variables are collected in another list of references.

and, oh wonder, we have all what's required to implement a GC!

In your model the reference lists (3) must be updated with every
assignment to a reference variable, and after exit from a subroutine.
Adding a reference (inc ref) doesn't cost much, but removing a reference
(dec ref) from the linked list can become expensive.

In a mark/sweep GC an additional mark bit in every object is required.
There exist enough usable bits, e.g. the low bits in every object
reference. In the first pass (mark) the list of static (non-local)
variables is examined, and all referenced objects are marked (alive).
Then the active subroutine list (stack) is traversed, and all referenced
objects are marked. Finally the list of all objects is traversed and
split into a "life" and an "unknown" list. Every marked object is put
into the "life" list, and all objects that it references are marked
alive as well. In a simple implementation the remaining "unknown" object
list can be traversed until it contains no more alive members. More
sophisticated algorithms may do that recursively, where recursion is
limited by the number of yet unmarked objects. The key point is the
linear traversal of the lists, without searches. In the final pass
(sweep) the mark bits in the "life" list are cleared, and it becomes
(is) the list of all remaining objects (2), and the objects in the
"unknown" list are discarded.

This may sound complicated, but all that happens in linear time. When
swapping will occur during GC, the same will occur in yourX-MozilX-Mozilla-Status: 0009ists are updated. Now it should be clear why frequent
updates of the management information should be avoided.


I'm not perfect, any comments on above are appreciated.

DoDi