Alocadores de heap personalizados

A maioria dos programas pode ser bastante casual quanto à alocação de heap, até o ponto em que as linguagens de programação funcionais preferem alocar novos objetos do que os antigos, e deixar o coletor de lixo se preocupar em liberar coisas.

Na programação incorporada, o setor silencioso, no entanto, existem muitos aplicativos em que você não pode usar a alocação de heap, devido à memória e a restrições em tempo real; o número de objetos de cada tipo que será tratado faz parte da especificação e tudo é estaticamente alocado.

A programação de jogos (pelo menos com os jogos ambiciosos em empurrar o hardware) às vezes fica entre: você pode usar alocação dinâmica, mas há memória suficiente e restrições suaves em tempo real que não pode tratar o alocador como uma caixa preta , muito menos usar a coleta de lixo, para que você tenha que usar alocadores personalizados. Essa é uma das razões pelas quais o C ++ ainda é amplamente utilizado na indústria de jogos; permite fazer coisas como http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html

Que outros domínios existem nesse território intermediário? Onde, além dos jogos, os alocadores personalizados são muito usados?

Sempre que você tiver um aplicativo que tenha um caminho crítico de alto desempenho, preocupe-se em como trata a memória. A maioria dos aplicativos do lado do cliente do usuário final não se enquadra nessa categoria, pois são orientados a eventos principais e a maioria dos eventos vem de interações com o usuário, e isso não tem muitas restrições de desempenho (se é que existem).

No entanto, muitos softwares de back-end devem se concentrar em como a memória é manipulada, porque muitos deles podem ser dimensionados para lidar com um número maior de clientes, um número maior de transações, mais fontes de dados. empurrando os limites, você pode começar a analisar como os usuários de software armazenam e escrevem esquemas de alocação personalizados, adequados ao seu software, em vez de confiar em um alocador de memória completamente genérico que foi criado para lidar com qualquer caso de uso imaginável.

Para dar alguns exemplos ... na minha primeira empresa, trabalhei em um pacote Historian, software responsável por coletar / armazenar / arquivar dados de controle de processos (pense em uma fábrica, usina nuclear ou refinaria de petróleo com 10 milhões de sensores, armazenaríamos esses dados). Sempre que analisamos qualquer gargalo de desempenho que impedia o Historiador de processar mais dados, na maioria das vezes o problema estava em como a memória era manipulada. Passamos por grandes esforços para garantir que malloc / free não fossem chamados, a menos que fossem absolutamente necessários.

No meu trabalho atual, trabalho no gravador de vídeo digital de vigilância e no pacote de análise. A 30 qps, cada canal recebe um quadro de vídeo a cada 33 milissegundos. No hardware que vendemos, podemos gravar facilmente 100 canais de vídeo. Portanto, esse é outro caso para garantir que no caminho crítico (chamada de rede => componentes de captura => software de gerenciamento de gravadores => componentes de armazenamento => disco) não haja alocações dinâmicas de memória. Temos um alocador de quadro personalizado, que contém depósitos de buffers de tamanho fixo e usa LIFO para reutilizar buffers alocados anteriormente. Se você precisar de 600Kb de armazenamento, poderá acabar com um buffer de 1024Kb, o que desperdiça espaço, mas, como é adaptado especificamente para o nosso uso em que cada alocação é de curta duração, funciona muito bem porque o buffer é usado,

No tipo de aplicativos que descrevi (mover muitos dados de A para B e manipular um grande número de solicitações de clientes), ir para o heap e back é uma das principais fontes de gargalos no desempenho da CPU. Manter a fragmentação de heap no mínimo é um benefício secundário, no entanto, até onde eu sei, os sistemas operacionais modernos já implementam heaps de baixa fragmentação (no mínimo, eu sei que o Windows faz, e espero que outros o façam). Pessoalmente, em mais de 12 anos trabalhando nesses tipos de ambientes, vi problemas de uso da CPU relacionados ao heap com bastante frequência, enquanto nunca vi um sistema que sofria de heap fragmentado.

Processamento de vídeo, efeitos visuais, sistemas operacionais etc. Geralmente, as pessoas os usam demais. A estrutura de dados e o alocador não precisam ser separados para obter uma alocação eficiente.

Por exemplo, está introduzindo muita complexidade extra para dividir a alocação eficiente de nós em uma octree da octree e confiar em um alocador externo. Não é necessariamente uma violação do SRP fundir essas duas preocupações e tornar responsabilidade da octree alocar muitos nós ao mesmo tempo de forma contígua, pois isso não aumenta o número de razões para mudar. Pode, na prática, diminuí-lo.

No C ++, por exemplo, um dos efeitos colaterais retardados de ter contêineres padrão dependem de um alocador externo tornou estruturas vinculadas std::mape std::listconsideradas quase inúteis pela comunidade C ++, uma vez que elas são comparadas com elasstd::allocatorenquanto essas estruturas de dados alocam um nó por vez. É claro que suas estruturas vinculadas terão um desempenho ruim nesse caso, mas as coisas teriam sido muito diferentes se a alocação eficiente de nós para estruturas vinculadas fosse considerada mais uma responsabilidade da estrutura de dados do que um alocador. Eles ainda podem usar uma alocação personalizada por outros motivos, como rastreamento / criação de perfil de memória, mas contar com o alocador para tornar eficientes as estruturas vinculadas ao tentar alocar nós um de cada vez torna todos eles, por padrão, extremamente ineficientes, o que seria aceitável se houvesse uma advertência conhecida de que as estruturas vinculadas agora precisam de um alocador personalizado, como lista livre, para serem razoavelmente eficientes e evitar acionar falhas de cache à esquerda e à direita. Muito mais praticamente aplicável, poderia ter sido algo comostd::list<T, BlockSize, Alloc>, em que BlockSizeindica o número de nós contíguos a serem alocados de uma vez para a lista livre (a especificação de 1 levaria efetivamente ao std::listatual).

Mas não existe essa ressalva, o que leva a uma comunidade inteira de cabeças-grossas ecoando um mantra de culto de que as listas vinculadas são inúteis, por exemplo,

Outra área em que você pode querer um alocador personalizado é evitar a fragmentação de heap . Com o tempo, seu heap pode alocar pequenos objetos fragmentados por todo o heap. Se o seu programa não conseguir manter a memória da pilha unida, quando ele alocar um objeto maior, ele precisará reivindicar mais memória do sistema, pois não poderá encontrar um bloco livre entre a pilha fragmentada existente (muitas pequenas objetos estão no caminho). O uso total de memória do seu programa aumentará com o tempo e você consumirá páginas adicionais de memória desnecessariamente. Portanto, esse é um problema muito grande para os programas que devem rodar por longos períodos de tempo (pense em bancos de dados, servidores, etc.).

Onde, além dos jogos, os alocadores personalizados são muito usados?

Facebook

Confira jemalloc que o Facebook está começando a usar para melhorar seu desempenho de heap e diminuir a fragmentação.