[gclist] Representation of pointer set

[Boehm, Hans]

Carl Hauser at Xerox PARC modified the PCR collector (more than 10 years
ago) to optionally keep the grey list approximately sorted.  In swap limited
situations, this seemed to help by a bit more than factor of two.  (More in
earlier versions of the collector that touched pointerfree objects during
marking.) The code was more expensive in the nonpaging case, and hence was
eventually only triggered when substantial paging was detected.

It's better to keep it only approximately sorted into a few buckets, since
you can do that in linear time, and it's good enough to deal with paging
issues.

The code was dropped from our stand-alone collector for two reasons:

1) It helped only under conditions that most people would try to avoid, and
then not by really huge factors.  It added to the code size and complexity.

2) It made it far harder to recover from mark stack overflows, and it was
likely to provoke mark stack oveflows, since the data structure was less
compact.  This was viewed as a significant deficiency by at least some of
its users.

I suspect you can still find the code on the Xerox PARC ftp site.

Hans  

-----Original Message-----
From: Charles Fiterman [mailto:cef@geodesic.com]
Sent: Tuesday, May 02, 2000 10:58 AM
To: gclist@iecc.com
Subject: RE: [gclist] Representation of pointer set



Currently I agree with representing the pointer set (mark stack) as an
array and operating systems have these neat expanding stacks.

Has anyone experimented with keeping a sorted heap instead of a stack? Now
initially this sounds insane. Why would anyone put an expensive data
structure like a sorted heap in the most time sensitive part of their
program.

But collection can be swap limited and sorting these pointers would improve
locality of reference.

This is a good argument for object oriented design. You could trivially do
such experiments.