Does This Type of Memory Get Allocated on the Heap or the Stack

What and where are the stack and heap?

The stack is the memory set aside as scratch space for a thread of execution. When a function is called, a block is reserved on the top of the stack for local variables and some bookkeeping data. When that function returns, the block becomes unused and can be used the next time a function is called. The stack is always reserved in a LIFO (last in first out) order; the most recently reserved block is always the next block to be freed. This makes it really simple to keep track of the stack; freeing a block from the stack is nothing more than adjusting one pointer.

The heap is memory set aside for dynamic allocation. Unlike the stack, there's no enforced pattern to the allocation and deallocation of blocks from the heap; you can allocate a block at any time and free it at any time. This makes it much more complex to keep track of which parts of the heap are allocated or free at any given time; there are many custom heap allocators available to tune heap performance for different usage patterns.

Each thread gets a stack, while there's typically only one heap for the application (although it isn't uncommon to have multiple heaps for different types of allocation).

To answer your questions directly:

To what extent are they controlled by the OS or language runtime?

The OS allocates the stack for each system-level thread when the thread is created. Typically the OS is called by the language runtime to allocate the heap for the application.

What is their scope?

The stack is attached to a thread, so when the thread exits the stack is reclaimed. The heap is typically allocated at application startup by the runtime, and is reclaimed when the application (technically process) exits.

What determines the size of each of them?

The size of the stack is set when a thread is created. The size of the heap is set on application startup, but can grow as space is needed (the allocator requests more memory from the operating system).

What makes one faster?

The stack is faster because the access pattern makes it trivial to allocate and deallocate memory from it (a pointer/integer is simply incremented or decremented), while the heap has much more complex bookkeeping involved in an allocation or deallocation. Also, each byte in the stack tends to be reused very frequently which means it tends to be mapped to the processor's cache, making it very fast. Another performance hit for the heap is that the heap, being mostly a global resource, typically has to be multi-threading safe, i.e. each allocation and deallocation needs to be - typically - synchronized with "all" other heap accesses in the program.

A clear demonstration:


_{Image source: vikashazrati.wordpress.com}

Does this type of memory get allocated on the heap or the stack?

Given a slight modification of your example:

class Foo{
    private:
        int x[100];
        int *y;
    public:
        Foo()
        {
           y = new int[100];
        }
        ~Foo()
        { 
           delete[] y; 
        }

}

Example 1:

Foo *bar = new Foo();

• x and y are on the heap:
• sizeof(Foo*) is created on the stack.
• sizeof(int) * 100 * 2 + sizeof(int *) is on the heap

---

Example 2:

Foo bar;

• x is on the stack, and y is on the heap
• sizeof(int) * 100 is on the stack (x) + sizeof(int*)
• sizeof(int) * 100 is on the heap (y)

Actual sizes may differ slightly due to class/struct alignment depending on your compiler and platform.

Allocated memory is in the stack or heap

Possibly neither. The precise terms are

• static storage: for data that exists as long as the process exists;
• automatic storage: for data that is allocated and fred as the process enters/exits different scopes;
• dynamic storage: for data that must be explicitly requested and exists until it is explicitly fred.

Usually automatic memory lives in the stack and dynamic storage lives in the heap. But the compiler is completely free to implement all those storage types in whatever way they want, as long as it respects the rules for lifespan.

So:

static vector1Int hello;

is in the file scope and creates an object of type vector1Int in static storage.

And this

hello = vector1Int(8,12);

will cause std::vector to create room for at least 8 integers. We can usually assume that this will be taken from dynamic storage. However, this is not a rule. For instance, you could easily make std::vector use static or automatic memory by implementing your own allocator (not general purpose memory allocator, but STL allocator).

When your program reaches the end of the main function, the destructor of std::vector will be called for hello, and any dynamic memory that hello had requested will be given back to the memory manager.

The memory for the object hello itself is not fred because it is static. Instead, it is given back to the OS together with anything else the process used when the process terminates.

Now, if hello had been declared as a local variable of create, then the destructor would be called at the end of that function. In that case, hello would have been allocated at automatic storage, and would be fred at the end of create.

memory allocation in Stack and Heap

I'm not entirely sure what you're asking, but I'll try my best to answer.

The following declares a variable i on the stack:

int i;

When I ask for an address using &i I get the actual location on the stack.

When I allocate something dynamically using malloc, there are actually TWO pieces of data being stored. The dynamic memory is allocated on the heap, and the pointer itself is allocated on the stack. So in this code:

int* j = malloc(sizeof(int));

This is allocating space on the heap for an integer. It's also allocating space on the stack for a pointer (j). The variable j's value is set to the address returned by malloc.

When vectors are allocated, do they use memory on the heap or the stack?

vector<Type> vect;

will allocate the vector, i.e. the header info, on the stack, but the elements on the free store ("heap").

vector<Type> *vect = new vector<Type>;

allocates everything on the free store.

vector<Type*> vect;

will allocate the vector on the stack and a bunch of pointers on the free store, but where these point is determined by how you use them (you could point element 0 to the free store and element 1 to the stack, say).

Stack and heap misunderstanding in Swift

I've always known that reference type variables are stored in the heap while value type variables are stored in the stack.

This is only partially true in Swift. In general, Swift makes no guarantees about where objects and values are stored, except that:

1. Reference types have a stable location in memory, so that all references to the same object point to exactly the same place, and
2. Value types are not guaranteed to have a stable location in memory, and can be copied arbitrarily as the compiler sees fit

This technically means that object types can be stored on the stack if the compiler knows that an object is created and destructed within the same stack frame with no escaping references to it, but in practice, you can basically assume that all objects are allocated on the heap.

For value types, the story is a little more complicated:

• Unless a location-based reference is required of a value (e.g., taking a reference to a struct with &), a struct may be located entirely in registers: operating on small structs may place its members in CPU registers so it never even lives in memory. (This is especially the case for small, possibly short-lived value types like Ints and Doubles, which are guaranteed to fit in registers)
• Large value types do actually get heap-allocated: although this is an implementation detail of Swift that theoretically could change in the future, structs which are larger than 3 machine words (e.g., larger than 12 bytes on a 32-bit machine, or 24 bytes on a 64-bit machine) are pretty much guaranteed to be allocated and stored on the heap. This doesn't conflict with the value-ness of a value type: it can still be copied arbitrarily as the compiler wishes, and the compiler does a really good job of avoiding unnecessary allocations where it can

So where are ints, doubles, strings, etc. are kept when they are defined inside a class, aka reference type?

This is an excellent question that gets at the heart of what a value type is. One way to think of the storage of a value type is inline, wherever it needs to be. Imagine a

struct Point {
    var x: Double
    var y: Double
}

structure, which is laid out in memory. Ignoring the fact that Point itself is a struct for a second, where are x and y stored relative to Point? Well, inline wherever Point goes:

┌───────────┐
│   Point   │
├─────┬─────┤
│  x  │  y  │
└─────┴─────┘

When you need to store a Point, the compiler ensures that you have enough space to store both x and y, usually one immediately following the other. If a Point is stored on the stack, then x and y are stored on the stack, one after the other; if Point is stored on the heap, then x and y live on the heap as part of Point. Wherever Swift places a Point, it always ensures you have enough space, and when you assign to x and y, they are written to that space. It doesn't terribly matter where that is.

And when Point is part of another object? e.g.

class Location {
    var name: String
    var point: Point
}

Then Point is also laid out inline wherever it is stored, and its values are laid out inline as well:

┌──────────────────────┐
│       Location       │
├──────────┬───────────┤
│          │   Point   │
│   name   ├─────┬─────┤
│          │  x  │  y  │
└──────────┴─────┴─────┘

In this case, when you create a Location object, the compiler ensures that there's enough space to store a String and two Doubles, and lays them out one after another. Where that is, again, doesn't matter, but in this case, it's all on the heap (because Location is a reference type, which happens to contain values).

---

As for the other way around, object storage has to components:

1. The variable you use to access the object, and
2. The actual storage for the object

Let's say that we changed Point from being a struct to being a class. When before, Location stored the contents of Point directly, now, it only stores a reference to their actual storage in memory:

┌──────────────────────┐      ┌───────────┐
│       Location       │ ┌───▶│   Point   │
├──────────┬───────────┤ │    ├─────┬─────┤
│   name   │   point ──┼─┘    │  x  │  y  │
└──────────┴───────────┘      └─────┴─────┘

Before, when Swift laid out space to create a Location, it was storing one String and two Doubles; now, it stores one String and one pointer to a Point. Unlike in languages like C or C++, you don't actually need to be aware of the fact that Location.point is now a pointer, and it doesn't actually change how you access the object; but under the hood, the size and "shape" of Location has changed.

The same goes for storing all other reference types, including closures. A variable holding a closure is largely just a pointer to some metadata for the closure, and a way to execute the closure's code (though the specifics of this are out of scope for this answer):

┌───────────────────────────────┐     ┌───────────┐
│           MyStruct            │     │  closure  │
├─────────┬─────────┬───────────┤ ┌──▶│  storage  │
│  prop1  │  prop2  │  closure ─┼─┘   │  + code   │
└─────────┴─────────┴───────────┘     └───────────┘

What is a Memory Heap?

Presumably you mean heap from a memory allocation point of view, not from a data structure point of view (the term has multiple meanings).

A very simple explanation is that the heap is the portion of memory where dynamically allocated memory resides (i.e. memory allocated via malloc). Memory allocated from the heap will remain allocated until one of the following occurs:

1. The memory is free'd
2. The program terminates

If all references to allocated memory are lost (e.g. you don't store a pointer to it anymore), you have what is called a memory leak. This is where the memory has still been allocated, but you have no easy way of accessing it anymore. Leaked memory cannot be reclaimed for future memory allocations, but when the program ends the memory will be free'd up by the operating system.

Contrast this with stack memory which is where local variables (those defined within a method) live. Memory allocated on the stack generally only lives until the function returns (there are some exceptions to this, e.g. static local variables).

You can find more information about the heap in this article.

Huge memory allocation: stack vs heap

The size of the stack is usually around one to few megabytes by default on typical desktop systems. Probably less on embedded devices.

If you allocate more memory than fits on the stack, the operating system will typically terminate the program as soon as you attempt to access the memory.

Does it mean it's recommended to story big amount of data in the heap?

It is recommended to use the free store (dynamic allocation) for big amount of data, because big amount of data would overflow the stack.

Application Manager i saw it is not using that amount of memory (just few KBs).

Typically, an operating system allocates a page of memory for a process when that memory is accessed. Since your program didn't crash due to stack overflow, I suspect that you never accessed the memory, and therefore no memory was allocated for the data.

---

Related Topics