STACK v/s HEAP
=> C/C++ supports 3 basic types of memory allocation,
1) Static memory allocation
# happens for static and global variables.
# Memory is allocated once when program is ran and persists throughout the life of program.
# The size of the variable / array must be known at compile time.
# Memory allocation and de-allocation happens automatically (when the variable is instantiated / destroyed).
2) Automatic memory allocation
# happens for function parameters and local variables.
# Memory is allocated when the relevant block is entered, and freed when the block is exited, as many times as necessary.
# The size of the variable / array must be known at compile time.
# Memory allocation and de-allocation happens automatically (when the variable is instantiated / destroyed).
3) Dynamic memory allocation
# Used when one or both constraints cause problem, i.e. memory size & memory allocation time.
# usually when dealing with external (user or file) input.
=> Declaring size of everything at compile time is poor solution, because
1) leads to wasted memory if variables (extra size) aren't actually used
2) no direct provision for information about bits of memory are actually used. This necessitates having some way to tell active from inactive items, which adds complexity and can use up additional memory.
3) most normal variables (including fixed arrays) are allocated in a portion of memory called the STACK. The amount of STACK memory for a program is generally quite small (Default 1 MB on Visual Studio). Exceeding this number will result to stack overflow, and the operating system will probably close down the program.
4) lead to artificial limitations (by not allowing to exceed the fixed size) and/or array overflows (unhandling exceeded array size)
*) These problems are easily addressed via Dynamic Memory Allocation. Dynamic memory allocation is a way for running programs to request memory from the operating system when needed.
*) This memory does not come from the program’s limited STACK memory -- instead, it is allocated from a much larger pool of memory managed by the operating system called the HEAP. On modern machines, the HEAP can be gigabytes in size.
*) Pointers are useful to hold the address of the Dynamically Allocated Memory, otherwise there would have no way to access the memory that was just allocated!
=> STACK & HEAP, Both stored on system's RAM
STACK
1) used for static memory allocation
2) Variables allocated on the STACK are stored directly to the memory
3) Access to this memory is very fast and easy; can't leak.
4) It's allocation is dealt with when the program is compiled
5) Mechanism:
a, b) When a function calls another function which in turns calls another function etc., the execution of all those functions remains suspended until the very last function returns its value.
c) The STACK is always reserved in a LIFO order, the most recently reserved block is always the next block to be freed.
d) This makes it really simple to keep track of the STACK, freeing a block from the STACK is nothing more than adjusting one pointer.
6) Can use the STACK when know exactly how much data will need to allocate before compile time
7) it is not too big.
8) STACK is thread specific. In a multi-threaded situation each thread will have its own completely independent STACK. The STACK is important to consider in exception handling and thread executions.
HEAP
1) used for dynamic memory allocation
2) HEAP size is only limited by the size of virtual memory
3) Accessing this memory is a bit slower
4) Variables allocated on the HEAP have their memory allocated at run time
5) Mechanism:
a) Element of the heap have no dependencies with each other
b) can always be accessed randomly at any time
c) can allocate a block at any time and free it at any time.
d) This makes it much more complex to keep track of which parts of the HEAP are allocated or free at any given time.
6) can use heap if don't know exactly how much data will need at runtime
7) or if need to allocate a lot of data.
8) HEAP is application specific. In a multi-threaded situation each thread will share the HEAP.
=> When to use dynamic allocation,
1) If need to keep lifetime of a variable (keep variable alive) around a long time (like global) or out of the a limited scope. (For short life within a limited scope, static allocation preferable to use)
When memory must live after the function return. (STACK memory is destroyed when function ends, not Dynamic memory)
2) When need lot of memory (i.e large block of memory for a large array, a big structure those can change size dynamically). (Typical STACK size is 1 MB, so anything bigger than 50-100KB should be better be dynamically allocated)
3) For building a structure of unknown size in a loop.
4) For dealing with relatively small variables that only need to persist as long as function using them is alive.
=> Memory areas used by an application
Any system has memory (probably lots of it) that is available for applications to use. When an application is running, operating system loads the application into some of that memory. This memory used by application is divided into different areas, each of which serves a different purpose.
- One area contains program code.
- Another area is used for normal operations (keeping track of which functions were called, creating and destroying global and local variables, etc…).
- However, much of the memory available just sits there, waiting to be handed out to programs that request it.
*) Unlike static or automatic memory, the program itself is responsible for requesting and disposing of dynamically allocated memory.
=> How does dynamic memory allocation work?
- When application dynamically allocate memory, application request the operating system to reserve some of that memory for program’s use. If it can fulfill this request, it will return the address of that memory to application. From that point forward, application can use this memory as it wishes. When application is done with the memory, it can return the memory back to the operating system to be given to another program.
=> What does it mean to delete memory?
- The delete/free operation simply returns the memory being pointed-to back to the operating system. The operating system is then free to reassign that memory to another application (or to same application again later).
- Even after delete/free operation, the pointer variable still has the same scope as before, and can be assigned a new value just like any other variable.
- C/C++ does not make any guarantees about what will happen to the contents of deallocated memory, or to the value of the pointer being freed/deleted. In most cases, the memory returned to the operating system will contain the same values it had before it was returned, and the pointer will be left pointing to the now deallocated memory.
- NOTE: Deleting a pointer that is not pointing to dynamically allocated memory may cause bad things to happen.
- Dangling Pointer: A pointer that is pointing to deallocated memory. Dereferencing or deleting a dangling pointer will lead to undefined behavior.
=> Few best practices
1) Try to avoid having multiple pointers point at the same piece of dynamic memory. If this is not possible, be clear about which pointer “owns” the memory (and is responsible for deleting it) and which are just accessing it.
2) Rule: Set deleted pointers to 0 (or nullptr in C++11) unless they are going out of scope immediately afterward.
=> Initialization:
Direct Initialization int* ptr1 = new int (5);
Uniform Initialization int* ptr2 = new int {6};
=> C++ new operator can fail
- When requesting memory from the operating system, in rare circumstances, the operating system may not have any memory to grant the request with.
- If new fails, a bad_alloc exception is thrown (by default); which may need to handle properly.
- There's an alternate form of new (to return null pointer if memory can't allocated), that can be used instead of throwing an exception. This is done by adding the constant std::nothrow between the new keyword and the allocation type.
int *value = new (std::nothrow) int; // value will be set to a null pointer if the integer allocation fails
- NOTE: It may be common to skip NULL check after allocation; as memory allocation only fails rarely (and almost never in a dev environment), and there might be serious reason (/leak) for memory fail.
=> Null pointers (pointers set to address 0 or nullptr) basically says “no memory has been allocated/pointed to this pointer”. This is useful to avoid access of non-allocated & Dangling pointer. NOTE: Delete/free operation on a null pointer has no effect.
One should be careful not to dereference dangling or null pointer.
=> Memory leaks
- Dynamically allocated memory effectively has no scope (i.e. it stays allocated until it is explicitly deallocated or until the program ends/terminates and the operating system cleans it up, assuming your operating system does that).
- However, the pointers used to hold dynamically allocated memory addresses follow the scoping rules of normal variables.
- This mismatch can create Memory Leaks, which happen when program loses the address of some bit of dynamically allocated memory before giving it back to the operating system. When this happens, your program can’t delete the dynamically allocated memory, because it no longer knows where it is. The operating system also can’t use this memory, because that memory is considered to be still in use by your program.
Memory leaks eat up free memory while the program is running, making less memory available not only to this program, but to other programs as well. Programs with severe memory leak problems can eat all the available memory, causing the entire machine to run slowly or even crash. Only after your program terminates is the operating system able to clean up and “reclaim” all leaked memory.
- A Memory Leak can occur if a pointer holding the address of the dynamically allocated memory is assigned another value / pointer before delete/free dynamically allocated memory.
- A Memory Leak is also possible via double-allocation, with delete/free the pointer before re-assigning