STL Allocator com low-fragmentation heap

O STL provê uma série de estruturas de dados, como o std::list ou std::vector, normalmente chamados de containers. Esses containers possuem a capacidade de mudar de tamanho durante a execução do aplicativo, para isso ele se utiliza dos alocadores dinamicos, ou simplesmente allocators. O STL ja provê os alocadores padrão para uso geral, porém também é possível desenvolver um alocador para ser usado com os containers. A desvantagem dos alocadores padrão é que se utilizam diretamente de new/delete, assim como malloc/free, o que acarreta implicações no desempenho que não devem ser ignoradas.

English version of this article: STL Allocator with low-fragmentation heap.

Existem alocadores disponíveis na web que podem ser utilizados em quaisquer aplicativos como o da biblioteca, que eu gosto sempre de citar, Boost, o fast_pool_allocator. Porém aproveitando a técnica das private heaps apesentada no artigo Gerenciamento de memória em aplicações Windows, estamos disponibilizando um alocador dinâmico baseado na classe HeapSpace que foi apresentada:

#include <iostream>
#include <windows.h>
#include "HeapSpace.h"

template <typename T>
class HeapAllocator {
public:
    HeapSpace* HeapHandler;
    int* Copies;

public:
    // type definitions
    typedef T        value_type;
    typedef T*       pointer;
    typedef const T* const_pointer;
    typedef T&       reference;
    typedef const T& const_reference;
    typedef std::size_t    size_type;
    typedef std::ptrdiff_t difference_type;

    // rebind allocator to type U
    template <typename U>
    struct rebind {
        typedef HeapAllocator<U> other;
    };

    // return address of values
    pointer address (reference value) const {
        return &value;
    }
    const_pointer address (const_reference value) const {
        return &value;
    }

    /* constructors and destructor
    */
    HeapAllocator() throw() {
        HeapHandler = new HeapSpace(50*sizeof(T));
        Copies = (int*)HeapHandler->alloc(sizeof(Copies));
        *Copies = 1;
    }
    HeapAllocator(HeapAllocator const& arg) throw() {
        Copies = arg.Copies;
        HeapHandler = arg.HeapHandler;
        (*Copies)++;
    }
    template <typename U>
    HeapAllocator (HeapAllocator<U> const& arg) throw() {
        Copies = arg.Copies;
        HeapHandler = arg.HeapHandler;
        (*Copies)++;
    }
    ~HeapAllocator() throw() {
        (*Copies)--;
        if (*Copies == 0)
            delete HeapHandler;
    }

    // return maximum number of elements that can be allocated
    size_type max_size () const throw() {
        return size_t(-1) / sizeof(value_type);
    }

    // allocate but don't initialize num elements of type T
    pointer allocate (size_type num, const void* = 0) {
        return (pointer) this->HeapHandler->alloc((unsigned long)(num*sizeof(T)));
    }

    // initialize elements of allocated storage p with value value
    void construct (pointer p, const T& value) {
        new((void*)p)T(value);
    }

    // destroy elements of initialized storage p
    void destroy (pointer p) {
        p->~T();
    }

    // deallocate storage p of deleted elements
    void deallocate (pointer p, size_type num) {
        this->HeapHandler->free((void*)p);
    }
};

// return that all specializations of this allocator are interchangeable
template <typename T1, typename T2>
bool operator==(HeapAllocator<T1> const& Type1, HeapAllocator<T2> const& Type2) throw()
{
    return Type1.HeapHandler == Type2.HeapHandler;
}

template <typename T1, typename T2>
bool operator!=(HeapAllocator<T1> const& Type1, HeapAllocator<T2> const& Type2) throw()
{
    return Type1.HeapHandler != Type2.HeapHandler;
}

Notem que esse alocador mantém a mesma instância do gerenciador de memória mesmo quando é recriado com outro tipo, dessa forma ele terá somente uma instância do gerenciador de memória, com o seu espaço de memória heap, por instância do container. Antes de continuar, vejamos uma comparação:

Observe que o alocador LFH se mostrou vantajoso para ser aplicado tanto com std::queue, como com o std::deque. Porém foi com o std::queue que apresentou a melhor perrformance, realizando a tarefa em cerca de metade do tempo. Também foram feitos testes com std::list, std::vector e outros, casos em que também foram obtidos ganhos, mas com escalas totalmente diferentes, demorando dezenas de vezes mais, que foram descartadas para melhor entendimento do gráfico. Essas medições foram feitas individualmente, um container de cada vez, retirando a média do tempo que leva uma longa sequência de inserções e retiradas da fila sendo feita por 10 threads simultaneamente. Lembrando que esse teste simula uma condição artificial de estresse forçado que pode não representar a realidade de outros aplicativos, é sempre recomendado testes específicos de performance em aplicativos onde o tempo de resposta for crítico.

Alguns exemplos de métodos para configurar os containers utilizando esse alocador:

//utilizando std::queue (FIFO mais rápido)
std::queue<int,std::deque<int,HeapAllocator<int>>> Queue;

//utilizando std::deque
std::deque<int,HeapAllocator<int>> Queue;

//std::vector
std::vector<int,HeapAllocator<int>> Queue;

//std::list
std::list<int,HeapAllocator<int>> Queue;