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

[Jules Bean]

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.

Jules