2

I saw 3 functions to compute the length of a list on https://www.haskell.org/haskellwiki/Performance/Accumulating_parameter

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

len' :: [a] -> Int -> Int
len' [] acc = acc
len' (x:xs) acc = len' xs (1 + acc) 

len'' [] acc = acc
len'' (x:xs) acc = len'' xs $! (1 + acc)

In GHCi, function len is slowest and len'' is fastest. But when I compile it with GHC, function len is faster than len', Which means non tail-recursive function is faster than tail-recursive function. What's the reason for this?

Details:
len [1..10000000] : 3.05s
len' [1..10000000] 0 : 3.52s
len [1..50000000] : 13.67s
len' [1..50000000] 0 : 16.13s

Sven
  • 21
  • 2
  • 3
    `len''` recurses to `len'`. Was that intentional? – MathematicalOrchid Dec 05 '14 at 16:51
  • 3
    Can you please show your code which prints out times? – tohava Dec 05 '14 at 16:51
  • 1
    @MathematicalOrchid Sorry, it's a big mistake. Len'' is fastest, but len' is still slower than len. – Sven Dec 05 '14 at 16:59
  • 7
    Never use ghci to make any performance arguments. Compile with -O2 instead. – augustss Dec 05 '14 at 16:59
  • len' is building a huge thunk. Of coarse it's going to be slow. – Thomas M. DuBuisson Dec 05 '14 at 17:03
  • Your question is misleading then, since both functions are tail recursive, but the second function is also strict. – tohava Dec 05 '14 at 17:06
  • @tohava I use "time ./tmp" to get times – Sven Dec 05 '14 at 17:07
  • @tohava len is not tail recursive, but it's faster than len' – Sven Dec 05 '14 at 17:09
  • Odd... for me `len'` is faster than `len`. Also, the list sizes you wrote require lots of memory, are you using the `-K` switch? I tried both with and without `-O2` – tohava Dec 05 '14 at 17:10
  • Without strictness, there's no reason one would outperform the other, since they both build up massive summation expressions. Tail-recursion is only of benefit for strict functions. – AndrewC Dec 05 '14 at 17:13
  • @ThomasM.DuBuisson I don't know much about lazy evaluation. Do you mean "(1 + acc)" will build a huge thunk, and "len xs + 1" will not? – Sven Dec 05 '14 at 17:17
  • @tohava I'm not using any switch: ghc tmp.hs, time ./tmp . And my GHC version is 7.8.3 – Sven Dec 05 '14 at 17:24
  • Odd... I'm using GHC 7.4.1. If this also occurs with `-O2` I would recommend sending this as a bug report to the ghc people. – tohava Dec 05 '14 at 17:29
  • @tohava with `-O2`, `len'` is faster than `len`, thank you! – Sven Dec 05 '14 at 17:40
  • It's not actually a duplicate but the evolution of the question suggests that it was originally somewhat ill-specified. 1) Don't use GHCi 2) Don't compare monomorphic and polymorphic functions (`len''` didn't have a type and would use `Integer`). 3) Always use `-O2`. 4) Strictness analysis is sufficient in this case to result in `len'` being equivalent to `len''`. – Thomas M. DuBuisson Dec 05 '14 at 17:41
  • @ThomasM.DuBuisson When I add `len'' :: [a] -> Int -> Int`, it's equivalent to `len'`. Your answer is quite helpful, thank you! – Sven Dec 05 '14 at 17:49
  • @ThomasM.DuBuisson I support reopening if you'd like to write an answer. Yes? – AndrewC Dec 05 '14 at 19:50
  • Nah, it's basically a typo so let's leave it closed. – Thomas M. DuBuisson Dec 05 '14 at 20:22

0 Answers0