Exemplos convincentes de alocadores personalizados de C ++?

Quais são realmente algumas boas razões para abandonar std::allocatoruma solução personalizada? Você já se deparou com alguma situação em que era absolutamente necessário para correção, desempenho, escalabilidade etc.? Algum exemplo realmente inteligente?

Alocadores personalizados sempre foram um recurso da Biblioteca Padrão que eu não precisava muito. Eu estava pensando se alguém aqui no SO poderia fornecer alguns exemplos convincentes para justificar sua existência.

Como mencionei aqui , vi o alocador STL personalizado da Intel TBB melhorar significativamente o desempenho de um aplicativo multithread simplesmente alterando um único

std::vector<T>

para

std::vector<T,tbb::scalable_allocator<T> >

(esta é uma maneira rápida e conveniente de alternar o alocador para usar os heaps bacanas de thread-private da TBB; consulte a página 7 deste documento )

Uma área em que os alocadores personalizados podem ser úteis é o desenvolvimento de jogos, especialmente em consoles de jogos, pois eles têm apenas uma pequena quantidade de memória e nenhuma troca. Em tais sistemas, você deseja garantir um controle rígido sobre cada subsistema, para que um sistema não crítico não possa roubar a memória de um sistema crítico. Outras coisas, como alocadores de pool, podem ajudar a reduzir a fragmentação da memória. Você pode encontrar um artigo longo e detalhado sobre o tópico em:

EASTL - Biblioteca de modelos padrão de artes eletrônicas

Estou trabalhando em um mmap-alocador que permite que vetores usem memória de um arquivo mapeado na memória. O objetivo é ter vetores que usem armazenamento diretamente na memória virtual mapeados pelo mmap. Nosso problema é melhorar a leitura de arquivos realmente grandes (> 10 GB) na memória sem sobrecarga de cópia; portanto, preciso desse alocador personalizado.

Até agora, tenho o esqueleto de um alocador personalizado (que deriva de std :: alocador), acho que é um bom ponto de partida para escrever alocadores próprios. Sinta-se livre para usar este trecho de código da maneira que desejar:

#include <memory>
#include <stdio.h>

namespace mmap_allocator_namespace
{
        // See StackOverflow replies to this answer for important commentary about inheriting from std::allocator before replicating this code.
        template <typename T>
        class mmap_allocator: public std::allocator<T>
        {
public:
                typedef size_t size_type;
                typedef T* pointer;
                typedef const T* const_pointer;

                template<typename _Tp1>
                struct rebind
                {
                        typedef mmap_allocator<_Tp1> other;
                };

                pointer allocate(size_type n, const void *hint=0)
                {
                        fprintf(stderr, "Alloc %d bytes.\n", n*sizeof(T));
                        return std::allocator<T>::allocate(n, hint);
                }

                void deallocate(pointer p, size_type n)
                {
                        fprintf(stderr, "Dealloc %d bytes (%p).\n", n*sizeof(T), p);
                        return std::allocator<T>::deallocate(p, n);
                }

                mmap_allocator() throw(): std::allocator<T>() { fprintf(stderr, "Hello allocator!\n"); }
                mmap_allocator(const mmap_allocator &a) throw(): std::allocator<T>(a) { }
                template <class U>                    
                mmap_allocator(const mmap_allocator<U> &a) throw(): std::allocator<T>(a) { }
                ~mmap_allocator() throw() { }
        };
}

Para usar isso, declare um contêiner STL da seguinte maneira:

using namespace std;
using namespace mmap_allocator_namespace;

vector<int, mmap_allocator<int> > int_vec(1024, 0, mmap_allocator<int>());

Pode ser usado, por exemplo, para registrar sempre que a memória é alocada. O que é necessário é a estrutura de religação, caso contrário, o contêiner de vetor usa os métodos de alocação / desalocação de superclasses.

Atualização: o alocador de mapeamento de memória agora está disponível em https://github.com/johannesthoma/mmap_allocator e é LGPL. Sinta-se livre para usá-lo em seus projetos.

Estou trabalhando com um mecanismo de armazenamento MySQL que usa c ++ para seu código. Estamos usando um alocador personalizado para usar o sistema de memória MySQL em vez de competir com o MySQL por memória. Isso nos permite garantir que estamos usando a memória como o usuário configurou o MySQL para usar, e não "extra".

Pode ser útil usar alocadores personalizados para usar um conjunto de memórias em vez do heap. Esse é um exemplo entre muitos outros.

Na maioria dos casos, essa é certamente uma otimização prematura. Mas pode ser muito útil em certos contextos (dispositivos incorporados, jogos, etc).

Não escrevi código C ++ com um alocador STL personalizado, mas posso imaginar um servidor Web escrito em C ++, que usa um alocador personalizado para exclusão automática de dados temporários necessários para responder a uma solicitação HTTP. O alocador personalizado pode liberar todos os dados temporários de uma vez, após a geração da resposta.

Outro possível caso de uso para um alocador personalizado (que eu usei) está escrevendo um teste de unidade para provar que o comportamento de uma função não depende de parte da entrada. O alocador personalizado pode preencher a região da memória com qualquer padrão.

Ao trabalhar com GPUs ou outros co-processadores, às vezes é benéfico alocar estruturas de dados na memória principal de uma maneira especial . Esta maneira especial de alocar memória pode ser implementada de maneira conveniente em um alocador personalizado.

O motivo pelo qual a alocação personalizada por meio do tempo de execução do acelerador pode ser benéfica ao usar aceleradores é o seguinte:

1. através da alocação personalizada, o tempo de execução ou o driver do acelerador é notificado sobre o bloco de memória
2. além disso, o sistema operacional pode garantir que o bloco de memória alocado esteja bloqueado por página (alguns chamam essa memória fixada ), ou seja, o subsistema de memória virtual do sistema operacional pode não mover ou remover a página dentro ou da memória
3. se 1. e 2. são retidos e é solicitada uma transferência de dados entre um bloco de memória bloqueado por página e um acelerador, o tempo de execução pode acessar diretamente os dados na memória principal, pois sabe onde está e pode ter certeza de que o sistema operacional não mover / remover
4. isso salva uma cópia da memória que ocorreria com a memória alocada de maneira não bloqueada por página: os dados devem ser copiados na memória principal para uma área temporária bloqueada por página do acelerador, que pode inicializar a transferência de dados (por meio do DMA )

Estou usando alocadores personalizados aqui; você pode até dizer que foi para solucionar outro gerenciamento de memória dinâmica personalizado.

Antecedentes: temos sobrecargas para malloc, calloc, free e as diversas variantes do operador new e delete, e o vinculador faz feliz pelo STL usá-las para nós. Isso nos permite fazer coisas como pool automático de objetos pequenos, detecção de vazamentos, preenchimento de alocação, preenchimento livre, alocação de preenchimento com sentinelas, alinhamento da linha de cache para determinadas alocações e atraso na liberação.

O problema é que estamos rodando em um ambiente incorporado - não há memória suficiente para realmente fazer a contabilidade de detecção de vazamento corretamente por um longo período. Pelo menos, não na RAM padrão - há outro monte de RAM disponível em outro lugar, por meio de funções personalizadas de alocação.

Solução: escreva um alocador personalizado que use o heap estendido e use-o apenas nas partes internas da arquitetura de rastreamento de vazamento de memória ... Todo o resto é padronizado com as sobrecargas normais de exclusão / exclusão que fazem o rastreamento de vazamentos. Isso evita o rastreamento do rastreador em si (e fornece algumas funcionalidades extras de empacotamento, sabemos o tamanho dos nós do rastreador).

Também usamos isso para manter os dados de perfil de custo da função, pelo mesmo motivo; escrever uma entrada para cada chamada e retorno de função, bem como comutadores de threads, pode ficar caro rapidamente. Alocador personalizado novamente nos fornece alocações menores em uma área maior de memória de depuração.

Estou usando um alocador personalizado para contar o número de alocações / desalocações em uma parte do meu programa e medir quanto tempo leva. Existem outras maneiras de conseguir isso, mas esse método é muito conveniente para mim. É especialmente útil que eu possa usar o alocador personalizado para apenas um subconjunto dos meus contêineres.

Uma situação essencial: ao escrever código que deve funcionar além dos limites do módulo (EXE / DLL), é essencial manter as alocações e exclusões acontecendo em apenas um módulo.

Onde me deparei com isso foi uma arquitetura Plugin no Windows. É essencial que, por exemplo, se você passar uma std :: string através do limite da DLL, todas as realocações da string ocorram da pilha de onde se originou, NÃO a pilha da DLL que pode ser diferente *.

* Na verdade, é mais complicado do que isso, como se você estivesse vinculando dinamicamente ao CRT, isso pode funcionar de qualquer maneira. Mas se cada DLL tem um link estático para o CRT, você está indo para um mundo de dor, onde erros de alocação fantasma ocorrem continuamente.

Um exemplo de como as usei foi trabalhar com sistemas embarcados com muitos recursos limitados. Digamos que você tenha 2k de RAM grátis e seu programa precisa usar parte dessa memória. Você precisa armazenar as sequências 4-5 em algum lugar que não esteja na pilha e, além disso, você precisa ter um acesso muito preciso sobre onde essas coisas são armazenadas; é uma situação em que você pode escrever seu próprio alocador. As implementações padrão podem fragmentar a memória, isso pode ser inaceitável se você não tiver memória suficiente e não puder reiniciar o programa.

Um projeto em que eu estava trabalhando era usar o AVR-GCC em alguns chips de baixa potência. Tivemos que armazenar 8 sequências de comprimento variável, mas com um máximo conhecido. A implementação da biblioteca padrão do gerenciamento de memóriaé um invólucro fino em torno do malloc / free, que monitora onde colocar os itens, acrescentando cada bloco de memória alocado com um ponteiro para passar o final desse pedaço de memória alocado. Ao alocar uma nova parte da memória, o alocador padrão precisa percorrer cada uma das partes da memória para encontrar o próximo bloco disponível onde o tamanho solicitado da memória se ajustará. Em uma plataforma de desktop, isso seria muito rápido para esses poucos itens, mas você deve ter em mente que alguns desses microcontroladores são muito lentos e primitivos em comparação. Além disso, o problema de fragmentação da memória era um problema enorme que significava que realmente não tínhamos escolha a não ser adotar uma abordagem diferente.

Então, o que fizemos foi implementar nosso próprio pool de memória . Cada bloco de memória era grande o suficiente para caber na maior sequência que precisaríamos. Isso alocou blocos de memória de tamanho fixo com antecedência e marcou quais blocos de memória estavam em uso no momento. Fizemos isso mantendo um número inteiro de 8 bits, onde cada bit representava se um determinado bloco era usado. Trocamos o uso de memória aqui por tentar acelerar todo o processo, o que, no nosso caso, foi justificado quando estávamos empurrando esse chip de microcontrolador para perto de sua capacidade máxima de processamento.

Há várias outras vezes em que consigo escrever seu próprio alocador personalizado no contexto de sistemas incorporados, por exemplo, se a memória da sequência não estiver no ram principal, como pode ser o caso nessas plataformas .

Link obrigatório para a palestra CppCon 2015 de Andrei Alexandrescu sobre alocadores:

https://www.youtube.com/watch?v=LIb3L4vKZ7U

O bom é que apenas inventá-las faz você pensar em idéias de como usá-las :-)

Para a memória compartilhada, é vital que não apenas a cabeça do contêiner, mas também os dados que ele contém sejam armazenados na memória compartilhada.

O alocador do Boost :: Interprocess é um bom exemplo. No entanto, como você pode ler aqui, isso não é suficiente, para tornar todos os contêineres STL compatíveis com a memória compartilhada (devido a diferentes deslocamentos de mapeamento em diferentes processos, os ponteiros podem "quebrar").

Algum tempo atrás, achei esta solução muito útil para mim: Alocador rápido de C ++ 11 para contêineres STL . Acelera levemente os contêineres STL no VS2017 (~ 5x), bem como no GCC (~ 7x). É um alocador de finalidade especial baseado no pool de memória. Só pode ser usado com contêineres STL, graças ao mecanismo que você está solicitando.

Eu pessoalmente uso o Loki :: Allocator / SmallObject para otimizar o uso de memória para objetos pequenos - ele mostra boa eficiência e desempenho satisfatório se você precisar trabalhar com quantidades moderadas de objetos realmente pequenos (1 a 256 bytes). Pode ser até 30 vezes mais eficiente do que a alocação nova de exclusão / exclusão de C ++, se falarmos em alocar quantidades moderadas de objetos pequenos de vários tamanhos diferentes. Além disso, existe uma solução específica para VC chamada "QuickHeap", que oferece o melhor desempenho possível (as operações de alocação e desalocação apenas leem e gravam o endereço do bloco que está sendo alocado / retornado ao heap, respectivamente em até 99. (9)% dos casos - depende das configurações e inicialização), mas a um custo de uma sobrecarga notável - ele precisa de dois ponteiros por extensão e um extra para cada novo bloco de memória. Isto'

O problema com a implementação new / delete padrão do C ++ é que geralmente é apenas um wrapper para alocação C / malloc / free e funciona bem para blocos maiores de memória, como 1024 ou mais bytes. Possui uma sobrecarga notável em termos de desempenho e, às vezes, memória extra usada para mapeamento também. Portanto, na maioria dos casos, os alocadores personalizados são implementados de forma a maximizar o desempenho e / ou minimizar a quantidade de memória extra necessária para alocar objetos pequenos (≤ 1024 bytes).

Em uma simulação gráfica, vi alocadores personalizados usados ​​para

1. Restrições de alinhamento que std::allocatornão suportam diretamente.
2. Minimizando a fragmentação usando conjuntos separados para alocações de curta duração (apenas esse quadro) e de longa duração.