Why does traversing a large binary tree result in a stack overflow even when using continuation-passing style?

Question

Chapter 9 of the book Expert F# 3.0 shows how to use continuation-passing style to avoid stack overflows when traversing binary trees. I have written tree traversal code that is almost identical to the code from the book, but I get stack overflows nevertheless. My code is as follows:

type 'a Tree =
  | Leaf   of 'a
  | Branch of 'a Tree * 'a Tree

let rec mkLeftLeaningTree n tree =
  if n = 0 then
    tree
  else
    Branch (mkLeftLeaningTree (n - 1) tree, Leaf "right")

let leftLeaningTree1 = Leaf "left"
let leftLeaningTree2 = mkLeftLeaningTree 30000 leftLeaningTree1
let leftLeaningTree3 = mkLeftLeaningTree 30000 leftLeaningTree2
let leftLeaningTree4 = mkLeftLeaningTree 30000 leftLeaningTree3
let leftLeaningTree5 = mkLeftLeaningTree 30000 leftLeaningTree4
let leftLeaningTree6 = mkLeftLeaningTree 30000 leftLeaningTree5

let sizeContAcc tree =
  let rec worker acc tree cont =
    match tree with
      | Leaf _               -> cont (acc + 1)
      | Branch (left, right) -> worker acc left  (fun acc ->
                                worker acc right cont)
  worker 0 tree id

Loading this into the F# interactive environment and evaluating the expression sizeContAcc leftLeaningTree6 makes the stack overflow. Why is this?

Swore

You actually overflow much earlier, when creating the leftLeaningTree2: let leftLeaningTree2 = mkLeftLeaningTree 30000 leftLeaningTree1. – Middleclass

Whether the computation of leftLeaningTree2 overflows the stack depends on the particular platform. If you get an overflow at this point, you can replace the occurrences of 30000 by lower numbers. If this, in turn, results in sizeContAcc leftLeaningTree6 not overflowing the stack, you can use more tree construction steps (adding leftLeaningTree7 and so on). – Swore

That is indeed true, I was wondering if you were running this on Linux, which has a bigger stack than windows (1MB ;-). – Middleclass

Yes, I am running this on Linux. Does this problem also show up on Windows after having tuned parameters accordingly? – Swore

I want to add that I am using F# 4.0. – Swore

I would suspect FSI in this case. At count 270,001 (19 trees with 15,000 leafs) it doesn't overflow. Can you make sure that FSI is running in 64-bit if you are using it, otherwise have it compiled in Release mode, 64-bit with Optimization and Tail Calls turned on. – Middleclass

In FSI the options would be --optimize --tailcalls but I'm not familiar with mono (which I assume you are using). – Middleclass

I have tried to run fsharpi with options --optimize and --tailcalls, but the stack still overflows. I have also tried to compile my F# code using these options, but the stack overflow also occurs then. – Swore

That is very unfortunate. I would suspect either a bug or some setting in mono. I will post some more details, but I'm afraid that might not help you directly, since it won't be mono. I added that tag to the Q. – Middleclass

Can you get rid of the stack overflow on Microsoft .NET by using --optimize and --tailcalls? – Swore

Yes. See my (not really...) answer below. – Middleclass

Answer 1

Unfortunately this might not help you to actually fix the issue but maybe it provides some pointers in where to look. First, the code and the setup. I decreased the tree size itself to make it work on Windows. The rest is .NET 4.6, 64-bit, win7, in VS2015 Update3.

type 'a Tree =
    | Leaf   of 'a
    | Branch of 'a Tree * 'a Tree

[<EntryPoint>]
let main argv =

    ///https://mcmap.net/q/1800961/-why-does-traversing-a-large-binary-tree-result-in-a-stack-overflow-even-when-using-continuation-passing-style



    let rec mkLeftLeaningTree n tree =
      if n = 0 then
        tree
      else
        Branch (mkLeftLeaningTree (n - 1) tree, Leaf "right")



    let leftLeaningTree1 = Leaf "left"
    let leftLeaningTree2 = mkLeftLeaningTree 15000 leftLeaningTree1
    let leftLeaningTree3 = mkLeftLeaningTree 15000 leftLeaningTree2
    let leftLeaningTree4 = mkLeftLeaningTree 15000 leftLeaningTree3
    let leftLeaningTree5 = mkLeftLeaningTree 15000 leftLeaningTree4
    let leftLeaningTree6 = mkLeftLeaningTree 15000 leftLeaningTree5
    let leftLeaningTree7 = mkLeftLeaningTree 15000 leftLeaningTree6
    let leftLeaningTree8 = mkLeftLeaningTree 15000 leftLeaningTree7
    let leftLeaningTree9 = mkLeftLeaningTree 15000 leftLeaningTree8
    let leftLeaningTree10 = mkLeftLeaningTree 15000 leftLeaningTree9
    let leftLeaningTree11 = mkLeftLeaningTree 15000 leftLeaningTree10
    let leftLeaningTree12 = mkLeftLeaningTree 15000 leftLeaningTree11
    let leftLeaningTree13 = mkLeftLeaningTree 15000 leftLeaningTree12
    let leftLeaningTree14 = mkLeftLeaningTree 15000 leftLeaningTree13
    let leftLeaningTree15 = mkLeftLeaningTree 15000 leftLeaningTree14
    let leftLeaningTree16 = mkLeftLeaningTree 15000 leftLeaningTree15
    let leftLeaningTree17 = mkLeftLeaningTree 15000 leftLeaningTree16
    let leftLeaningTree18 = mkLeftLeaningTree 15000 leftLeaningTree17
    let leftLeaningTree19 = mkLeftLeaningTree 15000 leftLeaningTree18
    let leftLeaningTree20 = mkLeftLeaningTree 15000 leftLeaningTree19
    let leftLeaningTree21 = mkLeftLeaningTree 15000 leftLeaningTree20
    let leftLeaningTree22 = mkLeftLeaningTree 15000 leftLeaningTree21
    let leftLeaningTree23 = mkLeftLeaningTree 15000 leftLeaningTree22
    let leftLeaningTree24 = mkLeftLeaningTree 15000 leftLeaningTree23
    let leftLeaningTree25 = mkLeftLeaningTree 15000 leftLeaningTree24
    let leftLeaningTree26 = mkLeftLeaningTree 15000 leftLeaningTree25
    let leftLeaningTree27 = mkLeftLeaningTree 15000 leftLeaningTree26
    let leftLeaningTree28 = mkLeftLeaningTree 15000 leftLeaningTree27
    let leftLeaningTree29 = mkLeftLeaningTree 15000 leftLeaningTree28
    let leftLeaningTree30 = mkLeftLeaningTree 15000 leftLeaningTree29
    let leftLeaningTree31 = mkLeftLeaningTree 15000 leftLeaningTree30

    let sizeContAcc tree =
      let rec worker acc tree cont =
        match tree with
          | Leaf _               -> cont (acc + 1)
          | Branch (left, right) -> worker acc left  (fun acc ->
                                    worker acc right cont)
      worker 0 tree id



    sizeContAcc leftLeaningTree31  |> printfn "%A"

    printfn "%A" argv
    0 // return an integer exit code

This is compiled with tail calls, optimize in Release mode:

C:\Program Files (x86)\Microsoft SDKs\F#\4.0\Framework\v4.0\fsc.exe -o:obj\Release\ConsoleApplication8.exe --debug:pdbonly --noframework --define:TRACE --doc:bin\Release\ConsoleApplication8.XML --optimize+ --platform:x64 -r:"C:\Program Files (x86)\Reference Assemblies\Microsoft\FSharp.NETFramework\v4.0\4.4.0.0\FSharp.Core.dll" -r:"C:\Program Files (x86)\Reference Assemblies\Microsoft\Framework.NETFramework\v4.6\mscorlib.dll" -r:"C:\Program Files (x86)\Reference Assemblies\Microsoft\Framework.NETFramework\v4.6\System.Core.dll" -r:"C:\Program Files (x86)\Reference Assemblies\Microsoft\Framework.NETFramework\v4.6\System.dll" -r:"C:\Program Files (x86)\Reference Assemblies\Microsoft\Framework.NETFramework\v4.6\System.Numerics.dll" --target:exe --warn:3 --warnaserror:76 --vserrors --LCID:1033 --utf8output --fullpaths --flaterrors --subsystemversion:6.00 --highentropyva+ --sqmsessionguid:057b9ccf-c89e-4da6-81ab-5295156e7a19 "C:\Users\userName\AppData\Local\Temp.NETFramework,Version=v4.6.AssemblyAttributes.fs" AssemblyInfo.fs Program.fs 1> ConsoleApplication8 -> C:\Users\userName\Documents\Visual Studio 2015\Projects\StackOverflow6\ConsoleApplication8\bin\Release\ConsoleApplication8.exe

So with 31 trees this works:

 .\ConsoleApplication8.exe
450001

Now let's compile this in Debug mode:

C:\Program Files (x86)\Microsoft SDKs\F#\4.0\Framework\v4.0\fsc.exe -o:obj\Debug\ConsoleApplication8.exe -g --debug:full --noframework --define:DEBUG --define:TRACE --doc:bin\Debug\ConsoleApplication8.XML --optimize- --tailcalls- --platform:anycpu32bitpreferred -r:"C:\Program Files (x86)\Reference Assemblies\Microsoft\FSharp.NETFramework\v4.0\4.4.0.0\FSharp.Core.dll" -r:"C:\Program Files (x86)\Reference Assemblies\Microsoft\Framework.NETFramework\v4.6\mscorlib.dll" -r:"C:\Program Files (x86)\Reference Assemblies\Microsoft\Framework.NETFramework\v4.6\System.Core.dll" -r:"C:\Program Files (x86)\Reference Assemblies\Microsoft\Framework.NETFramework\v4.6\System.dll" -r:"C:\Program Files (x86)\Reference Assemblies\Microsoft\Framework.NETFramework\v4.6\System.Numerics.dll" --target:exe --warn:3 --warnaserror:76 --vserrors --LCID:1033 --utf8output --fullpaths --flaterrors --subsystemversion:6.00 --highentropyva+ --sqmsessionguid:057b9ccf-c89e-4da6-81ab-5295156e7a19 "C:\Users\userName\AppData\Local\Temp.NETFramework,Version=v4.6.AssemblyAttributes.fs" AssemblyInfo.fs Program.fs 1> ConsoleApplication8 -> C:\Users\userName\Documents\Visual Studio 2015\Projects\StackOverflow6\ConsoleApplication8\bin\Debug\ConsoleApplication8.exe

And, oops:

> .\ConsoleApplication8.exe
Process is terminated due to StackOverflowException.

So what is the difference?

In the Release version there are 9 tail calls, if you decompile the IL, and I assume this is represented by some sort of while loop.

IL_0073: ldloc.s 6
IL_0075: tail.
IL_0077: call int32 [FSharp.Core]Microsoft.FSharp.Core.LanguagePrimitives/HashCompare::GenericComparisonWithComparerIntrinsic<!a>(class [mscorlib]System.Collections.IComparer, !!0, !!0)

In the Debug version, this will be missing:

L_007d: ldloc.s 6
IL_007f: call int32 [FSharp.Core]Microsoft.FSharp.Core.LanguagePrimitives/HashCompare::GenericComparisonWithComparerIntrinsic<!a>(class [mscorlib]System.Collections.IComparer, !!0, !!0)
IL_0084: ret

For a simpler example to test you can check this Question as it has both a recursive and tail recursive version of the algorithm.

Middleclass

Answer 2

My first guess was that you are stacking functions on top of each other in your cont argument, I understood it as a stack that might overflow (whereas it is a heap as explained by Wolfgang in a comment) but I did some tests using a cont argument and it didn't cause any stackoverflow. Instead, I had a significant slowdown and finally reached a memory overflow.

A solution to your specific problem would be to explicitly store the trees you will need to explore in a list (you will still be limited by the maximum size for a list) :

let sizeContAcc tree =
  let rec worker acc tree contList =
    match tree with
      | Leaf _ -> 
        match contList with
        | [] -> acc+1
        | t::cl -> worker (acc+1) t cl
      | Branch (left, right) -> worker acc left (right::contList)
  worker 0 tree []

It works and instantly gives me 150001 for leftLeaningTree6.

Hayfork

I don't think this is right - none of the operations in sizeContAcc should result in deeper stack frames like your (f >> f) example does. – Doreathadoreen

The term “stack” in “stack overflow” does not refer to any stack structure in an F# program. It refers to the system stack. An F# program internally uses a stack and a heap. While I am building kind of a stack of functions in my code, this nested function expression is build on the heap (which is larger than the stack); so it should not cause the system stack to overflow. The overflower and the nonOverflower in your example are fundamentally different. The former applies the function f exponentially often, the latter only linearily often. – Swore

Thank you Wolfgang, I just reread my code and you are indeed right. I removed the wrong example and added a remark based on further tests. – Hayfork