March 2009 - Haskell-Cafe

possible memory leak in uvector 0.1.0.3
by Manlio Perillo 05 Mar '09

05 Mar '09

Hi. In the "help optimizing memory usage for a program" I discovered some interesting things: 1) Using lazy ByteStrings to read files it not a good choice, since the garbage collector is not able to proper garbage cleanup. Running with -F1 RTS flag, however, keeps memory usage down. 2) UArr from uvector leaks memory. I'm rather sure about this. In fact the memory usage of my program is 815 MB, when: - I use lazy ByteString with -F1 flag or - if I use strict ByteString Using UArray and strict ByteString, memory usage is 660 MB. In total I have 17770 arrays, so there is a leak of about 9146 bytes per array. In another program, where I do a lot of array concatenations, memory leak is much more evident. Even using -F1 flag, memory usage grows too much. Is this a know bug? How can I verify if it is really a memory leak bug? pumpkin_ (on #haskell.it) suggested me to use a more recent version of uvector package, from http://patch-tag.com/publicrepos/pumpkin-uvector Using this version memory usage is, finally, 643 MB! (and execution if a bit faster, too). The other program, with a lot of array concatenations, still eats a lot of memory... Thanks Manlio Perillo

8 20

help optimizing memory usage for a program
by Manlio Perillo 05 Mar '09

05 Mar '09

Hi. After some work I have managed to implement two simple programs that parse the Netflix Prize data set. For details about the Netflix Prize, there was a post by Kenneth Hoste some time ago. I have cabalized the program, and made available here: http://haskell.mperillo.ath.cx/netflix-0.0.1.tar.gz The process-data-1 program parse the training data set, grouping ratings by movies. The process-data-2 program, instead, groups ratings by users. The structure of the two programs is similar: I create singletons IntMap and then use foldl + union to merge them together. The data structure used is: type Rating = Word32 :*: Word8 -- id, rating type MovieRatings = IntMap (UArr Rating) UArr is from uvector package. The training data set contains about 100 million ratings, so, in theory, the amount of memory required to store pairs of (id, rating) is about 480 MB. The process-data-1 program parse the entire dataset using about 1.4 GB of memory (3x increment). This is strange. The memory required is proportional to the number of ratings. It may be IntMap the culprit, or the garbage collector than does not release the memory to the operating system (or, worse, does not deallocate all used temporary memory). The process-data-2 has much more problems. When I try to parse *only* 500 movie ratings, the memory usage is 471 MB; 780 MB after all data has been fully evaluated (array concatenations). I'm using ghc 6.8.2 on Debian Etch. I would like to do some tests with recent GHC versions, but it may be a problem. Thanks Manlio Perillo

6 16

binary serialization
by FFT 05 Mar '09

05 Mar '09

Is there a way to do binary serialization of Haskell values (in GHC, at least)? If you propose a method, what are its type safety and portability properties?

3 2

ANN: Happstack 0.2 Released
by Matthew Elder 05 Mar '09

05 Mar '09

Happstack 0.2 has been released; it is available on Hackage. A lot of community effort has gone into it! For details, please see this post: http://blog.happstack.com/2009/03/04/happstack-02-released Regards, Matthew Elder -- Need somewhere to put your code? http://patch-tag.com Want to build a webapp? http://happstack.com

1 0

Optimizing array operation?
by Xiao-Yong Jin 05 Mar '09

05 Mar '09

Dear list, I decided to extract some common code I use in my data analysis code and end up with some interesting pattern. > -- | Confined array operation. The type Arr here is actually used as > -- a C-like array with index runs from 0 to n-1. > type Arr = Array Int > > -- | Element fetching function, no bounds checking. Works with array > -- with index [0..n-1] > (!>) :: Arr e -> Int -> e > (!>) = unsafeAt > {-# INLINE (!>) #-} > > -- | Length of the array. > arrLength :: Arr e -> Int > arrLength = numElements > {-# INLINE arrLength #-} > > -- | Sequentially loop over all elements in an array. > loopArrM :: (Monad m) => > (e -> m a) -- ^ function to apply to elements > -> Arr e -- ^ the array > -> m () > loopArrM = loopArrMp (\ _ -> True) > {-# INLINE loopArrM #-} > > -- | Same as loopArrM but only to those with index satisfies predicate. > loopArrMp :: (Monad m) => > (Int -> Bool) -- ^ predicate > -> (e -> m a) -- ^ function to apply to elements > -> Arr e -- ^ the array > -> m () > loopArrMp p f arr = loopArrMG 0 end p f arr > where > end = arrLength arr > {-# INLINE loopArrMp #-} > > -- | Same as loopArrM but only to indices within a range. > loopArrMr :: (Monad m) => > Int -- ^ start index > -> Int -- ^ end index > -> (e -> m a) -- ^ function to apply to elements > -> Arr e -- ^ the array > -> m () > loopArrMr start end = loopArrMG start end (\ _ -> True) > {-# INLINE loopArrMr #-} > > -- | Generic loopArrM for indices with in a range [start, end-1] and > -- satisfy predicate. > loopArrMG :: (Monad m) => > Int -- ^ start index > -> Int -- ^ end index > -> (Int -> Bool) -- ^ predicate > -> (e -> m a) -- ^ function to apply to elements > -> Arr e -- ^ the array > -> m () > loopArrMG start end p f arr = go start > where > go !j | j == end = return () > | p j = f (arr !> j) >> go (j + 1) > | otherwise = go (j + 1) > {-# INLINE loopArrMG #-} It is quite frequently to loop over Arr with various conditions, so I wrote loopArrMG to do it. I know a list comprehension would just do the trick, but the extra time and heap allocation is not what I want. My question here is that whether there is a better data structure available to accomplish such task? If not, is there a better way to write the above code? Thanks, Xiao-Yong -- c/* __o/* <\ * (__ */\ <

1 0

(no subject)
by R J 05 Mar '09

05 Mar '09

Could someone provide an elegant solution to Bird problem 4.2.13? Here are the problem and my inelegant solution: Problem ------- Since concatenation seems such a basic operation on lists, we can try to construct a data type that captures concatenation as a primitive. For example, data (CatList a) = CatNil | Wrap a | Cat (CatList a) (CatList a) The intention is that CatNil represents [], Wrap x represents [x], and Cat x y represents x ++ y. However, since "++" is associative, the expressions "Cat xs (Cat ys zs)" and "Cat (Cat xs ys) zs" should be regarded as equal. Define appropriate instances of "Eq" and "Ord" for "CatList". Inelegant Solution ------------------ The following solution works: instance (Eq a) => Eq (CatList a) where CatNil == CatNil = True CatNil == Wrap z = False CatNil == Cat z w = ( z == CatNil && w == CatNil ) Wrap x == CatNil = False Wrap x == Wrap z = x == z Wrap x == Cat z w = ( Wrap x == z && w == CatNil ) || ( Wrap x == w && z == CatNil ) Cat x y == CatNil = x == CatNil && y == CatNil Cat x y == Wrap z = ( x == Wrap z && y == CatNil ) || ( x == CatNil && y == Wrap z ) Cat x y == Cat z w = unwrap (Cat x y) == unwrap (Cat z w) unwrap :: CatList a -> [a] unwrap CatNil = [] unwrap (Wrap x) = [x] unwrap (Cat x y) = unwrap x ++ unwrap y instance (Eq a, Ord a) => Ord (CatList a) where x < y = unwrap x < unwrap y This solution correctly recognizes the equality of the following, including nested lists(represented, for example, by Wrap (Wrap 1), which corresponds to [[1]]): Wrap 1 == Cat (Wrap 1) CatNil Cat (Wrap 1) (Cat (Wrap 2) (Wrap 3)) == Cat (Wrap 1) (Cat (Wrap 2) (Wrap 3)) Wrap (Wrap 1) == Wrap (Cat (Wrap 1) CatNil) Although this solution works, it's a hack, because unwrap converts CatLists to lists. The question clearly seeks a pure solution that does not rely on Haskell's built-in lists. What's the pure solution that uses cases and recursion on CatList, not Haskell's built-in lists, to capture the equality of nested CatLists? _________________________________________________________________ Windows Live™: Life without walls. http://windowslive.com/explore?ocid=TXT_TAGLM_WL_allup_1a_explore_032009

2 1

Optimization by cafe
by ChrisK 05 Mar '09

05 Mar '09

I have a performance glitch in regex-tdfa related to GHC-6.10.1 (on a PPC G4 with -O2). I have okay code that runs in 0.2 seconds. I simplify this code to run faster and it takes 4.0 seconds (it allocates something in the loop, I think) I turn on -prof for the simpler code and it runs in 0.25 seconds. I can't profile my way out of it, due to above paradox. Has anyone else seen this sort of paradox? The simpler code's loop is just a bunch of pattern matching and lookups, multi: > matchTest :: Regex -> S.ByteString -> Bool > matchTest !r !input = ... > > multi (Simple' {dt_win=w,dt_trans=CharMap t, dt_other=o}) !off = > if IMap.null w > then if off > endOff > then False > else case IMap.findWithDefault o (fromEnum (input `S.unsafeIndex` off)) t of > Transition {trans_many=DFA {d_dt=dt'}} -> > multi dt' (succ off) > else True All the above regex search does is look for a match. It is a tester, returning Bool. The "w" is checked for winning, if it wins it returns True. If not winning, the offset is checked against the end (cached in endOff). If the end has been reach it returns False. Otherwise it looks up the Word8 at offset "off" in "input" , looks up this Word8 as an Int in the t::IntMap Transition , defaulting to Transition "o" The next DT is followed with the (succ off), note that !off is strict. I cannot think of how to reduce the code any further. It should not be doing any allocation. The Regex is being compiled once, cached, and run 10^6 times against a short piece of text. I know it can run fast because I have huge module running in ST.Strict that does all kinds of extra computation and runs in 0.2 seconds. It should be possible to cut this down and win. So I also applied my delete key to most of the code in the complicated ST.Strict module, keeping the runST. The end result was not unlike the above code, and ran in 4.0 seconds instead of 0.2 seconds. I have looked hard at the core output. I am at a loss. So I have turned to haskell-cafe for insight and moral support. -- Chris

1 0

environment variables for runghc?
by Erik de Castro Lopo 05 Mar '09

05 Mar '09

Hi all, Is there some environment variable I can set so that runghc can be told to always use -Wall? Cheers, Erik -- ----------------------------------------------------------------- Erik de Castro Lopo ----------------------------------------------------------------- "... a discussion of C++'s strengths and flaws always sounds like an argument about whether one should face north or east when one is sacrificing one's goat to the rain god." -- Thant Tessman

3 4

Re: Left fold enumerator - a real pearl overlooked?
by John Lato 04 Mar '09

04 Mar '09

Hello Günther, I think the largest reason Haskellers don't use left-fold enumerators is that there isn't a ready-to-use package on Hackage. Oleg's code is extremely well commented and easy to follow, but it's not cabalized. In addition to Takusen, Johan Tibbe's hyena application server uses enumerators for IO: http://github.com/tibbe/hyena/tree/master There is a darcs repo of a cabalized iteratee package available at http://inmachina.net/~jwlato/haskell/iteratee/ This is essentially Oleg's code, slightly modified and reorganized. If anyone is interested in using left-fold enumerators for IO, please give it a look and let me know what you think. I'd like to put this on hackage in about a week or so, if possible. I would especially appreciate build reports. There are a few iteratee/enumerator design questions that remain, which Oleg and others would like to explore more fully. The results of that research will likely find there way into this library. Sincerely, John Lato > Hi all, > > in the last few months I was looking for haskell database library, > eventually settling for HDBC (thanks John btw). > > Takusen also caught my eye although I even failed installing it. > > Nevertheless a particular property of takusen, left-fold-enumerator, > also sparked my interest and I tried to follow it up. > > I had the impression this is something of relevance but something that > is not mentioned or made use of often. There are actually only a few > references on the net and most of those by one person only, Oleg. > > There was one post from John Goerzen about Haskell HTTP libraries in > which he hinted using left-fold enumerators. > > Anyway what I'm saying is that the whole topic is somewhat off the radar > of the larger haskell community, how come, or am I merely overestimating > its relevance and usefulness? > > Günther

12 19

*almost* composition in writer monad
by Edsko de Vries 04 Mar '09

04 Mar '09

Hi, Does this function remind anybody of anything? It seems like I'm missing an obvious abstraction: composeWriter :: [a -> (a, b)] -> a -> (a, [b]) composeWriter [] a = (a, []) composeWriter (f:fs) a = let (a', b) = f a (final_a, bs) = composeWriter fs a' in (final_a, b:bs) It's almost but not quite composition for functions in the Writer monad; the difference is that every function has exactly one b result, rather than a list of them. Edsko

2 2