MailboxProcessor: memory leak using return! before receiving

Question

Given the following agent, which is a simple caching mechanism:

type CacheMsg<'a,'b> = Add of 'a * 'b | ForceFlush type CacheAgent<'a, 'b when 'a : comparison>(size:int, flushCont:Map<'a, 'b> -> unit) = let agent = MailboxProcessor.Start(fun inbox -> let rec loop (cache : Map<'a, 'b>) = async { let inline flush() = flushCont cache loop Map.empty if cache.Count > size then return! flush() let! msg = inbox.Receive() match msg with | Add (key, value) -> if cache.ContainsKey key then return! loop cache else return! loop (cache.Add(key, value)) | ForceFlush -> return! flush() } loop Map.empty) member x.AddIfNotExists key value = Add(key,value) |> agent.Post member x.ForceFlush() = agent.Post ForceFlush 

This agent will continue to occupy memory (it seems that memory is not freed when flushCont called).

Given the same code, but with a slight change:

 type CacheMsg<'a,'b> = Add of 'a * 'b | ForceFlush type CacheAgent<'a, 'b when 'a : comparison>(size:int, flushCont:Map<'a, 'b> -> unit) = let agent = MailboxProcessor.Start(fun inbox -> let rec loop (cache : Map<'a, 'b>) = async { let inline flush() = flushCont cache loop Map.empty let! msg = inbox.Receive() match msg with | Add (key, value) -> if cache.ContainsKey key then return! loop cache else let newCache = cache.Add(key, value) if newCache.Count > size then return! flush() else return! loop (cache.Add(key, value)) | ForceFlush -> return! flush() } loop Map.empty) member x.AddIfNotExists key value = Add(key,value) |> agent.Post member x.ForceFlush() = agent.Post ForceFlush 

I have moved an expression that decides when to collapse in the case of the Add join. This causes the memory to be freed as expected.

What is wrong with the first approach, since it leaks memory?

Answer 1

The first version is not tail recursive .

It is not tail recursive, because this expression is not the last expression in the function:

 if cache.Count > size then return! flush() 

After this expression you call

 let! msg = inbox.Receive() 

therefore, calling flush() not the last case. Upon completion of the recursive call, implicit in flush , execution will return to the next expression in which you call inbox.Receive() . This means that the context will have to contain the previous call on the stack, because recursion is not in the tail position: there is even more work.

In the second example, all calls to flush and loop are in tail positions.

If you come from a C # background, you tend to think that return! flush() return! flush() exits this function, but this is not entirely true. The only reason

 if cache.Count > size then return! flush() 

even compiles without the corresponding else branch because the expression returns unit . This means that the code inside the then branch does not really exit the function - it just does the work in the branch (in this case flush() ), and then continues to execute subsequent expressions.