February 2010 - Haskell-Cafe

Re: [Haskell-cafe] Generate random UArray in constant memory space.
by Daniel Fischer 09 Feb '10

09 Feb '10

Am Tuesday 09 February 2010 19:19:18 schrieben Sie: > Daniel, > > I've just run venum2 program locally and here is my results: > > $ ./venum2 10000000 +RTS -s > ./venum2 10000000 +RTS -s > 50000005000000 > 22,736 bytes allocated in the heap > 688 bytes copied during GC > 17,184 bytes maximum residency (1 sample(s)) > 19,680 bytes maximum slop > 1 MB total memory in use (0 MB lost due to fragmentation) > > $ ./venum2 1000000000 +RTS -s > ./venum2 1000000000 +RTS -s > 500000000500000000 > 24,152 bytes allocated in the heap > 688 bytes copied during GC > 17,184 bytes maximum residency (1 sample(s)) > 19,680 bytes maximum slop > 1 MB total memory in use (0 MB lost due to fragmentation) > > So my PC shows that there is constant memory allocation. Maybe I'm > doing something wrong ? Unlikely. However, I notice that you seem to have a 64-bit system. I don't know the details, but usually those have more registers than a 32- bit system, so you can get more complicated loops to run completely in the registers. I think that's what happens here, enumFromToU' is just complicated enough to not run in the registers on my 32-bit system, but still runs in the registers on your 64-bit system. The PRNG code is too complicated (too many temporary variables) to run in the registers on either system (BTW, have you tried it with the specialised PRNG code in the source file? I'm not sure whether that might be just small enough to run in the registers on a 64-bit system.). > > 2010/2/9 Daniel Fischer <daniel.is.fischer(a)web.de>: > > Am Tuesday 09 February 2010 15:43:13 schrieben Sie: > >> Update: > >> > >> I've implemented `enumFromToU` through `unfoldU`: > >> > enumFromToU' from to = unfoldU (to - from) f from > >> > where f i = let i' = i + 1 in JustS (i' :*: i') > >> > >> This code behaves similarly to `enumFromToU` (i.e. constantly uses > >> ~25 kb of memory, runs in the same time as above). > > > > Wait, > > > > $ cat venum2.hs > > module Main (main) where > > > > import Text.Printf > > import Control.Applicative > > import System.Environment > > import Data.Array.Vector > > > > main = do > > [size] <- map read <$> getArgs > > let ints = enumFromToU' 0 size :: UArr Int > > printf "%d\n" (sumU ints) > > > > enumFromToU' from to = unfoldU (to - from) f from > > where f i = let i' = i + 1 in JustS (i' :*: i') > > > > $ ghc -O2 --make venum2 > > [1 of 1] Compiling Main ( venum2.hs, venum2.o ) > > Linking venum2 ... > > $ ./venum2 +RTS -sstderr -RTS 1000000 > > ./venum2 1000000 +RTS -sstderr > > 1784293664 > > 48,256,384 bytes allocated in the heap > > 6,256 bytes copied during GC > > 26,804 bytes maximum residency (1 sample(s)) > > 25,524 bytes maximum slop > > 1 MB total memory in use (0 MB lost due to > > fragmentation) > > > > $ ./venum2 +RTS -sstderr -RTS 10000000 > > ./venum2 10000000 +RTS -sstderr > > -2004260032 > > 481,937,552 bytes allocated in the heap > > 19,516 bytes copied during GC > > 26,804 bytes maximum residency (1 sample(s)) > > 25,512 bytes maximum slop > > 1 MB total memory in use (0 MB lost due to > > fragmentation) > > > > So we have constant memory, but linear allocation, just like with the > > random numbers. > > > > With enumFromToU, also the allocation is constant, so unfoldU > > allocates, enumFromToU not. > > > >> So the question is why random number list generator eats O(n) memory > >> ? > > > > It doesn't, not here, at least. Using System.Random, the allocation > > figures are about ten times as high, but the residency is about the > > same. Putting the PRNG code in the same file and tweaking things a bit > > (eliminating all intermediate Integers, e.g.), I get > > > > $ cat ran2Vec.hs > > {-# LANGUAGE BangPatterns #-} > > module Main (main) where > > > > import Text.Printf > > import Control.Applicative > > import System.Environment > > import Data.Array.Vector > > > > randomListU :: (Int, Int) -> StdGen -> Int -> (UArr Int) > > randomListU b@(l,h) g size = unfoldU size gen g > > where > > !k = h-l+1 > > !b' = 2147483561 `rem` k > > gen !g = let (!x, !g') = stdNext g > > in JustS ((l+ (x+b') `rem` k) :*: g') > > > > main = do > > [size] <- map read <$> getArgs > > let ints = randomListU (-10, 10) (mkStdGen 1) size > > printf "%d\n" (sumU ints) > > > > data StdGen = StdGen {-# UNPACK #-} !Int {-# UNPACK #-} !Int > > > > mkStdGen :: Int -> StdGen > > mkStdGen s > > | s < 0 = mkStdGen (-s) > > | otherwise = StdGen (s1+1) (s2+1) > > where > > (q, s1) = s `divMod` 2147483562 > > s2 = q `mod` 2147483398 > > > > {-# INLINE stdNext #-} > > stdNext :: StdGen -> (Int, StdGen) > > -- Returns values in the range stdRange > > stdNext (StdGen s1 s2) = z' `seq` g' `seq` (z', g') > > where > > !g' = StdGen s1'' s2'' > > !z' = if z < 1 then z + 2147483562 else z > > !z = s1'' - s2'' > > > > !k = s1 `quot` 53668 > > !s1' = 40014 * (s1 - k * 53668) - k * 12211 > > !s1'' = if s1' < 0 then s1' + 2147483563 else s1' > > > > !k' = s2 `quot` 52774 > > !s2' = 40692 * (s2 - k' * 52774) - k' * 3791 > > !s2'' = if s2' < 0 then s2' + 2147483399 else s2' > > $ ghc -O2 -funbox-strict-fields -funfolding-use-threshold=16 --make > > ran2Vec -o ran2AVec5 > > Linking ran2AVec5 ... > > $ ./ran2AVec5 +RTS -sstderr -RTS 10000000 > > ./ran2AVec5 10000000 +RTS -sstderr > > 5130 > > 521,828,888 bytes allocated in the heap > > 8,664 bytes copied during GC > > 26,788 bytes maximum residency (1 sample(s)) > > 25,636 bytes maximum slop > > 1 MB total memory in use (0 MB lost due to > > fragmentation) > > > > nearly the same allocation figures as for the *much* simpler > > enumFromToU', and it's about ten times as fast as System.Random. > >

2 1

Strange Haddock output
by Sean Leather 09 Feb '10

09 Feb '10

I was browsing Hackage pointlessly and came across what appears to be strange Haddock formatting here: http://hackage.haskell.org/packages/archive/pointless-haskell/0.0.3/doc/htm… The following source -- | Polytypic 'Prelude.Functor' class for functor representations class Functor (f :: * -> *) where fmap :: Fix f -- ^ For desambiguation purposes, the type of the functor must be passed as an explicit paramaeter to 'fmap' -> (x -> y) -> Rep f x -> Rep f y -- ^ The mapping over representations produces the following view from the browser class Functor f where Polytypic Prelude.Functor class for functor representations Methods fmap :: => Fix f -> x -> y -> Rep f x The mapping over representations -> Rep f y with the Haddock 2.6.0 on Hackage. There seems to be an extraneous => in the signature of fmap, and the comment on Fix f does not show up. Sean

2 2

automatically exclude unused modules at compile time
by Hong Yang 09 Feb '10

09 Feb '10

When I turned on "-Wall" knob at compile time, I got a message: Warning: Module `System.Cmd' is imported, but nothing from it is used, except perhaps instances visible in `System.Cmd' To suppress this warning, use: import System.Cmd() Then I did four experiments as follows at compile time: 1) import System.Environment 2) import System.Environment() 3) import System.Environment(only the functions I used) 4) -- import System.Environment It turned out that case 1-3) have the size after compilation, and that case 4) has smaller size than the others. Can we make GHC a little bit more intelligent to automatically exclude unused modules at compile time as in case 4)? (Am I just too lazy to add several dashes?) Thanks, Hong

2 2

Re: [Haskell-cafe] Generate random UArray in constant memory space.
by Daniel Fischer 09 Feb '10

09 Feb '10

Am Tuesday 09 February 2010 15:43:13 schrieben Sie: > Update: > > I've implemented `enumFromToU` through `unfoldU`: > > enumFromToU' from to = unfoldU (to - from) f from > > where f i = let i' = i + 1 in JustS (i' :*: i') > > This code behaves similarly to `enumFromToU` (i.e. constantly uses ~25 > kb of memory, runs in the same time as above). Wait, $ cat venum2.hs module Main (main) where import Text.Printf import Control.Applicative import System.Environment import Data.Array.Vector main = do [size] <- map read <$> getArgs let ints = enumFromToU' 0 size :: UArr Int printf "%d\n" (sumU ints) enumFromToU' from to = unfoldU (to - from) f from where f i = let i' = i + 1 in JustS (i' :*: i') $ ghc -O2 --make venum2 [1 of 1] Compiling Main ( venum2.hs, venum2.o ) Linking venum2 ... $ ./venum2 +RTS -sstderr -RTS 1000000 ./venum2 1000000 +RTS -sstderr 1784293664 48,256,384 bytes allocated in the heap 6,256 bytes copied during GC 26,804 bytes maximum residency (1 sample(s)) 25,524 bytes maximum slop 1 MB total memory in use (0 MB lost due to fragmentation) $ ./venum2 +RTS -sstderr -RTS 10000000 ./venum2 10000000 +RTS -sstderr -2004260032 481,937,552 bytes allocated in the heap 19,516 bytes copied during GC 26,804 bytes maximum residency (1 sample(s)) 25,512 bytes maximum slop 1 MB total memory in use (0 MB lost due to fragmentation) So we have constant memory, but linear allocation, just like with the random numbers. With enumFromToU, also the allocation is constant, so unfoldU allocates, enumFromToU not. > > So the question is why random number list generator eats O(n) memory ? It doesn't, not here, at least. Using System.Random, the allocation figures are about ten times as high, but the residency is about the same. Putting the PRNG code in the same file and tweaking things a bit (eliminating all intermediate Integers, e.g.), I get $ cat ran2Vec.hs {-# LANGUAGE BangPatterns #-} module Main (main) where import Text.Printf import Control.Applicative import System.Environment import Data.Array.Vector randomListU :: (Int, Int) -> StdGen -> Int -> (UArr Int) randomListU b@(l,h) g size = unfoldU size gen g where !k = h-l+1 !b' = 2147483561 `rem` k gen !g = let (!x, !g') = stdNext g in JustS ((l+ (x+b') `rem` k) :*: g') main = do [size] <- map read <$> getArgs let ints = randomListU (-10, 10) (mkStdGen 1) size printf "%d\n" (sumU ints) data StdGen = StdGen {-# UNPACK #-} !Int {-# UNPACK #-} !Int mkStdGen :: Int -> StdGen mkStdGen s | s < 0 = mkStdGen (-s) | otherwise = StdGen (s1+1) (s2+1) where (q, s1) = s `divMod` 2147483562 s2 = q `mod` 2147483398 {-# INLINE stdNext #-} stdNext :: StdGen -> (Int, StdGen) -- Returns values in the range stdRange stdNext (StdGen s1 s2) = z' `seq` g' `seq` (z', g') where !g' = StdGen s1'' s2'' !z' = if z < 1 then z + 2147483562 else z !z = s1'' - s2'' !k = s1 `quot` 53668 !s1' = 40014 * (s1 - k * 53668) - k * 12211 !s1'' = if s1' < 0 then s1' + 2147483563 else s1' !k' = s2 `quot` 52774 !s2' = 40692 * (s2 - k' * 52774) - k' * 3791 !s2'' = if s2' < 0 then s2' + 2147483399 else s2' $ ghc -O2 -funbox-strict-fields -funfolding-use-threshold=16 --make ran2Vec -o ran2AVec5 Linking ran2AVec5 ... $ ./ran2AVec5 +RTS -sstderr -RTS 10000000 ./ran2AVec5 10000000 +RTS -sstderr 5130 521,828,888 bytes allocated in the heap 8,664 bytes copied during GC 26,788 bytes maximum residency (1 sample(s)) 25,636 bytes maximum slop 1 MB total memory in use (0 MB lost due to fragmentation) nearly the same allocation figures as for the *much* simpler enumFromToU', and it's about ten times as fast as System.Random. > > Regards, > Vasyl Pasternak > > 2010/2/9 Vasyl Pasternak <vasyl.pasternak(a)gmail.com>: > > Sorry, maybe I should ask more clearer. > > > > I've looked at dons article "Haskell as fast as C"[1], and tried to > > implement similar algorithm but for list of random numbers. > > > > Please look at code: > >> import Text.Printf > >> import Control.Applicative > >> import System.Environment > >> import Data.Array.Vector > >> > >> main = do > >> [size] <- map read <$> getArgs > >> let ints = enumFromToU 0 size :: UArr Int > >> printf "%d\n" (sumU ints) > > > > This code runs in constant space (on my pc ~25kb allocates on the > > heap) regardless of array size. So I tried to achieve similar with > > random list, just to replace `enumFromToU` with my own list generator. > > > > So the question - is it possible to implement random list similary to > > enumFromToU? > > > > > > [1]http://donsbot.wordpress.com/2008/06/04/haskell-as-fast-as-c-workin > >g-at-a-high-altitude-for-low-level-performance/ > > > > Thank you, > > Vasyl Pasternak > > > > 2010/2/9 Daniel Fischer <daniel.is.fischer(a)web.de>: > >> Am Dienstag 09 Februar 2010 13:18:23 schrieb Vasyl Pasternak: > >>> Hello Cafe, > >>> > >>> I tried to generate memory-efficient list of random numbers, so I've > >>> used uvector library for this task. But it doesn't work, > >>> it still allocates more than 6Gb of memory for the random list of 10 > >>> > >>> million elements. Here is the code: > >> > >> Hmm, > >> > >> $ ghc -O2 --make ranVec > >> [1 of 1] Compiling Main ( ranVec.hs, ranVec.o ) > >> Linking ranVec ... > >> $ ./ranVec 10000000 +RTS -sstderr > >> 5130 > >> 4,919,912,080 bytes allocated in the heap > >> 883,256 bytes copied during GC > >> 26,896 bytes maximum residency (1 sample(s)) > >> 25,620 bytes maximum slop > >> 1 MB total memory in use (0 MB lost due to > >> fragmentation) > >> > >> maximum residency is just eight bytes more than for 100,000 or > >> 1,000,000 numbers. I think that is constant space. > >> > >> The ~5 GB total allocation is sequential, ten million new StdGens are > >> produced and allocated, then immediately garbage collected. I see no > >> problem (except that StdGen is slow, e.g. the Mersenne twister is > >> much faster [and allocates less, but still linear in size]). > >> > >>> > import Text.Printf > >>> > import System.Random > >>> > import Control.Applicative > >>> > import System.Environment > >>> > import Data.Array.Vector > >>> > > >>> > randomListU :: (Int, Int) -> StdGen -> Int -> (UArr Int) > >>> > randomListU b g size = unfoldU size gen g > >>> > where gen g = let (x, g') = randomR b g > >>> > in JustS (x :*: g') > >>> > > >>> > main = do > >>> > [size] <- map read <$> getArgs > >>> > let ints = randomListU (-10, 10) (mkStdGen 1) size > >>> > printf "%d\n" (sumU ints) > >>> > >>> Could someone give a hint, how to implement this function in > >>> constant memory space? > >>> > >>> Thank you in advance. > >>> > >>> Best regards, > >>> Vasyl Pasternak

1 0

Re: [Haskell-cafe] Iteratee, parsec & co.
by John Lato 09 Feb '10

09 Feb '10

> From: Edward Kmett <ekmett(a)gmail.com> > > 3. Why Seek FileOffset is error message? >> > > I'm not quite sure what you're asking here. One of the infelicities of iteratee-0.3 is that it defines a data type: > data ErrMsg = Err String > | Seek FileOffset > deriving (Show, Eq) I believe this is what the OP is referring to. Oleg originally implemented seek using IORefs; I wanted to try this and didn't know if it would work so I used a minimal implementation. I've decided this is the correct approach, but the details need to be tweaked a bit. Cheers, John

1 0

various dependencies breakages
by Thomas Girod 09 Feb '10

09 Feb '10

Hi there. I'm trying to reinstall gitit after updating to ghc 6.12 and it's driving me crazy. I hope you will be able to help me troubleshoot this mess ... I'm starting from scratch again, using cabal. I will post more problems as they appears. $ cabal install gitit Resolving dependencies... cabal: cannot configure datetime-0.2. It requires QuickCheck ==2.* For the dependency on QuickCheck ==2.* there are these packages: QuickCheck-2.1, QuickCheck-2.1.0.1, QuickCheck-2.1.0.2 and QuickCheck-2.1.0.3. However none of them are available. QuickCheck-2.1 was excluded because happstack-util-0.4.1 requires QuickCheck <2 QuickCheck-2.1.0.1 was excluded because happstack-util-0.4.1 requires QuickCheck <2 QuickCheck-2.1.0.2 was excluded because happstack-util-0.4.1 requires QuickCheck <2 QuickCheck-2.1.0.3 was excluded because happstack-util-0.4.1 requires QuickCheck <2 Can't cabal handle several versions of the same library in parallel ? If not, how can I solve this problem ? cheers tom

3 3

Iteratee, parsec & co.
by Maciej Piechotka 09 Feb '10

09 Feb '10

I read a lot about iteratee IO and it seemed very interesting (Unfortunately it lacks tutorial). Especially features like 'no input yet' in network programming (with lazy IO + parsec I run into problems as it tried to evaluate the first response character before sending output). I decided first write a simple program and then attempt write a Stream implementation for parsec. > {-# LANGUAGE FlexibleInstances #-} > {-# LANGUAGE MultiParamTypeClasses #-} > import Data.Iteratee > import Text.Parse > > data Buffer a = Buffer > instance Monad m => Stream (Buffer a) (IterateeG [] a m) a where > uncons Buffer = IterateeG loop > where loop (Chunk []) = > return $! Cont (IterateeG loop) Nothing > loop (Chunk (x:xs)) = > return $! Done (Just (x, Buffer)) > (Chunk xs) > loop (EOF Nothing) = > return $! Done Nothing (EOF Nothing) > loop (EOF (Just e)) = > return $! throwErr e 1. I'm not quite sure what Cursor was suppose to do from A Parsing Trifecta presentation. 2. Is there any package which contains this stream definition? 3. Why Seek FileOffset is error message? Regards PS. I guess iteratee does qualify as cafe but if beginner would be more appropriate group then I'm sorry - I'll remember next time.

4 3

haskelldb in-memory driver?
by Johannes Waldmann 09 Feb '10

09 Feb '10

Is there a haskelldb-driver that works with a datasource that is in memory, as a Haskell object? (like LINQ can work on C# collections) - J.

4 4

Compiling on Windows - using a particular Manifest file
by Günther Schmidt 09 Feb '10

09 Feb '10

Hi, how can I make ghc use a particular manifest file for embedding? (on Windows) Günther

2 1

cannot post to haskellmode-emacs@projects.haskell.org
by Jose A. Ortega Ruiz 08 Feb '10

08 Feb '10

Hi, all my posts to the haskellmode-emacs list (using the address in the subject) are being rejected with the error: 451 451 Temporary local problem - please try later (state 18) (after several retries by the Google smtp server, which i use as a smarthost). Any idea of what could be causing this problem? Thanks! jao -- There are two ways to write error-free programs; only the third one works. - Alan Perlis, Epigrams in Programing

4 3