RE: robustness vs. conservative GC

[Bernard Dautrevaux <Dautrevaux at microprocess dot com>]

--- 

> -----Original Message-----
> From: dewar@gnat.com [mailto:dewar@gnat.com]
> Sent: Monday, July 30, 2001 9:04 PM
> To: fjh@cs.mu.oz.au; lord@regexps.com
> Cc: gcc@gcc.gnu.org
> Subject: Re: robustness vs. conservative GC
> 
> 
> <<  Any scheme for doing exact GC without cooperation from 
> the compiler
>   back-end needs to store pointers in a known location on the 
> stack, rather
>   than in registers, so that they can be updated when objects 
> are moved.
>   This denies the back-end compiler freedom to put such pointers in
>   registers.  Register allocation obviously has a big effect 
> on performance.
> >>
> 
> I don't accept that, and there are most certainly counter examples to 
> this claim (e.g. IBM mainframe SPITBOL). It is fine to have 
> pointers in
> registers, providing that you have sufficient information to 
> track them
> down, i.e. know where the register values are saved.
> 
> With regard to problems caused by optimizations, a tricky 
> case is virtual
> origins for arrays. This can be handled (see Steve Burov's thesis from
> IIT, 1977, R. Dewar advisor for a scheme applicable to Alogol 68 - in 
> fact while you are at it, read all the Algol-68 literature on garbage
> collection, which always assumed a type accurate model, and also had
> to deal with thread safety). However, it is definitely tricky, and in 
> fact it is possible to do virtual origin stuff at the source level in 
> C that can mess up a conservative allocator -- sure sure, I know this
> is not strictly legal C, but it is C that will in practice work over a
> wide range of architectures, providing that you are not using 
> conservative
> GC.
> 

Another tricky C pattern is the one that allow to maintain doubly-linked
lists while using only ONE pointer-sized link field in each record:

struct node {
	unsigned long	link;
	/* data fields here */
};

struct node* head;
struct node* tail;

walk_forward() {
	struct node* prev = 0;
	struct node* current = head;
	struct node* next;

	while (current) {
		/* do something on it */
		next = (struct node*)(((unsigned long)prev) ^
current->link);
		prev = current;
		current = next;
	}
}

The idea here is that the link field holds the exclusive or of the address
of its previous and following nodes; the first one has no previous node and
the last one no following one (that is their addresse are 0).

You can then walk through the list in either direction, just by keeping
track of from where you're coming and where you are.

The problem is that this is quite safe C (or even C++) code, that can be
very robust, quite efficient in execution time and VERY efficient in memory
consumption (especially if the data hold is short) but will definitely BREAK
any conservative GC.

However I must admit this will probably break *any* GC, except if there is
ways for the programmer to provide a "set-closure" algorithm :-)

Just my .02$

	Bernard

--------------------------------------------
Bernard Dautrevaux
Microprocess Ingenierie
97 bis, rue de Colombes
92400 COURBEVOIE
FRANCE
Tel:	+33 (0) 1 47 68 80 80
Fax:	+33 (0) 1 47 88 97 85
e-mail:	dautrevaux@microprocess.com
		b.dautrevaux@usa.net
-----------------------------------------