Sounds great! Thanks for the advice. :-) -Corey On Wed, Jul 23, 2008 at 1:18 PM, Don Stewart wrote:

coreyoconnor:

...

I have the need to regularly write tiny programs that analyze output logs. The output logs don't have a consistent formatting so I typically choose Perl for these tasks.

The latest instance of having to write such a program was simple enough I figured I'd try my hand at using Haskell instead. The short story is that I could quickly write a Haskell program that achieved the goal. Yay! However, the performance was ~8x slower than a comparable Perl implementation. With a lot of effort I got the Haskell version to only 2x slower. A lot of the optimization was done with guesses that the performance difference was due to how each line was being read from the file. I couldn't determine much using GHC's profiler.

I still have two questions after all this: - Can I get a Haskell implementation as fast as the Perl? - What do I need to do to get GHC's profiler to provide me usable information? Telling me that 98% of the time was in "main" is not very enlightening ;-)

All the code and data for this little experiment I've placed here: http://tothepowerofdisco.com/repo/sum_optimization/ My first, and shortest, version is SumTiny.hs. The optimized version is SumFast.hs.

The long version for the curious:

The (cleaned up) data was a 78k line file consisting of lines like the following: framerate (prev == no pts): 15 framerate (delta): 25 framerate (invalid timebase): 12.5 ... and so on.

The need was for a program that calculated 1.0 / framerate for each line and produced the sum. Easy no?

My straightforward Haskell solution was: ------------------------------------------------------------------- import Text.Regex.Posix

main = do f_lines <- readFile "test.out" >>= return . lines let duration = foldl add_line 0.0 f_lines add_line sum line = let [[_,m]] = line =~ "([0-9.]+)" framerate = read m delta = 1.0 / framerate in sum + delta putStrLn $ "Duration (sec): " ++ show duration

Could you try using lazy and/or strict bytestrings. For *any* IO performance issue, that should be your first stop.

See, e.g., this sum-file example,

http://shootout.alioth.debian.org/gp4/benchmark.php?test=sumcol&lang=ghc&id=6

which outperforms C on the benchmark.

The second point would be to avoid Text.Regex.Posix, which is algorithmically much worse than the PCRE regexes used by perl. Instead, try the pcre-light or regex-pcre packages, which have both better complexity, and operate on efficient bytestrings.

Finally, there's some small details about writing efficient loops. Give type declarations for atomic types like Int and Double, and use strict folds or explicit recursion, as in this post,

http://cgi.cse.unsw.edu.au/~dons/blog/2008/05/16#fast

For your task here, with those simple changes, it should be relatively easy to produce competitive-with-C performance.

-- Don

-- -Corey O'Connor

And against gawk 3.1.5: $ time awk -F: '{sum += 1 / $2} END{print sum}' test.out 3155.63 real 0m0.197s user 0m0.184s sys 0m0.004s compared to Don's Haskell version: $ time ./fastSum < test.out 3155.626666664377 real 0m0.072s user 0m0.056s sys 0m0.004s compared to the Corey's perl version: $ time perl Sum.pl Duration (sec): 3155.62666666438 real 0m0.181s user 0m0.164s sys 0m0.012s Regards, Brad Larsen On Wed, 23 Jul 2008 15:01:24 -0400, Don Stewart wrote:

coreyoconnor:

...

I have the need to regularly write tiny programs that analyze output logs. The output logs don't have a consistent formatting so I typically choose Perl for these tasks.

The latest instance of having to write such a program was simple enough I figured I'd try my hand at using Haskell instead. The short story is that I could quickly write a Haskell program that achieved the goal. Yay! However, the performance was ~8x slower than a comparable Perl implementation. With a lot of effort I got the Haskell version to only 2x slower. A lot of the optimization was done with guesses that the performance difference was due to how each line was being read from the file. I couldn't determine much using GHC's profiler.

{-# OPTIONS -fbang-patterns #-}

import qualified Data.ByteString.Char8 as S import Data.ByteString.Lex.Double import Debug.Trace

main = print . go 0 =<< S.getContents where go !n !s = case readDouble str of Nothing -> n Just (k,t) -> let delta = 1.0 / k in go (n+delta) t where (_, xs) = S.break ((==) ':') s str = S.drop 2 xs

It uses the bytestring-lexing package on Hackage to read the Doubles out,

$ ghc --make Fast.hs -O2 -fvia-C -optc-O2 $ time ./Fast < test.out 3155.626666664377 ./Fast < test.out 0.07s user 0.01s system 97% cpu 0.078 total

So that's twice as fast as the perl entry on my box,

$ time perl Sum.pl < test.out Duration (sec): 3155.62666666438 perl Sum.pl < test.out 0.15s user 0.03s system 100% cpu 0.180 total

Note that the safe Double lexer uses a bit of copying, so we can in fact do better still with a non-copying Double parser, but that's only for the hardcore.

-- Don _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe