Stack and Heap in C and C++





The Stack
It's a special region of your computer's memory that stores temporary variables created by each function (including the main() function). The stack is a "FILO" (first in, last out) data structure, that is managed and optimized by the CPU quite closely. Every time a function declares a new variable, it is "pushed" onto the stack. Then every time a function exits, all of the variables pushed onto the stack by that function, are freed (that is to say, they are deleted). Once a stack variable is freed, that region of memory becomes available for other stack variables.

Variables allocated on the stack, or automatic variables, are stored directly to this memory. Access to this memory is very fast, and it’s allocation is dealt with when the program is compiled.

1. lives in RAM (random-access memory), but has direct support from the processor via its stack pointer.
2. stack pointer is moved down to create new memory and moved up to release that memory.
3. extremely fast and efficient way to allocate storage, second only to registers.
Every thread requires its own stack, they are separated from other stacks, each stack may grow separately.
very fast access
don't have to explicitly de-allocate variables
space is managed efficiently by CPU, memory will not become fragmented
local variables only
limit on stack size (OS-dependent)
variables cannot be resized

The place where arguments of a function call are stored
The place where registers of the calling function are saved
The place where local data of called function is allocated
The place where called function leaves result for calling function
Supports recursive function calls

The Heap
Variables allocated on the heap, or dynamic variables, have their memory allocated at run time (ie: as the program is executing). Accessing this memory is a bit slower, but the heap size is only limited by the size of virtual memory. This memory remains allocated until explicitly freed by the program and, as a result, may be accessed outside of the block in which it was allocated.

Heap grows toward stack
All threads share the same heap
Data structures may be passed from one thread to another.
variables can be accessed globally
no limit on memory size
(relatively) slower access
no guaranteed efficient use of space, memory may become fragmented over time as blocks of memory are allocated, then freed
you must manage memory (you're in charge of allocating and freeing variables)
variables can be resized using realloc()

Difference between the stack and the heap
Both Stack and Heap are stored in RAM.
Every thread has its own stack, but all threads in one application shares one heap.
Variable allocation is fast on stack where as on heap its slow.
Variables on stack go out of scope automatically once their need is done. That means de-allocation on stack is automatic. On heap, in regards to C and C++ we have to manually de-allocate where as high-level languages such as Java has garbage collection schemes.
On stack, we can access variables without the need for pointers and hence its fast and that is the reason it is used to store local data, method arguments and the call stack etc all that which needs less amount of memory.
You would use stack only when you know for sure how much memory for your data you would need even before compile time. On the other hand, we can use heap without us having to know for sure the amount of memory we need.
Stack is used for static memory allocation and Heap for dynamic memory allocation.
Stack is thread specific and Heap is application specific.
Memory block in stack will be freed when thread is terminated while heap is freed only after application termination.

Stack Overflow and Heap Overflow(OutOfMemory)

Can an object be stored on the stack instead of the heap?
Yes, an object can be stored on the stack. If you create an object inside a function without using the “new” operator then this will create and store the object on the stack, and not on the heap. Suppose we have a C++ class called Member, for which we want to create an object.

Can the stack grow in size? Can the heap grow in size?
The stack is set to a fixed size, and can not grow past it’s fixed size (although some languages have extensions that do allow this). So, if there is not enough room on the stack to handle the memory being assigned to it, a stack overflow occurs. This often happens when a lot of nested functions are being called, or if there is an infinite recursive call.

If the current size of the heap is too small to accommodate new memory, then more memory can be added to the heap by the operating system.

What can go wrong with the stack and the heap?
If the stack runs out of memory, then this is called a stack overflow – and could cause the program to crash. 
The heap could have the problem of fragmentation, which occurs when the available memory on the heap is being stored as noncontiguous (or disconnected) blocks – because used blocks of memory are in between the unused memory blocks. When excessive fragmentation occurs, allocating new memory may be impossible because of the fact that even though there is enough memory for the desired allocation, there may not be enough memory in one big block for the desired amount of memory.
heap overflow is generally called 'out of memory'.

References
http://www.quora.com/Objective-C-programming-language/What-is-the-difference-between-the-stack-and-the-heap
http://www.programmerinterview.com/index.php/data-structures/difference-between-stack-and-heap/
http://timmurphy.org/2010/08/11/the-difference-between-stack-and-heap-memory-allocation/comment-page-1/

No comments:

Post a Comment

Labels

Algorithm (219) Lucene (130) LeetCode (97) Database (36) Data Structure (33) text mining (28) Solr (27) java (27) Mathematical Algorithm (26) Difficult Algorithm (25) Logic Thinking (23) Puzzles (23) Bit Algorithms (22) Math (21) List (20) Dynamic Programming (19) Linux (19) Tree (18) Machine Learning (15) EPI (11) Queue (11) Smart Algorithm (11) Operating System (9) Java Basic (8) Recursive Algorithm (8) Stack (8) Eclipse (7) Scala (7) Tika (7) J2EE (6) Monitoring (6) Trie (6) Concurrency (5) Geometry Algorithm (5) Greedy Algorithm (5) Mahout (5) MySQL (5) xpost (5) C (4) Interview (4) Vi (4) regular expression (4) to-do (4) C++ (3) Chrome (3) Divide and Conquer (3) Graph Algorithm (3) Permutation (3) Powershell (3) Random (3) Segment Tree (3) UIMA (3) Union-Find (3) Video (3) Virtualization (3) Windows (3) XML (3) Advanced Data Structure (2) Android (2) Bash (2) Classic Algorithm (2) Debugging (2) Design Pattern (2) Google (2) Hadoop (2) Java Collections (2) Markov Chains (2) Probabilities (2) Shell (2) Site (2) Web Development (2) Workplace (2) angularjs (2) .Net (1) Amazon Interview (1) Android Studio (1) Array (1) Boilerpipe (1) Book Notes (1) ChromeOS (1) Chromebook (1) Codility (1) Desgin (1) Design (1) Divide and Conqure (1) GAE (1) Google Interview (1) Great Stuff (1) Hash (1) High Tech Companies (1) Improving (1) LifeTips (1) Maven (1) Network (1) Performance (1) Programming (1) Resources (1) Sampling (1) Sed (1) Smart Thinking (1) Sort (1) Spark (1) Stanford NLP (1) System Design (1) Trove (1) VIP (1) tools (1)

Popular Posts