QISH introduction

Basile STARYNKEVITCH
basile@starynkevitch.net
http://www.starynkevitch.net/Basile/
8, rue de la Faïencerie, 92340 Bourg La Reine, France

$Id: qishintro.tex 19 2005-05-08 17:35:50Z basile $

Table of Contents

• 1  Short overview
• 2  Requirements
• 3  The garbage collector
  • 3.1  Introductory examples
  • 3.2  Data structure of objects
  • 3.3  required coding practices
    • 3.3.1  No interior pointers
    • 3.3.2  No multi-threading
    • 3.3.3  Limited global data
    • 3.3.4  Pointers are volatile
    • 3.3.5  Indicate arguments and locals to the GC
    • 3.3.6  No composition of function calls
    • 3.3.7  Complete allocation
    • 3.3.8  Notification of updates (write barrier)
    • 3.3.9  Optional explicit garbage collection
    • 3.3.10  Exception handling
    • 3.3.11  Utility routines
  • 3.4  Mandatory routines to the GC
    • 3.4.1  Copying function qish_gc_copy_p
    • 3.4.2  Minor scan of a movable object qish_minor_scan_p
    • 3.4.3  Full scan of a movable object qish_full_scan_p
    • 3.4.4  Full scan of a fixed object qish_fixed_scan_p
  • 3.5  Using Qish in C++ code
  • 3.6  Advanced application explicit forwarding.
• 4  A tiny benchmark
  • 4.1  benchmark results
  • 4.2  Tuning Qish
• 5  ToDo list (multi-threading?)

1  Short overview

2  Requirements

• Ruby (for scripting) see http://www.ruby-lang.org/. I don't know much Perl and prefer Ruby for scripting tasks
  
  
• a Glibc system such as GNU/Linux, etc... I am using a Linux Debian/Sid system with a 2.4.22 kernel.
  
  
• The GNU make utility, since I depend upon GNU make extensions - see http://www.gnu.org/software/make/. I am using make 3.80.
  
  
• The GNU GCC compiler version 3.3 or later (I recommend against using 3.2, 3.1, 3.0 or 2.x versions) - see http://www.gnu.org/software/gcc/.
  
  
• the Tiny CC compiler (by Fabrice Bellard) on http://tinycc.org is very useful to compile (perhaps generated) C code using Qish (but you may compile the runtime with GCC using optimisations). tcc 0.9.14 compiles very quickly (sometimes 10 times faster than gcc 3.2) while producing code no more than 30% slower than gcc -O3.
  
  
• This documentation is processed with LaTeX and HeVeA. HeVeA is a good LaTeX to HTML translator. See http://para.inria.fr/~maranget/hevea/ It is written in Ocaml. See http://www.ocaml.org/
  
  
• I am using PRCS for version control. See http://prcs.sourceforge.net/. But it is only needed in the scripts/qish_snap Ruby script. You should not need it otherwise.

3  The garbage collector

3.1  Introductory examples

struct ktuple_t {
unsigned header; // first word is a common discriminating header
void* tab[0]; // next words are GC-ed object pointers
};

struct ktuple_t*
ruk_dup_vector(struct ktuple_t* volatile vec) { // volatile arguments!

struct ktuple_t* volatile tup=0;
// local variable tup is also volatile
int kd=0; int len=0; int i=0;

// mandatory start of GC-ed frame
BEGIN_SIMPLE_FRAME(1, vec, 1, tup);
// we have 1 garbage collected argument starting at vec
// we have 1 GC-ed local pointer starting at tup

kd = ruk_kind(vec);
if (kd == KIND_VECTOR || kd == KIND_TUPLE) {
len = HEADERSIZE(vec->header);

tup = qish_allocate(sizeof(*tup) + len*sizeof(void*));
//a garbage collection may occur above, changing many pointers

tup->header = MAKEHEADER(KIND_VECTOR, len);
for (i=0; i<len; i++) tup->tab[i] = vec->tab[i];
} // end if kind is KIND_VECTOR or KIND_TUPLE

EXIT_FRAME();
return tup;
} // end of ruk_dup_vector

// preferred coding
void* foo(struct ktuple_t* volatile tup,
        void* volatile val) {
// declare and clear a volatile _locals_ structure for local pointers
volatile struct { void* ptr; void* res; } _locals_ = {0,0};
BEGIN_LOCAL_FRAME(2,tup);
//... use _locals_ fields as the only GC pointer local variables
if (some_condition(tup))
_locals_.res = val;
//...
EXIT_FRAME();
return _locals_.res;
}

// generated by gen_locals script
#define l_res _locals_.res

// this function set the component of a vector returning its previous value
void*
ruk_vector_set(struct ktuple_t* volatile tup, void* volatile val, int rk) {
int sz=0;
void* oldval=0;
BEGIN_SIMPLE_FRAME (2, tup, 1, oldval);
if (ruk_kind(tup) != KIND_VECTOR) goto end;
sz = HEADERSIZE(tup->header);
if (rk<0 || rk>=sz) goto end;
oldval = tup->tab[rk];
tup->tab[rk] = val;
qish_write_notify(tup); // notification of a changed object
end:
EXIT_FRAME();
return oldval;
}

3.2  Data structure of objects

enum {
  KIND_NONE=0 /*unused*/,
  KIND_BINOP,
  KIND_VARIABLE
};

  enum { OP_NONE, OP_ADD, OP_SUB, OP_MULT, OP_DIV };

  struct binop_st {
    short kind; /*always KIND_BINOP*/
    short opcode;
    void* left;
    void* right;
  };

 
  struct variable_st {
    short kind; /*always KIND_VARIABLE*/
    short namelen; /*length of name*/
    void* value; /*value of variable*/
    char name[1]; /*actually [namelen] bytes + final '\0' */
  };

3.3  required coding practices

3.3.1  No interior pointers

3.3.2  No multi-threading

3.3.3  Limited global data

1. you can use the small (fixed size) ¹⁵ array of global pointers qish_roots as you wish, reading and writing in it any pointer to a GC-ed object (or the nil pointer, or a tagged integer).
   
   
2. Each module is described by an entry in qish_moduletab. Each such entry contain a rather constant pointer. You can set or change the constant of module î to pointer p by calling qish_changeconstant(i, p), and you can get this constant by qish_constant(i) or even accessing directly the km_constant field in the entry of qish_moduletab. In practice, you could make this constant point to a structure of GC-ed pointers.

3.3.4  Pointers are volatile

#error formal argument not declared volatile
void* foo(struct variable_st* var) { /*body*/ }

/* explicit volatile argument */
void* foo(struct variable_st* volatile var) { /*body*/ }

3.3.5  Indicate arguments and locals to the GC

3.3.6  No composition of function calls

#error no function composition
l_res = f(g(y),l_z->ptrfield);

/* use a temporary variable */
l_tmp = g(y);
l_res = f(l_tmp, l_z->ptrfield);
}

3.3.7  Complete allocation

• qish_allocate(bytesize) to allocate an ordinary (movable) object with a natural (word) alignement. This is the most often used allocation function; usually the bytesize is some sizeof(type).
  
  
• qish_allocate_aligned(bytesize,alignment) to allocate a movable object with an explicit alignment expressed in bytes (which must be a small power of 2 in words).
  
  
• qish_fixed_alloc(bytesize,finalizer) to allocate a fixed finalized object (aligned to at least the sizeof(double)), with an optional finalising routine (called by the GC with the adress of the fixed object).

3.3.8  Notification of updates (write barrier)

3.3.9  Optional explicit garbage collection

3.3.10  Exception handling

BEGIN_EXCEPT_BLOCK(exv);
// your code here may directly or indirectly throw ``exceptions''

CATCH_EXCEPT_BLOCK(cod,_locals_.exobj);
// your code handle here exception of error cod ...
// ... with _locals_.exobj set to the exception object

// this ends the exception handling code
END_EXCEPT_BLOCK(exv);

3.3.11  Utility routines

• qish_strhash(string,length) compute an hashcode of a given string with an explicit length; if this length is negative, the string is supposed null-terminated, as if length == strlen(string)
  
  
• qish_sigexecvp(file,argv) spawn a process to execute file with the given program argv null-terminated arguments and wait for its completion.
  
  
• qish_prime_after(i) returns a prime number bigger than i provided that 0 < i < 10000000 = 10⁷ which can be useful for hashtables, etc.
  
  
• qish_parameter(name) retrieves the string-value of a runtime parameter of a given name.
  
  
• qish_put_parameter(name,val) put into the runtime paramter named name the string value val
  
  
• qish_parse_configfile(filename) parse a simple configuration file and set parameters appropriately
  
  
• qishgc_init(); should be called once to initialize the garbage collector, before any allocation!
  
  
• qish_load_module(modulename,rank) loads (with dlopen) a shared object module at a given rank. It returns 0 iff ok. A previous module at the same rank is closed latter with qish_postponed_dlclose
  
  
• qish_get_symbol(name,modrank) gets the address of the symbol of given name in a module of given modrank or in any modules if modrank < 0
  
  
• qish_postponed_dlclose() close any previous module with dlclose and should be called when the call stack is very low (i.e. in your event loop)
  
  
• qish_panic is a printf-like macro which aborts after displaying a panic message.

3.4  Mandatory routines to the GC

3.4.1  Copying function qish_gc_copy_p

/*after determining the dynamic object type*/
*((object_type*)dst) = *((object_type*)src); 
 return ((object_type*)dst)+1; 

3.4.2  Minor scan of a movable object qish_minor_scan_p

/*after determining the dynamic object type*/
QISHGC_MINOR_UPDATE(((object_type*)src)->ptrfield1);
QISHGC_MINOR_UPDATE(((object_type*)src)->ptrfield2);
/* etc for every field*/
 return ((object_type*)src)+1; 

3.4.3  Full scan of a movable object qish_full_scan_p

/*after determining the dynamic object type*/
QISHGC_FULL_UPDATE(((object_type*)src)->ptrfield1);
QISHGC_FULL_UPDATE(((object_type*)src)->ptrfield2);
/* etc for every field*/
 return ((object_type*)src)+1; 

3.4.4  Full scan of a fixed object qish_fixed_scan_p

/*after determining the dynamic object type*/
QISHGC_FULL_UPDATE(((object_type*)src)->ptrfield1);
QISHGC_FULL_UPDATE(((object_type*)src)->ptrfield2);
/* etc for every field*/
 return;

void* gc_copy(void**padr, void* dst, const void* src) {
  switch (*(short*)src) {
  case KIND_BINOP:
    *((struct binop_st*)dst) = *((struct binop_st*)src);
    return ((struct binop_st*)dst)+1;
  case KIND_VARIABLE:
    {  struct variable_st* srcvar = src;
       int srcnamlen = srcvar->namelen;
       memcpy(dst, src, sizeof(struct variable_st)+srcnamlen);
       if (srcnamlen & (sizeof(void*)-1)) {
         /*round up name length to word*/
         srcnamlen |= (sizeof(void*)-1); srcnamelen++;
       }
       return ((struct variable_st*)dst)->name + srcnamlen;
    }
  }
}

void* minor_scan(void*ptr) {
  switch (*(short*)ptr) {
  case KIND_BINOP: 
    QISHGC_MINOR_UPDATE(((struct binop_st*)ptr)->left);
    QISHGC_MINOR_UPDATE(((struct binop_st*)ptr)->right);
    return ((struct binop_st*)ptr)+1;
  case KIND_VARIABLE:    
    {  struct variable_st* var = ptr;
       int namlen = var->namelen;
       QISHGC_MINOR_UPDATE(var->value);
       if (namlen & (sizeof(void*)-1)) {
         /*round up name length to word*/
         namlen |= (sizeof(void*)-1); namelen++;
       }
       return var->name + srcnamlen;
    }
  }
} 

3.5  Using Qish in C++ code

1. no implicit or explicit use of this. Since it is not possible to declare the argument this to be a volatile pointer, you should not use it (either explicitly as in this->method(foo) or this->_field or implicitly as in method(foo) or _field). Instead, copy this to a local pointer, using it explicitly. This stylistical constraint is annoying.
   
   
2. no multiple inheritance. Since Qish does not support interior pointer, you cannot use multiple inheritance.
   
   
3. Have a tree and not a forest of classes by defining a common superclass to all your GC-ed objects. The virtual table pointer is usually the first word of such objects.

3.6  Advanced application explicit forwarding.

4  A tiny benchmark

4.1  benchmark results

• Qish GC (standard birth size of 8Mbytes): CPU 9.160 user + 4.510 system = 13.670 total time (sec); done 131 minor and 16 full garbage collections
  
  
• Boehm's GC: CPU 18.570 user + 0.310 system = 18.880 total time (sec); Completed 42 collections
  
  
• explicit malloc and free: CPU 24.810 user + 2.810 system = 27.620 total time (sec)
  
  
• Qish GC with the birth size reduced to 4 Mbytes made with make OPTIMFLAGS='-O2 -DNDEBUG -DMIN_BIRTH_SIZE=4194304' clean lib benchqish: CPU 13.810 user + 6.350 system = 20.160 total time (sec); Qish done 257 minor and 39 full garbage collections
  
  
• Qish GC with the birth size increased to 16Mbytes: CPU 6.900 user + 4.350 system = 11.250 total time (sec) Qish done 67 minor and 6 full garbage collections
  
  
• Qish GC with the birth size increased to 32Mbytes (probably not significant, since it is similar to the live object size): CPU 5.920 user + 3.700 system = 9.620 total time (sec) Qish done 34 minor and 2 full garbage collections
  
  
• Boehm's GC with holes make OPTIMFLAGS='-O2 -DNDEBUG -DHOLES' clean lib bench, so for every used node allocated, an extra useless (dead) node is also allocated: CPU 43.220 user + 0.380 system = 43.600 total time (sec) Completed 72 collections
  
  
• Qish GC with holes (and standard birth size of 8Mbytes): CPU 12.490 user + 7.380 system = 19.870 total time (sec) Qish done 197 minor and 23 full garbage collections
  
  
• Qish GC with holes and increased birth size of 16Mbytes: CPU 9.560 user + 6.460 system = 16.020 total time (sec) Qish done 99 minor and 10 full garbage collections
  
  
• Qish GC with holes and small birth size of 4Mbytes: CPU 17.530 user + 8.500 system = 26.030 total time (sec) Qish done 389 minor and 52 full garbage collections

4.2  Tuning Qish

• use the usual trick of allocating several objects simultanously (in one single qish_allocate for all of them).
  
  
• explicitly invoke qish_garbagecollect when needed (e.g. at start of a topmost loop...).
  
  
• set the number QISH_NB_ROOTS of variable roots (ie the size of the qish_roots global array) in include/qish.h to your needs. Leave it at most to a few hundred or dozen.
  
  
• change the MIN_BIRTH_SIZE and MAX_BIRTH_SIZE and FULL_GC_THRESHOLD in lib/qigc.c. The minimal birth size is a sensitive number (8 megabytes by default). I believe it should be at least half a megabyte (and at most a fraction, e.g. the tenth, of your available RAM). The maximal birth size limits the maximal size of allocated objects.
  
  
• change the QISH_MAXNBCONST number (65536) to a power of two (at least 1024). It is the maximal number of global constant pointers (for QISH_GLOBCONST)
  
  
• if your plateform has enough registers (this is false for x86 with 6 usable registers only) you could (with GCC) reserve global registers for qishgc_birth_cur and qishgc_birth_storeptr global variables (in include/qish.h).

5  ToDo list (multi-threading?)

1

On some machines you'll need to flush the register stack in qish_garbagecollect - for example, Sparc machines might need ta 3 to flush registers

2

With this flag, Qish compiles without warnings both on GNU gcc-3.2 with -pedantic -std=c99 and on tcc - see http://tinycc.org/

3

Boehm's GC has an interface compatible with malloc, is compatible with threads and finalization, and is used in GCC-3 for the Java runtime

4

Unlike Bartlett's GC -1990- US patent 4,907,151 - thanks to Gerd Moellmann for the reference

5

You tell the GC where are the stack pointers with the BEGIN_LOCAL_FRAME or equivalent macro, which tells the GC the number of local pointers, the first of them, and the number of argument pointers and the first such argument.

6

You tell the GC where are pointers inside heap objects by explicitly providing mandatory routines (see section 3.4) to scan and copy such heap objects.

7

This is why the volatile keyword is required for arguments and for the _locals_ structure.

8

But every GC, even conservative, for C requires some coding style, usually much less restrictive than for Qish...

9

Tcc don't optimise much and ignores the volatile keyword. The generated code is about 30% slower than GCC with optimisation, but the compilation time is sometimes ten times faster than with gcc.

10

it used to be GPL only.

11

In the past I experimented on a reflexive system that I also named Qish - they have no much in common except the name and the author

12

A zeroed first word indicates forwarded objects to the GC

13

The pointer could be some kind of descriptor, or even a C++ vtable pointer, if you have a tree of classes sharing a common root class, with only single inheritance, and virtual methods.

14

Conservative GCs [e.g. Boehm's] are much easier to use, but they might leak, may be slower on some applications, and do not compact memory. But Boehm's GC is not disruptive like Qish, and has an API compatible with (or similar to) malloc.

15

The global roots is an array of QISH_NB_ROOTS pointers defined as 64 in qish.h. You could if needed change it to a rather small value (at most a few hundreds): at every garbage collection, the whole roots array is scanned and updated, so having lots (e.g. thousands) of such roots will not be reasonable.

16

At least each function using directly or not the GC, i.e. either allocating memory with qish_allocate or calling -directly or indirectly- any function which itself does allocation

17

If you use C++ exceptions, ensure (by coding tricky appropriate constructors and destructors) that the EXIT_FRAME is called on exceptional frame unwinding. You are on your own.

18

So all occurrences are replaced only after a major full garbage collection; after a minor collection only some pointers are replaced!

19

If you need multi-threaded capable garbage collection, I suggest using Hans Boehm's collector.

This document was translated from L^AT_EX by H^EV^EA.