What gets allocated on the stack and the heap?

While Lundin has written a reasonably complete answer, I think it suffers a bit from the expert view: conflating core issues with implementation details related to modern hardware architecture. I'd like to try to separate these notions.

Kinds of variables

To start with I'm going to divide the uses of program storage into three categories. The categories are defined by the way the lifetime of the stored object is determined.

For simplicity I'm going to refer to these stored whatsits as "variables" even if they are constant in you program, and I'm going to assume a compiled implementation in which the compiler reads all your code ahead of time and then creates either machine code or byte-code to implement it.

It will turn out that the properties of these categories encourage different strategies for assigning (allocating) them space in memory, and those strategies are the basis of an abstract model of memory use that feature "the stack" and "the heap" as the main players.

Global and static

Some kinds of variables "exist" for the whole duration of the program (for values of "exist" that mean you could reference them in code and the compiler or interpreter would give you what you expect). The most common example is global variables, though many language also support the concept of "static" variables associated with some sub-program or named data structure (such as an object).

Examples include global variables in most language, the hidden pointer that makes C's strtok such a troublesome beast (marked with the static keyword).

Scoped

Some kinds of variables exist during the execution of a sub-program (whether you call that a "function", a "procedure", or even just a "scope block").

Generally a single name may exist in different scopes and it means different storage, and the location in memory is allowed to be different on different calls. Indeed, if the language supports recursion multiple different instances of the "same" variable may exist in memory at once.

Examples include function local variables, loop counters and so on.

On demand

Sometime you want to be able to say to your execution system "Hey, give me some space to store this thing" and have it hang around until you are ready to give it back. You may not even know how many times you want to say that in a given run of the program.

The lifetime of these variables is not linked to the execution of any particular sub-program: they can come into being in one function exist after that function returns and be destroyed much later but still before the program ends.

Examples include the nodes in a linked list.

Persistent

I'm not going to talk about data that is persisted between invocations of a program.

Natural implementations

Implementing these categories requires different strategies. I'm going to take them in reverse order, and describe the most common approach to dealing which each one. These are nearly ubiquitous today but the history of computing features variation and outright violations of the rules I write here.

On-demand

To implement a on-demand storage system you will need a chunk of available memory, at catalog of what is currently in use and what is free, a way to mark a new chuck as in use, and a way to mark a currently used chunk as no longer in use.

This structure is unambiguously called a "free store" but is often also termed "the heap" (not to me confused with a heap data structure). Actual implementation can be straight forward (which might actually use a heap data structure to maintain the free list) to very subtle.

Scoped

Two factors drive the handling of scoped memory allocations: (a) it's not needed all the time and (b) the possibility of duplicate copies of "one" variable if recursion occurs.

The former suggests that the associate of a particular part of memory with a variable name should be temporary (to reduce memory usage to what is currently being used), and the latter suggests that we should be building up and tearing down this storage as we enter and leave scopes (so that we can build the local storage for a function and when it calls itself build some new storage for the new invocation).

That is, we want to "add" storage to the end of a list when we enter a sub-program and remove that storage when we exit the sub-program. We can build onto the end if we call another sub-program, but we can't remove our own storage until we get control back (which means when everything added "beyond" our memory has already been reaped). So a data structure where we only add and remove stuff at one end: a stack.

Now, a stack of this kind could be implemented in several ways and in some sense the safest would be as a linked list on the free store, but that leaves a problem with tracking how names connect to nodes. On the other hand, most hardware architectures already have a function call stack and by allocating scoped storage on that stack the naming issue reduces to stack offsets that can be computed at compile-time.

By far the most common way of implementing scoped storage is on the call stack, generally shorted to "the stack".

Global and static storage

In principle this could be simply placed at the beginning of the stack, but hardware limits on stack size were ubiquitous and relatively small back in the "good" 'ole days, so that wasn't generally a good idea. Instead a separate section of memory was set aside. Due to the nature of this storage it's size could be computed in advance.

Names like "the data segment" and "bss" are basically implementation details from early systems that have become ubiquitous because we have to call them something.

Memory hierarchy

Wait! So, how does this related to registers and caches and stuff?

The thing about the discussion above is that it implicitly assumes that memory is a nice uniform thing that is all equivalent and has limited internal structure. That was reasonably true of, say, my Apple ][+, but isn't really true at all of a modern PC.

PC memory

These days CPU cycles are fast and your main RAM (while much faster than it used to be) simply can't keep up. Not because no one can build fast enough memory, but because that memory is unreasonably expensive. So the way a modern PC works is by having lots of slow memory (your RAM) and a small amount of fast memory (one or more layers of cache) which mirrors a ever changing part of RAM. And there is some sophisticated circuitry that decides what part of RAM to mirror at any given time. (On top of that, if you want to use more memory than you actually have the computer can use some of your disk or SSD to fake it, but that is even slower!)

On top of all this, processors have a very small amount of internal storage called "registers". These are even faster than cache.

How compilers take advantage of the memory hierarchy

A very simple compiler that you might write as a hobby would implement the abstract scheme discussed above more or less as I wrote it, and because "the heap", "the stack", and "the data segment" all reside (ultimately) in main memory the code it produced would be relatively slow (somewhat relieved by the hardware cache management).

But serious compiler projects (commercial or open source) compete on the speed of produced code. So, they will try to optimize any way they can. Maybe the heap can be managed to optimize cache performance. (Certainly some flow control constructs can be , but that is a different story.) Maybe some local variables (especially loop counters that don't last long) don't need to be put into memory at all but can just live in a register. The compiler could also give a variable a place in memory, but temporarily "move" it to a register in a stretch of code when it is in heavy rotation.

All of these tricks require the compiler to make sophisticated decisions, but a modern compiler is a very powerful program.

In short, register and cache storage don't play any part in the abstract model which divides program memory into "stack, heap, and data segment", but they do mean that reasoning based only on that model may miss important points.

Short answer

Local variables are notionally allocated "on the stack", dynamic variables "on the heap", and global or static variables in a third location, but the compiler may play games behind the scenes for reasons of its own and the multilayered structure of memory means that the actual authoritative location of any value could vary in time.

posted about 4 years ago

CC BY-SA 4.0

dmckee‭

673 reputation 5 9 80 17

"Stack vs heap" is a common over-simplification and not really a meaningful one, since those two areas have quite different, specialized uses. And no, those are not the only memory regions used by your program.

To understand where variables end up, we must understand how a computer works. Physically, computer memories consist of:

• Registers (fastest, restricted amount)
• Cache memory (fast, optional)
• RAM memory,
• ROM memory (possibly slow)
• External memories (very slow, lots of storage capacity).

This holds well for all computers from tiny microcontrollers to PC/desktop ones. "RAM" is a widely but sloppily used term, in this context it actually means read/write memory, which is volatile and loses its data during power down. Whereas ROM could either be a read-only part of the physical RAM memory, or it could be on-chip, non-volatile EEPROM or flash memory. External memories are things like hard drives, memory cards, extended parallel address buses, serial memories etc that have to be accessed through some manner of bus interface.

During optimization, a compiler tries to store as many variables as possible inside registers. Usually this is what happens with local scope variables. It's only when the compiler runs out of registers or when variables turn too large (such as arrays) that it needs to store them in RAM instead.

Regarding cache memories (if present): all variables stored in RAM may be loaded into data cache memory, which gives faster CPU access. This is handled by the CPU hardware, which predicts that certain areas of memory might soon be used and fetch those to cache in advance, while the CPU is busy executing something else. For example if we do a calculation repeatedly inside a loop, the array used by the loop is a likely candidate to end up in cache, given that it is allocated in adjacent memory cells.

In RAM, we typically have four different regions: the stack, the data section, the bss section and the heap.

The stack is what a compiler normally uses automatically when it runs out of registers. Registers + stack are therefore referred to as automatic storage, meaning they are handled automatically by the high level language compiler. The CPU has instruction support for handling that area of memory through a stack pointer (often named "SP"), which keeps track of how much stack that is currently used and where the next free memory cell is. Parameters and return values used during function calls have automatic storage too, stored in registers or on the stack based on the system-specific rules known as calling convention, that also specifies if the caller or callee is the one responsible for storing parameters. The stack is usually restricted to a limited amount of memory per program/process, so allocating very large objects in local scope with atomatic storage is a bad idea, that could lead to stack overflow when the program runs out of stack memory.

The data and bss sections is where variables with static storage duration go. All variables that must persist throughout the execution of the whole program end up in these sections, such as for example "global variables". All such variables that are explicitly initialized by the programmer to a value end up in the data section, and those who aren't explicitly initialized or initialized to zero end up in the bss section, where every variable is zero-initialized during program start-up.

The heap (sometimes called "free store") is a specialized area, either used when the amount of memory needed isn't known at compile time or when large amounts of memory are needed. Memory allocated on the heap is called allocated storage or dynamically allocated memory. It is not commonly used in low-end systems like microcontrollers, since such systems are deterministic, but also since dynamic allocation is often handled by the OS through API functions, so that multiple processes may co-exist and share RAM, requesting more memory from the OS when needed and handing it back when not needed.

In compiled languages such as C or C++, dynamic allocation is handled explicitly by calling functions like malloc/free or operators new/delete. Failing to free up heap memory through a bug is known as a "memory leak". Standard libraries particularly in C++ use dynamic allocation extensively for standard container classes. Higher level byte code or interpreted languages like for example Java, use heap memory even more often, handling dynamic allocation automatically by the compiler. This means that the programmer doesn't need to worry about where variables are stored, but also that they don't have to worry about memory leaks, since a separate thread known as the garbage collector is responsible for freeing up heap memory no longer used by the process.

In addition to the above mentioned read/write segments, variables can also end up allocated in a read-only data section, commonly called "rodata", which may be located either in RAM or ROM depending on system. And in some cases, read-only variables, numeric constants, strings etc end up allocated with the program itself, in the executable code which typically resides in a section called "text", which is always stored in ROM.

posted about 4 years ago

CC BY-SA 4.0

Lundin‭

8948 reputation 36 122 1027 166