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

[Aaron Denney]

On 2007-10-04, Jules Bean <jules at jellybean.co.uk> wrote:
> 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.

Caches are still limited sizes, and that can make a huge difference for
time.

-- 
Aaron Denney
-><-