Why to avoid Explicit recursion in Haskell?

Question

I am new to Haskell.

While studying about foldr many are suggesting to use it and avoid explicit recursion which can lead to Memory Inefficient code. https://www.reddit.com/r/haskell/comments/1nb80j/proper_use_of_recursion_in_haskell/

As I was running the sample mentioned in the above link. I can see the explicit recursion is doing better in terms of memory. First I thought May be running on GHCi is not near to perfect benchmark and I tried compiling it using stack ghc. And btw How can I pass Compiler Optimization flags via stack ghc. What am I missing from the Expression Avoid Explicit Recursion.

find p = foldr go Nothing
    where go x rest = if p x then Just x else rest

findRec :: (a -> Bool) -> [a] -> Maybe a
findRec _ [] = Nothing
findRec p (x:xs) = if p x then Just x else (findRec p xs)

main :: IO ()
main = print $ find (\x -> x `mod` 2 == 0) [1, 3..1000000] 
main = print $ findRec (\x -> x `mod` 2 == 0) [1, 3..1000000] 

-- find
Nothing
      92,081,224 bytes allocated in the heap
           9,392 bytes copied during GC
          58,848 bytes maximum residency (2 sample(s))
          26,704 bytes maximum slop
               0 MB total memory in use (0 MB lost due to fragmentation)

                                     Tot time (elapsed)  Avg pause  Max pause
  Gen  0        87 colls,     0 par    0.000s   0.000s     0.0000s    0.0001s
  Gen  1         2 colls,     0 par    0.000s   0.001s     0.0004s    0.0008s

  INIT    time    0.000s  (  0.000s elapsed)
  MUT     time    0.031s  (  0.043s elapsed)
  GC      time    0.000s  (  0.001s elapsed)
  EXIT    time    0.000s  (  0.000s elapsed)
  Total   time    0.031s  (  0.044s elapsed)

  %GC     time       0.0%  (0.0% elapsed)

  Alloc rate    2,946,599,168 bytes per MUT second

  Productivity 100.0% of total user, 96.8% of total elapsed

-- findRec
Nothing
      76,048,432 bytes allocated in the heap
          13,768 bytes copied during GC
          42,928 bytes maximum residency (2 sample(s))
          26,704 bytes maximum slop
               0 MB total memory in use (0 MB lost due to fragmentation)

                                     Tot time (elapsed)  Avg pause  Max pause
  Gen  0        71 colls,     0 par    0.000s   0.000s     0.0000s    0.0001s
  Gen  1         2 colls,     0 par    0.000s   0.001s     0.0004s    0.0007s

  INIT    time    0.000s  (  0.000s elapsed)
  MUT     time    0.031s  (  0.038s elapsed)
  GC      time    0.000s  (  0.001s elapsed)
  EXIT    time    0.000s  (  0.000s elapsed)
  Total   time    0.031s  (  0.039s elapsed)

  %GC     time       0.0%  (0.0% elapsed)

  Alloc rate    2,433,549,824 bytes per MUT second

  Productivity 100.0% of total user, 96.6% of total elapsed

user_625403 · Answer

You are measuring how quickly GHC can do half a million modulus operations. As you might expect, "in the blink of an eye" is the answer regardless of how you iterate. There is no obvious difference in speed.

You claim that you can see that explicit recursion is using less memory, but the heap profiling data you provide shows the opposite: more allocation and higher max residency when using explicit recursion. I don't think the difference is significant, but if it were then your evidence would be contradicting your claim.

As to the question of why to avoid explicit recursion, it's not really clear what part of that thread you read that made you come to your conclusion. You linked to a giant thread which itself links to another giant thread, with many competing opinions. The comment that stands out the most to me is it's not about efficiency, it's about levels of abstraction. You are looking at this the wrong way by trying to measure its performance.

user_7203016 · Answer

First, don't try to understand the performance of GHC-compiled code using anything other than optimized compilation:

$ stack ghc -- -O2 Find.hs
$ ./Find +RTS -s

With the -O2 flag (and GHC version 8.6.4), your find performs as follows:

      16,051,544 bytes allocated in the heap
          14,184 bytes copied during GC
          44,576 bytes maximum residency (2 sample(s))
          29,152 bytes maximum slop
               0 MB total memory in use (0 MB lost due to fragmentation)

However, this is very misleading. None of this memory usage is due to the looping performed by foldr. Rather it's all due to the use of boxed Integers. If you switch to using plain Ints which the compiler can unbox:

main = print $ find (\x -> x `mod` 2 == 0) [1::Int, 3..1000000]
                                             ^^^^^

the memory performance changes drastically and demonstrates the true memory cost of foldr:

      51,544 bytes allocated in the heap
       3,480 bytes copied during GC
      44,576 bytes maximum residency (1 sample(s))
      25,056 bytes maximum slop
           0 MB total memory in use (0 MB lost due to fragmentation)

If you test findRec with Ints like so:

 main = print $ findRec (\x -> x `mod` 2 == 0) [1::Int, 3..1000000]

you'll see much worse memory performance:

  40,051,528 bytes allocated in the heap
      14,992 bytes copied during GC
      44,576 bytes maximum residency (2 sample(s))
      29,152 bytes maximum slop
           0 MB total memory in use (0 MB lost due to fragmentation)

which seems to make a compelling case that recursion should be avoided in preference to foldr, but this, too, is very misleading. What you are seeing here is not the memory cost of recursion, but rather the memory cost of "list building".

See, foldr and the expression [1::Int, 3..1000000] both include some magic called "list fusion". This means that when they are used together (i.e., when foldr is applied to [1::Int 3..1000000]), an optimization can be performed to completely eliminate the creation of a Haskell list. Critically, the foldr code, even using list fusion, compiles to recursive code which looks like this:

main_go
  = \ x ->
      case gtInteger# x lim of {
        __DEFAULT ->
          case eqInteger# (modInteger x lvl) lvl1 of {
            __DEFAULT -> main_go (plusInteger x lvl);
                      -- ^^^^^^^ - SEE?  IT'S JUST RECURSION
            1# -> Just x
          };
        1# -> Nothing
      }
end Rec }

So, it's list fusion, rather than "avoiding recursion" that makes find faster than findRec.

You can see this is true by considering the performance of:

find1 :: Int -> Maybe Int
find1 n | n >= 1000000 = Nothing
        | n `mod` 2 == 0 = Just n
        | otherwise = find1 (n+2)

main :: IO ()
main = print $ find1 1

Even though this uses recursion, it doesn't generate a list (or use boxed Integers), so it runs just like the foldr version:

      51,544 bytes allocated in the heap
       3,480 bytes copied during GC
      44,576 bytes maximum residency (1 sample(s))
      25,056 bytes maximum slop
           0 MB total memory in use (0 MB lost due to fragmentation)

So, what are the take home lessons?

Always benchmark Haskell code using ghc -O2, never GHCi or ghc without optimization flags.
Less than 10% of people in any Reddit thread know what they're talking about.
foldr can sometimes perform better than explicit recursion when special optimizations like list fusion can apply.
But in the general case, explicit recursion performs just as well as foldr or other specialized constructs.
Also, optimizing Haskell code is hard.

Actually, here's a better (more serious) take-home lesson. Especially when you're getting started with Haskell, make every possible effort to avoid thinking about "optimizing" your code. Far more than any other language I know, there is an enormous gulf between the code you write and the code the compiler generates, so don't even try to figure it out right now. Instead, write code that is clear, straightforward, and idiomatic. If you try to learn the "rules" for high-performance code now, you'll get them all wrong and learn really bad programming style into the bargain.

Why to avoid Explicit recursion in Haskell?

2 Answers