General GC problems

[dmitry.z...@gmail.com]

1. Phantom needs GC subsystem which is able to work in huge address
space. Phantom's address space is equal in size to all computer's
disks, which means, in near future, some tens of terabytes. So main GC
must be able to process gigabytes of disk space.

2. Of course, GC'ing terabytes can't be fast. So we need some fast and
dirty (ie collecting not all of the garbage) GC able to collect short-
living objects effectively.

At the current point I suppose to use:

For the fast/dirty GC - refcount. It will loose (not collect) objects
organized in loops and objects travelling through some of the kernel
code, but it looks like (and literature says that) refcount GC is the
best solution in this situation.

For the long/final GC - trivial mark and sweep, but executed not on
the REAL OS memory, but on the snapshot. It is obvious that object
which was garbage yesterday will still be garbage today, so objects
collected in system RAM snap are surely can be freed in current OS
state as well.

Still it bothers me that complete GC over a few terabytes of disk
space can be very time- and io-consuming. So it will be nice to have
some GC that can process huge phantom's address space partially.

Some random thoughts on subject (possible approaches):

1. Extract 'constant' part of OS memory, compact it, collect all the
pointers looking out at once and stop processing it? It will let us to
stop traversing all the 'file-like' content - big binary objects such
as video, etc. But, on the other hand, these objects are big and have
not a lot of outgoing references, so it will be cheap to check them.

2. organize objects in 'zones' and make all inter-zone references to
go through some zone-border proxy objects, do GC in zone only,
knowing for sure if we have reference to object from another zone or
no. (and move out objects which have only refs from other zone)

Well, that is it. Comments? Ideas?

[lpauzner]

Long/final GC can be based on refcount either. There are algorithms
for collecting cyclic garbage in reference counting systems. It seems
to scale better on a very large main memory.

Unfortunately, several such algorithms known to be patent pending(!),
and it may be a significant problem to find algorithm variation free
from licensing issues.

Links:
http://en.wikipedia.org/wiki/Reference_counting
http://domino.research.ibm.com/comm/research_people.nsf/pages/bacon.patents.html/$FILE/US6879991.pdf
http://domino.research.ibm.com/comm/research_people.nsf/pages/bacon.patents.html/$FILE/US7216136.pdf