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?

--
Michael Birkmose

[Martin Dickopp]

Michael Sig Birkmose <mi*****@gisp.dk> writes:

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
--
,--. Martin Dickopp, Dresden, Germany ,= ,-_-. =.
/ ,- ) http://www.zero-based.org/ ((_/)o o(\_))
\ `-' `-'(. .)`-'
`-. Debian, a variant of the GNU operating system. \_/

[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+XAJ4yqmD3ENetUagtv05GXo 09dTWcbgCgj/ey
KJxr+b8pf6f76e04Bcwp2FA=
=Nu8R
-----END PGP SIGNATURE-----

[Rob Thorpe]

Michael Sig Birkmose <mi*****@gisp.dk> wrote in message news:<20*******************@server.gisp.dk>...

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]

Lew Pitcher <lp******@sympatico.ca> wrote...

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.

--
Peter

[Dan Pop]

In <20*******************@server.gisp.dk> Michael Sig Birkmose <mi*****@gisp.dk> writes:

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
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de

[CBFalconer]

Peter Nilsson wrote:

Lew Pitcher <lp******@sympatico.ca> wrote...

Michael Sig Birkmose wrote:
|
| 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.

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

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!

[Dan Pop]

In <1a**************************@posting.google.com > ro***********@antenova.com (Rob Thorpe) writes:

Michael Sig Birkmose <mi*****@gisp.dk> wrote in message news:<20*******************@server.gisp.dk>...

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.

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
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de

[Michael Wojcik]

In article <63**************************@posting.google.com >, ai***@acay.com.au (Peter Nilsson) writes:

Lew Pitcher <lp******@sympatico.ca> wrote...

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.

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.

--
Michael Wojcik mi************@microfocus.com

Please enjoy the stereo action fully that will surprise you. -- Pizzicato Five

[Dan Pop]

In <40***************@yahoo.com> CBFalconer <cb********@yahoo.com> writes:

Peter Nilsson wrote:

Lew Pitcher <lp******@sympatico.ca> wrote...

Michael Sig Birkmose wrote:
|
| 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.

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
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de

[Malcolm]

"Michael Wojcik" <mw*****@newsguy.com> wrote in message

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]

In article <c9*********@sunnews.cern.ch>, Da*****@cern.ch (Dan Pop) writes:

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 mi************@microfocus.com

[Michael Wojcik]

In article <c9**********@news7.svr.pol.co.uk>, "Malcolm" <ma*****@55bank.freeserve.co.uk> writes:

"Michael Wojcik" <mw*****@newsguy.com> wrote in message

Prolepsis: Spare me the "show me an implementation that doesn't
use stacks" argument.
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.

--
Michael Wojcik mi************@microfocus.com

Even though there may be some misguided critics of what we're trying
to do, I think we're on the wrong path. -- Reagan

[Malcolm]

"Michael Wojcik" <mw*****@newsguy.com> wrote in message

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]

CBFalconer <cb********@yahoo.com> writes:

Peter Nilsson wrote:

Lew Pitcher <lp******@sympatico.ca> wrote...

Michael Sig Birkmose wrote:
|
| 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.

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.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[kal]

Michael Sig Birkmose <mi*****@gisp.dk> wrote in message news:<20*******************@server.gisp.dk>...

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]

"Malcolm" <ma*****@55bank.freeserve.co.uk> wrote:

"Michael Wojcik" <mw*****@newsguy.com> wrote in message

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.

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]

In <c9********@news4.newsguy.com> mw*****@newsguy.com (Michael Wojcik) writes:

In article <c9*********@sunnews.cern.ch>, Da*****@cern.ch (Dan Pop) writes:

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?

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

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de

[Malcolm]

"Richard Bos" <rl*@hoekstra-uitgeverij.nl> wrote in message

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.

Comparing the drawing of a call-tree, even of a large program, to the
halting problem is ridiculous.
There are problems with recursive functions, and with function pointers
(this last more theoretical than a real issue), but for most structured
programs it should not be too difficult.

[Rob Thorpe]

Da*****@cern.ch (Dan Pop) wrote in message news:<c9**********@sunnews.cern.ch>...

In <1a**************************@posting.google.com > ro***********@antenova.com (Rob Thorpe) writes:

Michael Sig Birkmose <mi*****@gisp.dk> wrote in message news:<20*******************@server.gisp.dk>...

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.

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.

* 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.

Yep, for instance it does not work on a Cray.
Depending
on the program, even figuring out what is the point where the stack has
the greatest length may be far from trivial.

[Michael Wojcik]

In article <c9**********@news8.svr.pol.co.uk>, "Malcolm" <ma*****@55bank.freeserve.co.uk> writes:

"Michael Wojcik" <mw*****@newsguy.com> wrote in message

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.

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).

--
Michael Wojcik mi************@microfocus.com

[Michael Wojcik]

In article <c9***********@sunnews.cern.ch>, Da*****@cern.ch (Dan Pop) writes:

In <c9********@news4.newsguy.com> mw*****@newsguy.com (Michael Wojcik) writes:

In article <c9*********@sunnews.cern.ch>, Da*****@cern.ch (Dan Pop) writes:

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?

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

I figured that was what you meant. However, run-time efficiency is
not the sole metric of quality, and an implementation could prefer
a mechanism other than a (contiguous) stack for at least two reasons:
robust response to undefined behavior, and providing extensions to
the language (such as call-with-current-continuation).

Indeed, I think a C implementation that used non-contiguous activation
records with guard pages for function calls would be very handy
indeed, for development code - similar to an Electric Fence but for
activation records (and anything stored adjacent to them).

--
Michael Wojcik mi************@microfocus.com

Unlikely predition o' the day:
Eventually, every programmer will have to write a Java or distributed
object program.
-- Orfali and Harkey, _Client / Server Programming with Java and CORBA_

[Martin Dickopp]

"Malcolm" <ma*****@55bank.freeserve.co.uk> writes:

"Richard Bos" <rl*@hoekstra-uitgeverij.nl> wrote in message

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.

Comparing the drawing of a call-tree, even of a large program, to the
halting problem is ridiculous.

"Large" is not the same as "arbitrary". In fact, a program small enough
that it can be posted here suffices to show that drawing a call tree for
an arbitrary program is impossible.

Image a function `p' with the following prototype:

int p (const char *);

This function should accept C source code (in the form of a string) as
an argument. I don't require it to draw a complete call tree; all it
has to do is to determine whether the code passed as argument calls a
function `f'. If yes, it should return a nonzero value, otherwise zero.
Do you think such a function could in principle be written?

Consider the following translation unit. It should be linked together
with the implementation of the `p' function, and it should be stored
in a file `t.c' (so that it can read its own source code by reading a
text file `t.c').

#include <stdio.h>
extern int p (const char *);
void f (void) { }

int main (void)
{
FILE *fp;
char mycode [10000];

fp = fopen ("t.c", "r");
if (fp != NULL)
{
const size_t n = fread (mycode, 1, sizeof mycode - 1, fp);
fclose (fp);
mycode [n] = '\0';
if (!p (mycode))
f ();
}

return 0;
}

Let's assume for simplicity that no read error occurs when the program
reads its own source code. What will `p' return? Will it claim that
the code calls `f' or will it claim that it doesn't?

Martin
--
,--. Martin Dickopp, Dresden, Germany ,= ,-_-. =.
/ ,- ) http://www.zero-based.org/ ((_/)o o(\_))
\ `-' `-'(. .)`-'
`-. Debian, a variant of the GNU operating system. \_/

[Malcolm]

"Martin Dickopp" <ex****************@zero-based.org> wrote in message
news:cu*************@zero-based.org...

"Large" is not the same as "arbitrary". In fact, a program small
enough that it can be posted here suffices to show that drawing a
call tree for an arbitrary program is impossible.

Image a function `p' with the following prototype:

int p (const char *);

This function should accept C source code (in the form of a string) as
an argument. I don't require it to draw a complete call tree; all it
has to do is to determine whether the code passed as argument calls a
function `f'. If yes, it should return a nonzero value, otherwise zero.
Do you think such a function could in principle be written?

Consider the following translation unit. It should be linked together
with the implementation of the `p' function, and it should be stored
in a file `t.c' (so that it can read its own source code by reading a
text file `t.c').

#include <stdio.h>
extern int p (const char *);
void f (void) { }

int main (void)
{
FILE *fp;
char mycode [10000];

fp = fopen ("t.c", "r");
if (fp != NULL)
{
const size_t n = fread (mycode, 1, sizeof mycode - 1, fp);
fclose (fp);
mycode [n] = '\0';
if (!p (mycode))
f ();
}

return 0;
}

Let's assume for simplicity that no read error occurs when the program
reads its own source code. What will `p' return? Will it claim that
the code calls `f' or will it claim that it doesn't?

Firstly you often generate logical conundrums by applying a function (or a
statemement) to itself, eg "Everything I say is a lie".

Secondly, we want the call tree, so we simply assume that a conditional
branch can go each way. This is even in the case of statements such as if(
pow(x, 2) >= 0). We do not need to know if a function is actually called.
Normally we assume that if the programmer has put in a conditional branch
then he doesn't know which will be true at compile time.

In your example, f() is clearly part of the call tree. If p() returns false
it is taken. We don't need to know about the internals of p().

[James Kanze]

Da*****@cern.ch (Dan Pop) writes:

|> In <40***************@yahoo.com> CBFalconer <cb********@yahoo.com>
|> writes:
|> >Peter Nilsson wrote:
|> >> Lew Pitcher <lp******@sympatico.ca> wrote...
|> >>> Michael Sig Birkmose wrote:

|> >>>| 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.

|> >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.

Well, by definition the data structure for auto variables and return
addresses is a stack. How the stack is implemented, of course, is
implementation defined -- I once used a C compiler in which function
prologues called malloc to obtain the local stack frame.

--
James Kanze
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France [phone]

[Richard Bos]

"Malcolm" <ma*****@55bank.freeserve.co.uk> wrote:

"Richard Bos" <rl*@hoekstra-uitgeverij.nl> wrote in message

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.

Comparing the drawing of a call-tree, even of a large program, to the
halting problem is ridiculous.

It's not ridiculous, it's correct. It's nothing to do with mere size,
btw, and everything with logical complexity. If you want an accurate
prediction of how much memory a program could take, you have to be able
to predict which program paths it takes, and that means you have to
predict where it halts.
If, OTOH, you're satisfied with a rough guess, well, just do a
good-sized run, ask your OS how much memory it takes now, then double
that amount. Much simpler.

Richard

[CBFalconer]

Richard Bos wrote:

"Malcolm" <ma*****@55bank.freeserve.co.uk> wrote:

"Richard Bos" <rl*@hoekstra-uitgeverij.nl> wrote in message

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.

Comparing the drawing of a call-tree, even of a large program,
to the halting problem is ridiculous.

It's not ridiculous, it's correct. It's nothing to do with mere
size, btw, and everything with logical complexity. If you want an
accurate prediction of how much memory a program could take, you
have to be able to predict which program paths it takes, and that
means you have to predict where it halts.

If, OTOH, you're satisfied with a rough guess, well, just do a
good-sized run, ask your OS how much memory it takes now, then
double that amount. Much simpler.

On the contrary, speaking C, and ignoring memory usage via malloc
and friends, and also (IMPORTANT) assuming no recursion, we can
find maximum local (automatic) memory use for each function, and
then deduce the maximum usage from the call tree. The values will
not be portable, i.e. they will be system and compiler dependant.

Simple recursive functions can usually be also measured if they
properly protect themselves against bad calls, by examining the
conditions that terminate recursion. For example, a recursive
function to output a char representation of an integer is
intrinsically limited by the size of an integer, and thus the
maximum number of digits possible.

Once mutual recursion is encountered things become much murkier.
The comparison to the halting problem is valid for arbitrary
programs, but most code is not arbitrary, or at least we hope so.

--
A: Because it fouls the order in which people normally read text.
Q: Why is top-posting such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

[I. Appel]

"CBFalconer" <cb********@yahoo.com> wrote in message
news:40***************@yahoo.com...

Richard Bos wrote: On the contrary, speaking C, and ignoring memory usage via malloc
and friends, and also (IMPORTANT) assuming no recursion, we can
find maximum local (automatic) memory use for each function, and
then deduce the maximum usage from the call tree. The values will
not be portable, i.e. they will be system and compiler dependant.

People, you're reinventing the bycicle! Fortran 77 was designed to make
programs portable to stackless iron, so it permitted no recursion and
AFAIR no equivalent to malloc.

Ivan.

[ozbear]

On Tue, 01 Jun 2004 11:18:37 GMT, rl*@hoekstra-uitgeverij.nl (Richard
Bos) wrote:

"Malcolm" <ma*****@55bank.freeserve.co.uk> wrote:

"Richard Bos" <rl*@hoekstra-uitgeverij.nl> wrote in message

> 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.

Comparing the drawing of a call-tree, even of a large program, to the
halting problem is ridiculous.

It's not ridiculous, it's correct. It's nothing to do with mere size,
btw, and everything with logical complexity. If you want an accurate
prediction of how much memory a program could take, you have to be able
to predict which program paths it takes, and that means you have to
predict where it halts.
If, OTOH, you're satisfied with a rough guess, well, just do a
good-sized run, ask your OS how much memory it takes now, then double
that amount. Much simpler.

Richard

For a crude overestimate, assuming no recursion, one could just add
up all the automatic storage used in all functions irrespective
of whether they are ever called or not, then tack on the rest of
the variables (file-scope variables, statics, etc.).

Oz
--
A: Because it fouls the order in which people normally read text.
Q: Why is top-posting such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

[August Derleth]

On Wed, 02 Jun 2004 12:27:46 +0600, I. Appel wrote:

"CBFalconer" <cb********@yahoo.com> wrote in message
news:40***************@yahoo.com...

Richard Bos wrote:

On the contrary, speaking C, and ignoring memory usage via malloc
and friends, and also (IMPORTANT) assuming no recursion, we can
find maximum local (automatic) memory use for each function, and
then deduce the maximum usage from the call tree. The values will
not be portable, i.e. they will be system and compiler dependant.

People, you're reinventing the bycicle! Fortran 77 was designed to make
programs portable to stackless iron, so it permitted no recursion and
AFAIR no equivalent to malloc.

I believe Fortran 77 allowed recursion, but earlier versions did not.

And Fortran doesn't have malloc for the same reason Pascal and Perl don't:
It's operating too far above the machine level for malloc to make sense.
The compiler is expected to figure out the low-level stuff.

--
yvoregnevna gjragl-guerr gjb-gubhfnaq guerr ng lnubb qbg pbz
To email me, rot13 and convert spelled-out numbers to numeric form.
"Makes hackers smile" makes hackers smile.

[Rob Thorpe]

August Derleth <se*@sig.now> wrote in message news:<pa****************************@sig.now>...

On Wed, 02 Jun 2004 12:27:46 +0600, I. Appel wrote:

"CBFalconer" <cb********@yahoo.com> wrote in message
news:40***************@yahoo.com...

Richard Bos wrote: On the contrary, speaking C, and ignoring memory usage via malloc
and friends, and also (IMPORTANT) assuming no recursion, we can
find maximum local (automatic) memory use for each function, and
then deduce the maximum usage from the call tree. The values will
not be portable, i.e. they will be system and compiler dependant.
People, you're reinventing the bycicle! Fortran 77 was designed to make
programs portable to stackless iron, so it permitted no recursion and
AFAIR no equivalent to malloc.

I believe Fortran 77 allowed recursion, but earlier versions did not.

No, Fortran 77 does not require recursion to be supported. Fortran 90
does as long as the function is marked as recursive AFAIK.
And Fortran doesn't have malloc for the same reason Pascal and Perl don't:
It's operating too far above the machine level for malloc to make sense.

Fortran is not operating on a much different level to C. Allocatable
arrays plus the ALLOCATE and DEALLOCATE statements are used to give
the same effect as malloc and free. It also supports variable length
arrays that are allocated automatically, as C99 does.

[I. Appel]

"August Derleth" <se*@sig.now> wrote in message
news:pa****************************@sig.now...

On the contrary, speaking C, and ignoring memory usage via malloc
and friends, and also (IMPORTANT) assuming no recursion, we can
find maximum local (automatic) memory use for each function, and
then deduce the maximum usage from the call tree. The values will
not be portable, i.e. they will be system and compiler dependant.
People, you're reinventing the bycicle! Fortran 77 was designed to make
programs portable to stackless iron, so it permitted no recursion and
AFAIR no equivalent to malloc.

I believe Fortran 77 allowed recursion, but earlier versions did not.

It didn't.
And Fortran doesn't have malloc for the same reason Pascal and Perl don't:
It's operating too far above the machine level for malloc to make sense.
The compiler is expected to figure out the low-level stuff.

I denoted not the low-level memory blocks allocation, but general use of as
much memory
as you want. In Perl you can manage as much memory as you want, while in
Pascal
(and AFAIR in Fortran 77) all you can is to use arrays, whose size is
defined in the
compilation time.

Ivan.

[Michael Wojcik]

In article <40****************@news.individual.net>, rl*@hoekstra-uitgeverij.nl (Richard Bos) writes:

"Malcolm" <ma*****@55bank.freeserve.co.uk> wrote:

Comparing the drawing of a call-tree, even of a large program, to the
halting problem is ridiculous.

It's not ridiculous, it's correct. It's nothing to do with mere size,
btw, and everything with logical complexity. If you want an accurate
prediction of how much memory a program could take, you have to be able
to predict which program paths it takes, and that means you have to
predict where it halts.

I think there's a difference of definition here. I believe Malcolm
is referring not to a map of possible program paths, but a static
call graph.

That is, he's referring to a directed graph (it's only a tree for
programs where each function has exactly one caller, and all
functions are reachable from main - not the usual case) where nodes
are functions in the program, and there's an edge from node A to node
B if function A calls function B (directly or through a function
pointer).

Since C does not allow the dynamic construction of function calls,
it's possible to construct such a graph by static analysis of the
source. Whether a given edge will actually be followed in any run of
the program is a separate question (and is equivalent to the Halting
Problem).

For a C program which is non-recursive, the call graph will be
acyclic. If nodes are weighted by their automatic storage
requirement, then the maximum weighted depth of the graph can be
computed.

However, there's no mechanism in standard C for computing the
automatic storage requirement of a function; many interesting C
programs are recursive; and in many cases not all of the source is
available for analysis. And even for programs which satisfy the
latter two conditions and an implementation which supplies sufficient
information for the first, all you know is the upper bound on
automatic storage, which is unlikely to be particularly useful in
most cases. So the prospects for exact analysis of automatic storage
requirements are not good.

As a side note, the non-recursive constraint can be avoided. Any
recursive program can be algorithmically transformed into an
iterative one, by rewriting mutually-recursive functions as a single
function, singly-recursive functions with non-tail recursion as
tail-recursive continuation-passing functions, and finally
tail-recursive functions as iterative. Since C doesn't directly
support continuation-passing style, such a transformation would
require a manual implementation of it - which would mean, in effect,
implementing a CPS-capable language on top of C. Hardly worth the
effort. And all that does is transform auto-storage requirement into
direct-allocated storage requirement anyway, which is a zero-sum or
worse tradeoff in most environments.

--
Michael Wojcik mi************@microfocus.com

[After the lynching of George "Big Nose" Parrot, Dr. John] Osborne
had the skin tanned and made into a pair of shoes and a medical bag.
Osborne, who became governor, frequently wore the shoes.
-- _Lincoln [Nebraska] Journal Star_

[CBFalconer]

August Derleth wrote:

.... snip ...
I believe Fortran 77 allowed recursion, but earlier versions did
not.

And Fortran doesn't have malloc for the same reason Pascal and
Perl don't: It's operating too far above the machine level for
malloc to make sense. The compiler is expected to figure out the
low-level stuff.

Pascal has the equivalent of malloc. Try "new(p);" where p is a
pointer type. This is almost the equivalent of a c macro:

#define new(p) p = malloc(sizeof *p)

it exists until "dispose(p);"

--
fix (vb.): 1. to paper over, obscure, hide from public view; 2.
to work around, in a way that produces unintended consequences
that are worse than the original problem. Usage: "Windows ME
fixes many of the shortcomings of Windows 98 SE". - Hutchison

[Dan Pop]

In <pa****************************@sig.now> August Derleth <se*@sig.now> writes:

On Wed, 02 Jun 2004 12:27:46 +0600, I. Appel wrote:

"CBFalconer" <cb********@yahoo.com> wrote in message
news:40***************@yahoo.com...

Richard Bos wrote:

On the contrary, speaking C, and ignoring memory usage via malloc
and friends, and also (IMPORTANT) assuming no recursion, we can
find maximum local (automatic) memory use for each function, and
then deduce the maximum usage from the call tree. The values will
not be portable, i.e. they will be system and compiler dependant.

People, you're reinventing the bycicle! Fortran 77 was designed to make
programs portable to stackless iron, so it permitted no recursion and
AFAIR no equivalent to malloc.

I believe Fortran 77 allowed recursion, but earlier versions did not.

Nope, it didn't.
And Fortran doesn't have malloc for the same reason Pascal and Perl don't:
Pascal does have *explicit* support for dynamic memory allocation.
It's operating too far above the machine level for malloc to make sense.
The compiler is expected to figure out the low-level stuff.

Nonsense! It's a language issue, not a compiler issue. If the language
doesn't provide support for dynamically sized arrays, the compiler has
nothing to figure out. Many F77 implementations supported a Cray
extension that provided malloc functionality. F90 supports dynamic
memory allocation as a feature long awaited for by the Fortran community.

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de

[Dan Pop]

In <40***************@yahoo.com> CBFalconer <cb********@yahoo.com> writes:

Richard Bos wrote:

"Malcolm" <ma*****@55bank.freeserve.co.uk> wrote:

"Richard Bos" <rl*@hoekstra-uitgeverij.nl> wrote in message

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.

Comparing the drawing of a call-tree, even of a large program,
to the halting problem is ridiculous.

It's not ridiculous, it's correct. It's nothing to do with mere
size, btw, and everything with logical complexity. If you want an
accurate prediction of how much memory a program could take, you
have to be able to predict which program paths it takes, and that
means you have to predict where it halts.

If, OTOH, you're satisfied with a rough guess, well, just do a
good-sized run, ask your OS how much memory it takes now, then
double that amount. Much simpler.

On the contrary, speaking C, and ignoring memory usage via malloc
and friends, and also (IMPORTANT) assuming no recursion, we can

malloc and friends are a non-issue when measuring/evaluating the amount of
automatically allocated memory, anyway.
find maximum local (automatic) memory use for each function, and
then deduce the maximum usage from the call tree. The values will
not be portable, i.e. they will be system and compiler dependant.

C99 VLAs render this approach useless: you must simulate the program
execution in order to figure out their sizes.

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de

[Malcolm]

"Michael Wojcik" <mw*****@newsguy.com> wrote in message

I think there's a difference of definition here. I believe Malcolm
is referring not to a map of possible program paths, but a static
call graph.

Exactly. Consider this

long x, y, z;
scanf("%ld %ld %ld", &x, &y, &z)

x = clamp(x, 2, CUBEROOTLONGMAX);
y = clamp(y, 2, CUBEROOTLONGMAX);
z = clamp(z, 2, CUBEROOTLONGMAX);

if( x*x*x + y*y*y == z*z*z)
thisisnevercalled();
The function call can never be taken, regardless of the size of long (assume
CUBEROOTLONGMAX is calculated dynamically).

However how is an automatic simulator going to determine that? In fact the
average programmer probably couldn't prove it, unless he has a maths degree.

It is also not of practical use. We can imagine a young programmer writing
exactly this function to test Fermat's theorem for himself. If for some
reason he is short of stack space, he will want to know that the function
thisisnevercalled() doesn't overflow the stack.

[I. Appel]

"CBFalconer" <cb********@yahoo.com> wrote in message
news:40***************@yahoo.com...

And Fortran doesn't have malloc for the same reason Pascal and
Perl don't: It's operating too far above the machine level for
malloc to make sense. The compiler is expected to figure out the
low-level stuff.

Pascal has the equivalent of malloc. Try "new(p);" where p is a
pointer type. This is almost the equivalent of a c macro:

#define new(p) p = malloc(sizeof *p)

it exists until "dispose(p);"

I'm not sure it was in original Wirth's Pascal and I'm not sure it is
suitable for creating dynamic arrays.

Ivan.

[James Kanze]

"I. Appel" <ia****@rol.kill.the.spammers.ru> writes:

|> "CBFalconer" <cb********@yahoo.com> wrote in message
|> news:40***************@yahoo.com...
|> > > And Fortran doesn't have malloc for the same reason Pascal and
|> > > Perl don't: It's operating too far above the machine level for
|> > > malloc to make sense. The compiler is expected to figure out the
|> > > low-level stuff.

|> > Pascal has the equivalent of malloc. Try "new(p);" where p is a
|> > pointer type. This is almost the equivalent of a c macro:

|> > #define new(p) p = malloc(sizeof *p)

|> > it exists until "dispose(p);"

|> I'm not sure it was in original Wirth's Pascal and I'm not sure it
|> is suitable for creating dynamic arrays.

It was in Wirth's Pascal, but a lot of early Pascal compilers skipped
it.

--
James Kanze
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France [phone]

[August Derleth]

On Wed, 02 Jun 2004 15:10:31 +0000, Dan Pop wrote:

In <40***************@yahoo.com> CBFalconer <cb********@yahoo.com> writes:

find maximum local (automatic) memory use for each function, and
then deduce the maximum usage from the call tree. The values will
not be portable, i.e. they will be system and compiler dependant.

C99 VLAs render this approach useless: you must simulate the program
execution in order to figure out their sizes.

And hope nobody passes in a value too big to be used to size a VLA of a
given type. How big is too big? Only your debugger (or maintenance
programmer) knows for sure. Until then, you have no way of checking that
your next run won't cause all sorts of crap to happen.

At least malloc() gives me a fighting chance at handling errors in memory
allocation. You can quote at me all the systems which will over-commit to
Hell and back so malloc() can never fail*, but all things equal, I'd
rather have /something/ to test instead of being forced to hope nothing
blows up.

VLAs are the new gets().

*Yes, I'm following that thread with rapt interest.
--
yvoregnevna gjragl-guerr gjb-gubhfnaq guerr ng lnubb qbg pbz
To email me, rot13 and convert spelled-out numbers to numeric form.
"Makes hackers smile" makes hackers smile.

[Dan Pop]

In <pa****************************@sig.now> August Derleth <se*@sig.now> writes:

On Wed, 02 Jun 2004 15:10:31 +0000, Dan Pop wrote:

In <40***************@yahoo.com> CBFalconer <cb********@yahoo.com> writes:

find maximum local (automatic) memory use for each function, and
then deduce the maximum usage from the call tree. The values will
not be portable, i.e. they will be system and compiler dependant.

C99 VLAs render this approach useless: you must simulate the program
execution in order to figure out their sizes.

And hope nobody passes in a value too big to be used to size a VLA of a
given type. How big is too big? Only your debugger (or maintenance
programmer) knows for sure. Until then, you have no way of checking that
your next run won't cause all sorts of crap to happen.

At least malloc() gives me a fighting chance at handling errors in memory
allocation. You can quote at me all the systems which will over-commit to
Hell and back so malloc() can never fail*, but all things equal, I'd
rather have /something/ to test instead of being forced to hope nothing
blows up.

VLAs are the new gets().

I fail to see how are VLAs special in this context, as opposed to
automatically allocated fixed sized arrays. It is the automatic
allocation that is causing the problem, not the fixed vs variable nature
of the array size.

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de

[August Derleth]

On Thu, 03 Jun 2004 17:24:53 +0000, Dan Pop wrote:

In <pa****************************@sig.now> August Derleth <se*@sig.now>
writes:

On Wed, 02 Jun 2004 15:10:31 +0000, Dan Pop wrote:

In <40***************@yahoo.com> CBFalconer <cb********@yahoo.com>
writes:

find maximum local (automatic) memory use for each function, and then
deduce the maximum usage from the call tree. The values will not be
portable, i.e. they will be system and compiler dependant.

C99 VLAs render this approach useless: you must simulate the program
execution in order to figure out their sizes.

And hope nobody passes in a value too big to be used to size a VLA of a
given type. How big is too big? Only your debugger (or maintenance
programmer) knows for sure. Until then, you have no way of checking that
your next run won't cause all sorts of crap to happen.

At least malloc() gives me a fighting chance at handling errors in
memory allocation. You can quote at me all the systems which will
over-commit to Hell and back so malloc() can never fail*, but all things
equal, I'd rather have /something/ to test instead of being forced to
hope nothing blows up.

VLAs are the new gets().

I fail to see how are VLAs special in this context, as opposed to
automatically allocated fixed sized arrays. It is the automatic
allocation that is causing the problem, not the fixed vs variable nature
of the array size.

With fixed-length arrays, the compiler could in theory warn you about
making things too big for the current compilation mode. For example, a C
compiler for an x86 DOS machine could warn about an array that would push
the .COM file's size above the magic 64K limit. I don't know if such
warnings are even considered by the Standard, but it would be a very
definite QoI issue.

With VLAs, however, array size becomes a matter of what exactly happens at
runtime. As runtime is obviously affected by input and other external
events, the compiler is of no help. If someone manages to finesse the
array into being excessively large (by passing in a very long string,
knowing the VLA will be sized by a strlen() call, for example), he could
make your program do anything at all. Since VLAs obviously cannot return
error codes, your program absolutely cannot handle this dangerous event.

I'm willing to be proven wrong. I always am. I hope the Standards
Committee wasn't as stupid as the current state of VLAs implies they were.
But as long as code like this is valid:

#include <string.h>

char *danger(char *str1, char *str2)
{
char badarr[strlen(str1) + strlen(str2)]; return badarr;
}

I will be somewhat leery of the whole concept. After all, they kept
gets().

--
yvoregnevna gjragl-guerr gjb-gubhfnaq guerr ng lnubb qbg pbz
To email me, rot13 and convert spelled-out numbers to numeric form.
"Makes hackers smile" makes hackers smile.

[Keith Thompson]

August Derleth <se*@sig.now> writes:
[...]

But as long as code like this is valid:

#include <string.h>

char *danger(char *str1, char *str2)
{
char badarr[strlen(str1) + strlen(str2)]; return badarr;
}

I will be somewhat leery of the whole concept. After all, they kept
gets().

Well, I suppose that's valid, but the caller will invoke undefined
behavior if it refers to the returned pointer value. But that's
not because it uses VLAs; the following exhibits the same problem:

char *danger2(void)
{
char badarr[42];
return badarr;
}

(It might be possible to modify the language so an attempt to return a
pointer to local storage is illegal, rather than causing later
undefined behavior, but I don't know how.)

I don't think that's the point you were trying to make, though.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Richard Bos]

August Derleth <se*@sig.now> wrote:

If someone manages to finesse the
array into being excessively large (by passing in a very long string,
knowing the VLA will be sized by a strlen() call, for example), he could
make your program do anything at all.
With correctly coded VLAs, this is as impossible as with correctly coded
non-VL arrays. With brokenly coded VLAs, it is as possible as with
broken normal arrays.
I'm willing to be proven wrong. I always am. I hope the Standards
Committee wasn't as stupid as the current state of VLAs implies they were.
But as long as code like this is valid:

#include <string.h>

char *danger(char *str1, char *str2)
{
char badarr[strlen(str1) + strlen(str2)]; return badarr;
}

I will be somewhat leery of the whole concept.

Yes, if you write code like that, I would stay far, far away from VLAs.
However, I'd also suggest you stay far away from allocated memory and
from normal arrays, since your (highly probably) too short array size is
just as much of a bug with malloc() and friends, and returning the
address of a local array is a bug regardless of whether it has variable
length or not.

Richard

[Dan Pop]

In <pa****************************@sig.now> August Derleth <se*@sig.now> writes:

On Thu, 03 Jun 2004 17:24:53 +0000, Dan Pop wrote:

I fail to see how are VLAs special in this context, as opposed to
automatically allocated fixed sized arrays. It is the automatic
allocation that is causing the problem, not the fixed vs variable nature
of the array size.
With fixed-length arrays, the compiler could in theory warn you about
making things too big for the current compilation mode.

How could the compiler know, even in theory, the amount of space available
for automatically allocated objects?
For example, a C
compiler for an x86 DOS machine could warn about an array that would push
the .COM file's size above the magic 64K limit. I don't know if such
warnings are even considered by the Standard, but it would be a very
definite QoI issue.
What if foo() in foo.c calls bar() in bar.c and each of them allocate an
automatic of 40k? What if everything fits into 64K, but there are only
40k free when you try to execute the program?
With VLAs, however, array size becomes a matter of what exactly happens at
runtime.
What exactly happens at run time is also an issue with fixed size arrays,
as shown above.
I'm willing to be proven wrong. I always am. I hope the Standards
Committee wasn't as stupid as the current state of VLAs implies they were.
As I have already explained, it's the automatic nature of the allocation
that is at the root of the problem, not the variable size of the arrays.
But as long as code like this is valid:

#include <string.h>

char *danger(char *str1, char *str2)
{
char badarr[strlen(str1) + strlen(str2)]; return badarr;
}

I will be somewhat leery of the whole concept.
This is valid *only* if used as a void function. The value of the
appropriately named badarr becomes indeterminate as soon as the function
returns. Now, imagine that strlen(str1) and strlen(str2) are known, e.g.
as macros. Why would

char badarr[STR1_LEN + STR2_LEN];

be any better? How can the compiler decide, at translation time, that
there will be enough "stack" space for badarr at run time?

But, if you think that automatic allocation is a language misfeature,
keep its usage limited at scalars (still no guarantee that your code
will not crash with a stack overflow ;-) If you want to eliminate
automatic allocation from the language, this automatically implies
banning recursion and this is not going to make your proposal particularly
popular ;-)
After all, they kept gets().

Which is a good thing (sometimes it is exactly what you need).
The bad thing is that they didn't deprecate fgets, which is *never*
what you need.

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de

[CBFalconer]

Dan Pop wrote:

August Derleth <se*@sig.now> writes:

.... snip ...

With fixed-length arrays, the compiler could in theory warn you
about making things too big for the current compilation mode.

How could the compiler know, even in theory, the amount of space
available for automatically allocated objects?

By injecting a call, at function entry, to a system routine which
can compare the amount needed (a parameter) with the space
available. Many systems do this - it is usually called runtime
stack checking. At compile time it is only possible to detect
gross errors, such as attempting to assign more space than a stack
segment can hold.

--
A: Because it fouls the order in which people normally read text.
Q: Why is top-posting such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

[Dan Pop]

In <40**************@yahoo.com> CBFalconer <cb********@yahoo.com> writes:

Dan Pop wrote:

August Derleth <se*@sig.now> writes:
... snip ...

With fixed-length arrays, the compiler could in theory warn you
about making things too big for the current compilation mode.

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ How could the compiler know, even in theory, the amount of space
available for automatically allocated objects?

By injecting a call, at function entry, to a system routine which
can compare the amount needed (a parameter) with the space
available. Many systems do this - it is usually called runtime
stack checking.

Had you engaged your brain, you'd have realised that nobody was talking
about run time checks: they happen too late to be of any use. And they
work for VLAs just the same way they work for ordinary arrays, because
they are performed at run time.
At compile time it is only possible to detect
gross errors, such as attempting to assign more space than a stack
segment can hold.

Which are useless in most cases and quite often downright impossible,
as the size of the stack segment need not be the same at compile time
and at run time (on Unix systems, it is under user control, up to a
certain limit imposed by the kernel).

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de

[Dave Thompson]

On 2 Jun 2004 13:58:05 GMT, mw*****@newsguy.com (Michael Wojcik)
wrote:

In article <40****************@news.individual.net>, rl*@hoekstra-uitgeverij.nl (Richard Bos) writes: <snip> I think there's a difference of definition here. I believe Malcolm
is referring not to a map of possible program paths, but a static
call graph. <snip>
Since C does not allow the dynamic construction of function calls,
it's possible to construct such a graph by static analysis of the
source. Whether a given edge will actually be followed in any run of
the program is a separate question (and is equivalent to the Halting
Problem).
But C does allow dynamic selection of the callee by use of function
pointers. In general dataflow analysis to determine which function(s)
could be the value of a pointer at a given call site is the Halting
Problem; and even in practical cases it is often nontrivial. You can
limit it to targets whose (actual) signature is compatible with the
pointer used to call -- or for an "unspecified" K&R1-type pointer,
with the return and default-promoted arguments -- modulo a few special
cases, but that may not help very much.
For a C program which is non-recursive, the call graph will be
acyclic. If nodes are weighted by their automatic storage
requirement, then the maximum weighted depth of the graph can be
computed.

However, there's no mechanism in standard C for computing the
automatic storage requirement of a function; many interesting C
programs are recursive; and in many cases not all of the source is
available for analysis. And even for programs which satisfy the
The first and third can be solved by looking at object code; this is
implementation-dependent but that's "only" a constant factor harder,
which is completely ignored in complexity theory.
latter two conditions and an implementation which supplies sufficient
information for the first, all you know is the upper bound on
automatic storage, which is unlikely to be particularly useful in
most cases. So the prospects for exact analysis of automatic storage
requirements are not good.
Agree.
As a side note, the non-recursive constraint can be avoided. Any
recursive program can be algorithmically transformed <snip> in effect,
implementing a CPS-capable language on top of C. Hardly worth the
effort. And all that does is transform auto-storage requirement into
direct-allocated storage requirement anyway, which is a zero-sum or
worse tradeoff in most environments.

I'm not sure I'd go for "most" there; if done carefully, particularly
with customized allocation rather than raw malloc, I'd expect a slight
gain significantly often, though by no means always. But I would say
*not worth the hassle* in most cases.

- David.Thompson1 at worldnet.att.net

[Michael Wojcik]

In article <3t********************************@4ax.com>, Dave Thompson <da*************@worldnet.att.net> writes:

On 2 Jun 2004 13:58:05 GMT, mw*****@newsguy.com (Michael Wojcik)
wrote:

I think there's a difference of definition here. I believe Malcolm
is referring not to a map of possible program paths, but a static
call graph. <snip>
Since C does not allow the dynamic construction of function calls,
it's possible to construct such a graph by static analysis of the
source. Whether a given edge will actually be followed in any run of
the program is a separate question (and is equivalent to the Halting
Problem).
But C does allow dynamic selection of the callee by use of function
pointers.

Yes, but I don't think this is a problem. It's dynamic selection
from a fixed set of targets - the union of the functions declared by
the program (and in scope for a given pointer assignment, though this
can be ignored for the sake of simplicity), and the functions defined
by the implementation.

If static analysis can determine:

1. the set of all possible targets of function pointers, ie the set
described above, and

2. whether a function pointer is dereferenced in a given function

then it can add a node to the graph for each possible target (step 1)
and an edge to each such node, from every node where a function
pointer is dereferenced (2). This may produce some redundant nodes
(since some functions may be called both normally and through
pointers), and will almost certainly produce nodes that are never
actually reached in any execution of the program. It will also
almost certainly produce many edges that are never actually taken
(and cannot be taken, because no path through the program would
assign a function pointer a value such that the edge *would* be
taken).

However, the point of this mooted static analysis is to determine the
maximum possible depth of the call graph - it's pessimistic. So
having extra nodes and edges doesn't violate the specification.

In short (I know, too late), it's not necessary for this analysis to
determine whether function pointer A will point to function X in any
actual execution of the program; it's only necessary to assume that
it might, and add the corresponding edge to the graph.
In general dataflow analysis to determine which function(s)
could be the value of a pointer at a given call site is the Halting
Problem; and even in practical cases it is often nontrivial.

Agreed, and if this was meant to be a useful analysis of the call
graph that would be a problem. But for determining maximum possible
depth in this pessimistic, imprecise way, it isn't necessarily one.
Of course, the presence of function pointers, combined with this
pessimistic assumption that a function pointer can point to any
function, is likely to produce a cycle in the graph, in which case
this procedure determines that the maximum call depth is infinite -
not a useful answer anyway.

But I'd agree that *useful* analysis of calls through function
pointers is equivalent to the Halting Problem in the general case.

--
Michael Wojcik mi************@microfocus.com

Is it any wonder the world's gone insane, with information come to be
the only real medium of exchange? -- Thomas Pynchon