How do C++ programmers handle memory fragmentation?

Nov 20, 2023 c++, c-/-c++

Design of Custom Memory Allocator

Using Huge Page + Custom Memory Pool.

Note: Custom memory allocators can be more efficient than generic memory allocation frameworks/systems such as malloc, calloc, alloc, realloc only if they are closely tied to the specific requirements of the business.

If the memory usage strategy and characteristics of your business are not obvious, there is no need to make unnecessary effort. It is impossible for your design to be better than the generic one.

However, if your business has a particularly fixed memory usage strategy and obvious characteristics, for example:

All units have only two sizes: 8 and 64.
Business characteristics ensure that zero-filled memory will not occur.
The data structure has extremely strong regularity.

In this case, the memory allocator implemented by yourself can be much more efficient than the built-in system allocator.

Common Strategies for Memory Optimization

The mechanisms provided by general allocators are generally sufficient, which is why some answers say they do not handle it. In fact, it is still being handled, just not explicitly in the code.

The most common approach in code is to avoid memory allocation. For example, using objects on the stack, reusing existing objects, moving temporary objects, optimizing small-sized objects, optimizing empty classes, and so on.

If there is a high demand for memory fragmentation, the best strategy is usually to allocate memory only at the beginning of the program and not allocate or release it afterwards.

Only when this strategy is not feasible should one consider using more efficient memory allocators, allocation strategies, memory pools, and other optimization techniques.

Virtual Memory Handling

Not applicable.

For the program itself, it uses the virtual memory table. Since the actual physical memory is inherently discrete, there is no need to handle it.

Storage Advantages

Objects in C++ can be stored only on the stack, and for container types, they can also be stored contiguously, thus saving more memory and achieving more continuous memory allocation. Therefore, it is usually unnecessary to solve memory fragmentation.

Choosing a Memory Management Solution

Both the tcmalloc and jemalloc libraries, which are commonly used in modern systems, can handle most tasks with comparable performance. Unless you are working in scenarios such as embedded systems, you can disregard them for everyday needs.

There are a few scenarios worth noting:

Situations where a large amount of local computation is performed at once. In this case, you can allocate memory resources on the stack using memresource. You don’t need to worry about memory fragmentation, as you can simply release the memresource after the computation is completed.
Scenarios similar to ECS (Entity-Component-System), where it is preferable to allocate memory for types that will be extensively used together in order to take advantage of CPU locality.

Take a look at std::pmr for more information. However, keep in mind that developing your own memory pool in 2023 may not be as efficient as using existing solutions that have undergone years of iteration by others.

How to Avoid Memory Fragmentation

Conclusion:

Unless you are a kernel programmer at the operating system level, C++ programmers have no way to deal with memory fragmentation. What C++ programmers can do is to try to avoid memory fragmentation through programming habits and techniques.

It is well known that C++ is a high-level programming language. The term “high-level” here refers to its structure, which is close to natural language and facilitates the reading, understanding, and teaching of code, reducing the cost of learning and coding for humans. At the same time, C++ is also a low-level language because its essence lies in its ability to access more computer resources, such as memory and peripherals. The reason for this is that it is a native language and can generate executable binary programs (instruction set files) on the target machine through the compiler.

But even with all these magical powers, C++ is not omnipotent. There are limitations to what song you can sing on a particular platform, what tasks you can perform in a specific position, and what responsibilities you have based on your authority. If you are in the education department, you can’t just go to the family planning office and make a fuss~

C++ application programmers do not have the authority to manage memory resources. If they can return the memory they have used at the appropriate time and place, they should count their lucky stars. There wouldn’t be so many stories of accessing memory with wild pointers. If they can’t even guarantee that, would you trust them to manage memory? Or should we say that without the necessary expertise, would you dare to take on that delicate porcelain work? It is a mutual choice and quite interesting~

So how can C++ programmers try to avoid memory fragmentation? The answer can be summed up in one sentence:

Do not allocate memory frequently from the heap (avoid frequent allocation of memory from the heap)

To be more specific:

Avoid using the heap unless necessary, and use the stack instead.
If using the heap is necessary, control its frequency.
If using the heap is necessary and its frequency cannot be controlled, allocate a large block of memory when the program starts and release it back to the system when the program ends.

Solutions for Solving Memory Fragmentation

What are the other answers saying… Zhihu has sunk to an unthinkable level.

For programming languages like C++ that manually manage memory, there are the following solutions to address the problem of memory fragmentation:

Slab Allocator. This is the most commonly used solution because it doesn’t require any program modifications. The basic idea is to divide the memory into buckets, such as 32B, 64B, 128B, … 1KiB. When a new memory allocation request comes in, the allocator assigns the most suitable bucket instead of allocating exactly the requested size. Since the bucket sizes are all the same or multiples of each other, there is a higher chance of memory reuse. For large objects, the allocator still uses the traditional method of customizing the allocation. In actual programs, it is rare to allocate a large number of large objects, so everything is okay. Example: mimalloc.
Internal Reference. Instead of directly using pointers, handles are used. By using two-level indirection, the real position of the object can be found, allowing memory to be moved freely while keeping the objects valid. This method corresponds to read and write barriers for managed languages. Example: Generational Arena Allocator, ECS Entity ID, Windows Resource Handle & COM.
Memory pool, Object pool, Arena & Array of Data. I grouped these together because I think they all involve modifying the pattern of memory allocation in the program, which has a greater impact on the programming paradigm. Various pools correspond to the Flyweight Pattern in design patterns. Putting the same type of data in a continuous array is a common technique in data-driven design (a classic example is the DataFrame used in data processing tools like Pandas and R). The idea of Arena Allocator or Bumpalo is to allocate the required memory for temporary objects or one-time tasks (transactions) directly in units of virtual memory pages, without reclaiming it until the transaction is completed, and then directly release all the related memory. This not only solves the problem of memory fragmentation, but sometimes even improves performance. This corresponds to the young generation in generational memory allocation.

In addition, I vaguely remember reading a paper that mentioned if virtual memory is used in conjunction with sufficiently large physical memory, the problem of memory fragmentation may not be so severe. I can’t recall the specific details, maybe I’ll search for it another day if I’m interested.

Optimization Methods for Memory Management

Libraries like tcmalloc help take over the allocation and deallocation of memory with new and delete, making the memory allocation and release more reasonable.
If you want a native solution, you can use pmr with data structures like vector, which is supported in C++17 and can be considered an official memory pool in C++.
If you cannot use C++17, you can manage a large page by yourself and use your own memory pool to handle frequent memory allocation and deallocation, which avoids the generation of fragmentation. However, I recall that new also allocates memory from its own memory pool.

Reducing Memory Fragmentation in Memory Management Libraries

Today, many memory management libraries offer support for reducing memory fragmentation. Examples include tcmalloc and jemalloc.

Memory Pool and Allocator for Small Memory Objects

To optimize memory allocation, a memory pool is created by allocating a large block of memory. Subsequently, a custom allocator is implemented for allocating small memory objects within this memory pool.