aeyakovenko:

Program1:

module Main where

import Data.Binary import Data.List(foldl')

main = do let sum' = foldl' (+) 0 let list::[Int] = decode $ encode $ ([1..] :: [Int]) print $ sum' list print "done"

vs

Program2:

module Main where

import Data.Binary import Data.List(foldl')

main = do let sum' = foldl' (+) 0 let list::[Int] = [1..] print $ sum' list print "done"

neither program is expected to terminate. The point of these examples is to demonstrate that Data.Binary encode and decode have some strange memory allocation patters.

The encode instance for lists is fairly strict: instance Binary a => Binary [a] where put l = put (length l) >> mapM_ put l get = do n <- get :: Get Int replicateM n get This is ok, since typically you aren't serialising infinite structures. Use a newtype, and a lazier instance, if you need to do this. -- Don

On 10/2/07, Don Stewart wrote:

The encode instance for lists is fairly strict:

instance Binary a => Binary [a] where put l = put (length l) >> mapM_ put l get = do n <- get :: Get Int replicateM n get

This is ok, since typically you aren't serialising infinite structures.

Use a newtype, and a lazier instance, if you need to do this.

Maybe something like this (WARNING: ugly code, as in "not elegant", follows): newtype List a = List [a] split255 :: [a] -> (Word8, [a], [a]) split255 = s 0 where s 255 xs = (255, [], xs) s n (x:xs) = let (n', ys, zs) = s (n+1) xs in (n', x:ys, zs) s n [] = (n, [], []) instance Binary a => Binary (List a) where put (List l) = let (n, xs, ys) = split255 l in do putWord8 n mapM_ put xs when (n == 255) (put $ List ys) get = do n <- getWord8 xs <- replicateM (fromEnum n) get if n == 255 then get >>= \(List ys) -> return (List $ xs ++ ys) else return (List xs) It uses chunks of 255 elements and so doesn't traverse the whole list until starting to output something. OTOH, there's some data overhead (1 byte every 255 elements). Seems to run your example fine and in constant memory. HTH, -- Felipe.

servers never terminate, pretend that i have a server that reads a list encoded with data.binary from a socket, and sums it up and returns the current sum. i would expect it to run in constant memory, never terminate, and do useful work. which is basically the problem that I am facing right now. my program seems to grow randomly in memory use when marshaling large data types encoded using data.binary. On 10/2/07, Dan Weston wrote:

Maybe what you are observing is that the operational semantics of undefined is undefined. The program can halt, run forever, use no memory, use all the memory.

Although I doubt what GHC does with this code is a random process, I don't think it's too meaningful to ask what are the space usage patterns of a program returning bottom.

Anatoly Yakovenko wrote:

...

Program1:

module Main where

import Data.Binary import Data.List(foldl')

main = do let sum' = foldl' (+) 0 let list::[Int] = decode $ encode $ ([1..] :: [Int]) print $ sum' list print "done"

vs

Program2:

module Main where

import Data.Binary import Data.List(foldl')

main = do let sum' = foldl' (+) 0 let list::[Int] = [1..] print $ sum' list print "done"

neither program is expected to terminate. The point of these examples is to demonstrate that Data.Binary encode and decode have some strange memory allocation patters.

If you run Program1, it will run forever, but its memory usage on my machine goes to 500M then back down to 17M then back up to 500M then back down to 17M... repeatedly. I don't think this has anything to do with running out of space in a 32 bit integer.

Program2 on the other hand runs at constant memory at around 2M.

Anatoly

On 10/2/07, Anatoly Yakovenko wrote:

...

i am getting some weird memory usage out of this program:

module Main where

import Data.Binary import Data.List(foldl')

main = do let sum' = foldl' (+) 0 let list::[Int] = decode $ encode $ ([1..] :: [Int]) print $ sum' list print "done"

it goes up to 500M and down to 17M on windows. Its build with ghc 6.6.1 with the latest data.binary

Any ideas what could be causing the memory usage to jump around so much?

Thanks, Anatoly

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

If its specifically the list instance, where we currently trade laziness for efficiency of encoding (which may or may not be the right thing), I'd suggest a fully lazy encoding instance?

Its not really a list, its more of a tree that has shared nodes, so something like this: A / \ B C \ / D / \ E F I suspect that maybe after encode/decode i end up with something like A / \ B C / \ D D / \ / \ E F E F

Spencer Janssen wrote:

On Tuesday 02 October 2007 19:51:47 Anatoly Yakovenko wrote:

...

...

If its specifically the list instance, where we currently trade laziness for efficiency of encoding (which may or may not be the right thing), I'd suggest a fully lazy encoding instance? Its not really a list, its more of a tree that has shared nodes, so something like this:

A / \ B C \ / D / \ E F

I suspect that maybe after encode/decode i end up with something like

A / \ B C / \ D D / \ / \ E F E F

That is correct, binary doesn't attempt to share substructures. If you'd like to do this, you'll need to do it by hand.

...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. Of course, hashing doesn't actually observe the real sharing present, rather, it computes maximal sharing. There are some applications where this could be a worthwhile win. Jules PS Well, except unsafePtrEquality but I don't really want to go there...

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. cheers, T. -- Thomas Conway drtomc@gmail.com Silence is the perfectest herald of joy: I were but little happy, if I could say how much.

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