RE: [Caml-list] "super-compaction" of values

["Gregory Morrisett" <jgm@cs.cornell.edu>]

> > I ended up writing a naive implementation, without making stuff
> > garbage-collectible, but only using it for structures I knew were
> > persistent. To my chagrin, it turned out that Malcolm was absolutely
> > right. Space usage actually went *up*, presumably because 
> the hashing
> > datastructures were large enough to overwhelm the small amount of
> > sharing.

For the TAL type-checker, we used hash-consing to represent type terms
(which are quite big for TAL) and this had a significantly good impact
on performance.  See:

Dan Grossman and Greg Morrisett.  Scalable Certification for Typed
Assembly Language.  In the 2000 ACM SIGPLAN Workshop on Types in
Compilation, Montreal, Canada, September 2000.
www.cs.cornell.edu/talc/papers/tal_scale.ps

Similarly, Zhong Shao's Flint IL uses hash-consing for type terms
quite effectively.  I can dig up the reference if you like.  In
these two settings, one has to worry about the exponential blow
up you can get by turning a DAG into a tree.  In addition, the
hash-consing made structural equality tests quite cheap (O(1))
which is important for type checking or proof verification.  For
TAL, GC was not an issue, though we thought it might be.  For Flint,
if memory serves, they periodically flushed the table or used
some finalization/weak-pointer tricks.  

And long ago, I remember that Eric Cooper hacked the SML/NJ collector
to do hash-consing on major collections for immutable objects so as
to generically compress the heap.  If memory serves, he got fantastic
reductions in overall space (at the expense of much slower collections.)
Those were the days when SML/NJ did a lot of paging on a standard
workstation...

Another interesting data point is that Scott Nettles and his group
at Penn did some work compressing heap images and found that they
compress remarkably well, which suggests that we waste a lot of space.

-Greg
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr