The world’s leading publication for data science, AI, and ML professionals.

C++ Memory Allocation/Deallocation for Data Processing

Understanding how memory is managed under the hood will help us allocate/deallocate memory more wisely.

Photo by Possessed Photography on Unsplash
Photo by Possessed Photography on Unsplash

Overview

Unless you are working on very resource-constrained embedded systems running RTOS or bare metal, you will almost certainly need to dynamically allocate memory to process your data. There are many methods to dynamically allocate memory in C++ such as using new and delete operators and their counterparts new[] and delete[], std::allocator, or C’s malloc().

Regardless of the method, the system has to allocate blocks of memory contiguously.

The C++ STL provides many convenient libraries such as containers which also internally allocate memory dynamically. Dynamic memory allocation in C++ happens everywhere.

In this post, we will discuss how memory is managed in C++ so that we can use it more wisely.

Memory Layout

Physical and Virtual Memory

Keep in mind that this memory layout is a virtual memory layout for user-space applications. In systems like Linux, broadly physical memory is broadly divided into kernel space and user space, for applications we are talking about user-space. Furthermore, each process in the system is assigned virtual memory which is typically larger than the available one. For instance, in a system with 4GB of memory, each process assumes that it has all available to it.

C++ Memory Layout

C++ Memory Layout (Image by Author)
C++ Memory Layout (Image by Author)

This is the layout of our application’s virtual memory. In this post, we are interested in the Heap segment which is the segment that we use to dynamically allocate memory.

Text/Code is where our code instructions are stored, data/BSS is where our global data (initialized/uninitialized) is stored, and the stack is used for the call stacks to manage function calls and local variables.

How does the OS Manage the heap?

Different OSs manage heap memory differently, for the purpose of this article to provide an intuitive understanding of how it is managed let’s assume that we have a unix-like system such as Linux.

Controlling Program Break Address to allocate/deallocate memory (Image by Author)
Controlling Program Break Address to allocate/deallocate memory (Image by Author)

In Linux, we can allocate/deallocate memory by adjusting the Program Break which is the current heap limit. User-space applications can adjust it by using system calls brk() and sbrk() included in unistd.h, see man page for details.

Manually managing memory in this way isn’t recommended as it is error-prone. The first level of abstraction we have is the memory allocation library provided by the C runtime, the malloc() family.

C Dynamic Memory Allocation

The C standard library provides a more convenient way to allocate/deallocate memory compared to directly invoking system calls. It provides:

  • malloc(): allocates memory given its size
  • free(): deallocates previously allocated memory
  • realloc(): resizes previously allocated memory
  • calloc(): allocates memory for an array of objects

Using this is less error-prone because the application doesn’t need to know about the current heap limit. All it has to do is request blocks of memory by passing in the size and once it’s done with the memory, ask to free it by calling free().

int *ptr = (int *) malloc(sizeof(int));
free(ptr);

The malloc() family of APIs use brk(), sbrk(), and mmap() system calls to manage memory. This is the first level of abstraction.

How does malloc() work?

Implementation details may vary from compiler to compiler and OS to OS, but here we will cover an overview of the Memory Management done by malloc().

Internally, malloc() manages memory by adding metadata in each memory block requested by the application. For the purposes of this article let’s assume that it has two pieces of information in its metadata:

  • Size
  • Allocation status (in use/free)
Malloc memory block (Image by Author)
Malloc memory block (Image by Author)

What happens when you call malloc(), realloc(), or calloc() is that it searches for a free area in memory that fits the size you requested.

Example of malloc (Image by Author)
Example of malloc (Image by Author)

For example, the free blocks are shown in blue in the image above. If the size fits or is smaller, the blocks will be reused otherwise if free areas in the memory are still available in the system, malloc() will allocate new memory by invoking brk(), sbrk(), or mmap() system calls.

New blocks are allocated (Image by Author)
New blocks are allocated (Image by Author)

If no memory is available in the system malloc() will fail and return NULL.

Memory Allocation

When you want to allocate blocks of memory, what happens under the hood is a search. There are various strategies such as:

  • First-fit: the first encountered fit blocks of memory
  • Next-fit: the second encountered fit blocks of memory
  • Best-fit: the best-fit in terms of size

Not in all scenarios the size we request will match the available free blocks, most of the time only parts of the available free blocks will be used and the blocks will be split.

Available Blocks in blue (Image by Author)
Available Blocks in blue (Image by Author)
Memory Allocated in red (Image by Author)
Memory Allocated in red (Image by Author)

Memory Deallocation

When you free memory, it is not returned to the system. Only its metadata is changed to reflect its status that it is now not in use.

One thing that may happen when memory is deallocated is the free blocks coalesce. Adjacent free blocks can be coalesced to form a larger block which can be used for requests with the larger size.

If currently we have a small free block in the middle shown in the image below:

Current Status (Image by Author)
Current Status (Image by Author)

And we free the last block:

Another block is freed (Image by Author)
Another block is freed (Image by Author)

They will coalesce to form a larger block:

Final blocks (Image by Author)
Final blocks (Image by Author)

Memory Reallocation

As you may have guessed, memory reallocation, i.e. when we invoke realloc(), is just allocating memory + copying existing data to the newly allocated area.

Memory Fragmentation

Memory Fragmentation is a condition in which small blocks of memory are allocated across the memory in between larger blocks. This condition causes the system to fail to allocate memory even though large areas may be unallocated.

The image below illustrates the scenario:

All Free (Image by Author)
All Free (Image by Author)

We allocate 3 blocks, 1 block, and 8 blocks:

All Allocated (Image by Author)
All Allocated (Image by Author)

We then free 3 blocks and 8 blocks:

Two blocks of memory freed (Image by Author)
Two blocks of memory freed (Image by Author)

Now, we want to allocate 9 blocks, it fails even though we have 11 free blocks in total but they are fragmented.

This situation is likely to happen when your program allocates/deallocates small objects on the heap frequently during runtime.

C++ Dynamic Memory Allocation

Now that we have seen the first level of abstraction in our system, we can see the next level of abstraction that C++ provides.

New and Delete Operator

In C++ when we want to allocate memory from the free-store (or we may call it heap) we use the new operator.

int *ptr = new int;

and to deallocate we use the delete operator.

delete ptr;

The difference compared to malloc() in C Programming Language is that the new operator does two things:

  • Allocate memory (possibly by calling malloc())
  • Construct object by calling its constructor

Similarly, the delete operator does two things:

  • Destroy the object by calling its destructor
  • Deallocate memory (possibly by calling free())

The following code shows it:

To allocate memory and construct an array of objects we use:

MyData *ptr = new MyData[3]{1, 2, 3};

and to destroy and deallocate, we use:

delete[] ptr;

If we have allocated blocks of memory and only want to construct an object we can use what is called the placement new.

typename std::aligned_storage<sizeof(MyData), alignof(MyData)>::type data;
MyData *ptr = new(&amp;data) MyData(2);

The first line will allocate the memory needed to store the MyData object on the stack (assuming these lines of code are in a function), and the second line will construct the object at that location without allocating new memory. Be careful here because we should not call delete on ptr.

std::allocator

As you know that STL containers such as std::vector, std::deque, etc. allocate memory dynamically internally. They allow you to use your own memory allocator object, but as is often the case we use the default one the std::allocator.

The reason they don’t use the new and delete operators is that they want to allocate memory and create objects separately. For instance, std::vector dynamically increases its memory by doubling its current size to optimize speed, see my other post for more detailed information.

C++ Basics: Array Data Structure

We can think that under the hood std::allocator would call malloc(), though it might do some other things such as preallocate memory for optimization.

Smart Pointers

Everything we have seen so far doesn’t solve the manual memory management problem where the responsibility for allocating and deallocating memory lies with the developers. As we know, manual memory management can cause problems like:

  • Memory Leak, when we forget to free the memory
  • Crash/Undefined Behavior, when we try to free memory that has been freed or double free
  • Crash/Undefined Behavior, when we try access blocks of memory that we have freed

C++ does not have an implicit Garbage Collector to manage memory automatically due to performance vs. convenience tradeoffs. But it does have an explicit Garbage Collector in smart pointers that automatically allocate memory and deallocate memory when the object goes out of scope or has no other objects reference to it.

They are:

  • std::unique_ptr an object that manages pointer of another type that cannot be copied (unique)

  • std::shared_ptr similar to unique_ptr but can share ownership, by using a reference count

  • std::weak_ptr a non-owning object, it has reference to the pointer but doesn’t own it

Most of the time, you should use smart pointers and forget about when to free the memory. We can discuss the details in another post in the future.

Other Memory Management Library

There are other things that we may want to consider in memory management such as reducing the overhead when allocating/deallocating memory using the Memory Pool or in some situations, we may want to pay special attention to small object allocation. We’ll discuss them in future posts.

Summary

There are multiple levels of abstraction about how we can allocate/deallocate memory in C++. Knowing them is important because we know not only which level we should use, but also what issues may arise in our applications. The image below illustrates the APIs at different levels.

Memory Management at different levels in C++ (Image by Author)
Memory Management at different levels in C++ (Image by Author)

Get an email whenever Debby Nirwan publishes.


Related Articles