Stack usage

[Michael Sig Birkmose]

Hi everyone!

Does anyone know, if it is possible to meassure the maximum stack usage of
a C program throughout it's entire execution?

 

[Martin Dickopp]

Does anyone know, if it is possible to meassure the maximum stack
usage of a C program throughout it's entire execution?

There is no way to do this in standard C. However, your compiler
might provide a way. Compiler-specific questions are off-topic in
comp.lang.c, so please ask in a group dedicated to your compiler.

Martin

 

[Lew Pitcher]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Michael Sig Birkmose wrote:
| Hi everyone!
|
| Does anyone know, if it is possible to meassure the maximum stack usage of
| a C program throughout it's entire execution?

It may be, but it is irrelevant here. As far as standard C is concerned, there
is no such thing as a 'stack'. The C standards don't dictate how dynamic
allocations are to be managed 'under the covers'.


- --
Lew Pitcher

Master Codewright & JOAT-in-training | GPG public key available on request
Registered Linux User #112576 (http://counter.li.org/)
Slackware - Because I know what I'm doing.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFAtS7nagVFX4UWr64RAm+XAJ4yqmD3ENetUagtv05GXo09dTWcbgCgj/ey
KJxr+b8pf6f76e04Bcwp2FA=
=Nu8R
-----END PGP SIGNATURE-----

 

[Rob Thorpe]

Hi everyone!

Does anyone know, if it is possible to meassure the maximum stack usage of
a C program throughout it's entire execution?

If your platform uses a stack, and as previous posters have mentioned
it is not gauranteed to do so, then it's normally possible.

* At the beginning of the program take the address of a automatic
variable and store it.
* Find out which way the stack grows on your architecture.
* At any point in the program, call a function that creates an
automatic variable, take it's address. Compare it to the previously
stored address.

This is not gauranteed to work. To find the best way to do it ask on
an architecture specific newsgroup.

 

[Peter Nilsson]

Michael Sig Birkmose wrote:
| Hi everyone!
|
| Does anyone know, if it is possible to meassure the maximum stack usage of
| a C program throughout it's entire execution?

It may be, but it is irrelevant here. As far as standard C is concerned, there
is no such thing as a 'stack'. ...

Well, yes there is. It just isn't ever explicitly called a stack. But
the behaviour of function calls is well defined and consistent with
the notion of stacks.

 

[Dan Pop]

Does anyone know, if it is possible to meassure the maximum stack usage of
a C program throughout it's entire execution?

Not using portable C code.

Dan

 

[CBFalconer]

Well, yes there is. It just isn't ever explicitly called a stack.
But the behaviour of function calls is well defined and
consistent with the notion of stacks.

Nonsense. I can fairly easily design a machine with no stack, no
call instruction, and have it execute C programs.

 

[Dan Pop]

If your platform uses a stack, and as previous posters have mentioned
it is not gauranteed to do so, then it's normally possible.

It's hard to implement a language like C without using a stack data
structure. It is immaterial whether the underlying hardware has any
support for automatically managing it or not.

* At the beginning of the program take the address of a automatic
variable and store it.
* Find out which way the stack grows on your architecture.
* At any point in the program, call a function that creates an
automatic variable, take it's address. Compare it to the previously
stored address.

You can't perform such comparisons without invoking undefined behaviour.
You have to convert the addresses to the largest unsigned type available
and hope that it is large enough for your purpose (or to uintptr_t in
C99). Then, subtract the smaller value from the larger one.

This is not gauranteed to work.

Indeed, not even my improved approach is guaranteed to work. Depending
on the program, even figuring out what is the point where the stack has
the greatest length may be far from trivial.

Dan

 

[Michael Wojcik]

Well, yes there is. It just isn't ever explicitly called a stack. But
the behaviour of function calls is well defined and consistent with
the notion of stacks.

It's consistent with the notion of garbage-collected continuations,
too. Or with the notion of activation frames. So would you say that
as far as the Standard is concerned, C has garbage-collected
continuations and activation frames as well as a stack?

That something is consistent with the Standard is not an argument
that it is implied by the Standard. And there are other mechanisms
for implementing the behavior of function calls as described by the
Standard which do not use stacks. So I'd say you're 0 for 2 on that
one.

Prolepsis: Spare me the "show me an implementation that doesn't use
stacks" argument.

 

[Dan Pop]

Nonsense. I can fairly easily design a machine with no stack, no
call instruction, and have it execute C programs.

You forgot to engage your brain while reading Peter Nilsson's post.

It doesn't matter how function calls work, implementing C without at least
one stack data structure, even if conceivable, is not going to happen,
due to QoI reasons.

Dan

 

[Malcolm]

Prolepsis: Spare me the "show me an implementation that doesn't > use stacks" argument.

There's a difference between useful and useless pedantry. If the Op said
"how much automatic storage" he would have been more correct, but harder to
understand.

If a program contains no recursive functions you can measure the deepest
leaf, and barring library functions that is your stack usage.

Often by taking the address of a variable, and subtracting from a variable
in main(), you will get an idea of the size of the stack, but this technique
isn't strictly portable, and inf act is technically UB.

 

[Michael Wojcik]

It doesn't matter how function calls work, implementing C without at least
one stack data structure, even if conceivable, is not going to happen,
due to QoI reasons.

And what QoI reasons would those be?

 

[Michael Wojcik]

There's a difference between useful and useless pedantry.

Is that supposed to be a sequitur?

If the Op said
"how much automatic storage" he would have been more correct, but harder to
understand.

Is that?

If a program contains no recursive functions you can measure the deepest
leaf, and barring library functions that is your stack usage.

Except that 1) there still isn't any "stack" to be used in Standard
C, and 2) there still isn't any way to "measure the deepest leaf"
in Standard C, which makes this entirely off-topic.

If you have a language with first-class dynamic functions, you can
transform any recursive program into an iterative one by converting
all recursion to tail recursion with continuations, and then
rewriting the tail recursion as branching. And of course you can
perform this transformation manually and just slap all of your code
into main(), and use no automatic storage at all (except for main's
return value, and possibly argc and argv, if you wish to use them).
So what?

There's only one correct answer to the OP's question: a given C
implementation may have a thing called a stack, and it may
correspond to automatic storage, and there may be a way to
measure it; but all of these depend on the implementation.

 

[Malcolm]

2) there still isn't any way to "measure the deepest leaf"
in Standard C, which makes this entirely off-topic.

That's another example of useless pedantry. Of course there is no way of
preventing a perverse compiler from generating massive amounts of arbitrary
padding and making it impossible to determine which function is deepest.

However compilers aren't written by perverse people.

 

[Keith Thompson]

Nonsense. I can fairly easily design a machine with no stack, no
call instruction, and have it execute C programs.

I suppose it depends on your definition of "stack". If you limit the
definition to a consecutively allocated region of memory which grows
or shrinks in a particular direction, whose top is denoted by a
machine register, then of course you can implement C on a machine with
no stack. (The above definition is admittedly sloppy; it's intended
to refer to what's usually called "the stack" in the context of a CPU
architecture.)

On the other hand, if you use a more abstract definition that refers
only to how the thing behaves, and not to how it's stored in memory,
then C's function call semantics do imply the existence of a stack.
The activation records (not a C term) for nested function invocations
needn't be allocated consecutively in memory. It needn't even be
meaningful to ask about the order in which they're stored, since you
can't necessarily compare their addresses. Some or all of them could
be allocated in advance and/or deallocated long after the function
terminates, if ever. But there is a last-in first-out stack-like
pattern to the way local variables begin and end their lifetimes.

 

[kal]

Hi everyone!

Does anyone know, if it is possible to meassure the maximum stack usage of
a C program throughout it's entire execution?

Yes, it can be "sort of" done. But it will be implementation
specific and you have to make a lot of assumptions.

For a robust method you will have to modify the compiler's
code generation process. For GNU CC, start with the
"-fstack-check" option and go on from there.

For a naive attempt, take a look at the following code. Note
that on this implementation the stack grows DOWN. This won't
always work. The chances of it working are better if the
machine is quiescent.

<code>
#include <stdio.h>

const int con_pattern = 0xabc00def;

int main(int argc, char* argv[])
{
int i;
int *pi;

pi = &i;
for (i=4; i<1000; i++)
*(pi-i) = con_pattern;

/*
Rest of the code.
*/

printf("%d %d %d %d %d %d\n",1,2,3,4,5,6);

for (i=999; i>3; i--)
if (*(pi-i) != con_pattern)
break;

printf("%d\n",i);

return i;
}
</code>

Here is the output.
<output>
1 2 3 4 5 6
390

</output>

 

[Richard Bos]

That's another example of useless pedantry. Of course there is no way of
preventing a perverse compiler from generating massive amounts of arbitrary
padding and making it impossible to determine which function is deepest.

You don't understand what he's saying. There is _no_ way to predict, in
advance, what path an arbitrarily complex program with arbitrary human
input is going to take. It is tantamount to the halting problem.
Moreover, even if you could, there is no way for you to know how much
memory each call takes; not just because of _arbitrary_ padding, but
also because of necessary padding, additional bookkeeping data, and the
influence of things like inlining.

However compilers aren't written by perverse people.

<Looks at gcc and M$VC> Erm, I might disagree in at least two cases.

Richard

 

[Dan Pop]

And what QoI reasons would those be?

Run time efficiency. Maintaining a stack-like data structure has lower
overhead than the alternatives.

Dan

 

[Michael Wojcik]

That's another example of useless pedantry.

Perhaps you think being correct and critically examining your
assumptions is useless. I don't.

Of course there is no way of
preventing a perverse compiler from generating massive amounts of arbitrary
padding and making it impossible to determine which function is deepest.

I didn't say there wasn't any way to determine the deepest leaf;
I said there wasn't any way to measure it (without information about
the implementation which the implementation is not required to
provide).

 

[Rob Thorpe]

It's hard to implement a language like C without using a stack data
structure.

I didn't think of that, you're right.

It is immaterial whether the underlying hardware has any
support for automatically managing it or not.


You can't perform such comparisons without invoking undefined behaviour.
You have to convert the addresses to the largest unsigned type available
and hope that it is large enough for your purpose (or to uintptr_t in
C99). Then, subtract the smaller value from the larger one.


Indeed, not even my improved approach is guaranteed to work.

Yep, for instance it does not work on a Cray.