November 2012 - Haskell-Cafe

Re: [Haskell-cafe] I killed performance of my code with Eval and Strategies
by Janek S. 17 Nov '12

17 Nov '12

> Do you really mean to calculate the 'sin . sqrt' of just the head of the list, or do you mean: > calculateSeq = map (sin . sqrt) ? Argh.. of course not! That's what you get when you code in the middle of a night. But in my code I will not be able to use map because elements will be processed in pairs, so let's say that my sequential function looks like this: calculateSeq :: [Double] -> [Double] calculateSeq [] = [] calculateSeq [x] = [sin . sqrt $ x] calculateSeq (x:y:xs) = (sin . sqrt $ x) : (cos . sqrt $ y) : calculateSeq xs > I don't think there's a memory leak. It looks more like you're just > allocating much more than is sane for such a simple function. > On a recent processor, sin . sqrt is two instructions. Meanwhile, you have > a list of (boxed?) integers being split up, then recombined. That's bound > to hurt the GC. I am not entirely convinced that my idea of using eval+strategies is bound to be slow, because there are functions like parListChunk that do exactly this: split the list into chunks, process them in parallel and then concatenate the result. Functions in Control.Parallel.Strategies were designed to deal with list so I assume it is possible to process lists in parallel without GC problems. However I do not see a way to apply these functions in my setting where elements of lists are processed in pairs, not one at a time (parList and parMap will not do). Also, working on a list of tuples will not do. > Also, you might want to configure criterion to GC between > runs. That might help. The -g flag passed to criterion executable does that. > What I'd suggest doing instead, is breaking the input into chucks of, say, > 1024, and representing it with a [Vector]. Then, run your sin.sqrt's on > each vector in parallel. Finally, use Data.Vector.concat to combine your > result. As stated in my post scriptum I am aware of that solution :) Here I'm trying to figure what am I doing wrong with Eval. Thanks! Janek > > Hope that helps, > - Clark > > On Wed, Nov 14, 2012 at 4:43 PM, Janek S. <fremenzone(a)poczta.onet.pl> wrote: > > Dear Haskellers, > > > > I am reading Simon Marlow's tutorial on parallelism and I have problems > > with correctly using Eval > > monad and Strategies. I *thought* I understand them but after writing > > some code it turns out that > > obviously I don't because parallelized code is about 20 times slower. > > Here's a short example > > (code + criterion benchmarks): > > > > {-# LANGUAGE BangPatterns #-} > > module Main where > > > > import Control.Parallel.Strategies > > import Criterion.Main > > > > main :: IO () > > main = defaultMain [ > > bench "Seq" $ nf calculateSeq xs > > , bench "Par" $ nf calculatePar xs ] > > where xs = [1..16384] > > > > calculateSeq :: [Double] -> [Double] > > calculateSeq [] = [] > > calculateSeq (x:xs) = (sin . sqrt $ x) : xs > > > > calculatePar :: [Double] -> [Double] > > calculatePar xss = runEval $ go xss > > where > > go :: Strategy [Double] > > go [] = return [] > > go xs = do > > lsh <- (rpar `dot` rdeepseq) $ calculateSeq as > > lst <- go bs > > return (lsh ++ lst) > > where > > !(as, bs) = splitAt 8192 xs > > > > Compiling and running with: > > > > ghc -O2 -Wall -threaded -rtsopts -fforce-recomp -eventlog evalleak.hs > > ./evalleak -oreport.html -g +RTS -N2 -ls -s > > > > I get: > > > > benchmarking Seq > > mean: 100.5990 us, lb 100.1937 us, ub 101.1521 us, ci 0.950 > > std dev: 2.395003 us, lb 1.860923 us, ub 3.169562 us, ci 0.950 > > > > benchmarking Par > > mean: 2.233127 ms, lb 2.169669 ms, ub 2.296155 ms, ci 0.950 > > std dev: 323.5201 us, lb 310.2844 us, ub 344.8252 us, ci 0.950 > > > > That's a hopeless result. Looking at the spark allocation everything > > looks fine: > > > > SPARKS: 202 (202 converted, 0 overflowed, 0 dud, 0 GC'd, 0 fizzled) > > > > But analyzing eventlog with ThreadScope I see that parallel function > > spends most of the time doing > > garbage collection, which suggests that I have a memory leak somewhere. I > > suspected that problem > > might be caused by appending two lists together in the parallel > > implementation, but replacing > > this with difference lists doesn't help. Changing granularity (e.g. > > splitAt 512) also brings no > > improvement. Can anyone point me to what am I doing wrong? > > > > Janek > > > > PS. This is of course not a real world code - I know that I'd be better > > of using unboxed data > > structures for doing computations on Doubles. > > > > _______________________________________________ > > Haskell-Cafe mailing list > > Haskell-Cafe(a)haskell.org > > http://www.haskell.org/mailman/listinfo/haskell-cafe

2 2

ANN: hledger-web 0.19
by Simon Michael 16 Nov '12

16 Nov '12

I'm pleased to announce hledger-web 0.19, compatible with the latest hledger and Yesod. Release notes: * web: builds with yesod 1.1.3 * web: obeys command-line query options at startup again * the autogenerated session file is now a dot file (.hledger-web_client_session.aes) hledger is a command-line tool and haskell library for tracking financial transactions, which are stored in a human-readable plain text format. In addition to reporting, it can also help you record new transactions, or convert CSV data from your bank. Add-on packages include hledger-web, a web interface. hledger is inspired by and compatible with John Wiegley's Ledger. For more, see http://hledger.org . Install it: cabal update; cabal install hledger-web For more installation help, see http://hledger.org/MANUAL.html#installing . Or, sponsor a ready-to-run binary for your platform: http://hledger.org/DOWNLOAD.html .

1 0

Polymorphic Type Safe URL building -- I need advice on my project
by Kyle Hanson 16 Nov '12

16 Nov '12

Hello, So I started working on a project involving polymorphic type safe urls. I know there are other type-safe url's out there, but I want some advice before I start reorganizing it. It is located here: https://github.com/dracule/web-scatter One might ask why you would want polymorphic types in your URL. Current implementation of type-safe URLs use a single type and then have it pattern match on the constructors. However, It is a pretty common occurrence that you might want to use a type from other parts of code. Where this becomes prevalent is in IxSet and AcidState. For IxSet your Index keys all have to have separate types . So with this, you can convert your url into your index key's type and then just make your handler like this: myHandler :: BlogId -> SomeWebHandler I know my code probably has some terrible inefficiencies or something, so I am looking for some feedback on some jarring problems. Thank You

1 0

Taking over ghc-core
by Shachaf Ben-Kiki 16 Nov '12

16 Nov '12

With Don Stewart's blessing (<https://twitter.com/donsbot/status/267060717843279872>), I'll be taking over maintainership of ghc-core, which hasn't been updated since 2010. I'll release a version with support for GHC 7.6 later today. Shachaf

8 8

using createProcess and waitForProcess, but mpg123 plays for only 6 seconds
by rnons 15 Nov '12

15 Nov '12

Hi guys, I'm building an application that needs to wrap an external mp3 player, in this case mpg123. Here is my code: import System.IO import System.Process import Control.Concurrent mpgLoop = do let sh = "mpg123 -R" (Just hin, Just hout, _, hdl) <- createProcess (shell sh){ std_in = CreatePipe, std_out=CreatePipe } --hPutStrLn hin "SILENCE" hPutStrLn hin "LOAD /home/rnons/Music/test.mp3" hFlush hin waitForProcess hdl return () main = do forkIO mpgLoop -- threadDelay 20000000 getChar I expected with "waitForProcess", this program will be able to run till the song ends. However, mpg123 plays for only 6 seconds. Maybe I missed something? rnons

3 3

local type denotation
by Serge D. Mechveliani 14 Nov '12

14 Nov '12

Please, how to correctly set an explicit type for a local value in the body of a polymorphic function? Example (tested under ghc-7.6.1): data D a = D1 a | D2 a (a -> a) f :: Eq a => D a -> a f (D1 x) = x f (D2 x g) = let -- y :: Eq a => a y = g x in if x == y then x else g y main = putStr $ shows (f (D2 (1 :: Int) succ)) "\n" This is compiled by ghc --make Main Now I need, for a certain reason, to explicitly set the type for y in `let', with the meaning: "this very `a' which is in the signature for f" (and I think that this type Haskell assignes to y in "y = g x"). I need to declare this type in a separate line: y :: <what ever it is>. Both `y :: a' and `y :: Eq a => a' are not compiled. Please, copy the answer to mechvel(a)botik.ru Thanks, ------ Sergei

5 4

mtl-2.1 severly broken, cabal needs blacklisting
by Andreas Abel 14 Nov '12

14 Nov '12

After 2 days of shrinking 251 modules of source code to a few lines I realized that modify in MonadState causes <<loop>> in mtl-2.1. http://hackage.haskell.org/packages/archive/mtl/2.1/doc/html/src/Control-Mo… The bug has been fixed, apparently seven month ago. https://github.com/ekmett/mtl/pull/1 However, the "malicious" mtl-2.1 still lingers on: it is available from hackage and installed in many systems. This calls for a means of blacklisting broken or malicious packages. cabal update should also pull a blacklist of packages that will never be selected by cabal install (except maybe by explicit user safety overriding). I think such a mechanism is not only necessary for security purposes, but also to safe the valuable resources of our community. Cheers, Andreas -- Andreas Abel <>< Du bist der geliebte Mensch. Theoretical Computer Science, University of Munich Oettingenstr. 67, D-80538 Munich, GERMANY andreas.abel(a)ifi.lmu.de http://www2.tcs.ifi.lmu.de/~abel/

6 9

Does anyone know where George Pollard is?
by Myles C. Maxfield 14 Nov '12

14 Nov '12

Hello, I sent a message to George Pollard (porges(a)porg.es) about his 'idna' package [1] a couple days ago, but he hasn't responded. I'd like to depend on his package for something that I'm working on, but his package fails to build (The email I sent him includes a patch that should fix up the build problems). The package hasn't been updated for 3 years and he hasn't listed a source control repository. Does anyone know where he is? If not, is there an accepted practice to resolve this situation? Should I upload my own 'idna2' package? Thanks, Myles [1] http://hackage.haskell.org/package/idna

3 3

Re: [Haskell-cafe] Strange behavior with listArray
by oleg＠okmij.org 14 Nov '12

14 Nov '12

Alex Stangl wrote: > To make this concrete, here is the real solve function, which computes > a border array (Knuth-Morris-Pratt failure function) for a specified > string, before the broken memoization modification is made: > solve :: String -> String > solve w = let h = length w - 1 > wa = listArray (0, h) w > pI = 0 : solveR (tail w) 0 > solveR :: String -> Int -> [Int] > solveR [] _ = [] > solveR cl@(c:cs) k = if k > 0 && wa!k /= c > then solveR cl (pI!!(k-1)) > else let k' = if wa!k == c > then k + 1 > else k > in k' : solveR cs k' > in (intercalate " " . map show) pI > > Here solveR corresponds to f in the toy program and pI is the list > I would like to memoize since references to earlier elements could > get expensive for high values of k. Ok, let's apply a few program transformations. First we notice that the list pI must have the same length as the string w. Since we have already converted the string w to an array, wa, we could index into that array. We obtain the following version. > solve1 :: String -> String > solve1 w = (intercalate " " . map show) pI > where > h = length w - 1 > wa = listArray (0, h) w > pI = 0 : solveR 1 0 > solveR :: Int -> Int -> [Int] > solveR i k | i > h = [] > solveR i k = > let c = wa!i in > if k > 0 && wa!k /= c > then solveR i (pI!!(k-1)) > else let k' = if wa!k == c > then k + 1 > else k > in k' : solveR (i+1) k' > > t1s1 = solve1 "the rain in spain" > t1s2 = solve1 "aaaaaaaaaaaa" > t1s3 = solve1 "abbaabba" We don't need to invent an index: it is already in the problem. The unit tests confirm the semantics is preserved. The _general_ next step is to use the pair of indices (i,k) as the key to the two dimensional memo table. Luckily, our case is much less general. We do have a very nice dynamic programming problem. The key is the observation k' : solveR (i+1) k' After a new element, k', is produced, it is used as an argument to the solveR to produce the next element. This leads to a significant simplification: > solve2 :: String -> Array Int Int > solve2 w = pI > where > h = length w - 1 > wa = listArray (0, h) w > pI = listArray (0,h) $ 0 : [ solveR i (pI!(i-1)) | i <- [1..] ] > solveR :: Int -> Int -> Int > solveR i k = > let c = wa!i in > if k > 0 && wa!k /= c > then solveR i (pI!(k-1)) > else let k' = if wa!k == c > then k + 1 > else k > in k' > > t2s1 = solve2 "the rain in spain" > t2s2 = solve2 "aaaaaaaaaaaa" > t2s3 = solve2 "abbaabba" The unit tests pass.

2 1

Re: [Haskell-cafe] Strange behavior with listArray
by oleg＠okmij.org 13 Nov '12

13 Nov '12

Alex Stangl posed a problem of trying to efficiently memoize a function without causing divergence: > solve = let a :: Array Int Int > a = listArray (0, 3) (0 : f 0) > f k = if k > 0 > then f (a!0) > else 0 : f 1 > in (intercalate " " . map show . elems) a Daniel Fischer explained the reason for divergence: > The problem, Alex, is that > > f k = if k > 0 > then f (a!0) > else 0 : f 1 > > is strict, it needs to know the value of (a!0) to decide which branch to take. > But the construction of the array a needs to know how long the list (0 : f 0) > is (well, if it's at least four elements long) before it can return the array. > So there the cat eats its own tail, f needs to know (a part of) a before it > can proceed, but a needs to know more of f to return than it does. But the problem can be fixed: after all, f k is a list of integers. A list is an indexable collection. Let us introduce the explicit index: > import Data.Array((!),Array,elems,listArray) > import Data.List(intercalate) > > solve = (intercalate " " . map show . elems) a > where > a :: Array Int Int > a = listArray (0, 3) (0 : [f 0 i | i <- [0..]]) > > f 0 0 = 0 > f 0 i = f 1 (i-1) > f k i = f (a!0) i This converges. Here is a bit related problem: http://okmij.org/ftp/Haskell/AlgorithmsH.html#controlled-memoization

2 1