Stack size under Mono

Question

I have written a tiny recursive bit of F# code to see how many levels of recursion I can fit onto the stack under .NET/Mono. It just prints the recursion depth whenever it is an exact power of 2, so I find out the maximum depth to within a factor 2.

I start the code in a thread with a defined amount of stack space using System.Threading.Thread (ThreadStart, int). Under .Net it seems to take approx 100 bytes per level of recursion, and I can get about 16 million levels on a 2G stack. The memory usage is broadly similar under Mono, however I can only get about 30 thousand levels. Increasing the stack size value passed to Thread past over about 600000 does not increase the recursion depth.

ulimit reports the stack size limit is 1G.

An obvious explanation is that Mono will not obey the second argument of Thread if it is too large. Does anybody please know how to convince Mono to allocate a large stack?

The code is trivial, but it's below just in case someone cares:

let rec f i =
    if popcount i = 1 then // population count is one on exact powers of 2
        printf "Got up to %d\n" i
        stdout.Flush ()
    if i = 1000000000 then 0 else 1 + f (i+1)

Answer 1

Option 1: Change Mono Stack Size

An obvious explanation is that Mono will not obey the second argument of Thread if it is too large. Does anybody please know how to convince Mono to allocate a large stack?

You are correct that Mono will limit the stack size, even if you pass in a large value. For example, on my Cent OS 64-bit test machine, the maximum stack size that Mono will allocate is 2 megabytes. The Mono C# source file Thread.cs shows us what happens when you create a Mono thread:

public Thread (ThreadStart start, int maxStackSize)
{
    if (start == null)
        throw new ArgumentNullException ("start");

    threadstart = start;
    Internal.stack_size = CheckStackSize (maxStackSize);
}

static int CheckStackSize (int maxStackSize)
{
    if (maxStackSize < 0)
        throw new ArgumentOutOfRangeException ("less than zero", "maxStackSize");

    if (maxStackSize < 131072) // make sure stack is at least 128k big
        return 131072;

    int page_size = Environment.GetPageSize ();

    if ((maxStackSize % page_size) != 0) // round up to a divisible of page size
        maxStackSize = (maxStackSize / (page_size - 1)) * page_size;

    int default_stack_size = (IntPtr.Size / 4) * 1024 * 1024; // from wthreads.c
    if (maxStackSize > default_stack_size)
        return default_stack_size;

    return maxStackSize; 
}

The code above puts a hard limit on the stack size.

You could in theory change code in one or both of the above functions (bold lines) so that a larger stack size is allocated. Once you did this you would have to build the Mono runtime and then run your function to see if the change makes a difference.

I should stress that I do not know enough about Mono to understand if allocating a larger stack will help in your specific case. I would only do this as a last resort (if neither of my other answers work).

Answer 2

Option 3: Make it Iterative

One option is to rewrite your method so that it is not recursive, but iterative. That is, you change the method so that it is a loop that calculates the results:

let f i =
    let mutable acc = 0
    for counter in i .. 1000000000 do
        // display progress every 10k iterations
        let j = counter % 10000
        if j = 0 then
            printf "Got up to %d\n" counter
            stdout.Flush ()

        if counter < 1000000000 then
            acc <- acc + 1
    acc

For input value 1:

let result = f 1
printf "result %d\n" result

The output:

Got up to 10000
Got up to 20000
Got up to 30000
...
Got up to 999980000
Got up to 999990000
Got up to 1000000000
result 999999999

For input value 999,999,998:

let result = f 999999998
printf "result %d\n" result

The output:

Got up to 1000000000
result 2

The code above uses two variables to keep track of progress:

acc - the accumulater, which stores the result of the calculation

counter - is simply the number of iterative calls (number of loops)

Since we are using a loop to calculate the result, there is not any additional stack allocated.

Answer 3

This code gets around the mono limit. It is useful for dfs in competitive programming.

        public static void IncreaseStack(ThreadStart action, int stackSize = 16000000)
        {
            var thread = new Thread(action, stackSize);
#if __MonoCS__
        const BindingFlags bf = BindingFlags.NonPublic | BindingFlags.Instance;
        var it = typeof(Thread).GetField("internal_thread", bf).GetValue(thread);
        it.GetType().GetField("stack_size", bf).SetValue(it, stackSize);
#endif
            thread.Start();
            thread.Join();
        }

Answer 4

Option 2: F# Tail calls

One option is to rewrite your method so that you use recursive tail calls. From the prior (Wikipedia) link:

A tail recursive function is a special case of recursion in which the last instruction executed in the method is the recursive call. F# and many other functional languages can optimize tail recursive functions; since no extra work is performed after the recursive call, there is no need for the function to remember where it came from, and hence no reason to allocate additional memory on the stack.

F# optimizes tail-recursive functions by telling the CLR to drop the current stack frame before executing the target function. As a result, tail-recursive functions can recurse indefinitely without consuming stack space.

There is a caveat - Mono does not fully support tail recursive calls - what you should do is to test first in the .Net runtime, and then see if the code will run in Mono.

Here is your sample function re-written using a tail recursive call - it does work in both .NET (using Visual Studio 2010) and Mono (Mono version 3.2.0, F# 3.0):

let f i =
    let rec loop acc counter =
        // display progress every 10k iterations
        let j = counter % 10000
        if j = 0 then
            printf "Got up to %d\n" counter
            stdout.Flush ()

        if counter < 1000000000 then
            // tail recursive
            loop (acc + 1) (counter + 1)
        else
            acc

    loop 0 i

For input value 1:

let result = f 1
printf "result %d\n" result

The output:

Got up to 10000
Got up to 20000
Got up to 30000
...
Got up to 999980000
Got up to 999990000
Got up to 1000000000
result 999999999

For input value 999,999,998:

let result = f 999999998
printf "result %d\n" result

The output:

Got up to 1000000000
result 2

The code above uses two variables to keep track of progress:

acc - the accumulator, which stores the result of the calculation

counter - is simply the number of recursive calls

Why is your sample code not tail recursive?

Paraphrasing the How To Write Tail-Recursive Functions section of the Wikipedia article, we can rewrite this line of your code:

if i = 1000000000 then 0 else 1 + f (i+1)

as

if i = 1000000000 then 0
else
    let intermediate = f (i+1) // recursion
    let result = 1 + intermediate // additional operations
    result

The very definition of tail recursion says that there cannot be additional operations after the recursive call. As we can see in the rewritten version of your code, there are additional operations required to produce the result.

Resources

• Tail calls in F# at MSDN
• F Sharp Programming/Recursion at Wikipedia
• Tail calls in Mono - a tail call example that does not work in Mono
• Tail call support in F# in the Mono bug tracker
• How can I implement a tail-recursive list append?