Dynamic Memory Allocation and Virtual Memory

by Andrei Milea

Virtual Memory - looking "Under the Hood"

Every application running on your operating system has its unique address space, which it sees as a continuous block of memory. In fact the memory is not physically continuous (it is fragmented), this is just the impression the operating system gives to every program and it's called virtual memory. The size of the virtual memory is the maximum size of the maximum size your computer can address using pointers (usually on a 32-bit processor each process can address 4 GB of memory). The natural question that arises is what happens when a process wants to access more memory than your machine physically has available as RAM? Due to having a virtual address space, parts of the hard disk can be mapped together with real memory and the process doesn't have to know anything about whether the address is physically stored in RAM or on the hard disk. The operating system maintains a table, where virtual addresses are mapped with their correspondent physical addresses, which is used whenever a request is made to read or write to a memory address.

Typically, in each process, the virtual memory available to that process is called its address space. Each process's address space is typically organized in 6 sections that are illustrated in the next picture: environment section - used to store environment variables and command line arguments; the stack, used to store memory for function arguments, return values, and automatic variables; the heap (free store) used for dynamic allocation, two data sections (for initialized and uninitialized static and global variables) and a text section where the actual code is kept.

The Heap

To understand why the dynamic memory allocation is time consuming let's take a closer look at what is actually happening. The memory area where new gets its blocks of memory for allocation (usually called free store or heap) is illustrated in the following picture:

When new is invoked, it starts looking for a free memory block that fits the size for your request. Supposing that such a block of memory is found, it is marked as reserved and a pointer to that location is returned. There are several algorithms to accomplish this because a compromise has to be made between scanning the whole memory for finding the smallest free block bigger than the size of your object, or returning the first one where the memory needed fits. In order to improve the speed of getting a block of memory, the free and reserved areas of memory are maintained in a data structure similar to binary trees called a heap. The various algorithms for finding free memory are beyond the scope of this article and you can find a thorough discussion about them in D. Knuth's monograph The Art of Computer Programming -- Vol.1, Fundamental Algorithms). This overhead combined with the risk for memory leaks makes the use of automatic memory (allocated on the stack) preferred whenever possible and the allocation is not large.

How much Virtual Memory do you get

Even though every application has its own 4 GB (on 32-bit systems) of virtual memory, that does not necessarily mean that your program can actually use all of that memory. For example, on Windows, the upper 2 GB of that memory are allocated to the operating system kernel, and are unavailable to the process. (Therefore, any pointer starting with 0x8xxxxxxx is unavailable in user space.) On Linux, the upper 1 GB is kernel address space. Typically, operating systems provide means for changing these defaults (such as the /3GB switch on Windows. It is rare, however, that you really want or need to do so.

Address Space Fragmentation

Another concern with memory allocation is that if you allocate memory in non-contiguous blocks, over time "holes" will develop. For example, if you allocate 10 KB and it is taken from the middle of a 20 MB chunk of memory, then you can no longer allocate that 20 MB a one chunk of memory. Doing this enough times will cause you to no longer be able to allocate 20 MB at once. This can cause allocation failures even when there is free memory. Note that this is true even with virtual memory because what matters is that you need a continuous block of addresses, not a continuous block of physical memory.

One way to address this problem is to avoid doing things that have problems due to fragmentation, such as avoiding large allocations--anything more than a few tens of MB is certainly asking for trouble. Second, many heap implementations help you with this already by allocating a large chunk of virtual address space and carving it up for you (usually the heap allocates address space from the operating system and then provides smaller chunks when requested). But if you know that you will have a class that has a lot of small instances, you could overload operator new and preallocate a large continuous chunk of memory, splitting off small pieces for each class from that chunk.

Related articles

Dynamic Memory Allocation, Part 1: Advanced Memory Management

Dynamic Memory Allocation, Part 3: Customized Allocators with Operator New and Operator Delete

Dynamic Memory Allocation, Part 4: Common Memory Management Problems in C++