CODEWITHSUNDEEP
haskelloptimizationprofiling
twosan
twosan

Reputation: 79

Haskell: speed difference between two versions of code

I've started diving into Haskell by trying to solve some small problems.

I've stumbled upon a big performance difference(~100-200x) between the "standard haskell-friendly" solution and my "very-ugly and haskell-unfriendly" version.

I'm sure for fellow haskellers this difference in performance has a good reason, which I'm missing, and can educate me on this topic.

The problem: Find the maximum 5 digit number inside a numerical string

Both use the same concept in solving: generate all 5 digit numbers and find the maximum.

Elegant and fast code 

digit5 :: String -> Int
digit5 = maximum . map (read . take 5) . init . tails

Ugly and very slow code(once the string size is big)

digit5' :: String -> String -> String
-- xs - input string
-- maxim - current maximal value
digit5' xs maxim 
  | (length xs) < 5 = maxim
  | y > maxim = digit5' (drop 1 xs) y -- use new detected maximum value
  | otherwise = digit5' (drop 1 xs) maxim
  where y = take 5 xs

digit5 :: String -> Int
digit5 xs
-- return the original string if the input size is smaller than 6
  | length (xs) < 6 = read xs 
  | otherwise = read $ digit5' xs "00000"

For small inputs I get roughly the same execution times, for big inputs I start to see very big differences(for an input of 44550 elements):

Computation time for ugly version: 2.047 sec
Computation time for nice version: 0.062 sec

My superficial understanding of this is that the fast code is using pre-available higher order functions. For the slower version recursion is used but I think tail biting should be possible. But at a naive level, to me both seem to do the same thing.

While the slower function does comparisons on strings instead of converting them to numbers, I've also tried converting the strings to ints but without any big improvement

I've tried compiling using ghc without any flags and with the following commands:

ghc 
ghc -O2 
ghc -O2 -fexcess-precision -optc-O3 -optc-ffast-math -no-
recomp 
stack runhaskell 
ghc -O3

For sake of reproducibility I'm adding a link to the code contaning also the test vector: https://pastebin.com/kuS5iKgd

Upvotes: 3

Views: 255

Answers (1)

Fyodor Soikin
Fyodor Soikin

Reputation: 80714

The problem with your "slow" version is this line:

| length xs < 5 = maxim

This computes the length of xs, and because Haskell lists are singly-linked lists, this operation requires full traversal of the whole list, which is O(n). And it happens on every iteration. And there are N iterations. Which makes the whole process O(n^2).

The "fast" code, on the other hand, is just linear, which on large inputs shows up vividly.

If you just replace the offending line with this:

| null xs = maxim

it will make the whole thing just linear, and it will be just as fast as the "elegant" solution. Sure, this will result in extra 5 iterations, but that loss is more than compensated by reducing the overall complexity.

Or, alternatively, you can make the "elegant" solution just as slow by filtering out the tails that are 5 chars or shorter:

digit5 = maximum . map (read . take 5) . filter ((>= 5) . length) . tails

Upvotes: 9

Related Questions