pilha-gerente eficiente para churn pesado, pequenas alocações?

Question

Eu estou procurando idéias para um montão-gerente para lidar com uma situação muito específica: lotes e lotes de pequenas alocações, variando de 12 a 64 bytes cada. Qualquer coisa maior, eu vou passar para a pilha-manager regular, portanto, apenas pequenos blocos precisam ser atendidas. Apenas é necessário alinhamento de 4 bytes.

As minhas principais preocupações são

1. Overhead. A pilha libc regular irá tipicamente rodada para uma afectação a um múltiplo de 16 bytes, em seguida, adicione outro cabeçalho de 16 bytes -. Isso significa mais de 50% despesas gerais sobre a alocação de 20 bytes, que suga
2. Desempenho

Um aspecto útil é que Lua (que é o usuário deste montão) irá dizer-lhe o tamanho do bloco que está liberando quando ele chama free () -. Isto pode permitir certas otimizações

Vou postar minha abordagem atual, que funciona ok, mas eu gostaria de melhorá-lo, se possível. Alguma idéia?

Answer 1

É possível construir um gerenciador de heap que é muito eficiente para objetos que são todos do mesmo tamanho. Você poderia criar uma dessas pilhas para cada tamanho do objeto que você precisa, ou se você não se importa com um pouco de espaço, criar um para objetos de 16 bytes, um para 32, e um para 64. A sobrecarga máxima seria 31 bytes para uma atribuição 33 byte (que iria na pilha 64 de bloco).

Answer 2

Para expandir o que Greg Hewgill diz, uma maneira de fazer uma pilha de ultra-eficiente de tamanho fixo é:

1. Split um grande tampão para nós. tamanho do nó deve ser de pelo menos sizeof (* void).
2. reuni-los em uma lista individualmente ligado (a "lista livre"), utilizando o primeiro sizeof (void *) bytes de cada nó livre como um ponteiro link. nós alocados não vai precisar de um ponteiro link, assim por nó sobrecarga é 0.
3. Alocar, removendo a cabeça da lista e devolvê-lo (2 cargas, 1 loja).
4. Free inserindo na cabeça da lista (1 carga, 2 lojas).

Obviamente passo 3 também tem que verificar se da lista vazia, e se assim fazer um monte de trabalho a obtenção de um novo buffer grande (ou não).

Mesmo mais eficiente, como Greg D e digamos hazzen, é alocar por aumentar ou diminuir um ponteiro (1 carga, 1 loja), e não oferecem uma maneira de libertar um único nó em tudo.

Edit: Em ambos os casos, livre pode lidar com o "algo maior que eu passar a regulares pilha-manager" complicação pelo fato útil que você começa a parte de trás tamanho na chamada para livre. Caso contrário, você estaria olhando para qualquer um sinalizador (sobrecarga provavelmente 4 bytes por nó) ou então uma pesquisa em algum tipo de registro do buffer (s) que você usou.

Answer 3

A resposta pode depender dos padrões de vida para esses objetos. Se os objetos estão todos instanciado à medida que avançar, e depois todos retirados de uma só vez, pode fazer sentido para criar um gerenciador de heap muito simples que aloca memória simplesmente incrementar um ponteiro. Então, quando você estiver pronto, soprar toda a pilha.

Raymond Chen fez uma interessante pós que pode ajudar a inspirá-lo. :)

Answer 4

Gosto onebyones resposta.

Você também pode considerar a buddy sistema para seus conjuntos de pilhas de tamanho fixo.

Answer 5

Se um bando de memória é alocada, usados ??e liberados antes de passar para a próxima rodada de alocação, eu sugiro usar o mais simples alocador possível:

typedef struct _allocator {
    void* buffer;
    int start;
    int max;
} allocator;

void init_allocator(size_t size, allocator* alloc) {
    alloc->buffer = malloc(size);
    alloc->start = 0;
    alloc->max = size;
}

void* allocator_malloc(allocator* alloc, size_t amount) {
    if (alloc->max - alloc->start < 0) return NULL;
    void* mem = alloc->buffer + alloc->start;
    alloc->start += bytes;
    return mem;
}

void allocator_free(allocator* alloc) {
    alloc->start = 0;
}

Answer 6

Eu uso uma maioria O (1) Small Block memória Manager (SBMM). Basicamente ele funciona desta maneira:

1) Ele aloca superquadras maiores do OS e rastreia os endereços de início + End como um intervalo. O tamanho do superbloco ajustável, mas 1MB faz um tamanho muito bom.

2) As superquadras são divididos em blocos (também ajustável em tamanho ... 4K-64K é bom dependendo do seu app). Cada um destes blocos lida com alocações de um tamanho específico e lojas de todos os itens no bloco como uma lista vinculada isoladamente. Quando você atribuir um SuperBlock, você faz uma lista encadeada de blocos livres.

3) Atribuir meio alínea a) Verificar se existe um bloco com itens grátis lidar com esse tamanho - e se não, a atribuição de uma nova quadra da superquadras. B) A remoção do item da lista livre do bloco.

4) Libertar um item, por meio de endereços A) Finding SuperBlock contendo o endereço (*) B) Finding Block em SuperBlock (SuperBlock substrato endereço de início e dividir por tamanho Block) C) Empurrando item na lista grátis Item do bloco.

Como eu disse, este SBMM é muito rápido como ele é executado com O (1) desempenho (*). Na versão Eu tenho implementado, eu uso um AtomicSList (semelhante ao SLIST no Windows) para que ele não é apenas O (1) desempenho, mas também Threadsafe e LockFree na implementação. Você poderia realmente implementar o algoritmo usando Win32 SLIST se você quisesse.

Curiosamente, o algoritmo para alocação de blocos a partir das superquadras ou itens dos blocos resultar em código quase identicaly (ambos são O (1) alocações de fora de uma lista Free).

(*) Os superblocks estão dispostos em uma rangemap com O (1) o desempenho médio (mas um O potencial (lg n) para o pior caso, em que N é o número de superblocks). A largura do rangemap depende de saber aproximadamente a quantidade de memória que você vai necessidade, a fim de obter a O (1) desempenho. Se você superação, você vai perder um pouco de memória, mas ainda obter O (1) desempenho. Se você undershoot, você vai se aproximar O desempenho (Lg N), mas o N é para a contagem SuperBlock - não a contagem de item. Desde a contagem superbloco muito baixo quando comparado com a contagem Item (por cerca de 20 ordens binárias de magnitude no meu código), não é tão crítico como o resto do alocador.