[Texmacs-dev] Reference counting vs. conservative garbage collection

[Joris van der Hoeven]

It may be a good idea to make up a list of pros and cons of
our reference counting scheme (combined with fast allocation of
small objects) and conservative garbage collection.

Pros of reference counting
--------------------------
1. It is naturally incremental.
2. The worst-case overhead is "reasonably" small,
   so a minimal speed is garanteed.
3. It is relatively well adapted to the nature of TeXmacs,
   where cyclic pointer dependencies should remain rare.

Cons of reference counting
--------------------------
1. One has to check the absence of cyclic unused objects.
2. It does not allow for compactification.
3. All pointer operations have a small overhead.
4. Impossibility to do the collection in idle time.

1) We might temper the first drawback by implementing some tools
which allow for the automatic detection of cyclic objects,
like GC, Valgrind, modified pointer classes in debugging mode.

2) The second drawback is more structural, but it is also present
in conservative garbage collection (like Boehm-GC) which cannot
detect all pointers in a 100% reliable way.

3) The third drawback can be reduced by introducing const T& or
T::in types, at least for the core library. Of course, this does
not reduce the overhead for assignments to locally defined variables.

On the other hand, from the efficiency point of view, one has to
compare the cost of the small overhead with the cost of garbage
collection. For this, we have to find out how many times x
an average object is being copied. The cost of a fast garbage
collector should not exceed x times the number of allocations
times the cost of the reference counting overhead.

Moreover, for an incremental conservative garbage collector,
an additional overhead is needed in order to avoid the problem
I mentioned in my email yesterday. This can either be done by
blacklisting pages (I need to learn more about that, but it seems
that this can be quite rough) or by manually implementing
the GC and ... adding a small check when assigning pointers.
In other words, it seems that some small overhead for pointer
assignment is unavoidable if we want an incremental GC.

4) Reference counting forces us to do the GC in an on-the-fly way.
It might be interesting to delay this work to moments when
the editor waits for input. However, it may turn out that
on-the-fly garbage collection has a better cache behaviour,
because unneeded memory is returned quickly.

Other notes
-----------
1) It might be interesting to look how well our memory management
system for small objects (90% of the memory; the vaste majority
of allocations/deallocations) preserves locality. For that,
you may take a look at fast_alloc.cc and compute the mean
distances between successive objects in the linked lists
with free objects (for each size 4, 8, ..., 256).

2) If we have a marking/copying algorithm, then reference counting
may be combined with a copying compactifier which is launched at
idle time. This is interesting in relation with note 1),
because I suspect that the "mean locality" will decrease as
a function of time.