- Haskell-Cafe - Haskell.org

An interesting monad: "Prompt"
by Ryan Ingram 04 Jan '08

04 Jan '08

(This message is a literate haskell file. Code for the "Prompt" monad is preceded by ">"; code for my examples is preceded by "]" and isn't complete, but intended for illustration.) I've been trying to implement a few rules-driven board/card games in Haskell and I always run into the ugly problem of "how do I get user input"? The usual technique is to embed the game in the IO Monad: ] type Game = IO ] -- or ] type Game = StateT GameState IO The problem with this approach is that now arbitrary IO computations are expressible as part of a game action, which makes it much harder to implement things like replay, undo, and especially testing! The goal was to be able to write code like this: ] takeTurn :: Player -> Game () ] takeTurn player = do ] piece <- action (ChoosePiece player) ] attack <- action (ChooseAttack player piece) ] bonusTurn <- executeAttack piece attack ] when bonusTurn $ takeTurn player but be able to script the code for testing, allow undo, automatically be able to save replays, etc. While thinking about this problem earlier this week, I came up with the following solution: > {-# OPTIONS_GHC -fglasgow-exts -fallow-undecidable-instances #-} > -- undecidable instances is only needed for the MonadTrans instance below > > module Prompt where > import Control.Monad.Trans > import Control.Monad.Identity > class Monad m => MonadPrompt p m | m -> p where > prompt :: p a -> m a "prompt" is an action that takes a prompt type and gives you a result. A simple example: ] prompt [1,3,5] :: MonadPrompt [] m => m Int This prompt would ask for someone to pick a value from the list and return it. This would be somewhat useful on its own; you could implement a "choose" function that picked randomly from a list of options and gave non-deterministic (or even exhaustive) testing, but on its own this wouldn't be much better than the list monad. What really made this click for me was that the prompt type could be built on a GADT: ] newtype GamePrompt a = GP (GameState, GameChoice a) ] data GameChoice a where ] -- pick a piece to act with ] ChoosePiece :: Player -> GameChoice GamePiece ] -- pick how they should attack ] ChooseAttack :: Player -> GamePiece -> GameChoice AttackType ] -- etc. Now you can use this type information as part of a "handler" function: ] gameIO :: GamePrompt a -> IO a ] gameIO (GP (state, ChoosePiece player)) = getPiece state player ] gameIO (GP (state, ChooseAttack player piece)) = attackMenu player piece ] -- ... The neat thing here is that the GADT specializes the type of "IO a" on the right hand side. So, "getPiece state player" has the type "IO GamePiece", not the general "IO a". So the GADT is serving as a witness of the type of response wanted by the game. Another neat things is that, you don't need to embed this in the IO monad at all; you could instead run a pure computation to do AI, or even use it for unit testing! > -- unit testing example > data ScriptElem p where SE :: p a -> a -> ScriptElem p > type Script p = [ScriptElem p] > > infix 1 --> > (-->) = SE ] gameScript :: ScriptElem GameChoice -> GameChoice a -> Maybe a ] gameScript (SE (ChoosePiece _) piece) (ChoosePiece _) = Just piece ] gameScript (SE (ChooseAttack _ _) attack) (ChooseAttack _ _) = Just attack ] gameScript _ _ = Nothing ] ] testGame :: Script GameChoice ] testGame = ] [ ChoosePiece P1 --> Knight ] , ChooseAttack P1 Knight --> Charge ] , ChoosePiece P2 --> FootSoldier ] , ... ] ] So, how to implement all of this? > data Prompt (p :: * -> *) :: (* -> *) where > PromptDone :: result -> Prompt p result > -- a is the type needed to continue the computation > Prompt :: p a -> (a -> Prompt p result) -> Prompt p result This doesn't require GADT's; it's just using existential types, but I like the aesthetics better this way. Intuitively, a (Prompt p result) either gives you an immediate result (PromptDone), or gives you a prompt which you need to reply to in order to continue the computation. This type is a MonadPrompt: > instance Functor (Prompt p) where > fmap f (PromptDone r) = PromptDone (f r) > fmap f (Prompt p cont) = Prompt p (fmap f . cont) > > instance Monad (Prompt p) where > return = PromptDone > PromptDone r >>= f = f r > Prompt p cont >>= f = Prompt p ((>>= f) . cont) > > instance MonadPrompt p (Prompt p) where > prompt p = Prompt p return > > -- Just for fun, make it work with StateT as well > -- (needs -fallow-undecidable-instances) > instance (Monad (t m), MonadTrans t, MonadPrompt p m) => MonadPrompt p (t m) where > prompt = lift . prompt The last bit to tie it together is an observation function which allows you to run the game: > runPromptM :: Monad m => (forall a. p a -> m a) -> Prompt p r -> m r > runPromptM _ (PromptDone r) = return r > runPromptM f (Prompt pa c) = f pa >>= runPromptM f . c > > runPrompt :: (forall a. p a -> a) -> Prompt p r -> r > runPrompt f p = runIdentity $ runPromptM (Identity . f) p > > runScript :: (forall a. ScriptElem p -> p a -> Maybe a) > -> Script p -> Prompt p r -> Maybe r > runScript _ [] (PromptDone r) = Just r > runScript s (x:xs) (Prompt pa c) = case s x pa of > Nothing -> Nothing > Just a -> runScript s xs (c a) > runScript _ _ _ = Nothing > -- script & computation out of sync My original goal is now achievable: ] type Game = StateT GameState (Prompt GamePrompt) ] ] action :: GameChoice a -> Game a ] action p = do ] state <- get ] prompt $ GP (state, p) ] runGameScript :: Script GameChoice -> GameState -> Game a -> Maybe (GameState, a) ] runGameScript script initialState game ] = runScript scriptFn script' (runStateT game initialState) ] where ] script' = map sEmbed script ] scriptFn s (GP (s,p)) = gameScript (sExtract s) p ] sEmbed (SE p a) = SE (GP (undefined, p)) a ] sExtract (SE (GP (_,p)) a) = SE p a Any comments are welcome! Thanks for reading this far. -- ryan

8 22

isFunction
by john lask 04 Jan '08

04 Jan '08

Oleg provided the following code to test whether a is a function, this code will not type check in hugs, due to the overlapping instances in IsFunction (x->y) f IsFunction x f and the functional dependency | a-> b ERROR "isfunction.lhs":43 - Instances are not consistent with dependencies *** This instance : IsFunction a b *** Conflicts with : IsFunction (a -> b) c *** For class : IsFunction a b *** Under dependency : a -> b is there a way to acheive the same effect in hugs ? > data HTrue > data HFalse > > class IsFunction a b | a -> b > instance TypeCast f HTrue => IsFunction (x->y) f > instance TypeCast f HFalse => IsFunction x f > > -- literally lifted from the HList library > class TypeCast a b | a -> b, b->a where typeCast :: a -> b > class TypeCast' t a b | t a -> b, t b -> a where typeCast' :: t->a->b > class TypeCast'' t a b | t a -> b, t b -> a where typeCast'' :: t->a->b > instance TypeCast' () a b => TypeCast a b where typeCast x = typeCast' () x > instance TypeCast'' t a b => TypeCast' t a b where typeCast' = typeCast'' > instance TypeCast'' () a a where typeCast'' _ x = x _________________________________________________________________ New music from the Rogue Traders - listen now! http://ninemsn.com.au/share/redir/adTrack.asp?mode=click&clientID=832&refer…

1 0

Instance classes and error (also, related to Data.Binary.GET)
by bbrown 04 Jan '08

04 Jan '08

I am using the Data.Binary module and having some issues reading big endian files (actually, just reading the file). I can read the header but not the rest of the data which contains a set of row information. Also, go ahead and make fun my style of coding. Anyway, This is the my code and the error at the bottom. The issue stems from here, it says I didn't define an instance, but I did: instance Binary URLSet where put _ = do BinaryPut.putWord8 0 get = do remainingByteData <- BinaryGet.getRemainingLazyByteString i :: URLInfo <- decode remainingByteData j :: TitleInfo <- decode remainingByteData k :: DescrInfo <- decode remainingByteData x :: KeywordsInfo <- decode remainingByteData return (URLSet {urlinfo=i, titleinfo=j, descrinfo=k, keywordsinfo=x}) ----- module Main where import Data.Word import Data.Binary import qualified Data.ByteString.Lazy.Char8 as BSLC8 import Data.ByteString.Lazy (ByteString) import Data.Binary.Get as BinaryGet import Data.Binary.Put as BinaryPut import IO import Text.Printf import System.Environment import Control.Monad (replicateM, liftM) {- ********************************************************* Define the Database Data Types SpiderDatabase represents a singleton wrapper for an entire database. ********************************************************* -} data SpiderDatabase = SpiderDatabase { magicNumberA :: Word16, magicNumberB :: Word16, majorVers :: Word16, minorVers :: Word16, headerTag :: Word16, poolLen :: Word16, spiderpool :: [URLSet] } data URLSet = URLSet { urlinfo :: URLInfo, titleinfo :: TitleInfo, descrinfo :: DescrInfo, keywordsinfo :: KeywordsInfo } data URLInfo = URLInfo { tag :: Word8, urlid :: Word16, urllen :: Word16, url :: ByteString } data TitleInfo = TitleInfo { titletag :: Word8, titlelen :: Word16, title :: ByteString } data DescrInfo = DescrInfo { descrtag :: Word8, descrlen :: Word16, descr :: ByteString } data KeywordsInfo = KeywordsInfo { keywordstag :: Word8, keywordslen :: Word16, keywords :: ByteString } {- ********************************************************* Class instances ********************************************************* -} instance Show SpiderDatabase where show db = let magicb = (magicNumberB db) header = (headerTag db) poolct = (poolLen db) in "<<<Database Content>>>\n" ++ (((printf "Magic: %X %X\n") (magicNumberA db)) (magicNumberB db)) ++ printf "URL Pool Count: %d\n" poolct ++ "<<<End>>>" instance Binary URLInfo where put _ = do BinaryPut.putWord8 0 get = do urltag <- getWord8 idx <- getWord16be len <- getWord16be strdata <- BinaryGet.getLazyByteString (fromIntegral len) return (URLInfo {tag=urltag, urlid=idx, urllen=len, url=strdata}) instance Binary DescrInfo where put _ = do BinaryPut.putWord8 0 get = do tag <- getWord8 len <- getWord16be strdata <- BinaryGet.getLazyByteString (fromIntegral len) return (DescrInfo {descrtag=tag, descrlen=len, descr=strdata}) instance Binary TitleInfo where put _ = do BinaryPut.putWord8 0 get = do tag <- getWord8 len <- getWord16be strdata <- BinaryGet.getLazyByteString (fromIntegral len) return (TitleInfo {titletag=tag, titlelen=len, title=strdata}) instance Binary KeywordsInfo where put _ = do BinaryPut.putWord8 0 get = do tag <- getWord8 len <- getWord16be strdata <- BinaryGet.getLazyByteString (fromIntegral len) return (KeywordsInfo {keywordstag=tag, keywordslen=len, keywords=strdata}) instance Binary URLSet where put _ = do BinaryPut.putWord8 0 get = do remainingByteData <- BinaryGet.getRemainingLazyByteString i :: URLInfo <- decode remainingByteData j :: TitleInfo <- decode remainingByteData k :: DescrInfo <- decode remainingByteData x :: KeywordsInfo <- decode remainingByteData return (URLSet {urlinfo=i, titleinfo=j, descrinfo=k, keywordsinfo=x}) instance Binary SpiderDatabase where put _ = do BinaryPut.putWord8 0 get = do magicnumbera <- BinaryGet.getWord16be magicnumberb <- BinaryGet.getWord16be major <- BinaryGet.getWord16be minor <- BinaryGet.getWord16be header <- BinaryGet.getWord16be poolct <- BinaryGet.getWord16be -- ******************************* -- Get the remaining byte string data, -- So that we can use lazy bytestring to load to load the -- the data types. -- ******************************* remainingByteData <- BinaryGet.getRemainingLazyByteString -- pool <- (replicate (fromIntegral poolct) (decode remainingByteData)) z :: URLSet <- decode remainingByteData return (SpiderDatabase {magicNumberA=magicnumbera, magicNumberB=magicnumberb, majorVers=major, minorVers=minor, headerTag=header, poolLen=poolct }) main = do putStrLn "Running Spider Database Reader" args <- getArgs db :: SpiderDatabase <- decodeFile (args !! 0) putStrLn $ show db putStrLn "Done" *** *** Error: DbReader.hs:119:22: No instance for (Binary (Get URLInfo)) arising from a use of `decode' at DbReader.hs:119:22-45 Possible fix: add an instance declaration for (Binary (Get URLInfo)) In a 'do' expression: i :: URLInfo <- decode remainingByteData In the expression: do remainingByteData <- getRemainingLazyByteString i :: URLInfo <- decode remainingByteData j :: TitleInfo <- decode remainingByteData k :: DescrInfo <- decode remainingByteData .... In the definition of `get': get = do remainingByteData <- getRemainingLazyByteString i :: URLInfo <- decode remainingByteData j :: TitleInfo <- decode remainingByteData .... DbReader.hs:120:24: No instance for (Binary (Get TitleInfo)) arising from a use of `decode' at DbReader.hs:120:24-47 Possible fix: add an instance declaration for (Binary (Get TitleInfo)) In a 'do' expression: j :: TitleInfo <- decode remainingByteData In the expression: do remainingByteData <- getRemainingLazyByteString i :: URLInfo <- decode remainingByteData j :: TitleInfo <- decode remainingByteData k :: DescrInfo <- decode remainingByteData .... In the definition of `get': get = do remainingByteData <- getRemainingLazyByteString i :: URLInfo <- decode remainingByteData j :: TitleInfo <- decode remainingByteData .... DbReader.hs:121:24: No instance for (Binary (Get DescrInfo)) arising from a use of `decode' at DbReader.hs:121:24-47 Possible fix: add an instance declaration for (Binary (Get DescrInfo)) In a 'do' expression: k :: DescrInfo <- decode remainingByteData In the expression: do remainingByteData <- getRemainingLazyByteString i :: URLInfo <- decode remainingByteData j :: TitleInfo <- decode remainingByteData k :: DescrInfo <- decode remainingByteData .... In the definition of `get': get = do remainingByteData <- getRemainingLazyByteString i :: URLInfo <- decode remainingByteData j :: TitleInfo <- decode remainingByteData .... DbReader.hs:122:27: No instance for (Binary (Get KeywordsInfo)) arising from a use of `decode' at DbReader.hs:122:27-50 Possible fix: add an instance declaration for (Binary (Get KeywordsInfo)) In a 'do' expression: x :: KeywordsInfo <- decode remainingByteData In the expression: do remainingByteData <- getRemainingLazyByteString i :: URLInfo <- decode remainingByteData j :: TitleInfo <- decode remainingByteData k :: DescrInfo <- decode remainingByteData .... In the definition of `get': get = do remainingByteData <- getRemainingLazyByteString i :: URLInfo <- decode remainingByteData j :: TitleInfo <- decode remainingByteData .... DbReader.hs:142:21: No instance for (Binary (Get URLSet)) arising from a use of `decode' at DbReader.hs:142:21-44 Possible fix: add an instance declaration for (Binary (Get URLSet)) In a 'do' expression: z :: URLSet <- decode remainingByteData In the expression: do magicnumbera <- getWord16be magicnumberb <- getWord16be major <- getWord16be minor <- getWord16be .... In the definition of `get': get = do magicnumbera <- getWord16be magicnumberb <- getWord16be major <- getWord16be .... make: *** [dbreader] Error 1 -- Berlin Brown [berlin dot brown at gmail dot com] http://botspiritcompany.com/botlist/?

4 3

Consensus about databases / serialization
by Peter Verswyvelen 04 Jan '08

04 Jan '08

As I'm a selfmade man, I never really studied relational databases in detail. My intuition told me that the "relational" part was not really suitable for the 3D data, 2D images, animation curves, state machines, and other data I encountered in the videogame and animation business. I could always get away with files, and for the applications I needed to deploy, plugging in a couple of extra gigabytes of RAM and serializing the "object" state to disk was more practical, cheaper and faster. However, a couple of years ago I started studying computer science (I seem to do the theory after the practice, weird behavior ;-) at the Open University, and one of the exams I did was about databases. Initially this course convinced me that databases are actually very nice, but the course ended with a topic on object oriented databases, which were designed to make storing data like "3D models, graphs, networks, and complex datastructures" more practical. Duh. Since then, I did deploy a few commercial applications for customers using databases, which worked fine for the typical "simple/flat" database data. I hated embedding a dynamic untyped language like SQL, as much as I hated embedding code in HTML or XML. IMHO it feels UGLY and unsafe. Regarding the other popular data storage format - XML - I did use that a lot, but it seems like going back to the stone ages, when hierarchical stores/databases got invented (and ditched?) Now, initially after an introduction to Microsoft's LINQ, and recently having read a very brief overview of HAppS, it seems I'm not the only one with those "feelings". Ouch, this introduction got way to long, sorry about that ;-) Finally some practical questions: . regarding Haskell and databases, the page http://haskell.org/haskellwiki/Libraries_and_tools/Database_interfaces describes a few, but which are the ones that are stable and practical? Any user experiences? . HApps is not listed in the page above, because it does not use databases? Is HApps reliable or experimental, and does it scale well? Any success stories? . regarding Haskell and serialization, I don't think that implementing Read/Show is a good way for real serialization, so what other options exist? I could find some libraries at http://hackage.haskell.org/packages/archive/pkg-list.html#cat:Data, but again which are the most practical and stable? When programming in C++/MFC and C#/.NET, I tended to develop my own serialization frameworks because I used that for many things, like logging commands to disk, performing undo/redo, intra and inter process cut/copy/paste, save/load, etc. . Regarding serialization, I'm kinda curious how ADTs and even GADTs are stored and retrieved in a relational database? I guess it could be done using BLOBs and serialization to ByteStrings, so bypassing a lot of the database table structures? . If I would want to experiment with say HAppS, the way I understand it, I first would first have to study "Scratch your boilerplate" and Template Haskell, and maybe some other language features? I'm still new to Haskell, and the road to understanding all language elements and extensions is very long, so sequentially learning it would be insane I guess. I have no practical experience with TH, but I spent a long time trying to do "aspect oriented programming" in C# without success, so TH looks uber to me. Thanks a lot and best wishes for 2008? Peter

9 14

Supporting both cabals?
by Magnus Therning 03 Jan '08

03 Jan '08

GHC 6.8 has just made it into Debian in a usable form. (w00t!) Due to the library split my old cabal files don't work any longer. updating them isn't the problem, the problem is keeping them compatible with both versions of Cabal. I searched the wiki (quickly) but didn't find anything on this topic. Is there a cookbook out there for it? /M -- Magnus Therning (OpenPGP: 0xAB4DFBA4) magnus＠therning．org Jabber: magnus．therning＠gmail．com http://therning.org/magnus What if I don't want to obey the laws? Do they throw me in jail with the other bad monads? -- Daveman

3 2

Importing Data.Char speeds up ghc around 70%
by Joost Behrends 03 Jan '08

03 Jan '08

Hi, while still working on optimizing (naively programmed) primefactors i watched a very strange behavior of ghc. The last version below takes 2.34 minutes on my system for computing 2^61+1 = 3*768614,336404,564651. Importing Data.Char without anywhere using it reduces this time to 1.34 minute - a remarkable speed up. System is WindowsXP on 2.2GHZ Intel, 512MB Ram. I give the complete code here - hopefully all tabs are (4) blanks. Can this be reproduced ? I compile just with --make -O2. module Main where import IO import System.Exit import Data.Char main = do hSetBuffering stdin LineBuffering putStrLn "Number to decompose ?" s <- getLine if s == [] then exitWith ExitSuccess else do putStrLn (show$primefactors$read s) main data DivIter = DivIter {dividend :: Integer, divisor :: Integer, bound :: Integer, result :: [Integer]} intsqrt m = floor (sqrt $ fromInteger m) primefactors :: Integer -> [Integer] primefactors n | n<2 = [] | even n = o2 ++ (primefactors o1) | otherwise = if z/=1 then result res ++[z] else result res where res = divisions (DivIter {dividend = o1, divisor = 3, bound = intsqrt(o1), result = o2}) z = dividend res -- is 1 sometimes (o1,o2) = twosect (n,[]) twosect :: (Integer,[Integer]) -> (Integer,[Integer]) twosect m |odd (fst m) = m |even (fst m) = twosect (div (fst m) 2, snd m ++ [2]) found :: DivIter -> DivIter found x = x {dividend = xidiv, bound = intsqrt(xidiv), result = result x ++ [divisor x]} where xidiv = (dividend x) `div` (divisor x) d2 :: DivIter -> DivIter d2 x |dividend x `mod` divisor x > 0 = x { divisor = divisor x + 2} |otherwise = found x d4 :: DivIter -> DivIter d4 x |dividend x `mod` divisor x > 0 = x { divisor = divisor x + 4} |otherwise = found x d6 :: DivIter -> DivIter d6 x |dividend x `mod` divisor x > 0 = x { divisor = divisor x + 6} |otherwise = found x divisions :: DivIter -> DivIter divisions y |or[divisor y == 3, divisor y == 5] = divisions (d2 y) |divisor y <= bound y = divisions (d6$d2$d6$d4$d2$d4$d2$d4 y) |otherwise = y

7 20

Escape Codes
by H. Mayer 03 Jan '08

03 Jan '08

Hello, Some days ago I needed escape codes on Win32. I didn't find any library for that, so I wrote a simple one. I thought, perhaps someone else will have the same problem, so I put it on my website:http://0hc.net/?what=downloads_sup_AWin32Console I've tested it with the ghc 6.6.1, and everything works as I expected it. I would be happy if someone else could test it and/or report if some important escape codes are missing. --Sincerely H. _________________________________________________________________ Erweitere dein digitales Leben. Hol dir jetzt gratis das neue Windows Live. http://get.live.com

3 2

Basic question concerning data constructors
by Joost Behrends 03 Jan '08

03 Jan '08

Hello, perhaps i will make a wishlist of topics not dealt in the tutorials. Here is something i miss in each of them: notes at the semantics of data constructors. We read data Pair a b = Pair a b in YetAnotherHaskellTutorial. And that is all ! If we omit "data" here, this would be a silly pleonasm. And no single word about this strange behavior of "data" in every tutorial i read. A similar point: The tutorials teach, that "=" has a similar meaning than "=" in mathematics. But there is a big difference: it is not reflexive. The the right side is the definition of the left. Thus "x=y" has still some kind of temporality, which mathematics doesn't have. Wadler himself describes bunches of lazily computed equations as "dataflows" somewhere. Ok, so much on theory. Here a concrete question: For adapting hws (one of the reasons for me to be here, not many languages have a native web server) to Windows i must work on time. In System.Time i found data ClockTime = TOD Integer Integer 2 questions arise here: Does this define "TOD" (which i do not find elsewhere) together with ClockTime also ? And: Why is this not: data ClockTime Integer Integer = TOD Integer Integer ? Is it just an abbreviation for the first? Or is there a connection to ClockTime as an "abstract data type" (a notion, which would have a subtle different meaning than in OOP - since "instance" is such different thing here). Thanks for your attention, Joost

16 31

regex package for yhc?
by Thomas Hartman 03 Jan '08

03 Jan '08

Is there some way to use any of the various regex packages on hackage via yhc? Has anyone installed one them successfully? I'd like regex-tdfa, but would settle for regex-posix, or really, anything that brings the convenience of regex to yhc. In general, is there a straightforward way to install "extralibs" type packages for universal "import" availability in yhc? Is there a cabal equivalent for yhc? Documentation pointer would be appreciated; I searched but couldn't find anything. Maybe not using the right keywords... t. --- This e-mail may contain confidential and/or privileged information. If you are not the intended recipient (or have received this e-mail in error) please notify the sender immediately and destroy this e-mail. Any unauthorized copying, disclosure or distribution of the material in this e-mail is strictly forbidden.

5 6

[16/16] SBM: Discussion and Conclusion
by Peter Firefly Brodersen Lund 03 Jan '08

03 Jan '08

General ------- Bytestrings are faster than haskell strings. This is good and expected. But their memory use, ouch! There seems to be a grave memory bug in 6.9. Lazy bytestrings are slower than strict bytestrings -- this was completely unexpected for me. The strictness analyzer works *very* well. It rarely made a difference to mark arguments as strict (and when it did, it was very easy to use). I/O --- The I/O patterns seen in the various programs are: 1) strict bytestrings = read increasingly large chunks (they double every time). I don't know if the already-read data have to be copied around or if the memory allocator can handle extending existing blocks (if they are at the "front" of the heap, say) like realloc() can. Even if the blocks do get copied around, that's not where the performance limiter is (speed-wise). It does seem to be a bit unwise in terms of memory pressure. Does the gc kick in every time the heap has to expand? Does it do a full collection then? If no other allocations have happened since the last collection than the allocation that caused the heap to expand, then perhaps skip the collection? (or some criteria similar to that) 2) lazy bytestrings = read blocks of 32K-8 bytes, as expected. The C benchmarks show that there's no penalty for reading 32K-8 vs. 32K. 3) native strings = read blocks 8K. The C benchmarks show that it barely matters if the block size is 4K, 32K, or 32K-8 bytes. In any case, the small differences due to block size are completely in the noise. Reading very large blocks, though, as the strict bytestrings do, actually has a cost (38-70% slower, depending on the CPU and kernel and RAM and busspeeds, etc -- see email 10 in the series). It is still peanets compared for almost all the benchmarks. Backend ------- The backend turns out to be rather bad. It is generally very easy to improve the generated code by hand without doing anything in terms of sophisticated analysis. One can rewrite inner loops using heroic code (load four characters at a time together into a 32-bit register or even use MMX to handle eight characters in parallel) but it isn't really necessary to do that to gain a good improvement and start being competitive with C. The backend is probably what is costly on some of the lazy bytestring and native string code because there are too many tests to see if the buffer has been exhausted (I think). Some simple hoisting and common subexpression elimination would go far here. For the simpler strict bytestring benchmarks, heroic backend optimizations are not necessary because they give less of an improvement over merely competent register use than sensible I/O and buffer management (cache effects start to be important once the compiler generates sensible code). I would have liked to examine backend performance further by playing with the generated C-- code but unfortunately, the C-- that ghc emits won't compile. Dissecting the generated machine code for the more complicated benchmarks was so hard that I skipped it -- I can't even recognize the labels! It's one thing if the backend generates lots of extra labels but another if the expected labels simply are not there! (this is why tools/cut.pl complains that it can't find the main loop for some of the programs -- if the */*.discut file is unexpectedly short, then that's the reason.) Quality of measurements ----------------------- The speed measurements are of extremely high quality, much more than it turns out is needed at this moment. I probably spent a bit too much effort there. The memory measurements are unusual. I don't recall having seen anything like them elsewhere because one seldom has to work with uncooperative programs when benchmarking (the preloading trick works with any program, as long as it is dynamically linked on Linux and uses the standard loader). They are probably the biggest single contribution from this work, together with the visualization provided by the bar charts. Thoroughness ------------ It really is necessary to benchmark more than one ghc/library combination, otherwise the bad memory bugs wouldn't stand out so clearly or I would have believed, as Don Stewart did, that he had fixed the memory allocation bug. It also matters what microarchitectures one use, as pointed out by email 10 in this series. And you gotta have many benchmarks, otherwise you might not really be measuring what you think you measure. I could probably have gotten away with fewer benchmarks in this case but that would have left a nagging feeling at the back of my head that there was a benchmark I /could/ have included that would have showed up a spectacular performance bug. Using so big input files (150MB) made the programs run slow enough that the timer granularity (1ms) was small compared to their runtime. It also made the memory performance problems really stand out (and be unignorable). I think that was a good idea. Having automatic feedback on the timing measurement quality helped a lot during the development of the testing harness because it made it easier and faster for me to eliminate the causes of imprecision. That's why I wrote the eatmem tool and that's why the test harness does a dd of the input file and the compiled program before running the tests. It should probably also dd the C library (and the few other libraries linked in: math, GNU multiprecision, and TLS stuff) but the quality estimators show that any improvement would be very small. Using top together with huge input files convinced me that -sstderr was untrustworthy so I developed the pause-at-end preloading hack. Paranoia paid off big time there. Visual presentation ------------------- The bar charts (with UTF-8) turned out to be so much more readably than raw numbers. This is a trick I learned from the Cairo team, which created a performance suite very early on. The bar is drawn with '%' if the measurement is bad. That turned out to be a much clearer visual indicator than my previous '*' and '!' flag characters. Really, there's no good reason not to use UTF-8 these days. I also discovered that the program names used for the benchmarks really matter. I had started out with names like 'cntspaces12' and 'cntbytes34' and kept getting confused about what program measured what. If the names are good, you don't need to put a description of each benchmark on the report. The order the benchmarks are presented in also matters. It is important that they are grouped and it is also important that the order is as stable as possible, even when not all runs contain exactly the same benchmarks. Separation of the time and memory bar charts + the separation of byte and space counting benchmarks also turned out to be useful. I had neither at first. And finally, merging of reports. I had no idea it would be so useful before I wrote the scripts for it. This is what makes the memory bugs in 6.9 really stand out and this is what shows the improvements of bytestring 0.9.0.2 (in particular with ghc 6.8.2). It also shows how wildly the performance of four different microarchitectures can differ. Scripting --------- Scripting everything is key to the success of an effort like this. I am VERY happy that scripted not just the running of the benchmarks but also the report handling and even the installation of the ghc/bytestring combinations. (I also scripted the sending of these 17 emails -- let's see if the script works :) ) The predictions elicited by my teaser email ------------------------------------------- As expected, predicting the performance of haskell programs is really hard, even modulo performance bugs. And, no, strings are not "silly". Action Items ------------ Suggested short-term actions: o Can the allocator expand blocks? If not, see if it can be implemented. o Find out why lazy bytestrings "by hand" are that slow - is it due to lack of hoisting in the backend? o Improve backend, mainly by not hiding information from register allocator. Alternatively, by using an assembly-to-assembly transformator that improves the register allocation. o Fix -sstderr. o perhaps even let the RTS print out /proc/self/maps or /proc/self/status or "peak RSS" returned by getrusage() in the ru_maxrss field? o Find memory leaks in ghc 6.9 code. o ghc should allow round-tripping of the C-- code it generates. o would be awfully nice if the backend didn't sometimes throw the recognizable labels away. o can the core/stg code be made easier to read? -Peter

3 3