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

On 2007-10-04, Jules Bean wrote:

Thomas Conway wrote:

...

On 10/4/07, Jules Bean 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 -><-