Heap vs Stack allocations

[MSG]

Hello

void f1(int n) { vector<int> x(n); /* C++ */ }

void f2(int n) { int x[n]; /* C99 only */ }

void f3(int n) { int* x = new int[n]; /* C++ */ delete [] x; }

void f4(int n) { int* x = (int*)malloc(n*sizeof(int));
/*...*/ free(x); }

In all of these cases it makes sense for the compiler to allocate x on
the stack instead of the heap. However, AFAIK, only in case of f2 the
compiler is required to do so. Without learning assembly, is there any
way to see how a particular compiler handles each of these cases?

Best wishes,
MSG

[Martin Dickopp]

ms*****@yahoo.com (MSG) writes:

void f1(int n) { vector<int> x(n); /* C++ */ }

void f2(int n) { int x[n]; /* C99 only */ }

void f3(int n) { int* x = new int[n]; /* C++ */ delete [] x; }

void f4(int n) { int* x = (int*)malloc(n*sizeof(int));
/*...*/ free(x); }
In all of these cases it makes sense for the compiler to allocate x on
the stack instead of the heap. However, AFAIK, only in case of f2 the
compiler is required to do so.
No, neither in C nor in C++ a heap and/or stack is even required to
exist. How/where the implementation allocates memory is unspecified.
Without learning assembly, is there any way to see how a particular
compiler handles each of these cases?

- Consult the compiler documentation.
- Ask the compiler vendor.
- For each combination of compiler and platform you have in mind, ask in a
newsgroup dedicated to that compiler/platform.

Martin

[E. Robert Tisdale]

MSG wrote:

void f1(int n) { vector<int> x(n); /* C++ */ }

void f2(int n) { int x[n]; /* C99 only */ }

void f3(int n) { int* x = new int[n]; /* C++ */ delete [] x; }

void f4(int n) { int* x = (int*)malloc(n*sizeof(int));
/*...*/ free(x); }

In all of these cases, it makes sense for the compiler to allocate x
on the stack instead of the heap.
Why?
However, AFAIK, only in case of f2, the compiler is required to do so.
Without learning assembly, is there any see
how a particular compiler handles each of these cases?

Yes.

Storage for array x is allocated from the free store (the "heap")
in all cases except f2.
Automatic storage is allocated (from the stack) in f2 for array x
if you use a C99 compliant C compiler or a C or C++ compiler
that supports variable size arrays as an extension to C89 or C++.

A new C++ standard has been drafted
but I don't think that it specifies support for variable size arrays ...
yet.

[J. J. Farrell]

ms*****@yahoo.com (MSG) wrote in message news:<54**************************@posting.google. com>...

void f1(int n) { vector<int> x(n); /* C++ */ }

void f2(int n) { int x[n]; /* C99 only */ }

void f3(int n) { int* x = new int[n]; /* C++ */ delete [] x; }

void f4(int n) { int* x = (int*)malloc(n*sizeof(int));
/*...*/ free(x); }

In all of these cases it makes sense for the compiler to allocate x on
the stack instead of the heap. However, AFAIK, only in case of f2 the
compiler is required to do so.
Are you saying that C99 introduced a requirement that implementations
have a stack? I'm surprised.
Without learning assembly, is there any
way to see how a particular compiler handles each of these cases?

Not in Standard C. A particular compiler might have a way to do it,
but you'd need to ask in a newsgroup that discussed that compiler.
I've no idea about C++.

[E. Robert Tisdale]

J. J. Farrell wrote:

[snip]

Are you saying that C99 introduced a requirement
that implementations have a stack? I'm surprised.

I don't think so.
Just substitute the phases "automatic storage" for "stack"
and "free store" for "heap" and the question will make sense.
I don't think that the question really has anything to do with
the implementation of automatic or free storage.

[Jack Klein]

On Thu, 22 Jan 2004 16:27:11 -0800, "E. Robert Tisdale"
<E.**************@jpl.nasa.gov> wrote in comp.lang.c:

MSG wrote:

void f1(int n) { vector<int> x(n); /* C++ */ }

void f2(int n) { int x[n]; /* C99 only */ }

void f3(int n) { int* x = new int[n]; /* C++ */ delete [] x; }

void f4(int n) { int* x = (int*)malloc(n*sizeof(int));
/*...*/ free(x); }

In all of these cases, it makes sense for the compiler to allocate x
on the stack instead of the heap.
Why?

However, AFAIK, only in case of f2, the compiler is required to do so.
Without learning assembly, is there any see
how a particular compiler handles each of these cases?

Yes.

No, there is no requirement in either C or C++ that anything be
allocated on "the stack", or even that there is one.
Storage for array x is allocated from the free store (the "heap")
in all cases except f2.
The term "free store" has meaning in C++. It has no such meaning in
C, not being defined by the language standard at all. The C standard
does not specify where allocated memory comes from, nor how it is
managed.
Automatic storage is allocated (from the stack) in f2 for array x
if you use a C99 compliant C compiler or a C or C++ compiler
that supports variable size arrays as an extension to C89 or C++.
Neither C nor C++ even mentions a "stack", nor requires that one
exist.
A new C++ standard has been drafted
but I don't think that it specifies support for variable size arrays ...
yet.

The OP quite plainly knows that C++ does not have variable size
arrays.

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.learn.c-c++
http://www.contrib.andrew.cmu.edu/~a...FAQ-acllc.html

[Martin Dickopp]

"E. Robert Tisdale" <E.**************@jpl.nasa.gov> writes:

MSG wrote:

void f1(int n) { vector<int> x(n); /* C++ */ }
void f2(int n) { int x[n]; /* C99 only */ }
void f3(int n) { int* x = new int[n]; /* C++ */ delete [] x; }
void f4(int n) { int* x = (int*)malloc(n*sizeof(int));
/*...*/ free(x); }
In all of these cases, it makes sense for the compiler to allocate x
on the stack instead of the heap.

Why?

However, AFAIK, only in case of f2, the compiler is required to do so.
Without learning assembly, is there any see
how a particular compiler handles each of these cases?

Yes.

Storage for array x is allocated from the free store (the "heap")
in all cases except f2.

That statement is correct in the same sense that "storage for array x
is allocated on Mars in all cases except f2" is correct. Since f2 is
the only case where an array x appears, no statement about array x in
all cases except f2 can be false.

Martin

[MSG]

"E. Robert Tisdale" <E.**************@jpl.nasa.gov> wrote in message news:<40**************@jpl.nasa.gov>...

MSG wrote:

void f1(int n) { vector<int> x(n); /* C++ */ }

void f2(int n) { int x[n]; /* C99 only */ }

void f3(int n) { int* x = new int[n]; /* C++ */ delete [] x; }

void f4(int n) { int* x = (int*)malloc(n*sizeof(int));
/*...*/ free(x); }

In all of these cases, it makes sense for the compiler to allocate x
on the stack instead of the heap.

Why?

LOL! A fella from JPL should know this, so listen good :-)

1. Stack allocation/deallocation is MUCH faster than heap -
approximately O(1) vs O(log(n)), where n is the number of allocated
pieces, IIRC.

2. Heap can become fragmented (unless you move memory blocks around,
which C/C++ does not usually do AFAIK), so allocating can fail long
before your memory is exhausted, OTOH stack allocation will always
succeed as long as you have enough stack left.

BTW, #2 can be a source of "interesting" behavior when your program
works fine for a while, but then starts acting funny. This however
happens only to software of a certain degree of quality, most C/C++
programs (*) will crash long before heap fragmentation becomes an
issue. LOL.

Best wishes,
MSG

* those written by present company excluded, of course

[Joona I Palaste]

MSG <ms*****@yahoo.com> scribbled the following
on comp.lang.c:

"E. Robert Tisdale" <E.**************@jpl.nasa.gov> wrote in message news:<40**************@jpl.nasa.gov>...

MSG wrote:

> void f1(int n) { vector<int> x(n); /* C++ */ }
>
> void f2(int n) { int x[n]; /* C99 only */ }
>
> void f3(int n) { int* x = new int[n]; /* C++ */ delete [] x; }
>
> void f4(int n) { int* x = (int*)malloc(n*sizeof(int));
> /*...*/ free(x); }
>
> In all of these cases, it makes sense for the compiler to allocate x
> on the stack instead of the heap.
Why?

LOL! A fella from JPL should know this, so listen good :-) 1. Stack allocation/deallocation is MUCH faster than heap -
approximately O(1) vs O(log(n)), where n is the number of allocated
pieces, IIRC. 2. Heap can become fragmented (unless you move memory blocks around,
which C/C++ does not usually do AFAIK), so allocating can fail long
before your memory is exhausted, OTOH stack allocation will always
succeed as long as you have enough stack left. BTW, #2 can be a source of "interesting" behavior when your program
works fine for a while, but then starts acting funny. This however
happens only to software of a certain degree of quality, most C/C++
programs (*) will crash long before heap fragmentation becomes an
issue. LOL.

Did you *read* the other replies? Neither C or C++ specifies that a
"stack" or a "heap" even exists. Trollsdale is only trying to
intentionally ignore this and discuss implementation details on
comp.lang.c. If you want to discuss a particular implementation, find
a newsgroup for that implementation.

--
/-- Joona Palaste (pa*****@cc.helsinki.fi) ------------- Finland --------\
\-- http://www.helsinki.fi/~palaste --------------------- rules! --------/
"There's no business like slow business."
- Tailgunner

[MSG]

"E. Robert Tisdale" <E.**************@jpl.nasa.gov> wrote in message news:<40**************@jpl.nasa.gov>...

MSG wrote:

void f1(int n) { vector<int> x(n); /* C++ */ }

void f2(int n) { int x[n]; /* C99 only */ }

void f3(int n) { int* x = new int[n]; /* C++ */ delete [] x; }

void f4(int n) { int* x = (int*)malloc(n*sizeof(int));
/*...*/ free(x); }

In all of these cases, it makes sense for the compiler to allocate x
on the stack instead of the heap.

Why?

LOL! A fella from JPL should know this, so listen good :-)

1. Stack allocation/deallocation is MUCH faster than heap -
approximately O(1) vs O(log(n)), where n is the number of allocated
pieces, IIRC.

2. Heap can become fragmented (unless you move memory blocks around,
which C/C++ does not usually do AFAIK), so allocating can fail long
before your memory is exhausted, OTOH stack allocation will always
succeed as long as you have enough stack left.

BTW, #2 can be a source of "interesting" behavior when your program
works fine for a while, but then starts acting funny. This however
happens only to software of a certain degree of quality, most C/C++
programs (*) will crash long before heap fragmentation becomes an
issue. LOL.

Best wishes,
MSG

* those written by present company excluded, of course

[CBFalconer]

MSG wrote:

<E.**************@jpl.nasa.gov> wrote in message

MSG wrote:

void f1(int n) { vector<int> x(n); /* C++ */ }
void f2(int n) { int x[n]; /* C99 only */ }
void f3(int n) { int* x = new int[n]; /* C++ */ delete [] x; }
void f4(int n) { int* x = (int*)malloc(n*sizeof(int));
/*...*/ free(x); }

In all of these cases, it makes sense for the compiler to
allocate x on the stack instead of the heap.

Why?

LOL! A fella from JPL should know this, so listen good :-)

.... snip ...

You are obviously not acquainted with our resident Trollsdale.
His advice and queries are normally nonsense, and even his quotes
are not to be trusted. He edits them, and totally changes their
meaning, without any annotation. I seriously doubt that he has
any connection with jpl or nasa, his alleged knowledge is just too
erroneous. However he may be a janitor there (which is perfectly
respectable, just not normally computer knowledgeable).

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

[E. Robert Tisdale]

Jack Klein wrote:

The term "free store" has meaning in C++.
It has no such meaning in C,
Nonsense!
It has exactly the same meaning that it has in C++.
not being defined by the [ANSI/ISO C] language standard at all.
Nonsense!

void free(void *ptr);

is defined by ANSI/ISO C[89]9.
The C standard does not specify where allocated memory comes from

Really?
Can a C program "steal" the memory that is allocated?

[Mark McIntyre]

On Fri, 23 Jan 2004 09:31:43 GMT, in comp.lang.c , CBFalconer
<cb********@yahoo.com> wrote:

meaning, without any annotation. I seriously doubt that he has
any connection with jpl or nasa, his alleged knowledge is just too
erroneous.
There apparently /is/ an ERTisdale there (his name has appeared on
some research papers). But that doesn't mean that /this/ ERT works
there, or even that this guy /is/ ERT. Its easy enough to fake up the
headers. After all, for all I know, you're a lesbian trucker from
Vermont called Shirley, and not a mongolian cat-skinner living in a
squat in Eastbourne at all.

Myself however, I believe he is the real thing. I met some VERY
self-opinionated research people when I was a postgrad, some of whom
thought that because they were (say) experts in the properties of
plasma in 30T torsional magnetic fields, they were naturally experts
in any other field of human endeavour. Given that many of them had
failed to master the art of washing their beards, wore shoes with
velcro and (aged 25) took all their laundry home to their mum every 8
weeks....
However he may be a janitor there (which is perfectly
respectable, just not normally computer knowledgeable).

You obviously don't read Dilbert.....

Never *ever* sass the garbage man....
--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
CLC readme: <http://www.angelfire.com/ms3/bchambless0/welcome_to_clc.html>
----== Posted via Newsfeed.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeed.com The #1 Newsgroup Service in the World! >100,000 Newsgroups
---= 19 East/West-Coast Specialized Servers - Total Privacy via Encryption =---

[MSG]

Joona I Palaste <pa*****@cc.helsinki.fi> wrote in message news:<bu**********@oravannahka.helsinki.fi>...

MSG <ms*****@yahoo.com> scribbled the following
on comp.lang.c:

"E. Robert Tisdale" <E.**************@jpl.nasa.gov> wrote in message news:<40**************@jpl.nasa.gov>...

MSG wrote:

> void f1(int n) { vector<int> x(n); /* C++ */ }
>
> void f2(int n) { int x[n]; /* C99 only */ }
>
> void f3(int n) { int* x = new int[n]; /* C++ */ delete [] x; }
>
> void f4(int n) { int* x = (int*)malloc(n*sizeof(int));
> /*...*/ free(x); }
>
> In all of these cases, it makes sense for the compiler to allocate x
> on the stack instead of the heap.

Why?

LOL! A fella from JPL should know this, so listen good :-)

1. Stack allocation/deallocation is MUCH faster than heap -
approximately O(1) vs O(log(n)), where n is the number of allocated
pieces, IIRC.

2. Heap can become fragmented (unless you move memory blocks around,
which C/C++ does not usually do AFAIK), so allocating can fail long
before your memory is exhausted, OTOH stack allocation will always
succeed as long as you have enough stack left.

BTW, #2 can be a source of "interesting" behavior when your program
works fine for a while, but then starts acting funny. This however
happens only to software of a certain degree of quality, most C/C++
programs (*) will crash long before heap fragmentation becomes an
issue. LOL.

Did you *read* the other replies? Neither C or C++ specifies that a
"stack" or a "heap" even exists. Trollsdale is only trying to

^^^^^^^^^^

It's not very nice of you. This is an international forum, so you need
to learn to be more tolerant of others' opinions, including opinions
as to what is on-topic.

"Love thy neighbor" - Mr. Fix It
intentionally ignore this and discuss implementation details on
comp.lang.c. If you want to discuss a particular implementation, find
a newsgroup for that implementation.

[Alan Balmer]

On 23 Jan 2004 14:49:24 -0800, ms*****@yahoo.com (MSG) wrote:

It's not very nice of you. This is an international forum, so you need
to learn to be more tolerant of others' opinions, including opinions
as to what is on-topic.

No. Topicality does not depend on nationality.

--
Al Balmer
Balmer Consulting
re************************@att.net

[Rolf Magnus]

Martin Dickopp wrote:

ms*****@yahoo.com (MSG) writes:

void f1(int n) { vector<int> x(n); /* C++ */ }

void f2(int n) { int x[n]; /* C99 only */ }

void f3(int n) { int* x = new int[n]; /* C++ */ delete [] x; }

void f4(int n) { int* x = (int*)malloc(n*sizeof(int));
/*...*/ free(x); }
In all of these cases it makes sense for the compiler to allocate x
on the stack instead of the heap. However, AFAIK, only in case of f2
the compiler is required to do so.

No, neither in C nor in C++ a heap and/or stack is even required to
exist. How/where the implementation allocates memory is unspecified.

I find it quite strange that C++ doesn't require a stack to exist, but
OTOH dictates that when an exception occurs, "stack unwinding" is done.
This term doesn't have a meaning if there is no stack, does it?

[Rolf Magnus]

E. Robert Tisdale wrote:

Jack Klein wrote:

The term "free store" has meaning in C++.
It has no such meaning in C,
Nonsense!
It has exactly the same meaning that it has in C++.

Could you quote the part that defines it? I didn't find it.

not being defined by the [ANSI/ISO C] language standard at all.

Nonsense!

void free(void *ptr);

is defined by ANSI/ISO C[89]9.

Yes it is. But what does the free() function have to do with the term
"free store"? I searched though the C99 standard, and no single
occurance of "free store" was found.
The C++ standard does use it, but it doesn't actually define the term
"free store". It just indicates that it ("free store") is the memory
where dynamic objects are allocated.

The C standard does not specify where allocated memory comes from

Really?

Well, if it does, can you quote the part that dictates the location of
that memory?
Can a C program "steal" the memory that is allocated?

The C standard neither requires nor forbids an implementation to provide
a way to "steal" memory, whatever that means.

[Mark McIntyre]

On 23 Jan 2004 14:49:24 -0800, in comp.lang.c , ms*****@yahoo.com
(MSG) wrote:

Joona I Palaste <pa*****@cc.helsinki.fi> wrote in message news:<bu**********@oravannahka.helsinki.fi>...

MSG <ms*****@yahoo.com> scribbled the following
on comp.lang.c:

> 1. Stack allocation/deallocation is MUCH faster than heap -
> approximately O(1) vs O(log(n)), where n is the number of allocated
> pieces, IIRC.

Did you *read* the other replies? Neither C or C++ specifies that a
"stack" or a "heap" even exists. Trollsdale is only trying to

^^^^^^^^^^
It's not very nice of you. This is an international forum, so you need
to learn to be more tolerant of others' opinions, including opinions
as to what is on-topic.

Whats on topic here in CLC is not a matter of opinion (or in CLC++
for that matter). And Joona is exceptionally tolerant, even of idiots.

--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
CLC readme: <http://www.angelfire.com/ms3/bchambless0/welcome_to_clc.html>
----== Posted via Newsfeed.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeed.com The #1 Newsgroup Service in the World! >100,000 Newsgroups
---= 19 East/West-Coast Specialized Servers - Total Privacy via Encryption =---

[Mark McIntyre]

On 22 Jan 2004 14:22:53 -0800, in comp.lang.c , ms*****@yahoo.com
(MSG) wrote:

void f1(int n) { vector<int> x(n); /* C++ */ }
void f2(int n) { int x[n]; /* C99 only */ }
void f3(int n) { int* x = new int[n]; /* C++ */ delete [] x; }
void f4(int n) { int* x = (int*)malloc(n*sizeof(int));
/*...*/ free(x); }

In all of these cases it makes sense for the compiler to allocate x on
the stack instead of the heap.
Why do you care? You don't need to know.....
However, AFAIK, only in case of f2 the
compiler is required to do so.
Um, since C doesnt require a compiler to use a heap or stack, then not
even f2 is required to use it.
Without learning assembly, is there any
way to see how a particular compiler handles each of these cases?

The existence of a heap or stack is utterly implementation dependent
and therefore depends on finding a means to monitor how your
implementation does something. A good debugger might help.

However the fundamental question is: why do you care? If you use the
knowledge of how your current compiler does it, then your code is
almost guaranteed to break when the maker upgrades it.

--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
CLC readme: <http://www.angelfire.com/ms3/bchambless0/welcome_to_clc.html>
----== Posted via Newsfeed.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeed.com The #1 Newsgroup Service in the World! >100,000 Newsgroups
---= 19 East/West-Coast Specialized Servers - Total Privacy via Encryption =---

[Rob Thorpe]

ms*****@yahoo.com (MSG) wrote in message news:<54**************************@posting.google. com>...

Hello

void f1(int n) { vector<int> x(n); /* C++ */ }

void f2(int n) { int x[n]; /* C99 only */ }

void f3(int n) { int* x = new int[n]; /* C++ */ delete [] x; }

void f4(int n) { int* x = (int*)malloc(n*sizeof(int));
/*...*/ free(x); }

In all of these cases it makes sense for the compiler to allocate x on
the stack instead of the heap. However, AFAIK, only in case of f2 the
compiler is required to do so. Without learning assembly, is there any
way to see how a particular compiler handles each of these cases?

Best wishes,
MSG

Although it is not in the C standard there is a function called
'alloca' that does this. Linux, all modern Unix implementaions and MS
Windows provide it.

y = alloca(x);

Allocates x bytes and gives a pointer to them. They are deallocated
at the end of the function.

The MS Windows version is called "_alloca"

It's not gauranteed to be faster than malloc, or in fact implemented
on the stack (I've come across it implemented on the heap) but it
normally is.

Personally I wish it was in the C standard, but it's not, because it
is hard to implement universally (on machines without stacks). So if
you want to know more post the question elsewhere, or email me
directly.

I wouldn't worry much about speed of memory allocation anyway, or
really about fragmentation, mallocs are good these days. But I do use
alloca because it demonstrates my intentions clearly i.e. that the
memory stops being used at the end of the function.