January 2008 - Haskell-Cafe

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

ANN: Dimensional 0.7.2
by Bjorn Buckwalter 03 Jan '08

03 Jan '08

Dear all, I've released version 0.7.2 of the Dimensional library. The only change from version 0.7.1 is that the CGS module has been re-enabled. Unless you use the CGS module there is no need to upgrade from 0.7.1. Note that this version is incompatible with GHC 6.8.1 due to bug #1919 (introduced in GHC 6.8.1 and fixed in 6.8.2). For GHC 6.8.1 use version Dimensional 0.7.1 which lacks the CGS module. Thanks, Bjorn Buckwalter http://dimensional.googlecode.com http://hackage.haskell.org/cgi-bin/hackage-scripts/package/dimensional On Nov 23, 2007 8:32 AM, Bjorn Buckwalter <bjorn.buckwalter(a)gmail.com> wrote: > Dear all, > > The Dimensional library has been ported to GHC 6.8.1 (it remains > backwards-compatible with GHC 6.6.1, and also with Cabal 1.1.6 I > believe). The new version number is 0.7.1. > > Due to a GHC 6.8.1 bug (#1919) the CGS module will not compile and has > been disabled. > > Thanks, > Bjorn Buckwalter > > http://dimensional.googlecode.com > http://hackage.haskell.org/cgi-bin/hackage-scripts/package/dimensional > http://hackage.haskell.org/trac/ghc/ticket/1919 >

1 0

FW: [Haskell-cafe] Is there anyone out there who can translate C# generics into Haskell?
by Peter Verswyvelen 02 Jan '08

02 Jan '08

I'm also new to Haskell, but I'm a C++/C# veteran, so I'll give it a shot. C#'s interfaces look a bit like Haskell's type classes. Although not exactly the same, you could try something like this: -- C#: interface IX1 { String foo1(int); } class IX1 obj where foo1 :: Int -> obj -> String -- C#: interface IX2<A> { String foo2(A); } class IX2 obj a where foo2 :: a -> obj -> String --C#: interface IX3<A> where A : IY { String foo3(A); } class IY a where {- ... -} class IY a => IX3 obj a where foo3 :: a -> obj -> String --C#: interface IX4<A> : IZ where A : IY class IZ a where {- ... -} class (IY a, IZ obj) => IX4 obj a where foo4 :: a -> obj -> String The C# "class" is called an "instance" in Haskell, so to implement an interface, you would do e.g. data X2 = X2 { x2Bla :: String, ... } instance IX2 X2 String where foo2 s o = (x2Bla o) ++ s This assumes your "objects" are immutable, otherwise you would have to return (obj,String) instead of just String and then you most likely want to use the state monad and "do notation" to make functional programming look more like imperative programming. You really have to drop the OO way of thinking, which I find the hardest :) Haskell's type classes are more powerful in some sense than C# interfaces; for example, in C# you can't attach an interface to any class (take for example the Point struct), it has to be your own class, while in Haskell, you can implement an instance of a type class for any datatype! Hope this helps a bit. As I'm new myself to Haskell, so take this with a "grain of salt". Once you bite the bullet, I found Haskell a lot more fun than C#, although C# of course comes with a gigantic .NET framework and tools... Peter -----Original Message----- From: haskell-cafe-bounces(a)haskell.org [mailto:haskell-cafe-bounces@haskell.org] On Behalf Of Nicholls, Mark Sent: Wednesday, January 02, 2008 5:41 PM To: haskell-cafe(a)haskell.org Subject: [Haskell-cafe] Is there anyone out there who can translate C# generics into Haskell? I'm trying to translate some standard C# constucts into Haskell... some of this seems easy.... Specifically 1) Interface IX { } 2) Interface IX<A> { } 3) Interface IX<A> Where A : IY { } 4) Interface IX<A> : IZ Where A : IY { } I can take a punt at the first 2....but then it all falls apart _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

1 0

I am looking for the source code for STM implementation ...
by Galchin Vasili 02 Jan '08

02 Jan '08

Hello, I found STM.c(lower layer), but cannot find the top layer code written Haskell.?? Vasya

2 1

Newbie question: can laziness lead to space compression?
by Brian Hurt 02 Jan '08

02 Jan '08

My apologies if this has been beat to death before, I'm still new to Haskell. But I was wondering if it is possible that lazy evaluation could lead to space compression, especially under heavily persistant usage patterns? Here's the argument I'm making. Say we have a tree-based Set with, say, 1024 values in it. For ease of math we'll assume that it's perfectly balanced. Say each node in the tree takes 5 words of memory. So in an eager language (for example, Ocaml), adding a new node to this tree requires the allocation of 10 new nodes, or 50 words of memory. In Haskell, what would happen (as I understand it) is that just a new lazy thunk would be allocated- say, 10 words of memory. Conceptually, we could think of the returned value as the original tree plus a small delta. The lazy implementation is using 40 fewer words of memory than the eager implementation. Note that the benefit isn't *big*- we're talking about 40 words of memory when the main data structure is taking up 5K plus words of memory- so it's less than 1% different. But there is a (small) upside in memory usage at least occassionally, right? Brian

3 2

[RFC] benchmarks of bytestrings, teaser
by Peter Lund 02 Jan '08

02 Jan '08

What do you think the relative speeds are of the six small haskell programs at the end of this email? All they do is read from stdin and count the number of spaces they see. There are two that use strict bytestrings, two that use lazy bytestrings, and two that use the standard Haskell strings. Three use a recursive function with an accumulator parameter and three use a foldl with a lambda function. Say the fastest one takes the time 1. How much time will the others take? And how about memory? How much memory do you think they require? Let's say we feed a 150MB(*) file into each of them, how many megabytes do you think they end up using (as seen from the OS, not in terms of how big the live heap is)? I'm going to post full benchmarks + analysis on Wednesday. -Peter *) hardddisk megabytes. The file is 150000034 bytes ≈ 143 mebibytes. PS: For extra credit, what do you think is the peak memory use for this program when given an input file of 150MB? {-# LANGUAGE BangPatterns #-} import qualified Data.ByteString.Lazy.Char8 as B import GHC.Int (Int64) -- note that D.BS.Lazy.Char8.length is ByteString -> Int64 -- D.BS.C8.length is ByteString -> Int cnt :: B.ByteString -> Int64 cnt bs = B.length (B.filter (== ' ') bs) main = do s <- B.getContents print (cnt s) ============================== hs/space-bs-c8-acc-1.hs: {-# LANGUAGE BangPatterns #-} import qualified Data.ByteString.Char8 as B cnt :: Int -> B.ByteString -> Int cnt !acc bs = if B.null bs then acc else cnt (if B.head bs == ' ' then acc+1 else acc) (B.tail bs) main = do s <- B.getContents print (cnt 0 s) ============================== hs/space-bslc8-acc-1.hs: {-# LANGUAGE BangPatterns #-} import qualified Data.ByteString.Lazy.Char8 as B cnt :: Int -> B.ByteString -> Int cnt !acc bs = if B.null bs then acc else cnt (if B.head bs == ' ' then acc+1 else acc) (B.tail bs) main = do s <- B.getContents print (cnt 0 s) ============================== hs/space-xxxxx-acc-1.hs: {-# LANGUAGE BangPatterns #-} cnt :: Int -> String -> Int cnt !acc bs = if null bs then acc else cnt (if head bs == ' ' then acc+1 else acc) (tail bs) main = do s <- getContents print (cnt 0 s) ============================== hs/space-bs-c8-foldlx-1.hs: {-# LANGUAGE BangPatterns #-} import qualified Data.ByteString.Char8 as B cnt :: B.ByteString -> Int cnt bs = B.foldl' (\sum c -> if c == ' ' then sum+1 else sum) 0 bs main = do s <- B.getContents print (cnt s) ============================== hs/space-bslc8-foldlx-1.hs: {-# LANGUAGE BangPatterns #-} import qualified Data.ByteString.Lazy.Char8 as B cnt :: B.ByteString -> Int cnt bs = B.foldl' (\sum c -> if c == ' ' then sum+1 else sum) 0 bs main = do s <- B.getContents print (cnt s) ============================== hs/space-xxxxx-foldl.hs: {-# LANGUAGE BangPatterns #-} cnt :: String -> Int cnt bs = foldl (\sum c -> if c == ' ' then sum+1 else sum) 0 bs main = do s <- getContents print (cnt s) ==============================

15 33

Problem building hdbc-sqlite3 with ghc 6.8.2
by manu 02 Jan '08

02 Jan '08

hello, has anybody managed to build hdbc-sqlite3 with ghc 6.8.2 ? I get the following error : Macintosh:HDBC-sqlite3-1.1.3.0 manu$ runhaskell Setup.lhs build Preprocessing library HDBC-sqlite3-1.1.3.0... ghc-6.8.2: unrecognised flags: -F/Users/manu/Library/Frameworks Usage: For basic information, try the `--help' option. compiling dist/build/Database/HDBC/Sqlite3/Statement_hsc_make.c failed command was: /usr/local/bin/ghc -c -package base-3.0.1.0 -package mtl-1.1.0.0 -package HDBC-1.1.3 -I. -F/Users/manu/Library/Frameworks dist/build/Database/HDBC/Sqlite3/Statement_hsc_make.c -o dist/build/ Database/HDBC/Sqlite3/Statement_hsc_make.o if somebody has an idea... Thanks E.D

2 1

Knowledge
by jlw501 02 Jan '08

02 Jan '08

I'm new to functional programming and Haskell and I love its expressive ability! I've been trying to formalize the following function for time. Given people and a piece of information, can all people know the same thing? Anyway, this is just a bit of fun... but can anyone help me reduce it or talk about strictness and junk as I'd like to make a blog on it? contains :: Eq a => [a]->a->Bool contains [] e = False contains (x:xs) e = if x==e then True else contains xs e perfectcomm :: Bool perfectcomm = undefined knowself :: Bool knowself = undefined allKnow :: Eq a => [a]->String->Bool allKnow _ "" = True allKnow [] k = False allKnow (x:[]) k = knowself allKnow (x:xs) k = comm x xs k && allKnow xs k where comm p [] k = False comm p ps k = if contains ps p then knowself else perfectcomm -- View this message in context: http://www.nabble.com/Knowledge-tp14423007p14423007.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

4 6

Missing join and split
by Mitar 02 Jan '08

02 Jan '08

Hi! I am really missing the (general) split function built in standard Haskell. I do not understand why there is something so specific as words and lines but not a simple split? The same goes for join. Yes, I can of course define them but ... in an interactive mode it would be quite handy to have them there. Or am I wrong and are those hidden somewhere? So what are common ways to get around this? What are elegant definitions? Inline definitions? Mitar

13 19