stratégie pour allouer/libérer beaucoup de petits objets

Question

Je suis en train de jouer avec certains algorithmes de mise en cache, ce qui est un peu difficile. Fondamentalement, il doit allouer beaucoup de petits objets (tableaux doubles, 1 à 256 éléments), avec des objets accessibles via la valeur mappée, map[key] = array. Le temps de mise en réseau initialisé peut être assez important, généralement supérieur à 10 000 cycles cpu.

Par lots, je veux dire environ gigaoctet au total. les objets peuvent devoir être sautés/poussés au besoin, généralement dans des endroits aléatoires, un objet à la fois. La durée de vie d'un objet est généralement longue, minutes ou plus, cependant, l'objet peut être soumis à allocation/désallocation plusieurs fois pendant la durée du programme.

Quelle serait une bonne stratégie pour éviter la fragmentation de la mémoire, tout en conservant une allocation raisonnable de la vitesse de désallocation? J'utilise C++, donc je peux utiliser new et malloc. Merci.

Je sais qu'il ya des questions similaires sur le site Web, Efficiently allocating many short-lived small objects, sont quelque peu différentes, la sécurité des threads n'est pas un problème immédiat pour moi.

ma plate-forme de développement est Intel Xeon, système d'exploitation Linux. Idéalement, je voudrais aussi travailler sur PPC Linux, mais ce n'est pas le plus important pour moi.

Answer 1

Créer un allocateur rainuré:

Allocataire est créé avec de nombreuses pages de mémoire, chacun de taille égale (512k, 256k, la taille devrait être accordé pour votre usage).

La première fois qu'un objet demande à cet allocateur de la mémoire, il alloue une page. L'allocation d'une page consiste à la supprimer de la liste libre (aucune recherche, toutes les pages ont la même taille) et à définir la taille des objets qui seront alloués sur cette page. Typiquement, cette taille est calculée en prenant la taille demandée et en l'arrondissant à la puissance la plus proche de 2. Les allocations suivantes de la même taille nécessitent juste un peu de calcul de pointeur et incrémentent le nombre d'objets sur la page.

La fragmentation est évitée car les emplacements ont tous la même taille et peuvent être rechargés lors d'affectations ultérieures. L'efficacité est maintenue (dans certains cas améliorée) car il n'y a pas de memheader par allocation (ce qui fait une grande différence quand les allocations sont faibles, une fois les allocations devenues importantes, cet allocator commence à gaspiller près de 50% de mémoire disponible).

Les allocations et les désallocations peuvent être effectuées à temps constant (aucune recherche de la liste libre pour les emplacements corrects). La seule chose délicate à propos d'une désallocation est que vous ne voulez généralement pas de memheader précédant l'allocation, donc vous devez trouver la page et l'index dans la page vous-même ... C'est samedi et je n'ai pas eu mon café donc je Je n'ai pas de bon conseil pour le faire, mais il est assez facile de le savoir à partir de l'adresse désaffectée.

Éditer: Cette réponse est un peu long. Comme d'habitude boost a votre dos.

Answer 2

Si vous connaissez la taille maximale de vos baies, vous pouvez utiliser un répartiteur personnalisé. Vous devrez écrire la classe d'allocateur vous-même. Ce qu'il devrait faire est d'allouer un gros morceau de mémoire à la fois et de le convertir en liste chaînée. Chaque fois qu'une instance d'objet doit être créée, vous supprimez la queue de la liste. Chaque fois que l'objet doit être libéré, vous ajoutez une entrée à la liste.

EDIT: Voici un exemple de Bjarne Stroustrup de Le langage C++ de programmation, 3e édition:

class Pool 
{ 
private: 
    struct Link 
    { Link * next; }; 

    struct Chunk 
    { 
    enum {size = 8*1024-16}; 

    Chunk * next; 
    char mem[size]; 
    }; 

private: 
    Chunk * chunks; 
    const unsigned int esize; 
    Link * head; 

private: 
    Pool (const Pool &) { }  // copy protection 
    void operator = (Pool &) { } // copy protection 

public: 
    // sz is the size of elements 
    Pool(unsigned int sz) 
    : esize(sz < sizeof(Link*) ? sizeof(Link*) : sz), 
     head(0), chunks(0) 
    { } 

    ~Pool() 
    { 
    Chunk * n = chunks; 

    while(n) 
    { 
     Chunk * p = n; 
     n = n->next; 
     delete p; 
    } 
    } 


public: 

    // allocate one element 
    void * alloc() 
    { 
    if(head == 0) 
     grow(); 

    Link * p = head; 
    head = p->next; 

    return p; 
    } 

    // put an element back into the pool 
    void free(void * b) 
    { 
    Link * p = static_cast<Link*>(b); 
    p->next = head; //put b back as first element 
    head = p; 
    } 

private: 
    // make pool larger 
    void grow() 
    { 
    Chunk* n = new Chunk; 
    n->next = chunks; 
    chunks = n; 

    const int nelem = Chunk::size/esize; 
    char * start = n->mem; 
    char * last = &start [ (nelem - 1) * esize ]; 

    for(char * p = start; p < last; p += esize) // assume sizeof(Link) <= esize 
     reinterpret_cast<Link>(p)->next = reinterpret_cast<Link *>(p + esize); 

    reinterpret_cast<Link *>(last)->next = 0; 
    head = reinterpret_cast<Link *>(start); 
    } 
}; 

Answer 3

Si vous pouvez prédire la taille de l'objet alloué à l'avance vous sera probablement préférable d'aller avec un morceau de mémoire alloué linéairement et votre propre allocateur personnalisé (comme suggéré par @Kerido). J'ajouterai que la méthode la plus efficace consisterait à zéro et échanger les positions dans l'allocation, sans se soucier de repartitionner et compacter le tableau (laisser l'espace mort entre les allocations) pour ne pas avoir à gérer les index et les index. entretien. Si vous pouvez partitionner vos objets à l'avance (vous savez que vous avez des éléments de taille non fixe, mais le groupe facilement), divisez-les en compartiments et préallouez des blocs de mémoire dans chaque compartiment et échangez les éléments en seau. Si vos objets peuvent changer de taille au cours de leur vie, ce qui peut être difficile à gérer, réfléchissez bien à cette approche.