June 2007 - Haskell-Cafe

Switch optimization
by Tom Pledger 10 Jun '07

10 Jun '07

Stefan O'Rear wrote: | On Mon, Jun 11, 2007 at 09:43:17AM +1000, Thomas Conway wrote: : | > codeLen 127 = 0 | > codeLen 128 = 1 | > ... | > codeLen 255 = 8 | > | > Now, compiling with ghc 6.6.1 and -O3, I see that it generates a long | > chain of conditional branches. : That's deeply tied in with Num being a subclass of Eq, isn't it? Pattern matching for /non-numeric/ data constructors should be more direct, at any optimisation level, thanks to the taglessness of the STG machine. | I'd suggest learning how to hack on GHC, I get a chain of branches even | at the maximum optimization setting. Hackers are always appreciated! Such a GHC hack may have to be limited to some known, standard numeric types. User-defined numeric types may not provide anything that you can use to look up a jump table. How would an array go, as a user-level optimisation? Regards, Tom

1 0

Re: HList questions
by oleg＠pobox.com 10 Jun '07

10 Jun '07

Marc Weber wrote: > Do you know what a type indexed coproduct is ? > (TIC.hs from HList) > What is the purpose of this module? In a regular Haskell record, we can retrieve the value of one of its components given the label. A type-indexed Product (TIP, or TIR) is a similar collection of values -- indexed not by their label but by their type. Given a TIP of an Int and a Char, we can retrieve either value just by specifying what return type we want (Int or Char). A type-indexed co-product, TIC, is a type-indexed sum. A TIC of Int and Char has the type of the union of Int and Char (think of Either Int Char). We can likewise ask for an Int element -- and receive either (Just val) or Nothing. Unlike (Either Int Char), we do not have to know whether Int is the first alternative of Either or the second one. We just ask for an Int. TIP and TIC have been introduced in M. Shields and E. Meijer. Type-indexed rows. (ref 31 of the HList paper) We wanted to show that HList can implement both. An implementation of TIC different from that of App C of the HList paper is used in the OOHaskell paper. That new implementation is based on nested Either datatypes rather than on Dynamics. The application is placing objects of two different types in the same list. There are two approaches: find the intersection of the object types and coerce objects to that intersection -- or find the union and inject objects into that union. The OOHaskell paper shows both approaches, with meet and joins of object types computed automatically. > Why the Proxy type has been introduced? Just to emphasize that we use the type as the index; to clarify the role of that argument. One can get be without them, their purpose is mere stylistic.

2 1

Switch optimization
by Thomas Conway 10 Jun '07

10 Jun '07

Hi All, I'm writing some variable byte codec routines, which are used in inner^N loops, and which I want to make really efficient. There are several spots where the code uses lookup tables. The best example is the table, which given the first byte, returns the number of additional bytes. It is a precomputed version of the following function: > codeLength :: Word8 -> Int > codeLength w > | w .&. 0x80 == 0 = 0 > | otherwise = 1 + (codeLength $ w `shiftL` 1) from which we construct a 256 entry table: codeLen 0 = 0 codeLen 1 = 0 codeLen 2 = 0 ... codeLen 127 = 0 codeLen 128 = 1 ... codeLen 255 = 8 Now, compiling with ghc 6.6.1 and -O3, I see that it generates a long chain of conditional branches. Now, even taking laziness into account, this seems like terribly inefficient code. I wrote this thinking it would be more efficient than constructing a CAF array: codeLens = listArray (0,255) (map codeLength [0..255]) but I'm guessing the CAF version would probably work out much more efficient in the long run. However, I think ghc (and any other compiler), should detect the following properties: 1. all the clauses are mutually exclusive, so the sequencing is irrelevant to the semantics 2. Given an explicit type declaration Word8 -> ...., the 256 cases cover all the possible constructors of the type, so there are no missing clauses. I would have expected the generated code to have the form: codeLen: x <- pick up arg return closure (codeLen' x) codeLen': x' <- force x update precomputed-table[x'] Even if you leave out property 2 and include bounds checks, this seems like an important kind of function to optimize well. So what have I missed, or is it time to learn how to hack on ghc? T. -- Thomas Conway drtomc(a)gmail.com Silence is the perfectest herald of joy: I were but little happy, if I could say how much.

2 1

How to dynamically attach readers to streams?
by Marc Weber 10 Jun '07

10 Jun '07

Example: main = readFile "/dev/input/mouse" >>= mapM print . streamToEvents That's no easy. Now I want to listen to those events remotely using a network conncetion Data.Network does provide everything I need. Is this done by substituting the print function with something like sent event = do writers <- getWritersFromMVar mapM (sent event) writers and using another lightweight thread to add writers/connections to the MVar? Would you implement this in another way? Marc

1 0

Data polymophism
by Phlex 10 Jun '07

10 Jun '07

Hello all, It seems this message was lost somehow, so i'm trying to send it again ....sorry if it comes up twice on the list ! I have this class which gives a common interface to (UniqueIndex a k) and (MultiIndex a k) : class (Show a, Key_ k) => Index_ i a k | i -> k, k -> a where buildKey :: (a -> k) insertIndex :: Id -> a -> i -> Maybe i deleteIndex :: Id -> a -> i -> i updateIndex :: Id -> a -> a -> i -> Maybe i updateIndex id oldItem newItem index = insertIndex id newItem $ deleteIndex id oldItem index Now i need to have these indexes in a list, so i declared that type : data DbIndex = forall a k i. (Show a, Key_ k, Index_ i a k) => DbIndex i Up to this point everything is fine, I can create concrete Indexes and put these different index types in the same list, after wrapping them in a DbIndex. But i don't seem to find a way to get out of this DbIndex type to actually work on the enclosed index. for instance, this doesn't work: liftDbIndex (DbIndex index) fun = DbIndex (fun index) this doesn't work either : dbIndexBuildKey (DbIndex index) value = (buildKey index) value How can i access the enclosed concrete index, via its Index_ class ? Maybe am I totally on the wrong track ? Thanks in advance, Sacha

3 5

Re: [Haskell-cafe] LaTeX
by Andrew Coppin 10 Jun '07

10 Jun '07

Brian Sniffen wrote: > lhs2TeX uses > \newcommand{\plus}{\mathbin{+\!\!\!+}} Ah, OK. That looks good... Thanks.

1 0

haskell version of fractal benchmark
by brad clawsie 09 Jun '07

09 Jun '07

i recently saw a (yet-another) benchark comparing various languages: http://www.timestretch.com/FractalBenchmark.html while no haskell example was listed, i thought i would try a naive implementation myself for comparison. it is available here: http://www.b7j0c.org/dev/haskell/misc/time.hs my timing of the compiled code was slightly under three seconds over a few tests, landing sort of where i would expect a naive haskell implementation to place. i am sure people here could greatly improve my attempt. it may be that my solution is not even correct.

7 12

Fast number parsing with strict bytestrings [Was: Re: Seemingly subtle change causes large performance variation]
by dons＠cse.unsw.edu.au 09 Jun '07

09 Jun '07

mdanish: > Hello, > > I've been playing with the INTEST problem on SPOJ which demonstrates > the ability to write a program which processes large quantities of > input data. http://www.spoj.pl/problems/INTEST/ > But when I make a slight modification, the program chews up a ton more memory > and takes more time: > > import Control.Monad > import Data.Maybe > import qualified Data.ByteString.Char8 as B > > divisibleBy :: Int -> Int -> Bool > a `divisibleBy` n = a `rem` n == 0 > > main :: IO () > main = do > [n,k] <- (map int . B.split ' ') `fmap` B.getLine :: IO [Int] > > let > doLine :: Int -> Int -> IO Int > doLine r _ = B.getLine >>= return . testDiv r > -- 'return' moved here ^^ What follows is a solution to the original question, and then a dramatic rewrite, showing the fastest way (that I know of) to parse \n separated lists of numbers in Haskell. The results should outperform C fairly well. *** Solution 1: don't be so lazy in the fold. First, look at that lazy fold. A simple fix, try being explict about forcing your accumulator: doLine :: Int -> Int -> IO Int doLine r _ = B.getLine >>= \s -> return $! testDiv r s And some timing data: Original: $ time ./A < in 29359 ./A < in 1.52s user 0.06s system 93% cpu 1.679 total Too lazy: $ time ./B < in 29359 ./B < in 3.84s user 0.26s system 82% cpu 4.957 total Hand back some strictness hints: $ time ./D < in 29359 ./D < in 1.52s user 0.03s system 94% cpu 1.637 total *** Solution 2: use lazy bytestrings to avoid gunky IO Now, however, I'd give up on that explict getLine stuff, and use a lazy bytestring. Something like this: import Data.Maybe import Data.List import qualified Data.ByteString.Lazy.Char8 as L main :: IO () main = do (l:ls) <- L.lines `fmap` L.getContents -- done with IO now. let [n,k] = map int (L.split ' ' l) print . foldl' (test k) 0 . map int . take n $ ls test :: Int -> Int -> Int -> Int test k acc n | n `divisibleBy` k = acc+1 | otherwise = acc int :: L.ByteString -> Int int = fst . fromJust . L.readInt divisibleBy :: Int -> Int -> Bool a `divisibleBy` n = a `rem` n == 0 The general rule for bytestring loops is to avoid IO, and to use lazy bytestrings if you need 'lines'. Also, program in a high level, using combinators, rather than your own loops, so that fusion will kick in (we get some list fusion here). And running it: $ time ./C < in 29359 ./C < in 1.22s user 0.04s system 94% cpu 1.335 total Ok, faster, and cleaner. Avoid mixing IO into your code! *** Solution 3: 4x faster by processing strict cache chunks Now the fun part. The following code is the fastest way I know to process lists of numbers (in any language). Its' based on similar code I wrote for the language shootout. The key trick is to use lazy bytestrings *only* as a method for filling the cache with newline-aligned chunks of numbers. Once you've got that perfectly-sized chunk, walk its lines, and process them. This is all done in Haskell, and relies on an understanding of the low level details of bytestring optimisations. The general framework could be reused for any code that needs to process a list of numbers in a file, where you care about speed. It performs as follows: $ time ./F < in 29359 ./F < in 0.24s user 0.01s system 76% cpu 0.327 total Pretty fast.. Previous experience[1] indicates it is pretty hard to write a C line parsing program[2] that that run this fast. And the code, with comments: 1. http://shootout.alioth.debian.org/gp4/benchmark.php?test=sumcol&lang=ghc&id… 2. http://shootout.alioth.debian.org/gp4/benchmark.php?test=sumcol&lang=gcc&id… {-# OPTIONS -fbang-patterns #-} import Data.Char import Data.Maybe import Data.ByteString.Base import qualified Data.ByteString.Char8 as S import qualified Data.ByteString.Lazy.Char8 as L main = do ss <- L.getContents -- done with IO now. let (l,ls) = L.break (=='\n') ss -- don't need count, we're allocating lazily k = fst . fromJust . L.readInt . last . L.split ' ' $ l file = L.toChunks (L.tail ls) -- a lazy list of strict cache chunks print $ process k 0 file divisibleBy :: Int -> Int -> Bool a `divisibleBy` n = a `rem` n == 0 -- --------------------------------------------------------------------- -- -- Optimised parsing of strict bytestrings representing \n separated numbers -- -- -- we have the file as a list of cache chunks -- align them on \n boundaries, and process each chunk separately -- when the next chunk is demanded, it will be read in. -- process :: Int -> Int -> [S.ByteString] -> Int process k i [] = i process k !i (s:t:ts) | S.last s /= '\n' = process k (add k i s') ts' where (s',r) = S.breakEnd (=='\n') s ts' = (S.append r t) : ts -- join chunks on line boundaries process k i (s: ss) = process k (add k i s) ss -- -- process a single cache-sized chunk of numbers, \n aligned -- add :: Int -> Int -> S.ByteString -> Int add k i s | S.null s = i | otherwise = test k i (parse x) xs where (x,xs) = uncons s -- -- process a single line, until \n -- test :: Int -> Int -> Int -> ByteString -> Int test k i !n t | y == '\n' = -- done reading the line, process it: if n `divisibleBy` k then add k (i+1) ys else add k i ys | otherwise = test k i n' ys where (y,ys) = uncons t n' = parse y + 10 * n parse c = ord c - ord '0' -- fastest way to take the head of a strict bytestring uncons s = (w2c (unsafeHead s), unsafeTail s) Cheers, Don

3 5

class MonoidBreak?
by Alex Jacobson 08 Jun '07

08 Jun '07

Is there a standard class that looks something like this: class (Monoid m) => MonoidBreak m where mbreak::a->m a->(m a,m a) and it should follow some law like: m == uncurry mappend $ mbreak x m -Alex-

3 3

Memoization
by Mark Engelberg 08 Jun '07

08 Jun '07

I'd like to write a memoization utility. Ideally, it would look something like this: memoize :: (a->b) -> (a->b) memoize f gives you back a function that maintains a cache of previously computed values, so that subsequent calls with the same input will be faster. I've searched the web for memoization examples in Haskell, and all the examples use the trick of storing cached values in a lazy list. This only works for certain types of functions, and I'm looking for a more general solution. In other languages, one would maintain the cache in some sort of mutable map. Even better, in many languages you can "rebind" the name of the function to the memoized version, so recursive functions can be memoized without altering the body of the function. I don't see any elegant way to do this in Haskell, and I'm doubting its possible. Can someone prove me wrong? --Mark

35 77