Computing memory usage?

Let us consider the following factorial example :

#include <iostream.h>

int factorial(int);

void main(void) {
    int number;

    cout << "Please enter a positive integer: ";
    cin >> number;
    if (number < 0)
        cout << "That is not a positive integer.\n";
    else
        cout << number << " factorial is: " << factorial(number) << endl;
}

int factorial(int number) {
    int temp;

    if(number <= 1) return 1;

    temp = number * factorial(number - 1);
    return temp;
}

How can I compute the memory used the function factorial() ? To be more precise I want to know how much memory the function uses ?

EDIT:

This is just a sample program and the program I'm working on is lot different and has many functions and I actually want to calculate the memory u开发者_StackOverflow中文版sage of every functions.

Since the function only uses stack memory, you can store the address of temp in a global variable just before you return 1, and compare that to the address of number:

#include <iostream.h>

int factorial(int);

void* tos;

void main(void) {
    int number;

    cout << "Please enter a positive integer: ";
    cin >> number;
    if (number < 0)
        cout << "That is not a positive integer.\n";
    else
        cout << number << " factorial is: " << factorial(number) << endl;

    cout << "factorial used " << ((char*)&number - (char*)tos) << " bytes of stack.\n";
}

int factorial(int number) {
    int temp;

    if(number <= 1) {
        tos = &temp;
        return 1;
    }

    temp = number * factorial(number - 1);
    return temp;
}

For my second answer (prompted by the comments to my first answer), you could use a function that computes how much of the stack has been touched. Here's one that hopefully doesn't make too many assumptions about the nature of the stack on a given architecture. It assumes a descending stack, which is a fairly safe bet for most people:

#define LU_RAND_SEED 123456789LU
#define LU_RAND(S) ((S) * 69069 + 362437 & 0XFFFFFFFFLU)

int depth(int maxdepth)
{
  unsigned long r = LU_RAND_SEED;
  int d = 0;
  unsigned long *stk = (unsigned long *)alloca(maxdepth);
  for (int i = maxdepth/sizeof(unsigned long); i--; )
    {
      r = LU_RAND(r);
      if (stk[i] != r)
        {
          stk[i] = r;
          d = i;
        }
    }
  return maxdepth - d*sizeof(unsigned long);
}

You call it once before the function you want to test, and once after. The second call will return how many bytes of the stack have been touched (minus some constant value that you'll have to determine experimentally). You have to make sure that only the code you are testing runs between the two calls to depth():

depth(512<<10);
int f = factorial(number);
int d = depth(512<<10);
cout << ... f ...

You also have to watch out for edge cases. For instance, if number is 0 or 1, the depth test fails for reasons I haven't figured out yet. And goodness knows what will happen if the compiler starts reusing stack slots. In a nutshell: caveat emptor.

Notes:

1. It almost goes without saying that this technique is probabilistic. If your function happens to populate all or part of the stack with the same data as the PRNG, the result may be compromised, though the probability of being more than a few bytes off is vanishingly small.
2. I lifted the PRNG from here. srand()/rand() or their thread-safe counterparts will probably work fine, but I wanted to avoid calling any function other than alloca().
3. unsigned long r = (unsigned long)&r; avoids the constant seed for slightly more randomness, and it works since if the two calls to depth() are made at different stack depths, this technique will fail anyway. I just don't know how safe the seeds thus generated will be.

Use profiling tool like http://code.google.com/p/google-perftools/

or valgrind

if you don't know how many recursions 'factorial' will have, it's impossible to determine how much memory it will consume. on 32 bit machine 1 recursion for this function should consume 8 bytes (4 bytes for return address and 4 bytes for argument)

Look at the map file that your compiler generates. This will show all the sizes.

1. Calculate the maximum call depth. (should be covered in any course on algorithmic analysis)

2. Find the stack usage per call (look at the assembly code for the function, don't forget to consult the CPU architecture manual to find out how much data a call instruction places on the stack.

3. Find the dynamic memory usage per call, looking for functions such as malloc and realloc, C++ operator new, and container classes such as std::vector.

4. Multiply.