"heap" vs "stack"

[Joe Van Dyk]

Can someone explain what a heap and what a stack is? And why I should
care? I used to know, but then I forgot. And I can't seem to find it
in the C++ FAQ.

I keep reading how allocating from the heap is slow or something, and I
have no idea why that would be.

Joe

[Victor Bazarov]

Joe Van Dyk wrote:

Can someone explain what a heap and what a stack is? And why I should
care? I used to know, but then I forgot. And I can't seem to find it
in the C++ FAQ.
A "heap" is usually a relatively unorganized data repository. A "stack"
is a quite ordered data container with elements queued up in the "first in
-- last out" manner.
I keep reading how allocating from the heap is slow or something, and
I have no idea why that would be.

In more loose lingo than C++ Standard uses, "heap" is the synonym for the
free store, and "stack" is the place where objects with automatic storage
duration are allocated.

V
--
Please remove capital As from my address when replying by mail

[Phlip]

Joe Van Dyk wrote:

Can someone explain what a heap and what a stack is? And why I should
care? I used to know, but then I forgot. And I can't seem to find it in
the C++ FAQ.
A stack is a data structure that runs Last In First Out. That's so efficient
and convenient that CPUs generally implement a stack in hardware, so
functions can park their local variables on it. When they call servant
functions, these add their variables to the current head of the stack, then
point the head to the next spot after their variables. So that's how
functions can call functions, each keeping private variables for as long as
each function runs.

A heap is simply the opposite of a stack. You can allocate and de-allocate
arbitrarily sized chunks of heap, in an arbitrary order.
I keep reading how allocating from the heap is slow or something, and I
have no idea why that would be.

A heap must perform much more work at allocation and deallocation time. It
searches for a good unused region, checks this is larger than the requested
size, writes markers around the block to reserve it, fixes up other markers
in the heap to point correctly, and returns a pointer to the block. When it
gets the block back from the program, it erases the markers, and fixes up
the other markers.

A good alternative is a custom heap that returns fixed sized blocks. That's
orders of magnitude faster. If each block is larger than a pointer, then the
heap can store its list of free blocks directly into storage area. Each free
block contains a pointer to the next free block.

--
Phlip
http://www.greencheese.org/ZeekLand <-- NOT a blog!!!

[osmium]

"Phlip" writes:

A heap is simply the opposite of a stack.

Much like a lizard is simply the opposite of a nuclear reactor?

[bb]

MyClass object1; // creates the object in stack

MyClass *object2 = new MyClass(); // creates the object in heap

When you create an object in stack, memory is managed automatically for
you i.e., memory is released as soon as it goes out of scope.

When you create an object in the heap, it is your RESPONSIBILITY to
release the memory as soon as you are finished with it by calling
'delete' or else it leads to memory leak.

'heap' helps you to allocate memory dynamically at run time.

BTW, in Java, you cannot allocate objects in the stack.

[Martin Jørgensen]

bb wrote:

MyClass object1; // creates the object in stack
I didn't get the impression that the above "created" anything anywhere.

I got the impression that it's purely a definition so the compiler knows
the data type, when it finds "object1" later in the program. object1 is
first created when it's first used I think..
MyClass *object2 = new MyClass(); // creates the object in heap

Agreed.
Best regards / Med venlig hilsen
Martin Jørgensen

--
---------------------------------------------------------------------------
Home of Martin Jørgensen - http://www.martinjoergensen.dk

[markmcb]

Allocating from the heap is slow because it involves system calls in
whatever operating system that you are using. When using the stack,
everything is setup at compile time, and you do not have to make system
calls. Variables declared on the stack are automatically deleted for
you when they go out of scope. Variable declared on the heap must be
explicitly deleted when finished or there will be a memory leak.

Cheers,
Mark

[Gavin Deane]

Martin Jørgensen wrote:

bb wrote:

MyClass object1; // creates the object in stack
I didn't get the impression that the above "created" anything anywhere.

It does.
I got the impression that it's purely a definition so the compiler knows
the data type, when it finds "object1" later in the program. object1 is
first created when it's first used I think..

A definition *is* the creation of something. You might be confusing the
concepts of definition and declaration.

That statment is both the declaration of object1 (introduction of the
name object1 and its type) and definition of object1 (actual creation
of the object). The default constructor of MyClass will be called to
construct object1 in that statement, not at some later point.

Gavin Deane

[Victor Bazarov]

Martin Jørgensen wrote:

bb wrote:

MyClass object1; // creates the object in stack
I didn't get the impression that the above "created" anything
anywhere.

It depends on where that statement appears. If it appears in a class
definition, then it's a mere declaration. If it appears outside of any
class definition, then it's a declaration _and_ a definition (and also
default-initialisation).

The "stack vs. not stack" is debatable. If the statement appears outside
of any function scope, it's not stack, usually.
I got the impression that it's purely a definition so the compiler
knows the data type, when it finds "object1" later in the program.
object1 is first created when it's first used I think..

No. The semantic rule is that it's created where it's defined. For all
intents and purposes, it may never be "used". Yet, it has to exist because
it will be destroyed.

MyClass *object2 = new MyClass(); // creates the object in heap

Agreed.

Yet, it creates the 'object2' _pointer_ elsewhere.

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

[Martin Jørgensen]

Gavin Deane wrote:

Martin Jørgensen wrote:

bb wrote:

MyClass object1; // creates the object in stack
I didn't get the impression that the above "created" anything anywhere.

It does.

I got the impression that it's purely a definition so the compiler knows
the data type, when it finds "object1" later in the program. object1 is
first created when it's first used I think..

A definition *is* the creation of something. You might be confusing the
concepts of definition and declaration.

Oh, yeah...... Ofcourse...
That statment is both the declaration of object1 (introduction of the
name object1 and its type) and definition of object1 (actual creation
of the object). The default constructor of MyClass will be called to
construct object1 in that statement, not at some later point.

Oh, yeah... I remember that now...
Best regards / Med venlig hilsen
Martin Jørgensen

--
---------------------------------------------------------------------------
Home of Martin Jørgensen - http://www.martinjoergensen.dk

[markmcb]

>> MyClass object1; // creates the object in stack

I didn't get the impression that the above "created" anything anywhere. I got the impression that it's purely a definition so the compiler knows
the data type, when it finds "object1" later in the program. object1 is
first created when it's first used I think..

Assuming that this declaration is in the scope of a function, it will
create object1 on the stack. If the declaraion is in a cpp file, but
outside the scope of a function, it will be allocated from the heap at
initialization time. If this is in a header file as part of a class
definition, then it is used by the compiler to determine the size of
the class that is being defined. In that case, object1 would only be
created when the class that contains it is instantiated, either on the
stack or heap.

Cheers,
Mark

[Joe Van Dyk]

Phlip wrote:

Joe Van Dyk wrote:

Can someone explain what a heap and what a stack is? And why I should
care? I used to know, but then I forgot. And I can't seem to find it in
the C++ FAQ.

A stack is a data structure that runs Last In First Out. That's so efficient
and convenient that CPUs generally implement a stack in hardware, so
functions can park their local variables on it. When they call servant
functions, these add their variables to the current head of the stack, then
point the head to the next spot after their variables. So that's how
functions can call functions, each keeping private variables for as long as
each function runs.

A heap is simply the opposite of a stack. You can allocate and de-allocate
arbitrarily sized chunks of heap, in an arbitrary order.

I keep reading how allocating from the heap is slow or something, and I
have no idea why that would be.

A heap must perform much more work at allocation and deallocation time. It
searches for a good unused region, checks this is larger than the requested
size, writes markers around the block to reserve it, fixes up other markers
in the heap to point correctly, and returns a pointer to the block. When it
gets the block back from the program, it erases the markers, and fixes up
the other markers.

A good alternative is a custom heap that returns fixed sized blocks. That's
orders of magnitude faster. If each block is larger than a pointer, then the
heap can store its list of free blocks directly into storage area. Each free
block contains a pointer to the next free block.

Ah, that's right. It's all flooding back to me now. omg, now I even
remember something called tail-recursion (or something like that).

Thanks everyone,
Joe

[Zodiaq]

Dnia 14 Apr 2006 07:18:03 -0700, ma*****@gmail.com napisa³(a):

Allocating from the heap is slow because it involves system calls in
whatever operating system that you are using. When using the stack,
everything is setup at compile time, and you do not have to make system
calls. Variables declared on the stack are automatically deleted for
you when they go out of scope. Variable declared on the heap must be
explicitly deleted when finished or there will be a memory leak.

But what about static 'local' (inside of functions/methods) variables?
These are exceptions from this rule - these are allocate on heap first time
they are used (until then these are declarations), yet You can't delete
these explicitly... an interesting exception to above rule :)

--
..:-Dad, do you think there's people on other planets? :.
..:-I don't know, Sparks. But I guess I'd say if it is just us...seems like:.
..: an awful waste of space. : JID: zodiaq(at)jabber.aster.pl Zodiaq ]] :.

[Ron Natalie]

Zodiaq wrote:

But what about static 'local' (inside of functions/methods) variables?
These are exceptions from this rule - these are allocate on heap first time
they are used (until then these are declarations), yet You can't delete
these explicitly... an interesting exception to above rule :)

Actually, static locals are NOT allocated from either heap nor stack
at runtime. They are typically part of the initial data allocation
when the program loads.

You're confusing allocation with initialization.

[Victor Bazarov]

Ron Natalie wrote:

But what about static 'local' (inside of functions/methods)
variables? These are exceptions from this rule - these are allocate
on heap first time they are used (until then these are
declarations), yet You can't delete these explicitly... an
interesting exception to above rule :)
Actually, static locals are NOT allocated from either heap nor stack
at runtime. They are typically part of the initial data allocation
when the program loads.

....which is not to say they are not allocated from free store. It is
unspecified how, or where from, the memory for them is obtained.
[..]

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

[Fei Liu]

Zodiaq wrote:

Dnia 14 Apr 2006 07:18:03 -0700, ma*****@gmail.com napisa³(a):

Allocating from the heap is slow because it involves system calls in
whatever operating system that you are using. When using the stack,
everything is setup at compile time, and you do not have to make system
calls. Variables declared on the stack are automatically deleted for
you when they go out of scope. Variable declared on the heap must be
explicitly deleted when finished or there will be a memory leak.

But what about static 'local' (inside of functions/methods) variables?
These are exceptions from this rule - these are allocate on heap first time
they are used (until then these are declarations), yet You can't delete
these explicitly... an interesting exception to above rule :)

A static variable is usually taken care of by a linker. Most unix
linker will put a static variable in the so called 'BSS' (block started
by symbol) segment where a variable only has its symbol and storage but
not its initial value. This is practical implementation detail and not
c++ relevant. A static variable is thus allocated by the
compiler/linker and stays static during runtime.