Heap and Stack memory

I can not get my head around it

Page 1 of 1

7 Replies - 2675 Views - Last Post: 14 October 2010 - 07:06 AM Rate Topic: -----

#1 surreal_kc  Icon User is offline

  • New D.I.C Head

Reputation: 5
  • View blog
  • Posts: 28
  • Joined: 27-September 10

Heap and Stack memory

Posted 13 October 2010 - 07:28 PM

This one is a bit more advanced then my previous questions. I am having a difficult time wrapping my head around the concept of Heap, Stack, and something to do with memory allocations? I know i probably wont need this information in my arsenal of knowledge for a long time to come, but when i find something that interests me i can not leave it alone. So i have done a lot of research, read a few documents that made me feel smarter, but nothing really clicked with me. I need some one who can explain to me what Heap and Stack are in the coding world, and explain it in terms i may be able to follow. Give examples of Heap and Stack in code, and explain how they work, why i need to know their difference and so forth.

This is what i have read so far, and still have very little understanding of what is going on. I kind of feel dumb, but the truth is, none of these links have any documentation i can relate to.
http://mailman.linux...ary/002013.html
http://en.wikipedia....data_structure)
http://en.wikipedia....iki/Heap_memory
http://www.maxi-pedi...+heap+and+stack

Is This A Good Question/Topic? 0
  • +

Replies To: Heap and Stack memory

#2 Oler1s  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1395
  • View blog
  • Posts: 3,884
  • Joined: 04-June 09

Re: Heap and Stack memory

Posted 13 October 2010 - 08:19 PM

Here are the basics. There are three ways something can be allocated. Automatic, static, and dynamic. Here's how you identify static. It's a global variable, or you used the keyword static. Dynamic? You used new (or malloc in C). Automatic? It's not static and it's not dynamic.

Automatic allocated stuff goes on the stack. You don't hear people talking about automatic allocation. You hear people talking about stack space, which is an OS concept. Dynamic matches to heap. Stack space is limited, so if you need to allocate large variables, like huge arrays, allocate dynamically.

Here's an illustrative example.

int * p = new int;



Is p on the stack or the heap? The answer is on the stack. It's pointing to an integer. Where is that integer? On the heap.
Was This Post Helpful? 2
  • +
  • -

#3 toshiro  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 21
  • View blog
  • Posts: 137
  • Joined: 27-June 09

Re: Heap and Stack memory

Posted 13 October 2010 - 08:22 PM

Within C, memory is divided into two broad catigories: Heap and Stack. A stack in C contains each of the function calls executed within a min method. WE'll call these activation records. One looks like this:

Method Sig

Local Variables

Global Variables

Return Type

Parameters

This is an abstract activation record - I think C handles it a bit differently.

Each of these sections of data are allocated the necessary bits to hold each value. Let's assume that in this case, we only deal in 32-bit primitive ints. So, if the sig is a mem location 0000 and the next free sector of legal memory would be the last memory location plus 32 bits. Each time this func is called, a new activation record is put on the Stack. The stack is a integral part of the C compiler and runner. Every time a method is called in the main func 'int main()' an activation record containing the local and global variables, parameters, and return type. The Heap on the other hand is the place that memory is allocated when the programmer explicitly calls for memory with a malloc statement. Malloc allocates a static amount of memory pre-compile that can't be modified during runtime. But keep in mind, when memory is allotted within the user-defined heap, the programmer must then deallocate the memory when the program has reached is closing case. Otherwise, a memory leak can occur when memory is not freed after a program's execution. This condition can cause programs to close unexpectedly and non-deterministically as they find that there is no where to write to memory. A reboot can usually cure this, or if there is a virtual machine in use, the system will purge memory.

THe next step in things that can go horribly wrong is a stack overflow error. Like a memory leak in a heap, a stack overflow happens when too many activation records are added to the stack. When there is not an attainable base/trivial case with a recursive function call, you get a stack overflow in which the CPU's physical memory is exceeded by trying to put too many activation records onto the stack.

In terms of data structures - without taking into account their use in a compiler - a stack is a first in, last out data structure that belongs to the linked lists of data structures since these structs usually have both a head and tail pointer, but sometimes only a head pointer. This stack acts just like the stack for activation records within a C compiler/operating system. A heap on the other hand is sometimes called a priority queue in which data comes in to the head and leaves first as well. Think of a line of people. The first person in line goes first and so on. The memory allocation heap in C and many other compilers acts just like that in terms of priority for allocation of memory.
Was This Post Helpful? 2
  • +
  • -

#4 surreal_kc  Icon User is offline

  • New D.I.C Head

Reputation: 5
  • View blog
  • Posts: 28
  • Joined: 27-September 10

Re: Heap and Stack memory

Posted 13 October 2010 - 08:45 PM

View PostOler1s, on 13 October 2010 - 07:19 PM, said:

Here are the basics. There are three ways something can be allocated. Automatic, static, and dynamic. Here's how you identify static. It's a global variable, or you used the keyword static. Dynamic? You used new (or malloc in C). Automatic? It's not static and it's not dynamic.


I'm sorry, your question marks are throwing me off. what do you mean at statis. Dynamic? That just makes me lost. I was following you up-to that point.

and what would making a pointer in the stack that points at heap values do for my program? Does it improve performance or something? How important is it that i learn Heap and Stack allocations?
Was This Post Helpful? 0
  • +
  • -

#5 Oler1s  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1395
  • View blog
  • Posts: 3,884
  • Joined: 04-June 09

Re: Heap and Stack memory

Posted 13 October 2010 - 09:33 PM

Quote

I'm sorry, your question marks are throwing me off. what do you mean at statis. Dynamic?
Here's what I said: "There are three ways something can be allocated. Automatic, static, and dynamic." Then I said "Here's how you identify static." Clearly, I'm pointing out how to identify each type of allocation.

Quote

and what would making a pointer in the stack that points at heap values do for my program?
Here's an exercise. Read a file of integers. You don't know how many integers there are until runtime.

Quote

Does it improve performance or something?
No. Dynamic allocation is generally less efficient. Depends on the language and implementation, actually. But, pretty much, you can go by the rule that dynamically allocate only when you need to.

Quote

How important is it that i learn Heap and Stack allocations?
Only a few steps better than asking me "how important is it that I learn about variables and constants?"
Was This Post Helpful? 1
  • +
  • -

#6 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5825
  • View blog
  • Posts: 12,677
  • Joined: 16-October 07

Re: Heap and Stack memory

Posted 14 October 2010 - 05:47 AM

View Posttoshiro, on 13 October 2010 - 09:22 PM, said:

Malloc allocates a static amount of memory pre-compile that can't be modified during runtime.


Post-compile?

View Posttoshiro, on 13 October 2010 - 09:22 PM, said:

But keep in mind, when memory is allotted within the user-defined heap, the programmer must then deallocate the memory when the program has reached is closing case.


The user doesn't define the heap, rather they ask for memory off of it. Their internal record of what they've been given from the heap, their pointer, is allocated on the stack. In C ( or C++ for that matter ) just loosing that pointer reference isn't enough to return that memory; it must be returned explicitly. When the program looses all reference to memory it's asked for without releasing it, that's a memory leak.

It's good to believe that memory leaks happen as you describe, impacting the entire OS; it keeps programmers honest. In reality, operating systems track the memory requested by a process. When the process dies, the OS reclaims the memory that was allocated to it. You can take a system down if the program never ends. However, when it does end it's sins are usually forgiven.

Processes are jailed to some extent in most modern OSes. You used to be able to write to just any memory location in old DOS land. Now it takes an act of god to do a direct screen write.
Was This Post Helpful? 1
  • +
  • -

#7 toshiro  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 21
  • View blog
  • Posts: 137
  • Joined: 27-June 09

Re: Heap and Stack memory

Posted 14 October 2010 - 07:00 AM

Right - thanks - don't know why i said user-defined heap. That's just silly. And thats right - mallocing happens post compile... oh well. Hopefully i haven't led the OP too far astray.
Was This Post Helpful? 1
  • +
  • -

#8 surreal_kc  Icon User is offline

  • New D.I.C Head

Reputation: 5
  • View blog
  • Posts: 28
  • Joined: 27-September 10

Re: Heap and Stack memory

Posted 14 October 2010 - 07:06 AM

View Posttoshiro, on 14 October 2010 - 06:00 AM, said:

Right - thanks - don't know why i said user-defined heap. That's just silly. And thats right - mallocing happens post compile... oh well. Hopefully i haven't led the OP too far astray.


Your slight mistakes lead baavgai to correct them leading to more on the issues at hand. Which in turn lead to me learning this stuff in another light. I appreciate the effort and the unexpected additional details xD
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1