Version française
Home     About     Download     Resources     Contact us    
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: Markus Mottl <markus@m...>
Subject: Re: [Caml-list] "super-compaction" of values
On Wed, 01 Aug 2001, John R Harrison wrote:
> About 5 years ago I became very enthusiastic about using hash-consing in
> the HOL Light prover to share common subterms of theorems. I was
> convinced it would cut space usage dramatically.

Well, it's actually not so much space savings that I am interested in,
but mostly exploiting (sub-)program equivalences to speed up expensive
computations.

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

I can well imagine this. In my case it's not "real" programming languages
that I have to deal with, but rather quite confined ones, and there are
likely to be hundreds of not-so-large programs that mostly differ by a
few subtrees only (= lots of opportunities for sharing). It seems worth
a try...

Regards,
Markus Mottl

-- 
Markus Mottl                                             markus@oefai.at
Austrian Research Institute
for Artificial Intelligence                  http://www.oefai.at/~markus
-------------------
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