5 ms·

I would note that determining maximum stack usage is similar to the halting problem in some cases. One must carefully restrict how the program is structured for

I would note that determining maximum stack usage is similar to the halting problem in some cases. One must carefully restrict how the program is structured for this analysis to be valid. As is stated, any sort of recursion or mutually dependent functions are out, and the use of function pointers could also cause issues. This approach provides a good baseline. However, I'd highly recommend empirical testing as well. For example, create a sufficiently large stack, initialize the stack with a known bit pattern and then check the high water mark after fully exercising the program.

eru 15y ago
I agree with your first two sentences. Why should recursion be out? You just need to be careful with it. Not having an infinite recursion is basically the same problem as not having an infinite loop.
- rgoddard 15y ago
  Since with recursion you can have a large but finite number of calls that could blow the stack, but not have the same problem with a for loop.
  - eru 15y ago
    Yes, you have to account for that. Also, tail recursion should be fine, if your compiler is smart enough. (I guess since the program is looking at assembly, it couldn't tell optimized tail recursion from a loop.)
- wlievens 15y ago
  If you want to prove the maximum stack usage of a recursive evaluation, you need to prove how deep it goes. Since that would depend on the inputs, you need to statically determine the limits on the inputs. It's all possible, but cases where it applies would be rare.
wlievens 15y ago
I worked on a compiler that did not support recursion, dynamic memory allocation or dynamic function calls (function pointers). We could statically guarantee the stack depth and thus the total memory usage of the program. You'll probably be wondering "what use could that crippled compiler probably have?". Well, most of the people here are carrying code emitted by it in their pocket.

eru 15y ago

I agree with your first two sentences. Why should recursion be out? You just need to be careful with it. Not having an infinite recursion is basically the same problem as not having an infinite loop.

rgoddard 15y ago
Since with recursion you can have a large but finite number of calls that could blow the stack, but not have the same problem with a for loop.
- eru 15y ago
  Yes, you have to account for that. Also, tail recursion should be fine, if your compiler is smart enough. (I guess since the program is looking at assembly, it couldn't tell optimized tail recursion from a loop.)
wlievens 15y ago
If you want to prove the maximum stack usage of a recursive evaluation, you need to prove how deep it goes. Since that would depend on the inputs, you need to statically determine the limits on the inputs. It's all possible, but cases where it applies would be rare.

wlievens 15y ago

I worked on a compiler that did not support recursion, dynamic memory allocation or dynamic function calls (function pointers). We could statically guarantee the stack depth and thus the total memory usage of the program. You'll probably be wondering "what use could that crippled compiler probably have?". Well, most of the people here are carrying code emitted by it in their pocket.