Re: dependency info

[chambers@cs.washington.edu (Craig Chambers)]

Self's dependency mechanism inspired some of our work in our ICSE'95 paper
on selective recompilation mechanisms.  One thing we tried to do was to
solve the problem with Self's dependencies, where if you add a new slot to
an object (e.g. define a new method or a new prototype), every lookup that
traversed that object went out of date.  Since prototypes are (used to be?) 
in the global name space, adding a new prototype ended up recompiling virtually
all compiled methods.  And there was a substantial space cost for the fine-
grained dependencies.

We introduced dependencies on method lookup results, and rechecked the method
lookup whenever a source change made the lookup potentially out of date (like
adding a method or prototype).  This "second chance" check made a big difference
in squashing unnecessary recompilation after adds, inheritance graph changes,
and the like.  We also described a generalization of this caching idea in
the ICSE paper.

To save space, we described a factoring technique which bundles together a
set of nodes that all depend on some other set of nodes (i.e. a complete
bipartite subgraph of the dependency graph) by introducing a single node to
stand for the bundle.  N*M edges -> N+M edges, plus 1 additional node.  In
our Cecil system, this factoring led to modest space savings, but I think it
would be more helpful in Self, since many compiled methods depend on the same
large set of global name space slots.  (Or at least they used to; the effective-
ness of factoring depends in large part on the kinds of inheritance structures
that are used in the host language.)

The idea of using 32 classes of objects to save space is interesting.  To
think this through, I'd suggest enumerating the different kinds of changes
that are typically made during programming, and see how selective the 
invalidations will become.  It seems that adding a new prototype or global
would still be very expensive under this scheme.

There's a link to our ICSE paper from the Cecil project web page.  Which is
reachable from my home page,
http://www.cs.washington.edu/people/faculty/chambers.html.

-- Craig


----- Begin Included Message -----