From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id PAA17030; Thu, 2 Aug 2001 15:50:03 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id PAA17158 for ; Thu, 2 Aug 2001 15:50:02 +0200 (MET DST) Received: from mrwall.kal.com (mrwall.kal.com [194.193.14.236]) by concorde.inria.fr (8.11.1/8.10.0) with SMTP id f72Do1X24367 for ; Thu, 2 Aug 2001 15:50:01 +0200 (MET DST) Received: from mrwall.kal.com [194.193.14.236] (HELO localhost) by mrwall.kal.com (AltaVista Mail V2.0J/2.0J BL25J listener) id 0000_002b_3b69_5b26_27d1; Thu, 02 Aug 2001 14:52:38 +0100 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Subject: RE: [Caml-list] "super-compaction" of values content-class: urn:content-classes:message X-MimeOLE: Produced By Microsoft Exchange V6.0.4417.0 Date: Thu, 2 Aug 2001 14:46:07 +0100 Message-ID: <8E31D6933A2FE64F8AE3CC1381EEDCE70B319A@NT.kal.com> Thread-Topic: [Caml-list] "super-compaction" of values Thread-Index: AcEbN//pQLCsYT2dRrK6c4qWm63BVwAHaKIAAAD3OQA= From: "Dave Berry" To: "Gregory Morrisett" , "Markus Mottl" , "John R Harrison" Cc: Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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 [mailto:jgm@cs.cornell.edu] Sent: 02 August 2001 14:28 To: Markus Mottl; John R Harrison Cc: caml-list@inria.fr 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=20 > 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. =20 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 ------------------- 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