[Haskell-cafe] Re: bizarre memory usage with data.binary

Jules Bean jules at jellybean.co.uk
Thu Oct 4 05:01:53 EDT 2007

Thomas Conway wrote:
> On 10/4/07, Jules Bean <jules at jellybean.co.uk> wrote:
>> ...and indeed it can't be done, except by the naive brute-force method
>> of comparing every subtree, possibly optimised by cryptographically
>> hashing a representation of every subtree, since sharing isn't an
>> observable property.
> At least one Prolog implementation (I forget which, I'm sorry), had a
> [de]serialisation library which used a hash-consing approach.
> Basically, it did its serialization using a post-order traversal and
> emitted references to previous values when the same value had already
> been emitted. Not rocket science. Actually, I've heard a Prolog guy -
> Bart Demoen - talk about doing pretty much this during GC to improve
> sharing.

Not rocket science at all, but relatively expensive. A time/space 
tradeoff. And these days, with memory and disks feeling cheap, most 
people want to trade time for space, not the other way around.

Not everyone, of course.


More information about the Haskell-Cafe mailing list