[m-dev.] New conservative GC

[Ralph Becket]

I've just put the finishing touches to my garbage collector (you can
check it out of the Mercury repository as `hgc').  I've made no attempt
to optimise it, but early benchmark results are encouraging.

Here are the results (run on swordfish, comparing hgc against Boehm GC
6.7, the latest stable version) for repeatedly building full binary
trees of a given depth and then discarding references to them:

 3.59s user: tree_test: 80000000 iterations; depth  1; using hgc
17.06s user: tree_test: 80000000 iterations; depth  1; using boehm

 6.04s user: tree_test:  4000000 iterations; depth  5; using hgc
26.57s user: tree_test:  4000000 iterations; depth  5; using boehm

 4.06s user: tree_test:    80000 iterations; depth 10; using hgc
18.46s user: tree_test:    80000 iterations; depth 10; using boehm

 2.98s user: tree_test:       40 iterations; depth 20; using hgc
11.94s user: tree_test:       40 iterations; depth 20; using boehm

 5.94s user: tree_test:       10 iterations; depth 22; using hgc
11.35s user: tree_test:       10 iterations; depth 22; using boehm

Here are the results for randomly updating an ordered binary tree:

 4.10s user: tree_test2: 40000000 iterations; range     1; using hgc
10.54s user: tree_test2: 40000000 iterations; range     1; using boehm

 4.43s user: tree_test2: 20000000 iterations; range    10; using hgc
14.52s user: tree_test2: 20000000 iterations; range    10; using boehm

 3.97s user: tree_test2:  8000000 iterations; range   100; using hgc
13.71s user: tree_test2:  8000000 iterations; range   100; using boehm

 3.53s user: tree_test2:   800000 iterations; range 10000; using hgc
 4.14s user: tree_test2:   800000 iterations; range 10000; using boehm

These numbers are sufficiently impressive that I'd like to experiment
with porting Mercury to use hgc.

HGC, the new garbage collector, is an incremental, generational,
conservative garbage collector.  It makes the following assumptions:
(a) almost all heap cells are small (say, less than 256 words in size);
(b) almost all heap cells are immutable and only reference previously
  created heap cells;
(c) mutable cells (which can reference more recently created cells) and
  large cells (>= 256 words) are rare and can be handled by relatively
  expensive methods without significantly affecting collector
  performance.

Can someone give me any pointers as to where I should start looking in
the Mercury code for adding a .hgc grade?  In particular, I need to
ensure that
(1) the collector is initialised at the start-of-day;
(2) heap allocation is handled correctly;
(3) any mutable data is identified;
(4) tail-call-modulo-cons and CTGC are disabled (they are incompatible
  with assumption (b)) when HGC is being used.

Thanks,
-- Ralph
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at csse.unimelb.edu.au
Administrative Queries: owner-mercury-developers at csse.unimelb.edu.au
Subscriptions:          mercury-developers-request at csse.unimelb.edu.au
--------------------------------------------------------------------------