Thread: Techniques for keeping memory usage bounded, especially the stack

  1. #1
    Registered User
    Join Date
    Mar 2020
    Posts
    12

    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.

  2. #2
    Registered User
    Join Date
    Mar 2020
    Posts
    12
    Bump

  3. #3
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > 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 log2 of the number of functions in the program, excluding recursion.

    Efficient recursive functions like say qsort are log2 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)
            ^
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  4. #4
    Registered User
    Join Date
    Mar 2020
    Posts
    12
    I hadn't known of the -Wstack-usage option, I'll have to look into it, thank you.

  5. #5
    Registered User
    Join Date
    May 2012
    Posts
    505
    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.
    I'm the author of MiniBasic: How to write a script interpreter and Basic Algorithms
    Visit my website for lots of associated C programming resources.
    https://github.com/MalcolmMcLean


  6. #6
    Registered User
    Join Date
    Mar 2020
    Posts
    12
    Agree with the rest but

    Quote Originally Posted by Malcolm McLean View Post
    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?

  7. #7
    Registered User
    Join Date
    Apr 2020
    Posts
    4
    can someone telll me ; Are we able to "like" the people who provide replys?? ��

  8. #8
    Registered User
    Join Date
    Apr 2019
    Posts
    114
    Quote Originally Posted by mctrader07 View Post
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Keeping track of STL container memory usage
    By IceDane in forum C++ Programming
    Replies: 2
    Last Post: 03-30-2010, 03:57 PM
  2. Memory Usage
    By MK27 in forum Linux Programming
    Replies: 2
    Last Post: 07-16-2009, 05:52 PM
  3. Memory usage and memory leaks
    By vsanandan in forum C Programming
    Replies: 1
    Last Post: 05-03-2008, 05:45 AM
  4. Stack usage
    By esben in forum C Programming
    Replies: 4
    Last Post: 05-19-2006, 10:15 AM
  5. stack usage
    By linucksrox in forum C++ Programming
    Replies: 3
    Last Post: 03-26-2006, 08:53 AM

Tags for this Thread