May 2009 - Haskell-Cafe

Data.Binary suboptimal instance
by Andrew Coppin 23 May '09

23 May '09

So lately I've been working on a little program to generate trippy graphics. (Indeed, some of you may remember it from a few years back...) Anyway, getting to the point, I just restructured my program. As part of the restructuring, I got rid of all the jiggery-pokery with Data.Array.Storable and so forth and decided to use Data.Binary. My first problem was quite simple. I want to write a program that reads an item from the input file, processes it, writes it to the output file, and repeats until the input file is empty. Data.Binary doesn't appear to provide any obvious way to do this. You can't be in the Get and Put monads simultaneously, and I can't figure out how to interleave them. In the end, I ended up with something like xs <- decodeFile f1 encodeFile f2 (map f xs) Unfortunately, it looks like this doesn't do what I want. Serialised lists have their length prepended to them, which means that encodeFile is going to have to generate the *entire* list in memory so it can count how big it is, before it can output a single byte to disk. (!) This is particularly annoying since the output list will be exactly the same size as the input one, and the very first thing decodeFile is doing is reading in that size figure. Maybe there's a way around this glitch, and I just haven't thought of it yet. But you'd think that wanting to lazily process data from an input file and write it into an output file would be an extremely common use-case. Given that, I'm not seeing an obvious way to handle it. Anyway, that's one small problem, but I can live with it. There's another, much bigger problem though, and that's really what I wanted to talk about... As we all know, Data.Binary is *built* for speed. So imagine my shock when my newly adjusted program now based around this library turned out to be massively slower, and the files it produced were drastically larger. It didn't take me that long to dig up the problem. The problem seems to boil down to this: The Binary instance for Double (and Float, by the way) is... well I guess you could argue it's very portable, but efficient it isn't. As we all know, an IEEE-754 double-precision floating-point number occupies 64 bits; 1 sign bit, 11 exponent bits, and 52 mantissa bits (implicitly 53). I had assumed that the Binary instance for Double would simply write these bits to disk, requiring approximately 0 computational power, and exactly 64 bits of disk space. I was wrong. ...what it *actually* does is convert the 64-bit Double into a 32-bit exponent and an arbitrary-precision integer part. (!) It appears to do this by floating-point arithmetic rather than just low-level bit shuffling. Looking up how arbitrary-precision integers are serialised, I see that there's an 8-bit "flag" indicating whether the integer fits into 32 bits, and if it doesn't, there's an 8-bit sign value, followed by a serialised list of bytes. So, in other words, a 32-bit length value, followed by the bytes themselves. To summarise, when I ask for a 64-bit Double to be serialised, I get this: 32-bit exponent. 8-bit flag (probably always "1") 8-bit sign (either "0" or "1") 32-bit size (probably always "8") 64-bit mantissa That's 144 bits in total, i.e., 225% larger than the original Double. (Let's not even go into how much computer power it takes to construct all this data before it's written to disk...) So, that's why my files balooned in size, and why my program slowed to a crawl. But how do I fix this? Well, my solution was simple, brutal, and probably *highly* non-portable. It begins with Unsafe.Coerce (that's never a good thing!) Put simply, if you take your 64-bit Double and unsafeCoerce it into a Word64 and then ask Data.Binary to serialise that, it writes it straight to disk without screwing around with it first. The result ought to be portable to any architecture that uses IEEE-754 arithmetic natively. (Anybody know of an arch this *doesn't* apply to?) But sure, if you wanted to do this on some other architecture with a different native float format, you'd have to write some trixy code to handle it. (And then add conditional compilation for it.) Is there any danger that there might be some kind of improvement to the Double instance in the next version of Data.Binary? END.

3 6

Re: Re: [Haskell-cafe] Re: A problem with par and modules boundaries...
by Duncan Coutts 23 May '09

23 May '09

On Sat, 2009-05-23 at 13:31 -0400, Mario Blažević wrote: > >>> You could probably see exactly what's happening in > >>> more detail by going through the Core output. > >> > >> Thank you, this advice helped. The Core output indicates > >> that function `test' evaluates the arguments to > >> `parallelize' before it calls it. In other words, the > >> call to `parallelize' is optimized as a strict function > >> call -- which it is. The problem is that this > >> optimization evaluates the arguments sequentially. > >> Compiling with optimizations turned off regains the > >> parallel execution. > >> > >> I guess I will report this as a GHC bug. Or is it a > >> feature request? > > > > As Duncan suggessted, try with GHC head (grab a snapshot). `par` et al > > are much improved. > > I already have, with the snapshot from 21st of April. It behaves the same > as 6.8.2, except it runs for twice as long. > > I'd like to take back a part of what I said before, though: `parallelize' should > be strict only in its second argument. parallelize a b = a `par` (b `pseq` (a, b)) GHC infers that strictness of parallelize. It thinks that it is lazy in both args (you can check this yourself using ghc --show-iface). That's because the definitions of par and pseq use the function 'lazy': -- The reason for the strange "lazy" call is that it fools -- the compiler into thinking that pseq and par are non-strict in -- their second argument (even if it inlines pseq at the call site). -- If it thinks pseq is strict in "y", then it often evaluates -- "y" before "x", which is totally wrong. pseq x y = x `seq` lazy y par x y = case (par# x) of { _ -> lazy y } So GHC thinks that par is lazy in both arguments, while it thinks pseq is strict in the first and lazy in the second. > Its strictness in the first argument should be the same as with `par`. Yes, which it is. > Even though `parallelize x y' always evaluates both x and y, Be careful about what you mean. Yes, it starts the evaluation of x in parallel with y, but that does not mean it is strict in x, as you notice with your example of undefined below. > the following test works fine with optimizations even if `parallelize' > is imported: > > main = putStrLn (snd $ parallelize undefined "Hello, World!") > > So the function is not strict, and I don't understand why GHC should evaluate the > arguments before the call. Right, it's lazy in the first and strict in the second argument. As far as I can see we have no evidence that is is evaluating anything before the call. > Does anybody know of a pragma or another way to make a function *non-strict* even > if it does always evaluate its argument? In other words, is there a way to > selectively disable the strictness optimization? Yes, which is what pseq and par already do. If there's a bug, we need to reproduce it and report it. I cannot reproduce it. Duncan

1 0

Fwd: [Haskell-cafe] Data.Binary suboptimal instance
by Antoine Latter 23 May '09

23 May '09

I suppose I should send my reply to the list ... ---------- Forwarded message ---------- From: Antoine Latter <aslatter(a)gmail.com> Date: Fri, May 22, 2009 at 5:54 PM Subject: Re: [Haskell-cafe] Data.Binary suboptimal instance To: Khudyakov Alexey <alexey.skladnoy(a)gmail.com> On Fri, May 22, 2009 at 4:36 PM, Khudyakov Alexey <alexey.skladnoy(a)gmail.com> wrote: >> You can! - It's again time to point out that Put shouldn't be a monad, but >> a monoid. But as it is, Put is a Writer monad on top of the Builder >> monoid. Better use that Builder monoid directly. > > Could you elaborate? I didn't quite understand. > > > Anyway I had similar problem and simply wrote few functions. They > encode/decode values of same type element by element. It's lazy enough so code > could be written in following style: > Or you could go for the compromise position, where the list can be part of a complex data structure so you're not relying on EOF to find the end. (warning, I don't have my compiler handy so this may not even typecheck) import Control.Monad import Data.Monoid import Data.Binary.Builder import Data.Binary.Get data ChunkedList a = Cons [a] (ChunkedList a) -- Non-null list | Nil chunkSize = 50 fromList :: [a] -> ChunkedList a fromList [] = Nil fromList xs = let (front,back) = splitAt chunkSize xs in Cons front (fromList back) toList :: ChunkedList a -> [a] toList Nil = [] toList (Cons front back) = front ++ toList back putList :: (a -> Builder) -> [a] -> Builder putList f xs = putChunkedList (fromList xs) where putChunkedList Nil = singleton 0 putChunkedList (Cons front back) = mconcat [ singleton (genericLength front) , mconcat $ map f front , putChunkedList back ] getList :: Get a -> Get [a] getList m = toList `liftM` getChunkedList where getChunkedList = do cLen <- getWord8 case cLen of 0 -> return Nil _ -> Cons `liftM` replicateM (fromIntegral cLen) m `ap` getChunkedList

2 1

Re: [Haskell-cafe] Re: A problem with par and modules boundaries...
by Mario Blažević 23 May '09

23 May '09

On Fri 22/05/09 10:51 AM , John Lato jwlato(a)gmail.com sent: > Hi Mario, > > It looks like the parallelize function is getting inlined when it's in > the same file, but not when it's in a separate file. > > Adding a {-# INLINE parallelize #-} pragma to the module with > parallelize recovers all the performance for me. > > You could probably see exactly what's happening in more detail by > going through the Core output. Thank you, this advice helped. The Core output indicates that function `test' evaluates the arguments to `parallelize' before it calls it. In other words, the call to `parallelize' is optimized as a strict function call -- which it is. The problem is that this optimization evaluates the arguments sequentially. Compiling with optimizations turned off regains the parallel execution. I guess I will report this as a GHC bug. Or is it a feature request?

2 1

A problem with par and modules boundaries...
by Mario Blažević 23 May '09

23 May '09

I'll cut to the chase. The short program below works perfectly: when I compile it with -O2 -threaded and run with +RTS -N2 command-line options, I get a nearly 50% real-time improvement: $ time ./primes-test +RTS -N2 5001 real 0m9.307s user 0m16.581s sys 0m0.200s However, if I move the `parallelize' definition into another module and import that module, the performance is completely lost: $ time ./primes-test +RTS -N2 5001 real 0m15.282s user 0m15.165s sys 0m0.080s I'm confused. I know that `par` must be able work across modules boundaries, because Control.Parallel.Strategies is a module and presumably it works. What am I doing wrong? > module Main where > > import Control.Parallel > import Data.List (find) > import Data.Maybe (maybe) > > --import Parallelizable > parallelize a b = a `par` (b `pseq` (a, b)) > > test :: Integer -> Integer -> Integer > test n1 n2 = let (p1, p2) = parallelize > (product $ factors $ product [1..n1]) > (product $ factors $ product [1..n2]) > in p2 `div` p1 > > factors n = maybe [n] (\k-> (k : factors (n `div` k))) > (find (\k-> n `mod` k == 0) [2 .. n - 1]) > > main = print (test 5000 5001)

5 8

import qualified?
by Vasili I. Galchin 23 May '09

23 May '09

Hello, I am working with some somewhat legacy code. I understand what "import qualified Blah as B" means but what does "import qualified Blah" mean? Is this a deprecated feature? I saw with user defined module as well as with "import qualified System" for example. REgards, Vasili

4 4

MPI ... Globus APIs
by Vasili I. Galchin 23 May '09

23 May '09

Hello, 1) I think I read before that there some kind of MPI API (bindings) in Haskell. Yes? If so, current state? 2) http://www.globus.org/ Globus bindings? Kind regards, Vasili

1 1

ANNOUNCE: text 0.2, fast and comprehensive Unicode support using stream fusion
by Bryan O'Sullivan 23 May '09

23 May '09

I'm pleased to announce the availability of text 0.2, an efficient Unicode text library that uses stream fusion. New and notable in this release is support for lazy, chunked text, so you can process text files far larger than memory using a small footprint. Hackage page: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/text Darcs repo: darcs get http://code.haskell.org/text Report bugs: http://trac.haskell.org/text/

1 0

community.haskell.org and code.haskell.org problems
by Neil Mitchell 22 May '09

22 May '09

Hi, I regularly (almost daily) have problems reaching both community and code.haskell.org, getting 500 server error messages. I've decided to make all my Haskell code available on community, which means that when it goes down, I can't access my repos - which is not great. Is there a reason for the poor reliability of these servers? Can anything be done to improve them? I know of servers running on Windows laptops which have far higher uptime :-) Thanks Neil

2 1

generic filter through MonadPlus
by Jason Dusek 22 May '09

22 May '09

It seems reasonable that filter should be generic. The underlying container need only support some kind of traversal, a zero element and a concatenation that eliminates zeroes. A `Monad` provides traversal via `join` and `fmap`; the remaining qualities are satisfied by `MonadPlus`. I've put together an implementation of `filter` for `MonadPlus` that works well enough for lists (though it presents somewhat greater obstacles to efficient compilation). I'm not sure whether `filter` is important enough to warrant its own generics package -- it's one of many collection operations that need to be generified. I'd like to know what folks think about the use of `MonadPlus` in this case. -- Jason Dusek |...an implementation of `filter`...| http://github.com/jsnx/genfil/blob/246026b975ec13587186681b7b346ae1e440d0c9…

2 1