I have a recursive function written in C++ that dynamically allocates 2D arrays using new.
How could I measure the total amount space function allocates on heap and stack during it's entire lifetime ?
Here is an example(it is not my code) of how to measure Stack.
unsigned int maxStackLocation ;
unsigned int minStackLocation ;
main ()
{
//get the address of a local variable before calling Quicksort
//the stack grows down, so this is the max stack location
int localVariable;
void *currPtrLocation = (void*)(&localVariable);
maxStackLocation = *(unsigned int *)(&currPtrLocation);
//we get the value for the minimum stack location in quicksort itself
//call quicksort
Quick (A, num);
space = maxStackLocation - minStackLocation;
}
//some redundant function whose stack usage will be measured
void Quick (unsigned int A[], int num)
{
if (num <= 1)
{
//check the stack usage
//figure out where we are on the stack by looking at the byte
// address of the local variable
//we do this by making a pointer to a local variable, and then
//casting it to a integer
void *currPtrLocation = (void*)(&num);
unsigned int currStackLocation = *(unsigned int*)(&currPtrLocation);
if (currStackLocation < minStackLocation)
minStackLocation = currStackLocation;
return;
}
}
Edit
Borgleader points out that my original question "Measuring max space function allocates on heap and stack during it's entire lifetime" is incorrect. I have changed "max" to "total".
Your example for measuring stack usage is spot-on, and will give you a (very nearly) correct answer. I have a suggestion for determining heap usage as well, but first....
In his book “More Effective C++” in item 27, Scott Meyers (incidentally my favorite author on C++) describes why it’s not possible in the general sense and within the bounds of portable or semi-portable C++ to definitively distinguish whether an object has been allocated on the stack, heap, or is statically allocated. But his explanation pertains to allocated objects from the perspective of the objects themselves, not allocations from the perspective of the code that requests such an allocation. From the perspective of code that requests an allocation you can know with certainty whether an object, regardless of its type, is allocated on the heap or stack based on how you requested its allocation. (Sidebar: Of course this depends on your system actually using a runtime stack, which some are quick to point out that the C++ standard does not guarantee, yet none of these standards snobs ever point out any real-world example of an otherwise standard-conforming C++ compiler that does not use a runtime stack. Back to our discussion...) For example:
int Fred; // Fred is allocated on the stack
int *Barney = new int; // Barney is allocated on the heap
Fred will destruct when he goes out of scope; you must explicitly delete Barney when you’re done with him. This works the same for user-defined types, including STL types:
std::string Fred; // Fred is allocated on the stack (see disclaimer*)
std::string *Barney = new std::string(); // Barney is allocated on the heap
// *Disclaimer: May not be totally true on some small embedded processors that
// implement the runtime stack in a special small address space
// separate from “normal” RAM.
...BUT: Though the std::string object known as Fred is itself allocated on the stack, we know of course that its data cannot be stack-allocated, because its data is variable-length and must be able to expand indefinitely as we add characters to it. So only the management portion of a std::string (i.e. the std::string object itself) can be stack-allocated.
Back to Scott Meyer’s item 27 and it applicability to this discussion:
myClass *someFunction() {
int someInputParameter = 42;
myClass Fred(someInputParameter); // Fred is allocated on the stack
myClass *Barney = new myClass(someInputParameter); // Barney is allocated on the heap
return Barney;
}
According to Scott Meyer’s item 27, neither Fred nor Barney can know for themselves whether they are stack- or heap-allocated, or for that matter, statically-allocated (i.e. “global” or “file scope” or a “static member of some other class”). But within someFunction(), we can know because we know how we requested the allocation.
Now, back to your problem:
As I said, the example you show for measuring stack usage is spot-on. You know for certain in main() that ‘localVariable’ is allocated on the stack. And you know for certain in Quick() that ‘currPtrLocation’ is on the stack. And if your stack grows down, you know for certain that because main() calls Quick(), the address of ‘currPtrLocation’ in Quick() will be lower than the address of ‘localVariable’ in main(), so your arithmetic works. It won’t give a perfectly correct answer because there may be other variables in Quick() that are allocated at stack locations yet lower than ‘currPtrLocation’, but your measurement will be really close; certainly as close as you should care about. Whatever the error amount is, it’s a fixed error regardless of how deep your call stack goes, and if you recurse any significant number of times, the error as a percentage of the whole will be negligible. One last thing: If you want the solution to be portable even to systems where the stack grows UP, you can detect the direction of the difference between the address of ‘localVariable’ and ‘currPtrLocation’ and compute the difference (i.e. swap the arguments in the subtraction) accordingly.
Regarding heap usage:
Your system may have hooks you can tie into for measuring heap usage stats, but if you don’t want to delve into that, you can do something along the lines of what Synxis proposed, but there are some serious problems with that answer. First of all, Synxis's suggestion misses all of the stack overhead, including return addresses, spilled registers, etc, which are not insignificant. Second, if you use the stack measuring technique like you show in your question, there’s no need to painstakingly maintain a sum of allocations for stack-allocated objects anyway. Third, assuming you only sum the allocations of heap-allocated objects (whose size you can get with the sizeof() operator), you can’t just keep summing them. You’d have to subtract the allocations’ sizes when you delete them so your “totalSize” maintains the total size of all currently allocated objects, and you’d want to separately keep track of the high-water-mark of the totalSize. That way you can know the largest amount of memory that your algorithm used at any one time. Without doing that, you might be confused when your algorithm reports that it used something like 758 Gigabytes even though you only have 4G of RAM. And finally, whether you allocate a given object itself on the stack or heap, it may make its own internal allocations on the heap. (If it makes temporary allocations on the stack when you call a method on that object, unless you put your stack-tracking code in that method as well, your stack total won't be exactly correct as I already described, but the error will continue to be more-or-less constant, depending on whether the method executes conditionals that might alter its calling behavior.) Anyway, regarding this "given object" that you allocate on the stack or heap; if it allocates its own internal heap memory, unless you add heap allocation tracking to the internal objects, you'll miss whatever amount of heap memory was allocated to those internal objects. So maybe you'd be better off looking into the heap stats hooks your system might make available.
Now, assuming you want to do track heap allocations yourself... Another option you might explore would be to write a base class from which your algorithm can derive for all of the objects it creates. Your base class could override operator new & operator delete such that the base class itself does all of the totalSize tracking (adding for ‘new’ and subtracting for ‘delete’) using a static class variable in the base class.