[gclist] [ANN] Qish rel. 0.5 (GPL) - runtime & garbage

[Basile STARYNKEVITCH]

>>>>> "Fergus" == Fergus Henderson <fjh@cs.mu.OZ.AU> writes:

    Fergus> On 02-Dec-2002, Basile STARYNKEVITCH
    Fergus> <basile@starynkevitch.net> wrote:
    >> I just released the release 0.5 -probably a beta quality
    >> release- of the qish runtime which contains a generational
    >> copying garbage collector (usable from C, in particular with
    >> some generated C code).
    >> 
    >> See http://starynkevitch.net/Basile/qishintro.html and download
    >> http://starynkevitch.net/Basile/qish-0.5.tar.gz
    >> 
    >> It could interest any people implementing a language in need of
    >> a Garbage Collector. Qish is probably a bit faster than Boehm's
    >> GC, but it is not multithreaded and requires carefully written
    >> (or machine generated) C code -respecting detailed (and
    >> documented) coding conventions.

    Fergus> The C code in Qish does not conform to the C standard.  As
    Fergus> a result, Qish is not portable. 

Agreed. I do use GCC extensions sometimes.

    Fergus>  Also, you need to compile
    Fergus> with `-fvolatile -fvolatile-global', which will reduce
    Fergus> performance even for parts of the code which do not use
    Fergus> pointers or GC at all.  You probably also need
    Fergus> `-fno-strict-aliasing'.

Actually I am not fully sure if these compile flags are needed. I
suspect that if the volatile keyword is carefully used as documented
in Qish, and if all local pointers are inside a volatile structure,
such flags are not necessary. Unfortunately, this was not my initial
coding style, and I got to need the -fvolatile -fvolatile-global
flags.


    Fergus> IMHO this is a pity, since it is not necessary.  It is
    Fergus> possible to write a generational copying garbage collector
    Fergus> with similar restrictions as Qish (single-threaded, code
    Fergus> using the collector needs to follow certain conventions)
    Fergus> in strictly conforming ANSI/ISO C code, without needing to
    Fergus> use `volatile'.  For details, see my recent paper [1].

I knew about this paper. But I have a remark (from experience). I
wrote (at work, so it is sadly proprietary -for bureaucratic reasons
only- and I cannot release it) a previous GC -for the TWO project-
similar to Qish in C++ (which is shortly explained in section 5 of
http://www.di.ens.fr/~goubault/papers/icse01.ps.gz). This C++ coded GC
also copied arguments like Fergus GC. and this detail (I speak by
profiling experience) changes a big lot the performance of the GC.

In the GC I coded for TWO, I had the following for locals pointers.

class Bas_Object; // common super class for GC-ed objects, with simple
                  // inheritance only

class Bas_Allocator; // the class for the GC, having only one instance

/* class for linking root frames */
class Bas_RootsLink {
  const int _nbr;
  Bas_RootsLink *_prev;
  Bas_Object*** const  _tabroots;
protected:
  Bas_RootsLink(int nbr, Bas_Object*** tab) : 
        _nbr(nbr), _prev(Bas_Allocator::_alroots), _tabroots(tab) {
    Bas_Allocator::_alroots  = this; 
  };
  ~Bas_RootsLink() {Bas_Allocator::_alroots = (Bas_Allocator::_alroots) ->_prev; }
public:
/* only called by BASROOTSi macros: */
  void set_root(int i, Bas_Object** const o) { _tabroots[i] = o; };
/* called by the_allocator */
  int nb_roots(void) const { return _nbr; };
}; // end of class Bas_RootsLink


// then I have a template for [len] local pointers
template <int len> class Bas_Roots : public Bas_RootsLink {
  Bas_Object** _tabroots[len];  
  Bas_Roots() : Bas_RootsLink(len, _tabroots) { ; };
  ~Bas_Roots() { ; };
  
};

// a macro to declare local GC roots
#define _BASROOTDCL(N) Bas_Roots<N> _basroot
// a macro (which copy the adress of a local pointer into the current
// Bas_Roots
#define _BASROOTSET(R,P) _basroot.set_root((R), (Bas_Object**) &(P))

// then I defined lots of macros BASROOTS1 ... BASROOTS24 like
#define BASROOTS2(P0,P1) _BASROOTDCL(2); { _BASROOTSET(0,P0); _BASROOTSET(1,P1); }

// then a typical use of such was
void* foo_fun(SomeObjectType* arg)
{ 
   SomeOtherObjectType* loc=0;
   BASROOTS2(loc, arg);
   // do something with loc & arg
}

the BASROOTS2 above expands to
  Bas_Roots<2> _basroot;
  _basroot.set_root(0, (Bas_Objects**) (&loc));
  _basroot.set_root(1, (Bas_Objects**) (&arg));

################
the problem with the above approach is the the systematic copying of
every argument and local is expansive (notably in tiny leaf
routines). Also, the "this" keyword could not be used, and has to be
explicitly copied to a local (and never implicitly used) so you had to
code any methods like

void YourObjectType::method(SomeObjectType* arg) {
  YourObjectType* self = this;
  BASROOTS2(self, arg);
  if (arg) self->doit(arg);
}

instead of the natural C++ coding

void YourObjectType::method(SomeObjectType* arg) {
    if (arg) doit(arg);
} 

    Fergus> References [1] Fergus Henderson, "Accurate garbage
    Fergus> collection in an uncooperative environment".  In
    Fergus> Proceedings of the 2002 International Symposium on Memory
    Fergus> Management, Berlin, Germany, June 2002, pages 150-156.
    Fergus> <http://www.cs.mu.oz.au/research/mercury/information/papers.html#high_level_gc>

I agree that the major non-portable hypothesis done in Qish is that
consecutive pointer arguments appear consecutively in memory (on the
call stack). But not copying them is (by experience) a significant win
in performance.

A big thanks to Fergus for his interest (and patch) in Qish. I will
try to take his comment into account for the next release.

Regards.
-- 

Basile STARYNKEVITCH         http://starynkevitch.net/Basile/ 
email: basile<at>starynkevitch<dot>net 
alias: basile<at>tunes<dot>org 
8, rue de la Faïencerie, 92340 Bourg La Reine, France