Ynvich GC

I may have idea how to turn tamarin into an exact incremental GC framework, easy for managing XPCOM.

In short, the idea is to replace colored states in mark stage with an exact reference count of ALL root parents (not just immediate as in XPCOM refcount) which is permanently keeped in sync with dependency list.

Concept comparison

Let's compare XPCOM refcount (XPCOM), the present MMgc idea (MMgc), and the proposed idea (XPgc - Cross Platform gc):

Parameter \ Version	XPCOM	MMgc	XPgc
Inter-object Relations
how stored	ignored	saved in place	saved in a table
when changed	--	in a write barrier	in a write barrier
Object GC-status
mechanism	immediate refcount	white/grey/black	full refcount
when updated	in a write barrier	during mark stage	in a write barrier
when applied	in a write barrier	during sweep stage	both variants possible

Discussion

MMgc doesn't store inter-object relations in a table, though. MMgc's DWB write barrier just queues the referent (the object being pointed at) for marking, if necessary. The queue doesn't track relations--it's just a bag of objects that need to be marked. --jorendorff 06:08, 15 October 2007 (PDT)

Now, it looks like MMgc scans the entire memory in search of collectable objects.Ynvich 09:14, 15 October 2007 (PDT)

Details

Several more issues need to be addressed:

• refcount cycles;
• what is the number of parents;
• multiple inheritance.

Dealing with Cycles

When we traverse dependency table during collection, we will keep a list of visited nodes in a temporary structure. If the same node is hit second or more time, it will be ignored.

Discussion

What exactly does the write barrier "traverse"? --jorendorff 07:02, 15 October 2007 (PDT)

s/write barrier/collection/ thanks. Ynvich 09:09, 15 October 2007 (PDT)

Fast Calculation of Full Refcount

We will increase/decrease refcount of the node and all child nodes by the refcount of the parent node.

Multuple Inheritance

Object nodes should be identified by the beginning of their address space. This is guaranteed if we cast object to (void *) from one of its methods (Visitor design pattern). This must be done two times: for the parent and for the child.

It can be done like that:

• nsISupports is changed

   -unsigned int AddRef();
   +unsigned int AddRef(void *parent);
   -unsigned int Release();
   +unsigned int Release(void *parent);

• GC has something like this

   unsigned int Add(void *parent, void *child);
   unsigned int Remove(void *parent, void *child);

• parent calls:

   child->AddRef(this);
   child->Release(this);

• child calls:

 unsigned int
 nsFoo::AddRef(void *parent)
 {
   return mGC->Add(parent, this);
 }

If type-safety is mandatory, (void *) casts may be replaced with (GCObject *) casts or the like.

Functional Comparison

Let's again compare XPCOM refcount (XPCOM), the present MMgc idea (MMgc), and the proposed idea (XPgc - Cross Platform gc):

Parameter \ Version	XPCOM	MMgc	XPgc
write barrier cost (add)	O(1)	O(1)	O(1) on demand
write barrier cost (remove)	O(M), M = (changes)	O(1)	O(1)
mark stage cost	--	O(X), X = (bytes in RAM)	O(M ln N), M = (changes), N = (all)
sweep misses	leaks on cycle	conservative leaks	safe
sweep starvation	absent	possible	absent on demand

This table shows that three solutions are not worse or better, they are different. Refcount is great for design which is free of cycles, MMgc and XPgc allows to postpone processing, and XPgc is considerably better when only a subset changes states between collection cycles.

In addition, XPgc allows to do collection incrementally without additional cost.

Discussion

The chart may be misleading, because everything depends on the constant factor of the tasks that are O(1). Write barriers are executed O(N)-ish times per cycle, so the total performance of your scheme is really O(N), not O(M log N)... unless M is some large fraction of N, in which case it's O(N log N), which would be really bad. Let me know what I'm missing. :) --jorendorff 06:22, 15 October 2007 (PDT)

Write barrier code can in the order of 20 machine instructions: adding a link to the queue using pool of pre-allocated link objects. So it is really a O(1). If Q objects pass write barrier, this part of overhead is O(Q). M is meant to be the number of links, that change their state during collection, and N is the total number of links in all managed objects, X is the size of RAM. Obviously, Q <= M <= N <= X, and it is likely that Q <= M << N << X (F.e., according to generational hypothesis).

O(M ln N) is a worst case estimate of the number of instructions of M searches in an efficient data structure with N elements. It is 'worst case, because we will be searching for ranges in the index, so N can be expected as O(sqrt N). But that doesn't change O(M ln N), anyway.Ynvich 09:06, 15 October 2007 (PDT)

Comments

Storing dependencies

We must use an efficient data structure (btree most likely) to actually achieve that O (M ln N) performance. We can use in-memory sqlite tables to handle this in the beginning.

Interface

Looks like it is possible to have C interface to this GC:

• callback Sweep;
• Add(void *, void *, void (void *));
• Remove(void *, void *, void (void *)).

C interface will allow to use XPgc not only from C++, but also from other languges like Java and Python. Ynvich 03:38, 15 October 2007 (PDT)