Is there a stack size limit for function calls?

[sethmachine]

Hi,

Is there a limit to how large of a stack a function call can lead to?

So if I have a recursive function, is there a limit to how many times it can call itself starting from the very first call?

A recursive function of mine is crashing, but only when the size of the problem set gets high enough. I want to know if it's because it's blowing the stack.

For exact figures, when the first function call will lead to about 700 recursive calls, the function crashes at some point.

 

[Nestharus]

There is both a stack limit and an op limit.

The stack limit can be observed with nested trigger evaluations.

To avoid the stack limit, linearize your algorithms.

To avoid the op limit, split your algorithms into trigger evaluations and use counters.

 

[sethmachine]

I lack the creativity and know-how to figure out those values, but is my question related to them?

And also I've got no idea what an OP limit is.

For example if I write this:

function foo takes integer iterations returns nothing
  local integer i = 0
  local integer limit = 5
  loop
    exitwhen i == 5
    call foo(iterations - 1)
    set i = i + 1
  endloop
endfunction

Will these calls all go to completion?

call foo(3)

call foo(5)

call foo(50)

call foo(100)

 

[Nestharus]

Test it and find out.

Put the function into a trigger and evaluate the trigger. At the start of the trigger, set a boolean to false. At the end, set that boolean to true. Outside of the trigger, if the boolean is false, the thread crashed.

I'm not going to do that for you


Trigger

set b = false
call foo(100)
set b = true

 

[sethmachine]

Fair enough. I figured if the stack or op limit were a fixed constant you could just tell me that value.

But I googled "how to linearize an algorithm" and nothing came up. No general process like this:

'Take your non-linear algorithm A and apply these steps. It will then be a linear algorithm.'

So I am guessing you mean avoid recursion? I have a feeling foo(100) will crash (everytime I hit about 700 calls my function crashed).

If I wanted to "compute" foo(100) (ignore the fact it just does nothing), that is I want to be able to make that many calls dynamically, how would I linearize it, as you say it.

 

[Nestharus]

It's a bit more than that, but anyways.

First, you would want to remove all recursion.

Next, you would want to split your algorithm up into different triggers.

Finally, you want 1 trigger for each loop. You evaluate the triggers until the function is done.

See AES or MD5 for examples in "My Resources"

BigInt is probably the biggest example of this with algorithms spreading across 3 triggers.

It will be ugly and it will require effort. You will also have to fine tune it.

 

[sethmachine]

It's a bit more than that, but anyways.

First, you would want to remove all recursion.

Next, you would want to split your algorithm up into different triggers.

Finally, you want 1 trigger for each loop. You evaluate the triggers until the function is done.

See AES or MD5 for examples in "My Resources"

BigInt is probably the biggest example of this with algorithms spreading across 3 triggers.

It will be ugly and it will require effort. You will also have to fine tune it.

Ah so you do know the exact value? My function should make 781 calls (it goes 5^0 + 5^1 + 5^2 + 5^3 + 5^4 = 781), so if it's crashing because of that, then I know it can't be more than 781. I suppose you're not telling me because I can go now and find it myself through testing.

I think I understand what you are saying, and I agree it would make things super ugly. I am using a recursive algorithm because I'm taking advantage of the recursive structure of my struct. It kind of defeats the whole purpose and simplicity to have to linearize it, but I guess that is the tradeoff.

When you say linearize you mean we're just dividing up the total calls so they each get their own limit. This should be easy if everything is independent of each other (e.g. making 10000 units). Ideally each trigger should make the maximum number of calls possible so we have as fewest triggers as possible (but that would require knowing the stack limit).

 

[WaterKnight]

Without trigger evaluations it's more likely the operation limit. Do you know what a thread is in wc3? One can only execute a limited amount of instructions before it terminates. This is a safety measure of Blizzard to avoid infinite loops and heavy game freezes. A thread can do up to 300k micro-ops but since e.g. loops are dynamic and a lot of stuff is counted therein, it's difficult/not generalizable to tell how pricey a function is.

 

[Cokemonkey11]

1. Myself, and I assume Nestharus as well, don't know the precise stack limit because there's never an application where you should be approaching it. (Function calls in JASS are expensive)

2. No one is giving you a value for the op-limit because different natives put different loads on the op-limit counter.

3. http://en.wikipedia.org/wiki/Inline_function is the process or unraveling repeating code, be it by recursion, looping, or nested function calls. (Not linearizing nestharus)

Inlining functions in real programming languages has applications in reducing complexity (dynamic programming), memoization, tail-recursion optimization, and branch optimizations.

Inlining functions in jass is useful because calling functions wastes precious operations (expensive)

 

[Nestharus]

No one is giving you a value for the op-limit because different natives put different loads on the op-limit counter.

op limit is known, I just don't know the number off the top of my head

my bad . Yea, I knew that linearization was the wrong term, but for some reason couldn't think of the right term .

 

[sethmachine]

So if all this is the case in real world programming too, why do they even teach recursion? Many problems require billions of iterations (e.g. approaching the global maximum of some crazy function).

 

[Nestharus]

It is very rare for you to get a stack overflow error as a result of recursion in a program. There are some cases where this will certainly happen, and for that you can just move out of recursion, but it is still rare.

 

[Cokemonkey11]

So if all this is the case in real world programming too, why do they even teach recursion? Many problems require billions of iterations (e.g. approaching the global maximum of some crazy function).

Recursion is a highly readable, highly concise, beautiful way to describe some algorithms. Additionally, different languages have different features. In haskell for example, recursion can be the only way to describe an algorithm - but it's okay because processes like tail-call optimization and memoization are automatic. Most of those optimizations I named are automatically done by high performance C family compilers as well. When you have such well made compilers and tools, the more readable solution is almost always the best one.

In Java that's not the case - there are some optimizations done by the compiler but for the most part, recursion still has a fair amount of room to mature to be on par with languages like Haskell.

In JASS, essentially none of the optimizations exist, and so you have to be very picky in determining readability versus good performance.

For a GREAT example of why inlining is powerful (in compilers and manually in languages like jass), see slides 1-5 http://www.inf.ed.ac.uk/teaching/courses/ads/Lects/lecture9.pdf

It is very rare for you to get a stack overflow error as a result of recursion in a program. There are some cases where this will certainly happen, and for that you can just move out of recursion, but it is still rare.

It's not so rare in Java, but I understand you're a C# guy. I don't know what C# optimizations are around but I imagine they're similar to java.

 

[Nestharus]

i like java more tbh >.>