[Haskell-cafe] help with Haskell performance

[Eugene Kirpichov]

2009/11/8 Gokul P. Nair <gpnair78 at yahoo.com>
>
> Hi all,
>
> The task I'm trying to accomplish:
>
> Given a log file containing several lines of white space delimited entries like this:
>
> [Sat Oct 24 08:12:37 2009] [error] GET /url1 HTTP/1.1]: Requested URI does not exist
> [Sat Oct 24 08:12:37 2009] [error] GET /url2 HTTP/1.0]: Requested URI does not exist
> [Sat Oct 24 08:12:37 2009] [error] GET /url1 HTTP/1.1]: Requested URI does not exist
> [Sat Oct 24 12:12:37 2009] [error] GET /url1 HTTP/1.1]: Requested URI does not exist
>
> filter lines that match the string " 08:", extract the 6th, 7th and 8th words from that line, group all lines that have the the same resulting string, do a count on them and sort the result in descending order of counts and print it out. So in the example above we'd end up with an output like this:
>
> ("GET /url1 HTTP/1.1]:", 2)
> ("GET /url2 HTTP/1.0]:", 1)
>
> Seems pretty straightforward, so I wrote a simple perl script to achieve this task (see the bottom of this email).
>
> The input file is 335 MB in size and contains about 2 million log line entires in it. The perl script does a pretty decent job and finishes in about 3 seconds.
>
> Now the interesting part. I decided to implememt this in Haskell (being my favorite language and all) and ended up with the following code:
>
> --- begin haskell code ---
>
> import Text.Regex.Posix ( (=~) )

First, you are using Text.Regex.Posix which is dog slow. Use
regex-tdfa or regex-pcre.
Second, you are using it on a String! Third, you are unpacking a lazy
bytestring for that! This alone is more than enough to make things
ridiculously slow.

>
> import qualified Data.List as List
> import qualified Data.Map as Map
> import qualified Data.ByteString.Lazy.Char8 as LB
>
> main = do
>   contents <- LB.readFile "log_file"
>   putStr . unlines . map ( show . (\(x, y) -> ((LB.unpack x), y)) ) .
This piece of code also does unpacking. If the output is small, it's
ok, otherwise assemble output in the form of a bytestring and print it
with B.putStr.

>     -- create a Map grouping & counting matching tokens and sort based on the counts
>     List.sortBy (\(_, x) (_, y) -> y `compare` x) . Map.toList . Map.fromListWith (+) . filtertokens .
The lambda can be replaced by "flip (comparing snd)"

>     LB.lines $ contents
Here, you should not use Map.fromListWith (+) because Map is not
strict in its entries and you end up having big fat thunks there.
You should use Map.fromListWith plus where x `plus` y = x `seq` y `seq` x+y.

>   where filtertokens = foldr (\x acc -> if (f x) then ((g x) : acc) else acc) []
>           -- filter lines starting with " 08:"
>           where f = (=~ " 08:") . LB.unpack
>                 -- extract tokens 6, 7 & 8 and create an association list like so ("GET /url2 HTTP/1.0]:", 1)
>                 g line = flip (,) 1 . LB.unwords . map (xs !!) $ [6, 7, 8] where xs = LB.words line
You are using random access on a list three times in a row.
map (xs!!) [6,7,8] is much faster when implemented as "take 3 (drop 6 xs)".


So.. Well. Try these suggestions, show the resulting performance and
then we'll see.

>
> --- end haskell code ---
>
> This haskell implementation takes a whopping 27 seconds to complete! About 9 times slower than the perl version! I'm using ghc 6.10.4, compiling with -O2 and even went to the extent of fusing an adjacent map and filter using a foldr like so: map f (filter g) => foldr ( if g x then f x ... ), fusing adjacents maps etc. Still the same result.
>
> I really hope I'm missing some obvious optimization that's making it so slow compared to the perl version, hence this email soliciting feedback.
>
> Thanks in advance.
>
> P.S. For reference, here's my corresponding perl implementation:
>
> --- start perl code ---
>
> #!/usr/bin/perl
> use strict;
> use warnings FATAL => 'all';
>
> my %urls;
> open(FILE, '<', $ARGV[0]);
> while(<FILE>) {
>     if (/ 08:/) {
>         my @words = split;
>         my $key = join(" ", ($words[6], $words[7], $words[8]));
>         if (exists $urls{$key}) { $urls{$key}++ }
>         else { $urls{$key} = 1 }
>     }
> }
> for (sort { $urls{$b} <=> $urls{$a} } keys %urls) { print "($_, $urls{$_})\n" }
>
> --- end perl code ---
>
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>



--
Eugene Kirpichov
Web IR developer, market.yandex.ru