Component of the Week #34: `bdlma_sequentialallocator`

Summary:

Allows mass-freeing of complex data structures with single operation.
Implements the bdlma::ManagedAllocator protocol and efficiently allocates heterogeneous memory blocks.
Allocation of small memory segments by client are batched together in large memory blocks allocated from the underlying allocator, resulting in greater allocation speed and efficiency.

Often, much of the effort of writing code is spent on the code that allocates and populates data structures prior to computation, and then traverses and frees those data structures when computation is done. The bdlma::ManagedAllocator interface allows all allocations that have happened with a single allocator to be freed effortlessly by the destructor of the allocator or by calling the bdlma::ManagedAllocator::release virtual function, saving large amounts of development time.

In addition, the underlying allocator (typically new/delete or malloc/free) often is a sophisticated allocator that maintains a free list, making allocations and deallocations directly to and from it slow and expensive. bdlma::SequentialAllocator allocates large buffers from the underlying allocator, then parcels out small segments from within those buffers without the expense of maintaining a free list, resulting in much faster allocation.

The main difference between bdlma::SequentialAllocator and bdlma::SequentialPool is that bdlma::SequentialAllocator is designed to be used through a bslma::Allocator * pointer, making it more general-purpose although potentially slower due to virtual function call overhead.

The sequential allocator is commonly used in parsers, temporary data structures, and algorithms that build up complex data structures that are discarded as a unit.

Key Features

No need to traverse and free data structures in detail – all allocations from the memory allocator are effortlessly freed by destructor, or release call.
Fast allocation: Sequential allocation from pre-allocated buffers is much faster than direct allocation from new/delete or malloc/free.
No individual deallocation: deallocate() is a no-op, reducing overhead.
Configurable growth: Supports geometric or constant growth strategies of underlying blocks.
Alignment control: Natural, maximum, or 1-byte alignment strategies.
Avoid memory leaks: that are often caused by defective datastructure freeing code.
Buffer size limits: Optional maximum buffer size to control memory usage, allocation of segments larger than maximum buffer size result in individual allocations from underlying allocator.

Performance Considerations

bdlma::SequentialAllocator is ideal for scenarios where:

Your data structures are complex, and you want to avoid having to write code to traverse and free it all.
You expect many allocations in your datastructure.
You want to free your datastructure all at once – individual deallocation is not needed.
You want to minimize allocation overhead and memory fragmentation.

Warning

The sequential allocator should not be used for long-lived data structures that are frequently allocating and deallocating memory, since the deallocations do nothing and the memory consumed by such a data structure would just grow indefinitely.

Basic Usage

The most common usage is to create a bdlma::SequentialAllocator and pass it to components that accept a bslma::Allocator*:

#include <bdlma_sequentialallocator.h>
#include <bsl_vector.h>
#include <bsl_iostream.h>

using namespace BloombergLP;
using bsl::cout;
using bsl::endl;

int main() {
    // Create a sequential allocator with default settings

    bdlma::SequentialAllocator alloc;

    // Use it with standard containers

    bsl::vector<int> vec(&alloc);

    // Fill the vector - all allocations come from sequential buffers

    for (int i = 0; i < 1000; ++i) {
        vec.push_back(i);
    }

    cout << "Vector size: " << vec.size() << endl;

    // All memory automatically released when 'alloc' goes out of scope

    return 0;
}

Configurable Buffer Management

You can configure the initial buffer size, maximum buffer size, growth strategy, and alignment strategy to optimize performance for your specific use case:

#include <bdlma_sequentialallocator.h>
#include <bslma_testallocator.h>
#include <bsls_blockgrowth.h>
#include <bsls_alignment.h>
#include <bsl_iostream.h>
#include <assert.h>

using namespace BloombergLP;
using bsl::cout;
using bsl::endl;

int main() {
    // Create allocator with custom configuration:
    // - Initial buffer: 1KB
    // - Max buffer size: 64KB
    // - Geometric growth strategy
    // - Natural alignment

    bslma::TestAllocator       ta;    // 'alloc' gets memory from 'ta'
    bdlma::SequentialAllocator alloc(
        1024,                                   // initialSize
        10 * 1024,                              // maxBufferSize
        bsls::BlockGrowth::BSLS_GEOMETRIC,      // growthStrategy
        bsls::Alignment::BSLS_NATURAL,          // alignmentStrategy
        &ta                                     // underlying allocator
    );

    // Allocate various sized blocks

    void *small  = alloc.allocate(16);
    void *medium = alloc.allocate(256);
    void *large  = alloc.allocate(4096);

    cout << "Allocated blocks: "
              << small << ", " << medium << ", " << large << endl;

    // Reserve capacity for future allocations

    alloc.reserveCapacity(8192);
    const bsl::size_t numAllocations = ta.numAllocations();

    // More allocations will be fast since capacity is pre-reserved

    for (int i = 0; i < 100; ++i) {
        void *ptr = alloc.allocate(64);
        (void)ptr;  // suppress unused variable warning
    }

    // 'alloc' has allocated no more memory from 'ta' since
    // 'reserveCapacity' was called.

    assert(ta.numAllocations() == numAllocations);

    void *reallyBig = alloc.allocate(20 * 1024);

    // That last allocation required more memory than had been reserved, so
    // additional memory was required from 'ta'.

    assert(ta.numAllocations() == numAllocations + 1);

    return 0;
}

For More Information See Also

For more details, see:

Component of the Week #34: bdlma_sequentialallocator