Gestionnaire de tas efficace pour les gros désabonnements, de minuscules allocations?

Question

Je cherche des idées pour qu'un gestionnaire de tas puisse gérer une situation très spécifique: beaucoup d'allocations très petites, allant de 12 à 64 octets chacune. Tout ce qui est plus gros, je le laisserai au gestionnaire de tas habituel, de sorte que seuls les petits blocs doivent être pris en charge. Seul un alignement de 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, ce qui représente une surcharge de plus de 50% pour une allocation de 20 octets, ce qui est nul.
2. Performances

Un aspect utile est que Lua (qui est l'utilisateur de ce segment de mémoire) vous indiquera la taille du bloc libéré lorsqu'il appelle free () - cela peut permettre certaines optimisations.

Je publierai mon approche actuelle, qui fonctionne bien, mais j'aimerais l'améliorer si possible. Des idées?

Answer 1

Il est possible de créer un gestionnaire de tas très efficace pour les objets de même taille. Vous pouvez créer l’un de ces tas pour chaque taille d’objet dont vous avez besoin ou, si vous le souhaitez, utiliser un peu d’espace, créez-en un pour les objets de 16 octets, un pour 32 et un pour 64. La surcharge maximale serait de: 31 octets pour une allocation de 33 octets (qui irait sur le tas de 64 blocs).

Answer 2

Pour approfondir les propos de Greg Hewgill, voici un moyen de créer un segment de taille fixe ultra efficace:

1. Divisez un grand tampon en nœuds. La taille du nœud doit être au moins sizeof (void *).
2. Chaînez-les ensemble dans une liste à lien unique (la "liste libre"), en utilisant les premiers octets sizeof (void *) de chaque nœud libre en tant que pointeur de lien. Les nœuds alloués n'auront pas besoin de pointeur de lien. Le surcoût par nœud est donc égal à 0.
3. Allouez en supprimant la tête de la liste et en la retournant (2 charges, 1 magasin).
4. Libérez en insérant en tête de liste (1 chargement, 2 magasins).

Il est évident que l’étape 3 doit également vérifier si la liste est vide et, le cas échéant, faire beaucoup de travail pour obtenir un nouveau grand tampon (ou échouer).

Encore plus efficace, comme le disent Greg D et hazzen, allouer en incrémentant ou décrémentant un pointeur (1 charge, 1 magasin) et en ne proposant aucun moyen de libérer un seul nœud.

Éditer: dans les deux cas, free peut gérer la complication "je ne transmets rien de plus grand au gestionnaire de tas normal". par le fait utile que vous obtenez la taille dans l'appel à libérer. Sinon, vous utiliseriez un indicateur (surcharge probablement de 4 octets par nœud) ou une recherche dans une sorte d’enregistrement du ou des tampons que vous avez utilisés.

Answer 3

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 de votre progression, puis supprimés en 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é, emportez tout le tas.

Raymond Chen a publié un message intéressant qui peut aider à vous inspirer. :)

Answer 4

J'aime onebyones répondre.

Vous pouvez également envisager le système de parrainage pour vos ensembles de tas de taille fixe.

Answer 5

Si un groupe de mémoire est alloué, utilisé et libéré avant de passer à la prochaine série d'allocation, nous suggérons d'utiliser l'allocateur le plus simple possible:

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

J'utilise un gestionnaire de mémoire pour petits blocs (SBMM) principalement O (1). Fondamentalement, cela fonctionne de la manière suivante:

1) Il alloue des SuperBlocks plus grands à partir du système d’exploitation et suit les adresses de début et de fin sous forme de plage. La taille du SuperBlock est ajustable mais 1 Mo fait une assez bonne taille.

2) Les SuperBlocks sont divisés en blocs (la taille du ... 4K-64K est également bonne en fonction de votre application). Chacun de ces blocs gère les allocations d'une taille spécifique et stocke tous les éléments du bloc sous forme de liste liée unique. Lorsque vous affectez un superbloc, vous créez une liste chaînée de blocs libres.

3) Allouer un article signifie A) Vérifier s’il existe un bloc avec des articles gratuits gérant cette taille - et si ce n’est pas le cas, allouer un nouveau bloc à partir du SuperBlocks. B) Suppression de l’élément de la liste libre du bloc.

4) Libérer un élément par adresse signifie A) Trouver une adresse contenant SuperBlock (*) B) Rechercher un bloc dans SuperBlock (soustrayez l’adresse de début du SuperBlock et divisez-la par la taille du bloc) C) Insérez cet élément dans la liste des éléments libres du bloc.

Comme je l’ai dit plus tôt, ce SBMM est très rapide car il tourne avec O (1) performance (*). Dans la version que j'ai implémentée, j'utilise un AtomicSList (similaire à SLIST dans Windows) pour qu'il ne s'agisse pas uniquement des performances O (1), mais également de ThreadSafe et de LockFree dans l'implémentation. Vous pouvez réellement implémenter l’algorithme en utilisant Win32 SLIST si vous le souhaitez.

Fait intéressant, l’algorithme d’attribution de blocs à partir de superblocs ou d’articles à partir de blocs produit un code presque identique (les deux affectations O (1) de la liste libre).

(*) Les SuperBlocks sont disposés dans un plan de terrain avec une performance moyenne de O (1) (mais un potentiel (O (Lg N)) pour le cas le plus défavorable où N est le nombre de SuperBlocks). La largeur du plan de rang dépend de la connaissance approximative de la quantité de mémoire dont vous aurez besoin pour obtenir les performances O (1). Si vous dépassez les objectifs, vous perdrez un peu de mémoire, mais vous obtiendrez tout de même des performances O (1). Si vous faites un tir inférieur, vous approcherez de la performance O (Lg N) mais le N correspond au nombre de SuperBlock - pas au nombre d'éléments. Le nombre de SuperBlock étant très faible par rapport au nombre d'éléments (d'environ 20 ordres de grandeur binaires dans mon code), il n'est pas aussi critique que le reste de l'allocateur.