L'efficacité de Boost Pool sans O (n) ou O (1)

Question

Récemment, j'ai découvert la bibliothèque Boos Pool et j'ai commencé à l'adapter à mon code. Une chose que la bibliothèque mentionne qu'il manquait était une classe de base qui remplacerait les opérateurs new/delete pour n'importe quelle classe et utiliserait le pool pour la gestion de la mémoire. J'ai écrit ma propre implémentation et avec une certaine programmation de méta-templates, elle est apparue vraiment décente (supporte n'importe quelle classe avec une taille entre 1 et 1024 octets en dérivant simplement de la classe de base)

J'ai mentionné ces choses parce que jusqu'ici c'était vraiment cool et excitant et puis j'ai trouvé ça post from Boost mailing list. Il semble que certaines personnes martèlent vraiment la bibliothèque Pool et soulignent en particulier l'inefficacité de la méthode free() qui s'exécute en O (n) time. Je suis entré dans le code et trouvé que cela la mise en œuvre de cette méthode:

void free(void * const chunk) 
{ 
    nextof(chunk) = first; 
    first = chunk; 
} 

Pour moi, cela ressemble à O (1) et je ne vois vraiment pas l'inefficacité dont ils parlent. Une chose que j'ai remarquée est que si vous utilisez plusieurs instances de singleton_pool (c'est-à-dire différentes balises et/ou tailles d'allocation), elles partagent toutes le même mutex (section critique pour être plus précis) et cela pourrait être optimisé. Mais si vous utilisiez des opérations de tas régulières, ils utiliseraient la même forme de synchronisation.

Alors quelqu'un d'autre considère-t-il que la bibliothèque Pool est inefficace et obsolète?

Answer 1

Cette certitude me semble constante. Peut-être l'auteur du message faisait référence à ordered_free, qui a cette mise en œuvre:

void ordered_free(void * const chunk) 
{ 
    // This (slower) implementation of 'free' places the memory 
    // back in the list in its proper order. 

    // Find where "chunk" goes in the free list 
    void * const loc = find_prev(chunk); 

    // Place either at beginning or in middle/end 
    if (loc == 0) 
    (free)(chunk); 
    else 
    { 
    nextof(chunk) = nextof(loc); 
    nextof(loc) = chunk; 
    } 
} 

Où find_prev est la suivante

template <typename SizeType> 
void * simple_segregated_storage<SizeType>::find_prev(void * const ptr) 
{ 
    // Handle border case 
    if (first == 0 || std::greater<void *>()(first, ptr)) 
    return 0; 

    void * iter = first; 
    while (true) 
    { 
    // if we're about to hit the end or 
    // if we've found where "ptr" goes 
    if (nextof(iter) == 0 || std::greater<void *>()(nextof(iter), ptr)) 
     return iter; 

    iter = nextof(iter); 
    } 
}