Greg Buchholz wrote:

True. But there are some tests like "fasta" that appear to have a laziness induced space leak that presumably could be fixed.

http://shootout.alioth.debian.org/benchmark.php?test=fasta&lang=all

Playing with the space-leaking code did not show any obvious reason to expect the space leak. By commenting out the third output in main it did not leak space. Could some look at the original code at the link above and let me know why there is a 300 MB space leak? But if you never express huge lists, then it won't leak space. Here is a tweaked version, called tweak6.hs, that interleaves making and writing a line of output. It runs in 2.16 MB of RSIZE instead of over 300 MB. Still slow, however. If you want more speed without extra libraries, then use an unboxed array of Word8 (length of one line: 60 bytes), since Unicode Char and linked lists are overkill. The other killer is probably the array of tuple linear lookup to find the chosen symbol. Hand coded if/then branches could be used to speed that up. For even faster speed, do not use 0.0 to 1.0 probabilities at all. Instead of normalize :: Int -> Double and then lookup (Double -> Base) remove the use of Double and do (Int -> Base) lookup. But the space leak was the embarrassing part. So I just fixed that. -- Chris Kuklewicz --------------- -- The Great Computer Language Shootout -- http://shootout.alioth.debian.org/ -- contributed by Jeff Newbern -- Modified to tweak6.hs by Chris Kuklewicz import Control.Monad.Trans import Control.Monad.State import System.IO (hFlush,stdout) {- original $ time ./fasta.ghc_run 2500000 > /dev/null real 1m17.596s user 0m44.838s sys 0m3.322s 330+ Megs! Space leaking all over the place. No idea why. $ time ./fasta.tweak6 2500000 > /dev/null real 0m30.477s user 0m23.356s sys 0m0.744s 2.2 Megs RSIZE -} -- Uses random generation code derived from Simon Marlow and Einar Karttunen's -- "random" test entry. -- Orignal version note: This code has not been optimized *at all*. -- It is written to be clear and to follow standard Haskell idioms as -- much as possible (but we have to match the stateful PRNG idiom in -- the test definition, which is oriented toward an imperative -- language). Performance is decent with ghc -O2, but if it can be -- improved without sacrificing the clarity of the code, by all means -- go for it! -- Mondified tweak6.hs version note: Use a StateT around IO to manage -- the seed. This makes interleaving the generation and output of the -- sequence easier. It is only *minimally* abstracted. import System(getArgs) type Base = Char type Sequence = [Base] alu :: Sequence -- predefined sequence alu = "GGCCGGGCGCGGTGGCTCACGCCTGTAATCCCAGCACTTTGG" ++ "GAGGCCGAGGCGGGCGGATCACCTGAGGTCAGGAGTTCGAGA" ++ "CCAGCCTGGCCAACATGGTGAAACCCCGTCTCTACTAAAAAT" ++ "ACAAAAATTAGCCGGGCGTGGTGGCGCGCGCCTGTAATCCCA" ++ "GCTACTCGGGAGGCTGAGGCAGGAGAATCGCTTGAACCCGGG" ++ "AGGCGGAGGTTGCAGTGAGCCGAGATCGCGCCACTGCACTCC" ++ "AGCCTGGGCGACAGAGCGAGACTCCGTCTCAAAAA" type BaseFrequency = (Base,Double) iub :: [BaseFrequency] iub = [ ('a', 0.27), ('c', 0.12), ('g', 0.12), ('t', 0.27), ('B', 0.02), ('D', 0.02), ('H', 0.02), ('K', 0.02), ('M', 0.02), ('N', 0.02), ('R', 0.02), ('S', 0.02), ('V', 0.02), ('W', 0.02), ('Y', 0.02) ] homosapiens :: [BaseFrequency] homosapiens = [ ('a', 0.3029549426680), ('c', 0.1979883004921), ('g', 0.1975473066391), ('t', 0.3015094502008) ] -- select a base whose interval covers the given double chooseBase :: [BaseFrequency] -> Double -> Base chooseBase [(b,_)] _ = b chooseBase ((b,f):xs) p | p < f = b | otherwise = chooseBase xs (p-f) type Seed = Int type Pseudo a = StateT Seed IO a prng :: Pseudo Double prng = let nextSeed s = (s * ia + ic) `mod` im normalize n = (fromIntegral n) * (1.0 / fromIntegral im) im = 139968; ia = 3877; ic = 29573 in do seed <- get let seed' = nextSeed seed put seed' return (normalize seed') prngN count = sequence $ replicate count prng -- write a sequence in Fasta format writeFasta :: String -> String -> Sequence -> IO () writeFasta label title sequence = do putStrLn $ ">" ++ (label ++ (" " ++ title)) writeWrapped 60 sequence where writeWrapped _ [] = do return () writeWrapped len str = do let (s1,s2) = splitAt len str putStrLn s1 writeWrapped len s2 writeFastaHeader :: (MonadIO m) => String -> String -> m () writeFastaHeader label title = liftIO $ putStrLn $ ">" ++ (label ++ (" " ++ title)) writeWrapped' :: Int -> Int -> (Double->Base) -> Pseudo () writeWrapped' wrap total trans = let work c = case c of 0 -> return () n -> do let c' = min wrap n nextC = c - c' s <- liftM (map trans) (prngN c') liftIO $ putStrLn s work nextC in work total writeWrapped = writeWrapped' 60 main = do args <- getArgs let n = if (null args) then 1000 else read (head args) writeFasta "ONE" "Homo sapiens alu" (take (2*n) (cycle alu)) writeFastaHeader "TWO" "IUB ambiguity codes" seed' <- execStateT (writeWrapped (3*n) (chooseBase iub)) 42 writeFastaHeader "THREE" "Homo sapiens frequency" execStateT (writeWrapped (5*n) (chooseBase homosapiens)) seed'

Peter Simons wrote:

It's because nobody took the time to write faster entries for the tests where Haskell is at the bottom of the pile. The "Computer Language Shootout Benchmark" is a fun idea, but it's quite pointless to draw any conclusions about programming languages from those results. If it were included in the contest, native assembler code would win every time.

If the results could be trusted, they would be useful. You could balance the expected loss in performance against other factors (e.g. speed of development). Cheers, Daniel. -- /\/`) http://oooauthors.org /\/_/ http://opendocumentfellowship.org /\/_/ \/_/ I am not over-weight, I am under-tall. /

Peter Simons wrote:

How do you measure the time it takes to come up with a QuickSort algorithm that, implemented in Haskell, crushes the MergeSort algorithm all other languages use? ;-)

:-) I've been impressed with Haskell so far. Today I implemented a reverse Polish notation calculator. The code is 55 lines, it's easy to read, and only took a few hours for this humble newbie to implement. The second function I wrote in Haskell was quicksort :) But still... I think that speed benchmarks can be useful. For example, I really like Ruby, but its speed would really stop me from using it for many applications even though it's a very expressive language. So it's good to know what speed limitations the language has. Right now I'd say that if I need a complex algorithm (e.g. an RPN calculator) I'd do it in Haskell, but when I have a simple algorithm and performance is an issue (e.g. modeling the colission of two galaxies) I'd use C. Cheers, Daniel. -- /\/`) http://oooauthors.org /\/_/ http://opendocumentfellowship.org /\/_/ \/_/ I am not over-weight, I am under-tall. /

On 23 Dec 2005 22:29:02 +0100, Peter Simons wrote:

Daniel Carrera writes:

...

when I have a simple algorithm and performance is an issue [...] I'd use C.

You don't have to. You can write very fast programs in Haskell.

I never really finished the article I wanted to write about this subject, but the fragment I have might be interesting or even useful nonetheless:

http://cryp.to/blockio/fast-io.html http://cryp.to/blockio/fast-io.lhs

One of the interesting points that this illustrates (to me) is that the "obvious" approach in Haskell can be seriously non-optimal in terms of performance. Add to this the fact that tuning functional programs is a non-trivial art, and it becomes quite easy to see why Haskell might come across as slow. Your wcLazy implementation is (as you say) the "obvious" approach. Your two other approaches aren't particularly obvious, althought they are far more efficient. It would be interesting to see standalone code for wcIOB (where you're allowed to assume that any helpers you need, like your block IO library, are available from the standard library). This would help in comparing the "obviousness" of the two approaches. Paul

Hello Joel, Saturday, December 24, 2005, 9:29:17 PM, you wrote:

...

One of the interesting points that this illustrates (to me) is that the "obvious" approach in Haskell can be seriously non-optimal in terms of performance. Add to this the fact that tuning functional programs is a non-trivial art, and it becomes quite easy to see why Haskell might come across as slow.

JR> I got totally burned by this trying to write a heavily threaded, JR> heavy networking app in Haskell. The obvious approach was a dead-end. your problem is not Haskell or GHC, your problem is just lack of experience in this area. remember how i decreased number of your threads in 4 times, remember that i found simple and obvious solution for problem, what you tried to fix 2 weeks and ended with attempt to write your own scheduler. remember that you start low-optimizing "functional pickling" library, which is inefficient by its functional composition design instead of give chances to all serialization libraries and select the most effective one so i think that your problems is due to bad design decisions caused by lack of experience. two weeks ago when you skipped my suggestions about improving this design and answered that you will use "systematic approach", i foresee that you will fail and say that Haskell is a bad language Haskell is really slow language. but even if it will be 100 times better, it can't write programs itself, some help from programmer anyway is needed :) -- Best regards, Bulat mailto:bulatz@HotPOP.com

On Sun, Dec 25, 2005 at 12:20:38PM +0000, Joel Reymont wrote:

A disclaimer for those who might think that I'm a newbit disillutioned with Haskell... I totally love Haskell, it just seems that you need to be a guru to do what I'm trying to do and I have not yet reached this status.

I am pleased to hear this. I would love to be able to help you more often, alas my job was very time demanding recently (but quite rewarding too :-). And we have Christmas right now. I think your work will be very important and valuable for the community. You've shown were Haskell could be better, and I believe it will catch up eventually, either by improvements in GHC, in libraries or simply in documentation. Merry Christmas! Tomasz -- I am searching for a programmer who is good at least in some of [Haskell, ML, C++, Linux, FreeBSD, math] for work in Warsaw, Poland

If anyone is interested, I posted the Erlang version of the pickler combinators at http://wagerlabs.com/erlang/pickle.erl Orignal paper at http://research.microsoft.com/~akenn/fun/ picklercombinators.pdf Notice that I did away with the "sequ" while preserving "wrap" and friends. Erlang does not have enums so I added support for those. I did not test the performance of this code yet. I used the "most natural way of doing things", though, and I expect performance to be excellent. I'm most interested in whether it's possible to get the performance of the Haskell version on par with this one. Thanks, Joel -- http://wagerlabs.com/

Paul Moore writes:

It would be interesting to see standalone code for wcIOB (where you're allowed to assume that any helpers you need, like your block IO library, are available from the standard library). This would help in comparing the "obviousness" of the two approaches.

A simple version of the program -- which doesn't need any 3rd party modules to compile -- is attached below. My guess is that this approach to I/O is quite obvious, too, if you have experience with system programming in C. IMHO, the main point of the example in the article is that wc :: String -> (Int, Int, Int) wc file = ( length (lines file) , length (words file) , length file ) is a crapy word-counting algorithm. I'm not sure whether conclusions about functional programming in general or even programming in Haskell can be derived from this code. Most people seem to have trouble with lazy-evaluation, first of all. Peter -- Compile with: ghc -O2 -funbox-strict-fields -o wc wc.hs module Main ( main ) where import System.IO import Foreign type Count = Int data CountingState = ST !Bool !Count !Count !Count deriving (Show) initCST :: CountingState initCST = ST True 0 0 0 wc :: Char -> CountingState -> CountingState wc '\n' (ST _ l w c) = ST True (l+1) w (c+1) wc ' ' (ST _ l w c) = ST True l w (c+1) wc '\t' (ST _ l w c) = ST True l w (c+1) wc _ (ST True l w c) = ST False l (w+1) (c+1) wc _ (ST False l w c) = ST False l w (c+1) bufsize :: Int -- our I/O buffer size bufsize = 4096 type IOHandler st = Ptr Word8 -> Int -> st -> IO st countBuf :: IOHandler CountingState countBuf _ 0 st@(ST _ _ _ _) = return st countBuf ptr n st@(ST _ _ _ _) = do c <- peek ptr let st' = wc (toEnum (fromEnum c)) st countBuf (ptr `plusPtr` 1) (n - 1) st' loop :: Handle -> Int -> IOHandler st -> st -> IO st loop h n f st' = allocaArray n (\ptr' -> loop' ptr' st') where loop' ptr st = st `seq` do rc <- hGetBuf h ptr n if rc == 0 then return st else f ptr rc st >>= loop' ptr main :: IO () main = do ST _ l w c <- loop stdin bufsize countBuf initCST putStrLn . shows l . (' ':) . shows w . (' ':) $ show c

Tomasz Zielonka writes:

...

wc :: String -> (Int, Int, Int) wc file = ( length (lines file) , length (words file) , length file )

I have a crazy idea: what if we computed all three length applications concurrently, with the RTS preempting the thread when it generates too much unreclaimable nodes?

That's a pretty good idea, actually. What is the state of the 'par' primitive in GHC 6.x? Now that I think of it, it seems that adding a proper "compute in parallel" annotation could make a big difference in this case. Peter

Back to where this came from, my view is that this is an education issue - tutorials tend to focus on lazy, functional techniques, and not on efficiency.

But the material is available, so people *can* learn. It just needs some effort (but possibly more than it should...)

Can anyone suggest some good tutorials, papers, or books to read for learning how to reason about laziness, specifically, time and space complexity? I seem to remember that Richard Bird's Introduction to Functional Programming book has a chapter or so on this subject, but what other material would anyone recommend for trying to understand how to write efficient, lazy algorithms? Maybe in the spirit of updating Wikis and such, we can collect this sort of material together... Jared. -- jupdike@gmail.com http://www.updike.org/~jared/ reverse ")-:"

wc :: String -> (Int, Int, Int) wc file = ( length (lines file) , length (words file) , length file )

Most people tend to think that imperative programming novices don't even start their obvious solutions from something as inefficient as this. Well, I beg to differ. For almost a decade, most (I dare claim even all) Pascal and C compilers were "three-pass" or "two-pass". It means perhaps the compiler reads the input two or three times (each for a different task, just like the above), or perhaps the compiler reads the input once, produces an intermediate form and saves it to disk, then reads the intermediate form from disk, produces a second intermediate form and saves it to disk, then reads the second intermediate form from disk, then it can produce machine code. It must have been the obvious method, since even though it was obviously crappy, everyone was doing it, and "everyone" obviously refers to both novices and gurus. It must also have been pretty non-obvious how to transition from the obvious slow method to a one-pass fast method, since for almost a decade no one did it. Most of us had to wait until someone figured it out and then we had Turbo Pascal. And it was the case with imperative programming.

On Thu, 2005-12-29 at 15:56 -0500, Albert Lai wrote: . . .

one-pass fast method, since for almost a decade no one did it. Most of us had to wait until someone figured it out and then we had Turbo

Judging from comments by U. Ammann [1],[2], part of the original Pascal implementation team at ETH Zurich, the first Pascal compiler for the CDC 6x00 family of computers was written in 1970-1971, and a second was developed from scratch for the same computers but compiling the revised language, was written in 1972-1974. I think both of these compilers were one-pass. -- Bill Wood [1] U. Ammann, "The Zurich Implementation", in D.W. Barron (ed.), _Pascal, The Language and its Implementation_, pp. 63-82, John Wiley and Sons, 1981. [2] U. Ammann, "Code Generation for a Pascal Compiler", in D.W. Barron (ed.), _Pascal, The Language and its Implementation_, pp. 83-124, John Wiley and Sons, 1981.