Polymorphic memory resource with constant allocation and deallocation times for real-time applications

MultiArena is a header-only library written in C++17. It implements a polymorphic memory resource to be used with a polymorphic allocator. The allocation and deallocation times are constant, which makes it suitable for real-time applications.

MultiArena algorithm

Initialization of the memory resource

The entire memory resource is preallocated upon the time of construction from the stack (or static memory), or alternatively using another (a.k.a upstream) memory resource in the constructor. After the initialization phase, the upstream resource is not accessed any more.

The memory in the resource is divided into a fixed number of arenas. Each arena consists of a fixed number of bytes. Each arena has the same size.

Management of the arenas

Initially every arena is empty and they are placed in a set of free arenas. The first allocation request taps an arena and marks it as active. From now on, all requested chunks of memory are carved from the active arena until there is too little memory left to satisfy a new request. Then the active arena is declared as full and the next free arena is tapped from the set and marked as active.

The occupied arenas know how many allocations they hold. Hence, deallocations are very simple. Only the allocation counter is decremented. Once the counter reaches zero, we know that every allocation in the arena has been deallocated and the arena has become empty again. It can now be returned to the list of free arenas.

Synchronized vs unsynchronized memory resources

MultiArena resource classes come in synchronized and unsynchronized variants, just like std::pmr::synchronized_pool_resource and std::pmr::unsynchronized_pool_resource. The unsynchronized version is fast and thread-unsafe whereas the synchronized version is a bit slower and thread-safe. The synchronized version uses locks on allocation so if several threads are using the same memory resource, they will sometimes have to wait each other. Deallocation is mostly lock-free even though a lock is acquired when an arena becomes empty and is returned to the list of free arenas.

The following example shows how to allocate synchronized and unsynchronized resources which live in either stack or heap. In each case, there are 16 arenas, containing 1024 bytes each.

    MultiArena::UnsynchronizedArenaResource<16, 1024> unsynchronized_in_stack;
    MultiArena::UnsynchronizedArenaResource unsynchronized_in_heap(16, 1024);

    MultiArena::SynchronizedArenaResource<16, 1024> synchronized_in_stack;
    MultiArena::SynchronizedArenaResource synchronized_in_heap(16, 1024);

In this chapter below we show how to store the data in memory reserved from an upstream memory resource instead of the heap (a.k.a. std::pmr::new_delete_resource).

During the debugging phase, when the number and the size of the arenas may not be known as yet, the above memory resources can be replaced with a debug helper. More on that below.

Member functions for status inquiry

MultiArena classes have a few methods for inquiring the status of the memory resource.

The methods are as follows:

• numArenas() returns the number of arenas in the resource. It is constexpr if the memory resource is statically allocated.
• arenaSize() returns the size of each arena. It is constexpr if the memory resource is statically allocated.
• numberOfAllocations() returns the current number of allocations in the resource. The value is indeed the allocation count, not the number of allocated bytes.
• numberOfBusyArenas() reports how many arenas are busy. An arena is regarded as busy if there is at least one active allocation refering to the address space of the arena.

The latter two methods can for instance be used in an assert to detect possible memory leaks. Note that this is not trivially possible with standard new-delete allocator.

Examples on calling these methods can be found in example-1.cc.

Using MultiArena with std-containers

Every dynamic container in std library like vector, list, map and string have polymorphic counterparts in std::pmr namespace. The polymorphic versions draw memory from the given memory resource

Let's look at some examples on how MultiArena can be used as the memory resource for std containers. These examples run on a single thread, so UnsynchronizedArenaResource will be used. In a multi-threaded case, simply replace UnsynchronizedArenaResource with SynchronizedArenaResource.

MultiArena resource living in stack

    MultiArena::UnsynchronizedArenaResource<16, 1024> arenaResource; // 16 arenas, 1024 bytes/arena
    std::pmr::vector<int> vec(&arenaResource); // Could be any std container (list, deque, map, ...)
    vec.reserve(8);  // The entire vector will fit in a single arena
    for (int i : {1,2,3,4,5,6,7,8})
        vec.push_back(i);

    std::cout << "vec.size() = " << vec.size() <<  ", "
              << "number of allocated memory chunks = " << arenaResource.numberOfAllocations() << ".\n";
// Output:
// vec.size() = 8, number of allocated memory chunks = 1.

MultiArena resource living in heap or in another resource

    MultiArena::UnsynchronizedArenaResource arenaResource(16, 1024); // 16 arenas, 1024 bytes/arena
    std::pmr::list<int> lst(&arenaResource);
    for (int i = 0; i < 256; ++i)
        lst.push_back(i);  // Will do one allocation per push_back.

    std::cout << "lst.size() = " << lst.size() <<  ", "
                << "number of allocated memory s = " << arenaResource.numberOfAllocations() << ".\n";
// Output:
// lst.size() = 256, number of allocated memory chunks = 256.

In this example, the memory for the arenas was allocated by default from the standard new-delete resource. However, any upstream resource can be used by simply passing it to a MultiArena resource like so:

        MultiArena::UnsynchronizedArenaResource arenaResource(16, 1024, &my_upstream_resource);
        // like above from this on...

For a runnable example, see Example 1.1 in example-1.cc.

Using MultiArena with unique pointers

std::unique_ptr can own an object allocated from a MultiArena resource and deallocate it automatically when the object goes out of scope. The object can be allocated and passed to a unique pointer with function MultiArena::makePolymorphicUnique<T>(pmr, args...). The function returns a unique pointer pointing to an object of type T. The object has been is allocated from the MultiArena resource pointed by pmr and constructed with constructor T(args...).

Let's look at an example.

    MultiArena::UnsynchronizedArenaResource<16, 1024> arenaResource;
    using T = std::pair<int, double>;
    {
        auto ptr = MultiArena::makePolymorphicUnique<T>(&arenaResource, 10, 3.14);
        std::cout << "*ptr = {" << ptr->first << ',' << ptr->second << "}\n";
        std::cout << "Number of allocations before ptr gone out of scope: "
                    << arenaResource.numberOfAllocations() << '\n';
    }
    std::cout << "Number of allocations after  ptr gone out of scope: "
                << arenaResource.numberOfAllocations() << '\n';
// Output:
//  *ptr = {10,3.14}
//  Number of allocations before ptr gone out of scope: 1
//  Number of allocations after  ptr gone out of scope: 0

For a runnable example, see Example 1.2 in example-1.cc.

Using MultiArena with shared pointers

A shared pointer pointing to data allocated from MultiArena (or any other polymorphic resource) can be constructed with library function std::allocate_shared. Notice that the first parameter will have to be a std::pmr::polymorphic_allocator which drived the memory resource, not the memory resource itself. Otherwise, the usage is very similar to that of the unique_ptr above. Both the payload data and the control block required for shared_ptr's internal book keeping are allocated from the memory resource with a single allocation. Here is an example.

    MultiArena::UnsynchronizedArenaResource arenaResource(16, 1024);
    using T = std::pair<int, double>;
    std::shared_ptr<T> p1, p2;
    {
        auto ptr = std::allocate_shared<T>(std::pmr::polymorphic_allocator<T>(&arenaResource), 10, 3.14);
        std::cout << "*ptr = {" << ptr->first << ',' << ptr->second << "}\n";
        // Make two more references.
        p1 = ptr; p2 = ptr;
        std::cout << "Number of allocations before ptr gone out of scope: " << arenaResource.numberOfAllocations() << '\n';
        std::cout << "  Shared pointer use count = " << p2.use_count() << '\n';
    }
    std::cout << "Number of allocations after  ptr gone out of scope: " << arenaResource.numberOfAllocations() << '\n';
    std::cout << "  Shared pointer use count = " << p2.use_count() << '\n';
    p1.reset();
    std::cout << "Number of allocations after  p1 released: " << arenaResource.numberOfAllocations() << '\n';
    std::cout << "