[darius at phidani.be: GC and Mercury]

[Fergus Henderson]

-----Forwarded message from Darius Blasband <darius at phidani.be>-----

Received: from mercury.miscrit.be (www.miscrit.be [194.78.53.194]) by mulga.cs.mu.OZ.AU with ESMTP
	id SAA25650; Sat, 14 Mar 1998 18:58:13 +1100 (EST)
Received: from goedel.miscrit.be ([194.78.53.212]) by mercury.miscrit.be
          (Post.Office MTA v3.1 release PO203a ID# 0-37066U100L100S0)
          with SMTP id AAA281; Sat, 14 Mar 1998 08:58:11 +0100
Received: by goedel.miscrit.be (4.1/SMI-4.1)
	id AA15383; Sat, 14 Mar 98 08:48:57 +0100
Received: from mercury.miscrit.be ([194.78.53.209]) by goedel.miscrit.be.miscrit.be (4.1/SMI-4.1)
	id AA15377; Sat, 14 Mar 98 08:48:55 +0100
Received: from out4.ibm.net ([165.87.194.239]) by mercury.miscrit.be
          (Post.Office MTA v3.1 release PO203a ID# 0-37066U100L100S0)
          with ESMTP id AAA283; Sat, 14 Mar 1998 08:58:05 +0100
Received: from darius (slip202-135-133-71.jk.id.ibm.net [202.135.133.71]) by out4.ibm.net (8.8.5/8.6.9) with SMTP id HAA172184; Sat, 14 Mar 1998 07:57:48 GMT
Message-Id: <3.0.3.32.19980314071925.006b54d8 at pop03.ca.us.ibm.net>
X-Sender: beinet.phidani at pop03.ca.us.ibm.net
X-Mailer: QUALCOMM Windows Eudora Light Version 3.0.3 (32)
Date: Sat, 14 Mar 1998 07:19:25 +0100
To: argo at miscrit.be
From: Darius Blasband <darius at phidani.be>
Subject: GC and Mercury
Cc: mvb at miscrit.be
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Sender: owner-argo at miscrit.be
Precedence: bulk
Reply-To: argo at miscrit.be

>The train algorithm is supposed to allow the release of large areas of
>memory in one block, thus making the collection of garbage a less
>disruptive process. At Sun, it is said that collection time would never
>exceed 3msec (but don't ask me in which conditions).
>
>I have asked Darius Blasband - who has a lot of expertise in GC for OO
>languages and a lot of expertise in compiler development - what he
>thought about this new algorithm. He found a paper on it and made
>comments that I couldn't copy as such, because they are in french. I
>would like to get him involved in the discussion because I am sure he
>can help (He could maybe rephrase his comments in english at a later
>stage).
>

Michel is definitely flattering me...

Regarding the train algorithm issue, I do have two articles sent to me
by participant of the gclist mailing list (where Fergus is an active
participant too). It led me to the following conclusions:

- The train algorithm aims at enabling incremental garbage collection
  for compaction-based garbage collectors, as opposed to mark & sweep
  gc's. 
- Intuition would lead to believe this is a daunting task, and it is
  indeed. In order to achieve this purpose, the system maintains
  a bidirectional graph of all object references (who do I reference ?
  who references me ?). By "maintain", one must understand that a
  rather complex write barrier mechanism makes plain pointer
  (or reference, as you might prefer) assignment a relatively painful
  operation. This must be compared with write barriers for m&s gc's
  (don't you think these are nice acronyms ?) that induce a constant
  and very reasonable performance penalty. 

  One of the two papers presents ways of reducing the performance penalty,
  but I don't believe it will make a order-of-magnitude difference.

The questions I would be led to ask are the following:

- Do you have to go for compaction ? Compacting GC's are intrinsically 
  heavier than m&s gc's. They do offer advantages (no asymptotic
fragmentation),
  but the cost seems to be overwhelming. On the other hand, m&s has advantages
  of its own: simplicity, performance, efficient support for large swap 
  spaces (while a compacting GC must swap the entire process in and out 
  on a global GC run). By using a m&s gc, one can take advantage of some
  of its properties (namely, the fact that an allocation does not move
  once allocated) to ease interfaces with the external world. 

- Do you have to go for incremental Gc ? As Bart Demoen quite rightly
  points out in a later mail, is real-time an issue ? We have had 
  excellent performance with blocking m&s gc, bluntly contradicting 
  the experience of many long time smalltalk users. In a compiled 
  environment, a straightforward and highly optimized blocking
  garbage collector can be made virtually unnoticed to interactive users. 

- Alternatively, what is the asymptotic performance penalty you are
  ready to accept for the sake of non-blocking gc ? Imagine a system
  that does not allocate anything anymore, working on a set of 
  previously allocated objects. Would you accept having it run
  at 50% of the performance of the same system with a blocking
  gc ?

- Do you have measured data about the distribution of the allocation sizes
  in Mercury systems ? If applicable (as it is the case for most systems I
have
  encountered so far), a fixed size slot allocation scheme could provide
  top performance for over 80% of the allocations, without extra
  fragmentation, thereby reducing the need for a compacting gc. 
  Alternatively, one could consider having two or three of such fixed
  size slot pools, reducing the proportion of larger allocations even further.
  I strongly believe that such a no-nonsense, pragmatic approach might
  lead to better results than most sophisticated strategies. It improves
  allocation and deallocation permance dramatically, as well as reducing
  fragmentation by a significant factor, by taking all the small
  allocations out of the picture.

- Phasing. Perhaps the nicest advantage of a m&s algorithm as opposed
  to a compacting algorithm from an industrial point of view 
  is the ability to support a simple
  but efficient non-incremental implementation, and to switch to an
  incremental version in a later stage. As mentioned above, a write
  barrier for such a gc is not an unmanageable obstacle. On the
  other hand, I am far from being convinced such a two-phase approach
  is applicable as is to a compacting gc. 

- Last but not least, the papers related to the train algorithm, as well 
  as my personal experience, show figures for a typical OO language,
  where allocations refer to each other without constraint. Such
  languages support arbitrary complex and tangled networks of interconnected
  objects. How do you stand with Mercury ? Are there properties about
  the data structures you manage (even if statistical rather than absolute)
  that might make a compacting (with or without train) algorithm more
  appropriate ? If is the case, then, I believe one should investigate
  how one can adapt the train algorithm to Mercury, taking advantage
  of these properties. 

This is of course only a personal opinion, based on my experience and
my biases.

Darius.

[ --- argo mailing list, served by majordomo 1.93 ]
[ --- Send 'help' to <majordomo at miscrit.be> for features ]
[ --- Mail to <owner-argo at miscrit.be> for problems ]


-----End of forwarded message-----

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"
PGP: finger fjh at 128.250.37.3        |     -- the last words of T. S. Garp.