Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
RE: [Caml-list] "super-compaction" of values
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Dave Berry <Dave@k...>
Subject: RE: [Caml-list] "super-compaction" of values
In a similar vein, way back in the 1980's Kevin Mitchell added
hash-consing to the top-level environment of the Edinburgh ML
interpreter.  This saved a great deal of space.

-----Original Message-----
From: Gregory Morrisett []
Sent: 02 August 2001 14:28
To: Markus Mottl; John R Harrison
Subject: RE: [Caml-list] "super-compaction" of values

> > 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.

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

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.

Bug reports:  FAQ:
To unsubscribe, mail  Archives:
Bug reports:  FAQ:
To unsubscribe, mail  Archives: