Why does moving a large binary tree lead to stack overflows even when using the continuation style?

Question

Chapter 9 of Expert F # 3.0 shows how to use the continuation style to avoid when moving binary trees. I wrote a tree traversal code that is almost identical to the code from the book, but nonetheless I get a stack overflow. 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 an F # interactive environment and evaluating the sizeContAcc leftLeaningTree6 expression makes the stack overflow. Why is this?

Answer 1

Unfortunately, this may not help you fix the problem, but it may contain some pointers to where to look. Firstly, code and customization. I myself have reduced the size of the tree so that it works 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://stackoverflow.com/questions/40477122/why-does-traversing-a-large-binary-tree-result-in-a-stack-overflow-even-when-usi 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, optimized in release mode:

C: \ Program Files (x86) \ Microsoft SDK \ 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 --systemystem: 6.00 --highentropyva + --sqmsessionguid: 057b9ccf-c89e-4da6- 81ab-5295156e7a19 "C: \ Users \ userName \ AppData \ Local \ Temp.NE TFramework, 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 SDK \ 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 --systemystem: 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?

There are 9 tail calls in the version version if you decompile IL, and I assume this is represented by some kind 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 absent:

 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 testing example, you can check this Question , since it has both a recursive and a tail recursive version of the algorithm.

Answer 2

My first assumption was that you put functions on top of each other in your cont argument, I understood it as a stack that can overflow (whereas this is a bunch, as Wolfgang explained in the comment), but I did some tests using the cont argument, and it did not call any stackoverflow. Instead, I had a significant slowdown and finally reached memory overflow.

The solution to your specific problem will be to explicitly store the trees that you need to explore in the list (you will still be limited by the maximum size for the 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.