Haskell Writing myLength

Question

I was working on this page

http://www.haskell.org/haskellwiki/99_questions/Solutions/4

I understand what each function means and it is fun to see that a function can be defined in numerous ways like this. However, I just started wondering which one is faster. And I thought it would be the one it says is length in Prelude.

length [] = 0
length (x:xs) = 1 + length xs

However, this is much slower than length in Prelude.

On my computer length in Prelude returns a length of [1..10^7] in 0.37 sec. However the function defined as above took 15.26 sec.

I defined my own length function, which makes use of an accumulator. It took only 8.99 sec.

I am wondering why these big differences occurred?

Answer 1

When you say "length in Prelude returns ... in 0.37 sec", which compiler are you referring to? If you are using GHC, you can see, e.g., here that the actual implementation differs from the simple

length [] = 0
length (x:xs) = 1 + length xs

Namely, it is:

length l = len l 0#
  where
    len :: [a] -> Int# -> Int
    len []     a# = I# a#
    len (_:xs) a# = len xs (a# +# 1#)

This code uses an accumulator and avoids the problem of huge unevaluated thunks by using unboxed integers, i.e., this version is highly optimized.

To illustrate the problem with the "simple" version, consider how length [1, 2, 3] is evaluated:

length [1, 2, 3]
  => 1 + length [2, 3]
  => 1 + (1 + length [3])
  => 1 + (1 + (1 + length []))
  => 1 + (1 + (1 + 0))

The sum is not evaluated until its result is really needed, thus you see that when the input is a huge list, you will create a huge sum in memory first and then only evaluate it when its result is really needed.

In contrast the optimized version evaluates as follows:

length [1, 2, 3]
  => len [1, 2, 3] 0#
  => len [2, 3] (1#)
  => len [3] (2#)
  => len [] (3#)
  => 3

i.e., the "+1" is done immediately.

Answer 2

Two steps that you should watch out for are:

• Are you running the code compiled and not in ghci?
• Are you using the -O2 flag

The following benchmarks were done in criterion and use the following functions along with prelude's length which requires the MagicHash pragma and importing GHC.Base:

myLength1 :: [a] -> Int                                                          
myLength1 [] = 0                                                                 
myLength1 (x:xs) = 1 + myLength1 xs                                              

myLength2 :: [a] -> Int                                                          
myLength2 lst = len lst 0                                                        
  where                                                                          
    len :: [a] -> Int -> Int                                                     
    len [] n = n                                                                 
    len (_:xs) n = len xs (n+1)                                                  

myLength3                  :: [a] -> Int                                         
myLength3 l                =  len l 0#                                           
  where                                                                          
    len :: [a] -> Int# -> Int                                                    
    len []     a# = I# a#                                                        
    len (_:xs) a# = len xs (a# +# 1#)

The results of the benchmark, found in full at the end, with out using teh -O2 flag are:

              mean
length    :   5.4818 ms
myLength1 : 202.1552 ms
myLength2 : 236.3042 ms
myLength3 :   5.3630 ms

Now lets use the -02 flag when compiling

              mean
length    :   5.2597 ms
myLength1 :   12.882 ms
myLength2 :   5.2026 ms
myLength3 :   5.6393 ms,

Notice that length the myLength3 do not change but the remaining two change considerably. The naive approach is inside a factor of 3 different and myLength2 is now comparible with the built in length by mimics the prelude length in all but using unboxing.

Also note worthy is that myLength3 which unboxes the Int does not change much and would probably preform much better in ghci then myLength 1 or 2.

Full code at: https://gist.github.com/Davorak/5457105

Edit: Some further information that would not fit in a comment:

The ghc flag -O2 with the letter means “Apply every non-dangerous optimisation, even if it means significantly longer compile times." I would not be surprised if this involves some unboxing of datatypes. You can find further explanations of different flags here. Here is a linke with a larger list of flags for ghc 7.6.2 the explanations can be short and cryptic however.

I am not intimately familiar with unboxing and primitive operations and their consequences here is a third link to the GHC manual that covers unboxed types. You will occasionally find them mention in optimization tutorials. Most of the time you should not bother with them unless you really need every gram of performance since as we say above they often will only make a constant difference after other optimization flags are used.