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 PAA16558; Thu, 2 Aug 2001 15:28:11 +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 PAA16555 for ; Thu, 2 Aug 2001 15:28:10 +0200 (MET DST) Received: from exchange.cs.cornell.edu (exchange.cs.cornell.edu [128.84.97.8]) by concorde.inria.fr (8.11.1/8.10.0) with ESMTP id f72DS9X23690 for ; Thu, 2 Aug 2001 15:28:09 +0200 (MET DST) content-class: urn:content-classes:message 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 X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 Date: Thu, 2 Aug 2001 09:28:04 -0400 Message-ID: <24C06C2959910949931A2337CB264DCB052044@opus.cs.cornell.edu> Thread-Topic: [Caml-list] "super-compaction" of values Thread-Index: AcEbN//pQLCsYT2dRrK6c4qWm63BVwAHaKIA From: "Gregory Morrisett" To: "Markus Mottl" , "John R Harrison" Cc: Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk > > 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