Exemplos convincentes de alocadores C ++ personalizados?

Quais são algumas boas razões para dispensar o std::allocator em favor de uma solução customizada? Você já se deparou com situações 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 para o qual eu não tive muita necessidade. Eu estava apenas imaginando se alguém aqui na SO poderia fornecer alguns exemplos convincentes para justificar sua existência.

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

 std::vector 

para

 std::vector > 

(esta é uma maneira rápida e conveniente de trocar o alocador para usar pilhas bacanas de threads particulares 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, já que eles têm apenas uma pequena quantidade de memory e nenhuma troca. Em tais sistemas, você quer ter certeza de que você tem um controle rígido sobre cada subsistema, de modo que um sistema não crítico não roube a memory de um sistema crítico. Outras coisas, como alocadores de pool, podem ajudar a reduzir a fragmentação de memory. Você pode encontrar um documento longo e detalhado sobre o assunto em:

EASTL – Biblioteca de modelos padrão da Electronic Arts

Eu estou trabalhando em um alocador mmap que permite que vetores usem memory de um arquivo mapeado na memory. O objective é ter vetores que usem armazenamento diretamente na memory virtual mapeada por mmap. Nosso problema é melhorar a leitura de arquivos realmente grandes (> 10 GB) na memory sem sobrecarga de cópia, portanto, eu preciso deste alocador personalizado.

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

 #include  #include  namespace mmap_allocator_namespace { // See StackOverflow replies to this answer for important commentary about inheriting from std::allocator before replicating this code. template  class mmap_allocator: public std::allocator { public: typedef size_t size_type; typedef T* pointer; typedef const T* const_pointer; template 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::allocate(n, hint); } void deallocate(pointer p, size_type n) { fprintf(stderr, "Dealloc %d bytes (%p).\n", n*sizeof(T), p); return std::allocator::deallocate(p, n); } mmap_allocator() throw(): std::allocator() { fprintf(stderr, "Hello allocator!\n"); } mmap_allocator(const mmap_allocator &a) throw(): std::allocator(a) { } template  mmap_allocator(const mmap_allocator &a) throw(): std::allocator(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_vec(1024, 0, mmap_allocator()); 

Pode ser usado, por exemplo, para registrar sempre que a memory é alocada. O que é necessário é a estrutura de rebinding, senão o contêiner de vetor usa os methods de alocação / desalocação de superclasss.

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

Eu estou trabalhando com um mecanismo de armazenamento MySQL que usa c + + para o seu código. Estamos usando um alocador customizado para usar o sistema de memory MySQL em vez de competir com o MySQL por memory. Isso nos permite ter certeza de que estamos usando memory como o usuário configurou o MySQL para usar, e não “extra”.

Pode ser útil usar alocadores personalizados para usar um pool de memory em vez do heap. Esse é um exemplo entre muitos outros.

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

Eu não tenho escrito 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 só vez, uma vez que a resposta tenha sido gerada.

Outro caso de uso possível para um alocador customizado (que eu usei) é escrever um teste de unidade para provar que o comportamento de uma function não depende de alguma parte de sua input. O alocador personalizado pode preencher a região de memory com qualquer padrão.

Estou usando alocadores personalizados aqui; Você pode até dizer que foi para trabalhar em torno de outro gerenciamento personalizado de memory dinâmica.

Antecedentes: temos sobrecargas para malloc, calloc, free, e as diversas variantes do operador new e delete, e o linker faz com que a STL as utilize para nós. Isso nos permite fazer coisas como agrupamento automático de objects 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 livre.

O problema é que estamos rodando em um ambiente embarcado – não há memory suficiente para realmente fazer a contabilização da detecção de vazamentos durante um longo período. Pelo menos, não na RAM padrão – há outro monte de RAM disponível em outros lugares, por meio de funções de alocação personalizadas.

Solução: escreva um alocador personalizado que use o heap estendido e use-o apenas nos componentes internos da arquitetura de rastreamento de vazamentos de memory … Todo o restante é padronizado para as sobrecargas normais de novo / exclusão que fazem o rastreamento de vazamentos. Isso evita o acompanhamento do rastreador em si (e também oferece um pouco de funcionalidade extra de embalagem, sabemos o tamanho dos nós rastreadores).

Também usamos isso para manter os dados do perfil de custo da function, pelo mesmo motivo; escrever uma input para cada chamada e retorno de function, assim como os interruptores de linha, pode ficar caro rapidamente. O alocador customizado novamente nos fornece alocações menores em uma área de memory de debugging maior.

Ao trabalhar com GPUs ou outros coprocessadores, às vezes é benéfico alocar estruturas de dados na memory principal de uma maneira especial . Essa maneira especial de alocar memory pode ser implementada em um alocador personalizado de maneira conveniente.

A razão pela qual a alocação personalizada por meio do tempo de execução do acelerador pode ser benéfica quando o uso de aceleradores é o seguinte:

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

Eu 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 demora. 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 de meus contêineres.

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

Onde eu corri para isso era uma arquitetura Plugin no Windows. É essencial que, por exemplo, se você passar um std :: string através do limite da DLL, que quaisquer realocações da seqüência de caracteres ocorram do heap de onde ele originou, NÃO o heap na DLL que pode ser diferente *.

* É mais complicado do que isso, na verdade, como se você estivesse ligando dinamicamente ao CRT, isso poderia funcionar de qualquer maneira. Mas se cada DLL tiver um link estático para o CRT, você estará indo para um mundo de problemas, onde ocorrem erros de alocação fantasma.

Um exemplo do tempo que usei foi trabalhar com sistemas incorporados com muitos resources restritos. Vamos dizer que você tem 2k de RAM livre e seu programa tem que usar um pouco dessa memory. Você precisa armazenar, digamos, 4-5 sequências em algum lugar que não esteja na pilha e, além disso, você precisa ter access muito preciso sobre onde essas coisas são armazenadas, essa é uma situação em que você pode querer escrever seu próprio alocador. As implementações padrão podem fragmentar a memory, isso pode ser inaceitável se você não tiver memory suficiente e não puder reiniciar o programa.

Um projeto em que eu estava trabalhando estava usando o AVR-GCC em alguns chips de baixa potência. Nós tivemos que armazenar 8 seqüências de comprimento variável, mas com um máximo conhecido. A implementação de biblioteca padrão do gerenciamento de memory é um wrapper fino em torno de malloc / free que controla onde colocar itens com prefixando cada bloco alocado de memory com um ponteiro para apenas passar do final da parte alocada da memory. Ao alocar uma nova peça de memory, o alocador padrão deve percorrer cada uma das partes da memory para localizar o próximo bloco que está disponível, onde o tamanho solicitado da memory 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 de memory era um problema enorme que significava que realmente não tínhamos outra escolha senão adotar uma abordagem diferente.

Então, o que fizemos foi implementar nosso próprio conjunto de memorys . Cada bloco de memory era grande o suficiente para caber na maior sequência que precisaríamos. Isso alocou blocos de memory de tamanho fixo com antecedência e marcou quais blocos de memory estavam em uso no momento. Fizemos isso mantendo um inteiro de 8 bits onde cada bit representava se um determinado bloco fosse usado. Nós trocamos o uso da memory aqui por tentarmos tornar todo o processo mais rápido, o que no nosso caso foi justificado, já que estávamos empurrando esse chip microcontrolador para perto de sua capacidade máxima de processamento.

Há várias outras vezes em que vejo escrever seu próprio alocador customizado no contexto de sistemas incorporados, por exemplo, se a memory para a sequência não estiver na memory RAM principal, como pode ser freqüentemente o caso nessas plataformas .

Para a memory compartilhada, é vital que não apenas a cabeça do contêiner, mas também os dados nela contidos, sejam armazenados na memory compartilhada.

O alocador de 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 memory compartilhada (devido a diferentes deslocamentos de mapeamento em diferentes processos, os pointers podem “quebrar”).

Link obrigatório para o CppCon 2015 de Andrei Alexandrescu falar sobre alocadores:

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

O bom é que apenas imaginá-los faz você pensar em idéias de como você os usaria 🙂

Há algum tempo, achei essa solução muito útil para mim: Alocador Fast C ++ 11 para contêineres STL . Ele acelera ligeiramente os contêineres STL no VS2017 (~ 5x), bem como no GCC (~ 7x). É um alocador de propósito especial baseado no pool de memory. Ele pode ser usado apenas com contêineres STL graças ao mecanismo que você está solicitando.

Eu pessoalmente uso o Loki :: Allocator / SmallObject para otimizar o uso de memory para objects pequenos – ele mostra boa eficiência e desempenho satisfatório se você tiver que trabalhar com quantidades moderadas de objects realmente pequenos (1 a 256 bytes). Ele pode ser até 30 vezes mais eficiente do que a alocação padrão de novo / excluir de C ++ se falarmos sobre a alocação de quantidades moderadas de pequenos objects de muitos tamanhos diferentes. Além disso, há uma solução específica de VC chamada “QuickHeap”, que traz o melhor desempenho possível (alocar e desalocar operações apenas ler e gravar o endereço do bloco sendo alocado / retornado ao heap, respectivamente em até 99. (9)% casos – depende das configurações e da boot), mas ao custo de uma sobrecarga notável – ele precisa de dois pointers por extensão e um extra para cada novo bloco de memory. É a solução mais rápida possível para trabalhar com enormes quantidades (10 000 ++) de objects sendo criados e excluídos se você não precisar de uma grande variedade de tamanhos de objects (cria um pool individual para cada tamanho de object, de 1 a 1023 bytes na implementação atual, portanto, os custos de boot podem diminuir o aumento geral de desempenho, mas é possível ir adiante e alocar / desalocar alguns objects simulados antes que o aplicativo entre em fase (s) crítica (s) ao desempenho).

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

Em uma simulação de charts, vi alocadores personalizados usados ​​para

  1. Restrições de alinhamento que o std::allocator não suportava diretamente.
  2. Minimizar a fragmentação usando pools separados para alocações de vida curta (apenas nesse quadro) e de vida longa.