[gclist] Detlef's Run-time Typing RCMap

Giuseppe Attardi attardi@DI.Unipi.IT
Wed, 14 Apr 1999 09:41:45 +0200 (MET DST)

   From: Cppljevans@aol.com
   Date: Tue, 13 Apr 1999 16:36:42 EDT
   Reply-To: Cppljevans@aol.com

   In the article "Garbage Collection and Run-time Typing as a C++ Library" 
   (from the _1992 Usenix C++ Conference Proceedings_) David L. Detlef described 
   a method of generating a map of internal pointers, RCMap, for each garbage 
   collected c++ class without compiler support.  However, I've been unable to 
   find anyone else using this method.  In particular, Attardi's "A Customizable 
   Memory Management Framework" from the 1994 USENIX C++ Conference 
   Proceedings_, does not mention this article; yet, Attardi's implementation 
   has, in file cmm.cpp, a method, GmmObject::getFieldTable, which is 
   essentially Detlef''s RCMap.  However, this is optionally included in the 
   source (via #if..#endif), and I didn't find how he calculated this. This code 
   is at /pub /project /posso /cmm /cmm-1-9.tgz at ftp.di.unipi.it .  

CMM uses a method traverse() to trace objects.
A version for this method must be supplied for each collectable class.

Here is an example for a node structure:

struct  cell : public CmmObject 
  cell  *car;
  cell  *cdr;
  int  value;
  void traverse()
      Cmm::heap->scavenge((CmmObject **)&car);
      Cmm::heap->scavenge((CmmObject **)&cdr);

Alternatively one can use a single definition for traverse() which uses
a class specific table to identify pointers.
Here is the same example:

struct  cell : public CmmObject 
  cell  *car;
  cell  *cdr;
  int  value;
  CmmFieldTable& getFieldTable()
      static CmmFieldPtr fields[] = { CmmFieldPtr(&cell::car),
				      CmmFieldPtr(&cell::cdr) };
      static CmmFieldTable table = { 2, fields };
      return table;

  CmmHeap* heap = Cmm::heap;
  CmmFieldTable& table = getFieldTable();
  int count = table.count;
  CmmFieldPtr* fields = table.fields;
  for (int i = 0; i < count; i++)
      CmmFieldPtr fp = fields[i];

typedef CmmObject* (CmmObject::*CmmFieldPtr);

The idea of the FieldTable was contributed by Patrick C. Beard
Experiments have shown however that pointers to members are not implemented
very efficiently.
For instance a call to scavenge() using FieldTable requires 15 machine
instructions on a Sparc, instead of a single one in the other version.

-- Beppe