Arena Allocation In C++

Introduction:

Arena allocation, alternatively referred to as region-centric memory management, is a strategy for managing memory that involves initially assigning memory in large chunks from a pre-assigned "arena" or "pool," which is then divided further to cater to smaller allocation demands. The fundamental concept revolves around pre-assigning a substantial, continuous memory block and orchestrating smaller allocations within this block in an efficient manner. This method proves particularly beneficial in situations characterized by frequent memory allocation and deallocation operations where optimal performance is paramount.

Program:

#include <iostream>
#include <stdexcept>
#include <cstddef>
#include <new>
class ArenaAllocator {
private:
    char* arena;         // Pointer to the start of the memory pool
    char* current;       // Pointer to the next available memory location
    size_t totalSize;    // Total size of the arena
    size_t usedSize;     // Amount of memory currently used
    // Helper function for alignment
    void* alignPointer(size_t alignment) {
        uintptr_t ptr = reinterpret_cast<uintptr_t>(current);
        size_t offset = (alignment - (ptr % alignment)) % alignment;
        if (usedSize + offset > totalSize) {
            throw std::bad_alloc(); // Not enough memory for alignment
        }
        current += offset;
        usedSize += offset;
        return current;
    }
public:
    // Constructor to initialize the arena
    explicit ArenaAllocator(size_t size) : totalSize(size), usedSize(0) {
        arena = new char[size];
        current = arena;
    }
    // Allocate memory from the arena
    void* allocate(size_t size, size_t alignment = alignof(std::max_align_t)) {
        if (size == 0) {
            throw std::invalid_argument("Allocation size must be greater than 0");
        }
        // Ensure proper alignment
        alignPointer(alignment);
        if (usedSize + size > totalSize) {
            throw std::bad_alloc(); // Not enough memory
        }
        void* allocated = current;
        current += size;
        usedSize += size;
        return allocated;
    }
    // Reset the arena (free all memory at once)
    void reset() {
        current = arena;
        usedSize = 0;
    }
    // Destructor to free the memory pool
    ~ArenaAllocator() {
        delete[] arena;
    }
    // Getters for diagnostic purposes
    size_t getUsedSize() const { return usedSize; }
    size_t getRemainingSize() const { return totalSize - usedSize; }
};
int main() {
    try {
        constexpr size_t ARENA_SIZE = 1024; // 1 KB memory pool
        ArenaAllocator arena(ARENA_SIZE);
        // Allocate an integer
        int* intPtr = static_cast<int*>(arena.allocate(sizeof(int)));
        *intPtr = 42;
        std::cout << "Integer allocated: " << *intPtr << "\n";
        // Allocate a double with alignment
        double* doublePtr = static_cast<double*>(arena.allocate(sizeof(double), alignof(double)));
        *doublePtr = 3.14159;
        std::cout << "Double allocated: " << *doublePtr << "\n";
        // Allocate an array of characters
        char* charArray = static_cast<char*>(arena.allocate(20));
        std::fill(charArray, charArray + 20, 'A');
        charArray[19] = '\0';
        std::cout << "Char array allocated: " << charArray << "\n";
        // Display arena usage
        std::cout << "Used memory: " << arena.getUsedSize() << " bytes\n";
        std::cout << "Remaining memory: " << arena.getRemainingSize() << " bytes\n";
        // Reset the arena
        arena.reset();
        std::cout << "Arena reset. Remaining memory: " << arena.getRemainingSize() << " bytes\n";
    } catch (const std::exception& e) {
        std::cerr << "Error: " << e.what() << "\n";
    }
    return 0;
}

Output:

Integer allocated: 42
Double allocated: 3.14159
Char array allocated: AAAAAAAAAAAAAAAAAAA
Used memory: 36 bytes
Remaining memory: 988 bytes
Arena reset. Remaining memory: 1024 bytes

Explanation:

1. Setting up the Arena

The process starts with the establishment of a memory pool known as an "arena." This consists of a sizable, pre-assigned chunk of memory that acts as the primary source for all memory allocations. An indicator (current) is employed to monitor the next available position within the arena. Additionally, there is a separate variable that maintains a record of the total memory utilized up to that point.

1. Allocating Memory

When a request for memory is made, the allocator verifies if adequate space is available within the arena to meet the request. If sufficient memory is available:

• ✅ The pointer is adjusted to align the memory correctly (according to the data type size or any alignment requirements).
• ✅ The allocation of memory occurs by returning the pointer's current location, followed by advancing the pointer by the size of the requested allocation.

If the allocation request surpasses the available space within the arena, the software will generate an error to signal that the allocation process cannot be carried out.

1. Dealing with Alignment

For specific data types such as doubles or other types that adhere to precise alignment regulations, the allocator guarantees that the memory address satisfies the alignment criteria. It computes the necessary offset to align the current pointer and adapts it accordingly prior to memory allocation. This guarantees that the memory allocated is both valid and optimal for the system's utilization.

1. Reinitializing the Arena

Unlike the traditional memory allocation method, the arena allocator does not support the deallocation of individual allocations. Instead, it enables freeing all allocated memory within the arena at once by resetting the current pointer back to the initial block position. This characteristic enhances efficiency when dealing with temporary data or scoped tasks that involve discarding all objects simultaneously.

1. Error Handling

The software incorporates protective measures:

• ✅ In case the desired size is either zero or surpasses the memory limit, it triggers an exception.
• ✅ Similarly, if the alignment requirements cannot be met because of inadequate memory, it indicates an error.

This guarantees the allocator's resilience and prevents memory corruption.

1. Memory Health Checkups

For enhanced troubleshooting, the software offers insights into memory utilization:

• ✅ It reveals the total allocated memory up to the current point (usedSize).
• ✅ It indicates the amount of memory that is yet to be utilized (remainingSize).

These measurements assist developers in monitoring and controlling memory consumption efficiently.

1. Sample Implementation

The program demonstrates allocating memory for different data types, including:

• ✅ A single integer.
• ✅ A floating-point number with specific alignment.
• ✅ A character array.

After each assignment, it demonstrates how the memory space adapts to accommodate the additional allocation. Upon finishing all operations, the memory arena is cleared, making all memory resources available once more.

1. Optimal Memory Control

The arena allocator prevents fragmentation and accelerates allocation by employing a straightforward pointer adjustment instead of intricate system-level memory management. This feature makes it well-suited for use in scenarios such as games, compilers, or systems that involve the creation and destruction of objects with comparable lifetimes.

Complexity analysis:

Time Complexity

Memory Assignment:

• ✅ Assigning memory includes advancing a pointer by the specified memory size and guaranteeing correct alignment. Both of these actions are executed in constant time.
• ✅ Computational Complexity: O(1) for each assignment.

Reset Action:

• ✅ To reset the arena, all that is required is to reposition the pointer to the beginning of the memory block.
• ✅ This operation has a time complexity of O(1).

Overall Effectiveness:

• ✅ This allocator eliminates the need for intricate record-keeping found in conventional memory allocators, guaranteeing swift and consistent operations.
• ✅ Sequential allocation and reset procedures sustain a steady O(1) efficiency, unaffected by the quantity of allocations.

Space Complexity

Memory Block:

• ✅ The space used by the allocator is the size of the pre-allocated memory block, which is fixed and determined at initialization.
• ✅ Additional space is used for a few pointers and size variables, which is negligible compared to the block size.
• ✅ Space Complexity: O(n), where n is the size of the pre-allocated memory block.

Alignment Overhead:

• ✅ A small amount of memory could be lost to guarantee correct data alignment, though this is negligible and varies based on the alignment specifications of the assigned data types.

If the aggregate memory requested is substantially less than the arena's size, the leftover unused space retains memory allocation without being utilized.

Approach 1: Chunk-Based Arena Allocator

This method enhances adaptability by segmenting the space into predetermined chunks, enabling efficient management of multiple allocations. It is effective for situations where memory requirements differ, preventing wastage caused by alignment constraints.

Programs:

#include <iostream>
#include <vector>
#include <cstddef>
#include <stdexcept>
#include <new>
class ChunkBasedArenaAllocator {
private:
    struct Chunk {
        char* data;         // Pointer to the memory block
        size_t capacity;    // Capacity of the chunk
        size_t offset;      // Current offset within the chunk
        Chunk(size_t size) : capacity(size), offset(0) {
            data = new char[size];
        }
        ~Chunk() {
            delete[] data;
        }
        // Allocate memory from the chunk
        void* allocate(size_t size, size_t alignment) {
            uintptr_t currentPtr = reinterpret_cast<uintptr_t>(data + offset);
            size_t padding = (alignment - (currentPtr % alignment)) % alignment;
            if (offset + padding + size > capacity) {
                return nullptr; // Not enough space
            }
            offset += padding; // Adjust for alignment
            void* allocation = data + offset;
            offset += size;
            return allocation;
        }
    };
    std::vector<Chunk*> chunks; // List of allocated chunks
    size_t chunkSize;           // Size of each chunk
public:
    explicit ChunkBasedArenaAllocator(size_t initialChunkSize) : chunkSize(initialChunkSize) {
        chunks.push_back(new Chunk(chunkSize));
    }
    void* allocate(size_t size, size_t alignment = alignof(std::max_align_t)) {
        if (size > chunkSize) {
            throw std::bad_alloc(); // Request exceeds maximum chunk size
        }
        for (auto& chunk : chunks) {
            void* allocation = chunk->allocate(size, alignment);
            if (allocation != nullptr) {
                return allocation;
            }
        }
        // If no space in existing chunks, create a new chunk
        Chunk* newChunk = new Chunk(chunkSize);
        chunks.push_back(newChunk);
        return newChunk->allocate(size, alignment);
    }
    void reset() {
        for (auto& chunk : chunks) {
            chunk->offset = 0; // Reset offset in each chunk
        }
    }
    ~ChunkBasedArenaAllocator() {
        for (auto& chunk : chunks) {
            delete chunk;
        }
    }
};
int main() {
    try {
        constexpr size_t CHUNK_SIZE = 256; // Each chunk has 256 bytes
        ChunkBasedArenaAllocator allocator(CHUNK_SIZE);
        // Allocate an integer
        int* intPtr = static_cast<int*>(allocator.allocate(sizeof(int)));
        *intPtr = 123;
        std::cout << "Integer: " << *intPtr << "\n";
        // Allocate a double
        double* doublePtr = static_cast<double*>(allocator.allocate(sizeof(double)));
        *doublePtr = 45.67;
        std::cout << "Double: " << *doublePtr << "\n";
        // Allocate a character array
        char* charArray = static_cast<char*>(allocator.allocate(50));
        std::fill(charArray, charArray + 50, 'X');
        charArray[49] = '\0';
        std::cout << "Char Array: " << charArray << "\n";
        // Reset the allocator
        allocator.reset();
        std::cout << "Allocator reset. Memory can be reused.\n";
    } catch (const std::exception& e) {
        std::cerr << "Error: " << e.what() << "\n";
    }
    return 0;
}

Output:

Integer: 123
Double: 45.67
Char Array: XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Allocator reset. Memory can be reused.

Explanation:

1. Structure of the Arena

In the chunk-based arena allocator, the arena is segmented into smaller blocks known as chunks, with each chunk representing a consistent block of memory. This approach enhances memory management flexibility by enabling numerous allocations across various chunks, thus minimizing potential memory wastage within the memory pool.

• ✅ The allocator commences with an initial chunk and possesses the capability to generate additional chunks on-the-fly when required. This feature mitigates the risk of memory fragmentation that could arise if all allocations were sourced from a single, expansive block.

1. Process of Allocation

When memory is requested:

• ✅ The allocator first checks if there's enough free space in the existing chunks to satisfy the request. Each chunk has a certain amount of memory, and a pointer (offset) keeps track of where the next allocation can begin within the chunk.
• ✅ To ensure proper alignment for data types, the allocator may add some padding between memory allocations within a chunk.
• ✅ If the requested size fits within the current chunk, the memory is allocated by adjusting the offset to point to the following available location. If there's not enough space in the current chunk, the allocator checks the next chunk, repeating this process.
• ✅ If none of the existing chunks have enough free space for the new allocation, the allocator creates a new chunk of memory and continues the allocation process there.

1. Handling Alignment

The growth of the memory pool dynamically adapts to the changing needs of the program, expanding to accommodate increasing memory demands while maintaining alignment requirements for different data types.

The arena allocator based on chunks begins with a single chunk and has the capability to expand dynamically by generating additional chunks whenever additional memory is required.

This enables the allocator to effectively manage varying memory request sizes by adding new chunks when the current ones reach capacity.

1. Refreshing the Arena

Once the program has completed the allocation process, the arena can undergo a reset. Rather than deallocating memory blocks one by one, the allocator resets the offset for each segment to zero. This action essentially releases all memory at once, clearing the arena for fresh allocations.

This reset method is highly effective as it only necessitates resetting a small number of pointers instead of scanning the complete memory block to free up each element individually.

1. Memory Cleanup

Once the allocator is no longer needed, it cleans up by deleting the chunks and their associated memory. This prevents memory leaks, ensuring that all memory is freed when the allocator goes out of scope.

1. Advantages of This Approach

• ✅ Efficient Memory Management: By dividing the arena into chunks, the allocator can handle varying allocation sizes more efficiently, minimizing wasted space.
• ✅ Dynamic Growth: The arena can grow as needed, ensuring that large requests don't run out of memory.
• ✅ Simple Reset: The reset function is quick and does not involve freeing individual allocations, making it suitable for short-lived objects or tasks.
• ✅ Alignment Handling: Proper alignment ensures that the allocated memory is suitable for different data types, avoiding misalignment issues.

Complexity analysis:

Time Complexity

Memory Allocation:

• ✅ The allocation process involves checking each chunk for available space, adjusting the pointer, and aligning the memory. This is done in constant time per chunk. Since each chunk is large enough to handle multiple allocations, the time to allocate memory from a chunk is O(1).
• ✅ If a chunk is complete, a new chunk is created, which also happens in O(1) time.
• ✅ Overall Time Complexity for Allocation: O(1) per allocation, assuming the allocation fits within the current chunk or is successfully assigned to a new chunk.

Resetting the Arena:

• ✅ Reinitializing the allocator simply requires resetting the offset for each segment, which is a constant time operation.
• ✅ Total Time Complexity for Reset: O(k), where k represents the quantity of segments (due to resetting the offset of each segment).

Space Complexity:

The memory allocated by the allocator increases with the size of the created portions. Every portion constitutes a continuous segment of memory, and additional portions are assigned dynamically when required.

The spatial complexity is denoted as O(n), where n represents the cumulative memory across all segments. This value escalates as more segments are generated to meet memory demands.