Memory (Basics) Memory (Basics) Memory
On Paper: C++'s Abstract Memory Model On Paper: Abstract Memory Model On Paper
C++'s language specification is based on an abstract memory model
Concrete implementations (= compiler, C++ runtime, …) can employ different strategies to satisfy these specifications on a concrete platform (= CPU architecture, operating system, …).
Memory Organisation
Example: std::int16_t i = 1234;
is an object with name i, a size of 2 bytes (= 16 bits)
and value 0000010011010010 which according to its
type int16_t represents the number 1234.
Note that the abstract model doesn't say anything about how memory is partitioned or about cache hierarchies.
Object Storage Duration Types
| Automatic | object lifetime tied to start & end of { … } block scopes |
local variables, function parameters |
|---|---|---|
| Dynamic | object lifetime controlled with special instructions | objects that can be created/destroyed on demand and independent of block scopes |
| Thread | object lifetime tied to start & end of a thread | per-thread storage |
| Static | object lifetime tied to start & end of the program | singletons, … |
In Practice: Actual Memory Handling In Practice: Memory Handling In Practice
Practical realizations of C++'s memory model
- are constrained by features & limitations of the target platform (CPU/memory architecture, operating system, compiler)
- need to fix choices left open by the C++ standard, e.g., number of bits in a byte (8 on most platforms)
- need to support object storage duration/lifetime schemes described by the C++ standard (automatic, dynamic, thread, static)
Common Solution: Dedicated Memory Partitions For Automatic/Dynamic Storage Durations
HEAP (also called Free Store
)
- used for objects of dynamic storage duration,
e.g. the contents of a
std::vector - big, can be used for bulk storage (most of main memory)
- possible to allocate & deallocate any object on demand
- (de-)allocations in no particular order ⇒ fragmentation
- slow allocation: need to find contiguous unoccupied space for new objects
STACK
- used for objects of automatic storage duration: local variables, function parameters, etc.
- small (usually only a few MB)
- fast allocation: new objects are always put on top
- objects de-allocated in reverse order of their creation
- can't de-allocate objects below the topmost (= newest)
Automatic Storage Automatic Storage Automatic
A stack is generally used for objects of automatic storage duration such as local variables (including function parameters):
Use the navigation buttons on the right/left to go forward/backwards.
int main () {
int i = 4;
for (int j = 0; j < i; j++) {
if (j > 2) {
int k = 2 * j;
}
}
}| STACK | ||
| ⋮ |
program starts
int main () {
int i = 4;
for (int j = 0; j < i; j++) {
if (j > 2) {
int k = 2 * j;
}
}
}| STACK | ||
| int i | 4 | |
| ⋮ |
Local variable i is pushed on the stack.
int main () {
int i = 4;
for (int j = 0; j < i; j++) {
if (j > 2) {
int k = 2 * j;
}
}
}| STACK | ||
| int j | 0 | |
| int i | 4 | |
| ⋮ |
- Loop-local variable j is pushed on the stack.
- First loop iteration.
int main () {
int i = 4;
for (int j = 0; j < i; j++) {
if (j > 2) {
int k = 2 * j;
}
}
}| STACK | ||
| int j | 1 | |
| int i | 4 | |
| ⋮ |
Second loop iteration: j is incremented to 1.
int main () {
int i = 4;
for (int j = 0; j < i; j++) {
if (j > 2) {
int k = 2 * j;
}
}
}| STACK | ||
| int j | 2 | |
| int i | 4 | |
| ⋮ |
Third loop iteration: j is incremented to 2.
int main () {
int i = 4;
for (int j = 0; j < i; j++) {
if (j > 2) {
int k = 2 * j;
}
}
}| STACK | ||
| int j | 3 | |
| int i | 4 | |
| ⋮ |
Fourth loop iteration: j is incremented to 3.
int main () {
int i = 4;
for (int j = 0; j < i; j++) {
if (j > 2) {
int k = 2 * j;
}
}
}| STACK | ||
| int k | 6 | |
| int j | 3 | |
| int i | 4 | |
| ⋮ |
- Condition
j > 2is true ⇒ enteringif-branch. - Branch-local variable
kis pushed on the stack.
int main () {
int i = 4;
for (int j = 0; j < i; j++) {
if (j > 2) {
int k = 2 * j;
}
}
}| STACK | ||
| 6 | ||
| int j | 3 | |
| int i | 4 | |
| ⋮ |
- Leaving
if-branch scope:kis popped from the stack. - Note that
k's value still remains in memory. Only the stack's top position marker is decreased by one.
int main () {
int i = 4;
for (int j = 0; j < i; j++) {
if (j > 2) {
int k = 2 * j;
}
}
}| STACK | ||
| 6 | ||
| 3 | ||
| int i | 4 | |
| ⋮ |
- Leaving the
forloop's scope:jis popped from the stack. - Note that
j's current value still remains in memory. Only the stack's top position marker is decreased by one.
int main () {
int i = 4;
for (int j = 0; j < i; j++) {
if (j > 2) {
int k = 2 * j;
}
}
} | STACK | ||
| 6 | ||
| 3 | ||
| 4 | ||
| ⋮ |
- Leaving the scope of the
mainfunction:iis popped from the stack. - Stack top position marker is decreased by one.
Dynamic Memory Allocation
For now: only by using std::vector
Next: more standard library containers (set, map, …)
Much later: manual dynamic memory allocation
In modern C++, manual allocation is actually only really necessary if you want to implement your own dynamic data structures / containers.
Each vector object holds a separate buffer that is dynamically allocated (on the heap) where the actual content is stored.
Right now we only know how to allocate objects on the stack,
but the vector object v itself could also
be allocated on the heap (more on that in later chapters).
vector<int> v {0,1,2,3,4};
Memory blocks, once allocated, can't be resized! (no guarantee that there is space left directly behind previously allocated memory block)
Dynamic array implementations separate the array object from the actual memory block for storing values.
Growth is then done the following way:
- dynamically allocate new, (≈1.1-2×) larger memory block
- copy/move old values to new block
- destroy old, smaller block
.size()→ number of elements in vector.resize(new_number_of_elements).capacity()→ number of avail.available memory slots.reserve(new_capacity)
vector<int> v;
v.push_back(7);
v.reserve(4);
v.push_back(8);
v.push_back(9);
auto s = v.size();
auto c = v.capacity();
v.resize(6,0);If you know the (approximate) number of elements in advance
⇒ reserve before adding elements to the vector!
This avoids unnecessary memory allocations and copying during the growth phase.
std::vector Memory Lifetime Example
vector Lifetime Example
Example
Use the navigation buttons on the right/left to go forward/backwards.
void foo (
vector<int> w,
int x)
{
w[0] = x;
}
int main () {
vector<int> v;
v.push_back(3);
v.push_back(6);
foo(v, 8);
}| HEAP | ||
| STACK | ||
| ⋮ |
program starts
void foo (
vector<int> w,
int x)
{
w[0] = x;
}
int main () {
vector<int> v;
v.push_back(3);
v.push_back(6);
foo(v, 8);
}| HEAP | ||
| STACK | ||
| v | … | |
| ⋮ |
v is put on the stack
void foo (
vector<int> w,
int x)
{
w[0] = x;
}
int main () {
vector<int> v;
v.push_back(3);
v.push_back(6);
foo(v, 8);
}| HEAP | ||
| 3 | ||
| STACK | ||
| v | … | |
| ⋮ |
vector v allocates buffer on the heap and puts 3 into it
void foo (
vector<int> w,
int x)
{
w[0] = x;
}
int main () {
vector<int> v;
v.push_back(3);
v.push_back(6);
foo(v, 8);
}| HEAP | ||
| 3 | ||
| STACK | ||
| v | … | |
| ⋮ |
vector v allocates new buffer in order to make room for
the next element 6
void foo (
vector<int> w,
int x)
{
w[0] = x;
}
int main () {
vector<int> v;
v.push_back(3);
v.push_back(6);
foo(v, 8);
}| HEAP | ||
| 3 | ||
| 6 | ||
| 3 | ||
| STACK | ||
| v | … | |
| ⋮ |
old elements of v are copied to new buffer and
new element 6 is added
void foo (
vector<int> w,
int x)
{
w[0] = x;
}
int main () {
vector<int> v;
v.push_back(3);
v.push_back(6);
foo(v, 8);
}| HEAP | ||
| 6 | ||
| 3 | ||
| STACK | ||
| v | … | |
| ⋮ |
v deallocated its old buffer
void foo(
vector<int> w,
int x)
{
w[0] = x;
}
int main () {
vector<int> v;
v.push_back(3);
v.push_back(6);
foo(v, 8);
}| HEAP | ||
| 6 | ||
| 3 | ||
| STACK | ||
| foo | … | |
| v | … | |
| ⋮ |
program execution jumps to function foo
void foo (
vector<int> w,
int x)
{
w[0] = x;
}
int main () {
vector<int> v;
v.push_back(3);
v.push_back(6);
foo(v, 8);
}| HEAP | ||
| 6 | ||
| 3 | ||
| STACK | ||
| w | … | |
| foo | … | |
| v | … | |
| ⋮ |
entering foo:
local parameter w is put on the stack
w allocates its buffer
void foo (
vector<int> w,
int x)
{
w[0] = x;
}
int main () {
vector<int> v;
v.push_back(3);
v.push_back(6);
foo(v, 8);
}| HEAP | ||
| 6 | ||
| 3 | ||
| 6 | ||
| 3 | ||
| STACK | ||
| w | … | |
| foo | … | |
| v | … | |
| ⋮ |
w copies elements from v
⇒ w is now a local copy of argument v
void foo (
vector<int> w,
int x)
{
w[0] = x;
}
int main () {
vector<int> v;
v.push_back(3);
v.push_back(6);
foo(v, 8);
}| HEAP | ||
| 6 | ||
| 3 | ||
| 6 | ||
| 3 | ||
| STACK | ||
| x | 8 | |
| w | … | |
| foo | … | |
| v | … | |
| ⋮ |
local parameter x is put on the stack
void foo (
vector<int> w,
int x)
{
w[0] = x;
}
int main () {
vector<int> v;
v.push_back(3);
v.push_back(6);
foo(v, 8);
}| HEAP | ||
| 6 | ||
| 8 | ||
| 6 | ||
| 3 | ||
| STACK | ||
| x | 8 | |
| w | … | |
| foo | … | |
| v | … | |
| ⋮ |
the first element of w is changed
void foo (
vector<int> w,
int x)
{
w[0] = x;
}
int main () {
vector<int> v;
v.push_back(3);
v.push_back(6);
foo(v, 8);
}| HEAP | ||
| 6 | ||
| 8 | ||
| 6 | ||
| 3 | ||
| STACK | ||
| x | 8 | |
| w | … | |
| foo | … | |
| v | … | |
| ⋮ |
foo ends:
its local parameters are removed from the stack, beginning with x
void foo (
vector<int> w,
int x)
{
w[0] = x;
}
int main () {
vector<int> v;
v.push_back(3);
v.push_back(6);
foo(v, 8);
}| HEAP | ||
| 6 | ||
| 3 | ||
| STACK | ||
| x | 8 | |
| w | … | |
| foo | … | |
| v | … | |
| ⋮ |
when w is destroyed, it deallocates its heap buffer
void foo (
vector<int> w,
int x)
{
w[0] = x;
}
int main () {
vector<int> v;
v.push_back(3);
v.push_back(6);
foo(v, 8);
}| HEAP | ||
| 6 | ||
| 3 | ||
| STACK | ||
| x | 8 | |
| w | … | |
| foo | … | |
| v | … | |
| ⋮ |
returned from foo;
note that the change to local parameter w
had no effect outside of foo
void foo (
vector<int> w,
int x)
{
w[0] = x;
}
int main () {
vector<int> v;
v.push_back(3);
v.push_back(6);
foo(v, 8);
} | HEAP | ||
| STACK | ||
| x | 8 | |
| w | … | |
| foo | … | |
| v | … | |
| ⋮ |
program ends:
when v is destroyed, it deallocates its heap buffer