Gestionnaire de tas efficace pour la grosse baratte, allocs minuscules?

Question

Je cherche des idées pour un gestionnaire de tas pour gérer une situation très spécifique: Beaucoup et beaucoup de très petites allocations, allant de 12 à 64 octets chacune. Quelque chose de plus gros, je vais passer au gestionnaire de tas régulier, donc seulement des blocs minuscules doivent être pris en compte. Seul l'alignement à 4 octets est nécessaire.

Mes principales préoccupations sont

1. Frais généraux. Le tas libc normal arrondit généralement une allocation à un multiple de 16 octets, puis ajoute un autre en-tête de 16 octets - cela signifie plus de 50% de surcharge sur une allocation de 20 octets, ce qui est nul.
2. Performance

Un aspect utile est que Lua (qui est l'utilisateur de ce tas) vous indiquera la taille du bloc, il est libérant quand il appelle libre() - cela peut permettre à certains OPTIMISATIONS.

Je vais poster mon approche actuelle, ce qui fonctionne bien, mais je voudrais améliorer si possible. Des idées?

Answer 1

Il est possible de créer un gestionnaire de segments de mémoire très efficace pour les objets de même taille. Vous pouvez créer un de ces segments pour chaque taille d'objet dont vous avez besoin ou, si cela ne vous dérange pas, utilisez un espace pour les objets de 16 octets, un pour 32 et un pour 64. Le surcoût maximum serait 31 octets pour une allocation de 33 octets (qui irait sur le tas de 64 blocs).

Answer 2

La réponse peut dépendre des modèles de durée de vie de ces objets. Si les objets sont tous instanciés au fur et à mesure, puis supprimés d'un seul coup, il peut être judicieux de créer un gestionnaire de tas très simple qui alloue de la mémoire en incrémentant simplement un pointeur. Ensuite, lorsque vous avez terminé, soufflez tout le tas.

Raymond Chen a créé un interesting post qui pourrait vous inspirer. :)

Answer 3

Si un groupe de mémoire est allouée, utilisé et libéré avant de passer à la prochaine ronde de l'allocation, je suggère d'utiliser la plus simple possible allocateur:

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 4

développiez ce que Greg Hewgill dit, une façon de faire un segment de taille fixe ultra-efficace est:

1. Diviser un gros tampon en nœuds. La taille du noeud doit être au moins sizeof (void *).
2. Rassemblez-les en une liste unique (la "liste libre"), en utilisant la première taille (octets *) de chaque nœud libre comme pointeur de liaison. Les noeuds alloués n'auront pas besoin d'un pointeur de lien, donc le préfixe par noeud est 0.
3. Allouer en supprimant la tête de la liste et en la renvoyant (2 charges, 1 magasin).
4. Gratuit en insérant en tête de liste (1 chargement, 2 magasins).

De toute évidence, l'étape 3 doit également vérifier si la liste est vide, et si c'est le cas, faites un tas de travail pour obtenir un nouveau gros buffer (ou échouer). Il est encore plus efficace, comme le disent Greg D et hazzen, d'allouer ou de décrémenter un pointeur (1 load, 1 store) et de ne pas offrir un moyen de libérer un seul nœud.

Editer: Dans les deux cas, free peut gérer la complication "quelque chose de plus gros que je passe sur le gestionnaire de tas ordinaire" par le fait que vous obtenez la taille de l'appel à libérer. Sinon, vous regarderez soit un drapeau (overhead probablement 4 octets par nœud), soit une recherche dans un type d'enregistrement du ou des tampons que vous avez utilisés.

Answer 5

J'aime onebyones réponse.

Vous pourriez également envisager le buddy system pour vos ensembles de tas de taille fixe.

Answer 6

J'utilise principalement un gestionnaire de mémoire de petit bloc (SBMM) O (1). Fondamentalement, cela fonctionne de la façon suivante:

1) Il alloue des SuperBlocks plus gros à partir du système d'exploitation et suit les adresses de début et de fin comme une plage. La taille du SuperBlock est réglable mais 1MB fait une assez bonne taille.

2) Les SuperBlocks sont cassés en blocs (également réglable en taille ... 4K-64K est bon en fonction de votre application). Chacun de ces blocs gère les allocations d'une taille spécifique et stocke tous les éléments dans le bloc en tant que liste liée individuellement. Lorsque vous allouez un SuperBlock, vous créez une liste liée de Blocs libres.

3) Allouer un article signifie A) Vérifier s'il y a un bloc avec des objets libres traitant cette taille - et sinon, allouer un nouveau bloc à partir des SuperBlocks. B) Retrait de l'élément de la liste libre du bloc. 4) Libérer un objet par adresse signifie A) Trouver l'adresse contenant le SuperBlock (*) B) Trouver le bloc dans SuperBlock (soustraire l'adresse de démarrage SuperBlock et diviser par la taille du bloc) C) Repasser l'item dans la liste des éléments libres du bloc.

Comme je l'ai dit, ce SBMM est très rapide car il s'exécute avec des performances O (1) (*). Dans la version que j'ai implémentée, j'utilise un AtomicSList (similaire à SLIST sous Windows) pour que ce ne soit pas seulement la performance O (1) mais aussi ThreadSafe et LockFree dans l'implémentation. Vous pouvez réellement implémenter l'algorithme en utilisant Win32 SLIST si vous le souhaitez. Il est intéressant de noter que l'algorithme d'allocation de blocs à partir des SuperBlocks ou des Eléments provenant des Blocs aboutit à un code presque identique (ce sont les deux allocations O (1) d'une liste libre). (*) Les SuperBlocks sont disposés dans un plan de rang avec une performance moyenne de O (1) (mais un potentiel O (Lg N) pour le pire où N est le nombre de SuperBlocks). La largeur du rangmap dépend de la quantité de mémoire dont vous aurez besoin pour obtenir la performance O (1). Si vous dépassez, vous perdrez un peu de mémoire tout en obtenant des performances O (1). Si vous sous-estimez, vous approchez la performance O (Lg N) mais le N est pour le compte SuperBlock - pas le nombre d'éléments. Comme le nombre de SuperBlock est très faible par rapport au nombre d'objets (d'environ 20 ordres de grandeur binaires dans mon code), il n'est pas aussi important que le reste de l'allocateur.