Why does this cause a memory leak in the Haskell Conduit library?

Question

I have a conduit pipeline processing a long file. I want to print a progress report for the user every 1000 records, so I've written this:

-- | Every n records, perform the IO action.
-- Used for progress reports to the user.
progress :: (MonadIO m) => Int -> (Int -> i -> IO ()) -> Conduit i m i
progress n act = skipN n 1
   where
      skipN c t = do
         mv <- await
         case mv of
            Nothing -> return ()
            Just v ->
               if c <= 1
                  then do
                     liftIO $ act t v
                     yield v
                     skipN n (succ t)
                  else do
                     yield v
                     skipN (pred c) (succ t)

No matter what action I call this with, it leaks memory, even if I just tell it to print a full stop.

As far as I can see the function is tail recursive and both counters are regularly forced (I tried putting "seq c" and "seq t" in, to no avail). Any clue?

If I put in an "awaitForever" that prints a report for every record then it works fine.

Update 1: This occurs only when compiled with -O2. Profiling indicates that the leaking memory is allocated in the recursive "skipN" function and being retained by "SYSTEM" (whatever that means).

Update 2: I've managed to cure it, at least in the context of my current program. I've replaced the function above with this. Note that "proc" is of type "Int -> Int -> Maybe i -> m ()": to use it you call "await" and pass it the result. For some reason swapping over the "await" and "yield" solved the problem. So now it awaits the next input before yielding the previous result.

-- | Every n records, perform the monadic action. 
-- Used for progress reports to the user.
progress :: (MonadIO m) => Int -> (Int -> i -> IO ()) -> Conduit i m i
progress n act = await >>= proc 1 n
   where
      proc c t = seq c $ seq t $ maybe (return ()) $ \v ->
         if c <= 1
            then {-# SCC "progress.then" #-} do
               liftIO $ act t v
               v1 <- await
               yield v
               proc n (succ t) v1
            else {-# SCC "progress.else" #-} do
               v1 <- await
               yield v
               proc (pred c) (succ t) v1

So if you have a memory leak in a Conduit, try swapping the yield and await actions.

Sensational

This is not actually tail recursive, the last call is not to skipN but rather to (>>) (yield v) (skipN x y). This is a common pitfall when writing recursive routines using monads. I'm not sure if GHC would optimize this correctly without looking at a core dump, but my initial guess is that you aren't actually using a tail-recursive function. – Belshazzar

Also can you add your memory leak report ? – Mckeon

I haven't profiled it: I've just run the program and watched the process memory grow. – Sensational

@bheklilr, could you explain why m>>n might not invoke n in tail position? – Reddick

@Reddick The same reason why sum (x:xs) = x + sum xs is not tail recursive, the last function being called is not sum, but (+) as it's equivalent to sum (x:xs) = (+) x xs. This is why we often write recursive functions using a helper function with an accumulator argument, or just use folds if the situation is simple enough, such as sum = go 0 where { go a [] = a; go a (x:xs) a = go (x + a) xs } or sum = foldl' (+) 0. Since the do notation desugars to use >> and >>=, this means that the last call in the stack is to one of those, not to it's second argument. – Belshazzar

@bheklilr, (+) needs to examine its second argument before it can dispose of its first. I don't know anything about conduits, but in IO, m >>= f translates to code that looks like "1. Execute m (non-tail). Put the result in r. 2. Execute f r (tail). By the time f is inspected, nothing remains of m but the result it produced, and (more importantly), >>= doesn't have to do anything with f r; its job is already done. Obviously this is not the case for all monads; maybe something about conduits breaks it? – Reddick

I think you are all focusing too much on the tail-recursive part. Neither pipes nor conduit need to be tail recursive to run in constant space. The tail recursive discussion is just a red herring. – Teutonic

@Reddick "Obviously this is not the case for all monads". Then why would you expect it GHC to optimize it away? There may be special optimizations made for IO compared to custom monads, since IO is a very special, low level monad, but for custom ones I would imagine that it could be important to consider things like this. – Belshazzar

@GabrielGonzalez I'm not saying that tail recursion is the issue here, I just wanted to point out to OP that de-sugared that is not a tail-recursive function, since he had stated it in his original question. – Belshazzar

I suspect that bheklilr is on the right track. Conduit works using continuations so evaluation order is a lot harder to figure out than in IO. I'll have to spend some time staring at the source code. – Sensational

It would be very helpful if you could post complete runnable code, i.e. including an example usage of progress that demonstrates the memory leak. – Calycine

Do you realise that t is never forced unless act forces it? Printing out a full stop won't do that ... – Calycine

@TomEllis, I'd have mentioned that if the OP hadn't already mentioned trying to force it explicitly. – Reddick

@dfeuer: Until we've seen the attempt we can't be sure he tried to force it in the right way! – Calycine

At a glance, I think you have too much laziness. If your report function is lazy in the 't' argument, you will keep accumulating thunks in 't'. Add bang patterns and try replacing skipN c t with skipN !c !t and see if it helps. – Crepe

@TomEllis, that said, most Int arithmetic is "conlike", and the initial t argument to skipN is locally known to be 1, so the compiler could safely make it strict in t. Whether it does or not I'm not sure, and that would certainly need optimizations to be enabled. – Reddick

This sounds to me like your accumulator leaked and you didn't force the accumulator the right way. We need to see the code you used to force the accumulator. – Teutonic

I've used an action that printed the accumulator 't', and I've tried saying "skipN c t = seq t $ seq c $ do ...". Neither made any difference. I'm pretty certain I'm not just accumulating thunks on 'c' and 't'. – Sensational

@PaulJohnson: Having written the code in the answer below with plenty of forcing I am inclined to agree with you. I don't understand why it still leaks. – Calycine

Answer 1

This isn't an anwser but it is some complete code I hacked up for testing. I don't know conduit at all, so it may not be the best conduit code. I've forced everything that seems like it needs to be forced, but it still leaks.

{-# LANGUAGE BangPatterns #-}

import Data.Conduit
import Data.Conduit.List
import Control.Monad.IO.Class

-- | Every n records, perform the IO action.
--   Used for progress reports to the user.
progress :: (MonadIO m) => Int -> (Int -> i -> IO ()) -> Conduit i m i
progress n act = skipN n 1
   where
      skipN !c !t = do
         mv <- await
         case mv of
            Nothing -> return ()
            Just !v ->
               if (c :: Int) <= 1
                  then do
                     liftIO $ act t v
                     yield v
                     skipN n (succ t)
                  else do
                     yield v
                     skipN (pred c) (succ t)

main :: IO ()
main = unfold (\b -> b `seq` Just (b, b+1)) 1
       $= progress 100000 (\_ b -> print b)
       $$ fold (\_ _ -> ()) ()

On the other hand,

main = unfold (\b -> b `seq` Just (b, b+1)) 1 $$ fold (\_ _ -> ()) ()

does not leak, so something in progress does indeed seem to be the problem. I can't see what.

EDIT: The leak only occurs with ghci! If I compile a binary and run it there is no leak (I should have tested this earlier ...)

Calycine

Thanks. I was planning on writing something like this today. – Sensational

This doesn't force 't', so you may still be accumulating thunks. I'll have to try playing with it tonight. – Sensational

@PaulJohnson, that bang pattern in skipN !c !t sure looks like it forces t. There's no need to force c (although it's probably a good idea, for speed) because it's forced by the if often enough. – Reddick

Please see my answer below, I think Tom's solution does not leak memory, but instead something's going on with print. – Si

Answer 2

I think Tom's answer is the right one, I'm starting this as a separate answer as it will likely introduce some new discussion (and because it's too long for just a comment). In my testing, replacing the print b in Tom's example with return () gets rid of the memory leak. This made me think that the problem is in fact with print, not conduit. To test this theory, I wrote a simple helper function in C (placed in helper.c):

#include <stdio.h>

void helper(int c)
{
    printf("%d\n", c);
}

Then I foreign imported this function in the Haskell code:

foreign import ccall "helper" helper :: Int -> IO ()

and I replaced the call to print with a call to helper. The output from the program is identical, but I show no leak, and a max residency of 32kb vs 62kb (I also modified the code to stop at 10m records for better comparison).

I see similar behavior when I cut out conduit entirely, e.g.:

main :: IO ()
main = forM_ [1..10000000] $ \i ->
    when (i `mod` 100000 == 0) (helper i)

I'm not convinced, however, that this is really a bug in print or Handle. My testing never showed the leak reaching any substantial memory usage, so it could just be that a buffer is growing towards a limit. I'd have to do more research to understand this better, but I wanted to first see if this analysis meshes with what others are seeing.

Si

Previously I only tested my code in ghci, I didn't bother compiling it. Having now done the latter I notice there is no leak in a compiled version (even at -O0). So perhaps there is a bug in ghci? (I am on 7.6). – Calycine

By the way, in ghci the memory leak is enormous. It quickly gobbles up 50% of my 4GB memory. – Calycine

@PaulJohnson: Do you see the space leak in the compiled version? – Calycine

Yes, the leak was in the compiled version. – Sensational

I'm trying to produce a sample program that reproduces the leak, but I'm not having a lot of luck. – Sensational

OK. Colour me completely confused. I deleted my ~/.ghc (i.e. all locally installed packages) and reinstalled everything with "cabal install -p" (which enables library profiling) so that I could try to profile the problem. The memory leak has now gone away. – Sensational

Confusion removed: the leak happens when I turn on optimisation. – Sensational

@PaulJohnson Do you have a standalone program that demonstrates the memory leak fully? That would help quite a bit. – Si

I've been trying to develop one, but I can't reproduce the problem anywhere except the original. I'll keep at it. – Sensational

Answer 3

I know it's two years later, but I suspect what's happening is that full laziness is lifting part of the body the await until before the await, and this is causing a space leak. It looks similar to the case in section "Increasing Sharing" in my blog post on this very topic.

Buonomo