Techniques for keeping memory usage bounded, especially the stack

Stack allocation naturally has several advantages, such as not having to worry about freeing memory after allocation etc. (It has some disadvantages too, like not having as refined a control as dynamic allocation as to when an item is freed; "freeing" only occurs when the function call ends). However the danger with allocating on the stack is that of stack smashing, a very big danger indeed. What techniques do you use to determine beforehand (if possible) maximum memory usage bounds (naturally this would require keeping track of the possible call graphs especially wrt recursion)?

Also, what are some techniques to determine memory bounds beforehand in general including for dynamic allocation using malloc() and such?

For example, some things would be hard/impossible to predict before hand like say a linked list that is populated by the user, but there are many cases where it might be quite possible to compute bounds beforehand by various static analysis techniques.

Bump

> However the danger with allocating on the stack is that of stack smashing, a very big danger indeed.
No less dangerous than heap smashing, but certainly more immediately obvious.
If you write bad code, then it really doesn't matter where you allocate the memory, you're screwed either way.

> What techniques do you use to determine beforehand (if possible) maximum memory usage bounds
> (naturally this would require keeping track of the possible call graphs especially wrt recursion)?
On a desktop environment, I generally don't care at all.
The default stack in such an environment is typically in the megabytes - that's a lot of stack frames (like 1000's).

As a rough guess, the typical deepest stack (number of functions) is somewhere between the square root of the number of functions, and log₂ of the number of functions in the program, excluding recursion.

Efficient recursive functions like say qsort are log₂ of their input size. So 1 million records would be around 20 frames, 1 billion records would be around 30 frames.

Bad recursive functions, like say a naive Fibonacci, typically start taking too long to be of any practical use before their recursion gets near to being deep enough to be a problem.

Mind you, doesn't stop the newbies from trying int array[1000][1000], which we usually see every couple of months on the forums.

But hey, if you're curious, use -Wstack-usage on your GCC command line.

Code:

---

$ g++ -std=c++11 -Wall -Wstack-usage=512 proj.cpp
proj.cpp: In function ‘std::__cxx11::string test0()’:
proj.cpp:8:8: warning: stack usage is 576 bytes [-Wstack-usage=]
 string test0(void)
        ^
proj.cpp: In function ‘std::__cxx11::string test1()’:
proj.cpp:20:8: warning: stack usage is 640 bytes [-Wstack-usage=]
 string test1(void)
        ^
proj.cpp: In function ‘std::__cxx11::string test2()’:
proj.cpp:34:8: warning: stack usage is 640 bytes [-Wstack-usage=]
 string test2(void)
        ^

---

I hadn't known of the -Wstack-usage option, I'll have to look into it, thank you.

You need to know where your data comes from. Is it entered by the user at run time, read from a file but ultimately entered by a human, or generated by some automatic recording device?
If the first, it's unlikely that a user can enter more than a megabyte or so of information. If the second, about a gigabyte will usually cover the worst case scenario. If the last, you
need to know what sort of recording device is attached to the computer. Is it an audio microphone, a video camera, a temperature sensor, an image scanner? You need to calculate
how much data is likely to arrive, and how the memory you have corresponds to the worst case.
Remember that for most proograms, the memory take is dominated by one or two items, and everything else can be ignored. Also, memory is usually cheap in relation to the value
of the data. So you can usually assume that users will be willing to pay for a generous margin of extra capacity which is unlikely to be used. The exception is when the memory
size is limited by the processor rather than the ability of the user to buy memory chips, as happened recently when 32 bit systems were limited to 4GB. However that situation
wasn't allowed to persist for long.

In C, it is best to keep big items off the stack, and to pass in a depth sanity parameter to limit recursion. Another technique is to iterate over the siblings, recurse over the children -
most real data is wider than it is deep. These rules don't necesarily apply to other languages, which can manage things differently under the hood.

Agree with the rest but

Quote:

---

Originally Posted by Malcolm McLean

memory is usually cheap

---

hard disagree

Why else would I be asking questions for a language that favors manual memory management, and all things being equal, has a relatively smaller footprint than other languages?

can someone telll me ; Are we able to "like" the people who provide replys?? ��

Quote:

---

Originally Posted by mctrader07

can someone telll me ; Are we able to "like" the people who provide replys?? ��

---

Like it, love, hate it or be indifferent. When you live in the REAL world, all feeling/thought are possible.