[MIT-Scheme-devel] ephemerons in fasl files

[Taylor R Campbell]

The efficient (linear-time) ephemeron garbage collection algorithm I
implemented uses a hash table mapping objects to the list of live
ephemerons that have those objects as their keys.  The hash table is
stored in a vector pre-allocated by MAKE-EPHEMERON, which records how
many ephemerons there are and expands the vector if necessary to have
enough entries for reasonable hash table performance during garbage
collection.

However, fasloading doesn't update the ephemeron count or expand the
vector.  Consequently, after FASLOAD or DISK-RESTORE, the next garbage
collection may perform poorly, and, more importantly, `scheme --band
foo.com' may crash if foo.com has any ephemerons in it.  (Under
certain conditions, it won't crash, which is why I didn't notice this
before.)  I see three ways to fix this problem:

1. Let the first garbage collection after FASLOAD, DISK-RESTORE, or
   `scheme --band foo.com' run in quadratic time, by guaranteeing that
   there is space in the vector for at least one ephemeron.  This
   means that the vector can't be used instead, say, for a sorted
   array cum binary tree of ephemerons, a possibility I left open by
   reserving the use of the vector strictly to gcloop.c.  This is easy
   to implement, but I don't like garbage collection in quadratic
   time.

2. Change the BINARY-FASLOAD and LOAD-BAND primitives to scan the
   constant and heap space for ephemerons in order to get an accurate
   head count, and allocate the vector then.  This is complicated to
   implement.

3. Change the fasl format to specify the number of ephemerons.  Then
   BINARY-FASLOAD and LOAD-BAND can use that to allocate the vector.
   This is easy to implement, but requires changing the fasl format.
   Fortunately, the change is compatible in the sense that newer
   microcodes can easily read older fasl files, except those created
   since I committed support for ephemerons.  With a little more work,
   the fasdumper could dynamically choose the version depending on
   whether there are any ephemerons in the fasl, but this is probably
   more work than it's worth.

I'm leaning toward option 3.  Thoughts?