difference between stack & heap (general, for a newbie)

[Sean Cook]

guys (& gals)--

can anyone give me a good, thorough explanation of the difference
between the heap and the stack in C++?

thanks.

sean

 

[Victor Bazarov]

guys (& gals)--

can anyone give me a good, thorough explanation of the difference
between the heap and the stack in C++?

'Stack' is a common name for the memory space in which automatic
variables (and often function parameters) are allocated. 'Heap'
is a common name for the "free store", the memory space where
dynamic objects are allocated (see "new" and "delete"). For more
thorough explanation, ask particular questions.

V

 

[SaltPeter]

guys (& gals)--

can anyone give me a good, thorough explanation of the difference
between the heap and the stack in C++?

thanks.

sean

The stack is used to allocate temporary objects while the heap is used by a
programmer to reserve allocation. Basicly, an object in a heap is not scope
dependent, it dies when you tell it to. Meanwhile, an object on the stack is
destroyed automatically when its scope ends.

 

[Kevin Goodsell]

The stack is used to allocate temporary objects while the heap is used by a
programmer to reserve allocation.

Chapter and verse, please.

To the best of my knowledge, the standard does not require any such
thing, and does not define "stack" or "heap" in this kind of context.
These may be common names used for a common way of implementing
automatic and dynamic storage, but such an implementation is not required.

-Kevin

 

[osmium]

Chapter and verse, please.

To the best of my knowledge, the standard does not require any such
thing, and does not define "stack" or "heap" in this kind of context.
These may be common names used for a common way of implementing
automatic and dynamic storage, but such an implementation is not required.

There is a group, comp.std.c, for questions and answers about what the
standard says. If the OP had had a question about the standard, he would
probably have posted to that group. What he wanted to know was, *if* their
happens to be a thing called a stack and/or a thing called a heap, what
*are* these things? I thought the answer he was given was helpful, much
more helpful than a response that said "They are a figment of your
imagination".

Chapter and verse sounds like something delivered from a pulpit, which is
really quite appropriate.

 

[Kevin Goodsell]

There is a group, comp.std.c, for questions and answers about what the
standard says. If the OP had had a question about the standard, he would
probably have posted to that group.

We can't talk about the language described by the standard while
ignoring what the standard says.

What he wanted to know was, *if* their
happens to be a thing called a stack and/or a thing called a heap, what
*are* these things?

From the perspective of standard C++ (the topic of this group), they
don't exist.

If a person has questions about implementing automatic or dynamic
memory, they should ask somewhere like comp.compilers. If they have
questions about how they are implemented in a particular C++
implementation, they should ask in a group that discusses the compiler
or OS.

If someone wants to talk about *possible* implementations of C++
features here, that's probably not a big deal. But passing off one of
many possible implementations as the one and only way, when it's not
dictated by the standard, is misleading.

I thought the answer he was given was helpful, much
more helpful than a response that said "They are a figment of your
imagination".

Victor's answer was helpful because it wasn't misleading.

-Kevin

 

[Andrey Tarasevich]

...
can anyone give me a good, thorough explanation of the difference
between the heap and the stack in C++?
...

Your question is too ambiguous to be answered right away.

There are data structures called 'stack' (see 'std::stack') and 'heap'
(see 'std::make_heap').

There are memory types commonly referred to as 'stack' and 'heap'
(although these terms are unofficial or semi-official in C++ world).

Would you please clarify what your question is about?

 

[Sean Cook]

Andrey (and others),

I now see that my question was far too ambiguous. I understand the
difference between std::stack and std::heap as far as looking at each
of those data structures as abstract data types, I just do not
understand how these two data structures are implemented when your C++
code is compiled.

What I should've asked is "what is the scope of data when allocated
from the heap, and what is the scope of data when allocated from the
stack (where ``heap'' and ``stack'' are not standards, but are merely
common terms.)

And also, is there a performance difference, in general, of objects
allocated on the stack versus those allocated on the heap, or is this
a completely meaningless question?

Thanks.
Sean

 

[Karl Heinz Buchegger]

Andrey (and others),

What I should've asked is "what is the scope of data when allocated
from the heap, and what is the scope of data when allocated from the
stack (where ``heap'' and ``stack'' are not standards, but are merely
common terms.)

Now we are getting somewhere

The scope of memory allocated on the 'stack' is the scope
of the enclosing block. They get destroyed when the enclosing
block is finished. Thats why they are called 'auto' objects.

Example:

{
int i;

} // block ends, i gets destroyed

The scope of memory allocated on the 'heap' is different. Objects
get allocated with new (or malloc) and get destroyed when a corresponding
delete (or free) is executed. Blocks do no longer influence the scope of
these objects.

Example:

int* pJ;

{
int* pI = new int [20];

// Note that 2 things are happening here:
// 1.) An int array is allocated on the free store (aka heap).
// This array will be there until a corresponding delete [] is
// executed
// 2.) A variable pI is created. Since pI was not dynamically created
// with new or malloc, it is an auto object (created on the stack)
// Thus the enclosing block determines its lifetime

pJ = pI;

} // block ends. pI gets destroyed, but not so the int array. It
// will stay there in memory until a delete is done.

delete [] pJ; // now the memory in the free store (aka heap) gets
// released.

And also, is there a performance difference, in general, of objects
allocated on the stack versus those allocated on the heap, or is this
a completely meaningless question?

Free store allocation usually takes more time

 

[Rolf Magnus]

There is a group, comp.std.c, for questions and answers about what the
standard says.

No. This newsgroup is about _why_ the standard says something. If you
want to talk about the standard itself (ask why something is defined
the way it is, or propose changes to the standard), comp.std.c++ is the
way to go. If, however, you want to ask something about the language as
it is defined by that standard, comp.lang.c++ is the right group.

If the OP had had a question about the standard, he would
probably have posted to that group.
Yes.

What he wanted to know was, *if* their happens to be a thing called a
stack and/or a thing called a heap,

.... which is not the case in C++ ...

what *are* these things? I thought the answer he was given was
helpful, much more helpful than a response that said "They are a
figment of your imagination".

The answer should be something like "There is no such thing in C++ as
heap or stack, but those terms are often used to describe the places
where dynamic and automatic objects live, ..." followed by a
description of those.

Chapter and verse sounds like something delivered from a pulpit, which
is really quite appropriate.

People usually expect someone who ansers a question in this newsgroup to
be very correct. This might be a bit pedantic, but if you are in a
programming language newsgroup, you should expect that.

 

[Kevin Goodsell]

Note: Please don't top-post. Consult section 5 of this group's FAQ for
more information.

http://www.parashift.com/c++-faq-lite/

Andrey (and others),

I now see that my question was far too ambiguous. I understand the
difference between std::stack and std::heap as far as looking at each
of those data structures as abstract data types, I just do not
understand how these two data structures are implemented when your C++
code is compiled.

Two points here: First, there is no std::heap, but there are some
functions (such as std::make_heap) for acting on sequences that happen
to be arranged as a heap.

Second, the concept of a "heap" as a data structure seems to be
completely separate from a "heap" as a memory allocation pool. As far as
I can tell there's not any strong similarities between these two things,
they just happen to go by the same name.

What I should've asked is "what is the scope of data when allocated
from the heap, and what is the scope of data when allocated from the
stack (where ``heap'' and ``stack'' are not standards, but are merely
common terms.)

To answer this, I'm going to quote and expand on what Karl said in his
reply:

The scope of memory allocated on the 'stack' is the scope
of the enclosing block. They get destroyed when the enclosing
block is finished. Thats why they are called 'auto' objects.

To this I would add that sometimes the declaration is not physically
inside the block. For example:

int i;
for (int j=0; j<10; ++j)
{
int k;
}

Here, 'j' goes out of scope when the loop finishes, just as 'k' does.
This is different from old "ARM" C++, where 'j' would continue to exist
after the loop, going out of scope at the same time as 'i'. Some
compilers still implement this old rule, and others use their own rule
which allows code using either rule to be accepted (which violates the
standard, by the way).

More from Karl's post:

The scope of memory allocated on the 'heap' is different.
Objects get allocated with new (or malloc) and get destroyed
when a corresponding delete (or free) is executed. Blocks do
no longer influence the scope of these objects.

I want to mention that things that are deallocated with 'free' don't get
"destroyed" in one sense of the word - their destructors don't get
called (unless you do it explicitly). This doesn't always make a
difference, but when it does the difference can be very important. This
is one of the reasons why we usually stick to 'new' and 'delete' in C++.
In fact, you should even avoid 'new' and 'delete' when you can help it.
Explicit memory (or any resource) management is a hassle, and makes it
easy for bugs and lack of exception safety to creep in.

And also, is there a performance difference, in general, of objects
allocated on the stack versus those allocated on the heap, or is this
a completely meaningless question?

Conventional wisdom is that auto (stack) variables are very fast, while
allocating dynamic memory might be slow. In my experience, I've usually
found allocating dynamic memory to be so fast that it doesn't matter
much, but this could depend on several factors. I would suggest not
making speed one of the primary factors in deciding which to use, unless
you have a demonstrated speed problem that can be traced to your memory
allocation.

Allocating an auto variable (one that would be on "the stack") in a
typical C++ implementation using stack frames is a constant time
operation, but the implementation might be able to do even better than
that. Typically, several variables may be allocated at once, and the
entire operation is constant time (this may happen on entry to a
function, and all variables used in the function might be allocated at
this time). Even better, some auto variables might have space reserved
for them when the program begins, so they don't need to be allocated on
"the stack" at all. This only works for auto variables in certain
functions - for example, it won't work for a variable in a function that
is called recursively, where multiple instances of the variable need to
exist simultaneously.

As for dynamic memory... well, I don't know much about typical
implementations of that. But there's been a lot of work done in this
area, and some implementations should be quite fast. I wouldn't expect
it to be as fast as auto variables (it's hard to beat constant-time or
zero-time, after all), but a good implementation should be fast enough
for all but the most extreme situations.

-Kevin

 

[Victor Bazarov]

[...]
To answer this, I'm going to quote and expand on what Karl said in his
reply:

The scope of memory allocated on the 'stack' is the scope
of the enclosing block. They get destroyed when the enclosing
block is finished. Thats why they are called 'auto' objects.

To this I would add that sometimes the declaration is not physically
inside the block. For example:

int i;
for (int j=0; j<10; ++j)
{
int k;
}

Here, 'j' goes out of scope when the loop finishes, just as 'k' does.

Just a short addition: 'k' goes out of scope after _every_ execution
of the controlled statement, and 'j' stays on for all ten iterations.

Victor

 

[MSG]

Two points here: First, there is no std::heap, but there are some
functions (such as std::make_heap) for acting on sequences that happen
to be arranged as a heap.

Second, the concept of a "heap" as a data structure seems to be
completely separate from a "heap" as a memory allocation pool. As far as
I can tell there's not any strong similarities between these two things,
they just happen to go by the same name.

LOL!

That must be because your familiarity with computing is limited to
what C++ standard says (which goes for everyone who cries "off-topic"
at any mention of things they do not understand).

First and foremost, Heap and Stack are data structures, and algorithms
that work on them. "Free store" and "automatic storage" memory
operations use these data structures and algorithms. Hope this clears
it up for you.

MSG

 

[E. Robert Tisdale]

First and foremost,
Heap and Stack are data structures, and algorithms that work on them.

Actually, the term "heap" is just a *pun*
which contrasts with the notion of a stack.
The technical term is free list.

"Free store" and "automatic storage" memory operations
use these data structures and algorithms.

The ANSI/ISO C++ standard doesn't need to specify that
automatic storage is implemented on the program stack or that
free storage is managed as a free list so it doesn't.
But these *are* typical implementations and
every viable C compiler implements them this way.

Hope this clears it up for you.

Actually, the free store is exactly what it appears to be --
storage that is free to be allocated to your program.
*Typically*, the free store extends down from the text
(program) and [static] data segments to the top of the stack.

 

[Sean Cook]

LOL!

That must be because your familiarity with computing is limited to
what C++ standard says (which goes for everyone who cries "off-topic"
at any mention of things they do not understand).

First and foremost, Heap and Stack are data structures, and algorithms
that work on them. "Free store" and "automatic storage" memory
operations use these data structures and algorithms. Hope this clears
it up for you.

MSG

All,

Thanks for the great explanation(s). (And sorry for the top-posting!)

Sean

 

[Rolf Magnus]

Thanks for the great explanation(s). (And sorry for the top-posting!)

One could also call them "stack postings", since they have to be read
bottom up ;-)