qual è la differenza tra boost :: pool <> :: malloc e boost :: pool <> :: ordered_malloc, e quando dovrei usare boost :: pool <> :: ordered_malloc?

Question

Sto usando boost.pool, ma non so quando usare boost::pool<>::malloc e boost::pool<>::ordered_malloc?

così,

1. qual è la differenza di boost::pool<>::malloc e boost::pool<>::ordered_malloc?

2. quando devo usare boost::pool<>::ordered_malloc?

Answer 1

In primo luogo, dovremmo sapere l'idea di base dietro la libreria Boost Pool: simple_segregated_storage, è simile ad una lista concatenata semplice, e responsabile per il partizionamento di un blocco di memoria in blocchi di dimensione fissa:

Un pool di memoria mantiene un elenco gratuito di blocchi di memoria. Quindi abbiamo menzionato blocchi e blocchi: il pool di memoria utilizza new o malloc per allocare un blocco di memoria e lo divide in molti blocchi di memoria che hanno le stesse dimensioni.
Si supponga che l'indirizzo sia allineato di 8, 4 byte per memorizzare l'indirizzo del blocco successivo, quindi un blocco di memoria (8 byte * 32 blocchi) è il seguente (l'indirizzo di memoria è solo per illustrare la domanda, non reale) :

Ora, supponiamo che l'utente assegna la memoria 8 byte due volte, quindi i pezzi: [0xDD00,0xDD08), [0xDD08,0xDD10) vengono utilizzati. Dopo un po ', l'utente rilascia la memoria a [0xDD00,0xDD08), quindi questo blocco tornerà alla lista libera. Ora il blocco è come questo:

Successivamente l'utente rilascia la memoria a [0xDD08,0xDD10), il modo più semplice per collocare questo pezzo indietro nella lista è quello di aggiornare il first per puntare ad esso, costante di tempo complessità. il simple_segregated_storage<T>::free() sta facendo esattamente questo:

void free BOOST_PREVENT_MACRO_SUBSTITUTION(void * const chunk) 
{ //! Free a chunk. 
    //! \pre chunk was previously returned from a malloc() referring to the same free list. 
    //! \post !empty() 
    BOOST_POOL_VALIDATE_INTERNALS 
    nextof(chunk) = first; 
    first = chunk; 
    BOOST_POOL_VALIDATE_INTERNALS 
} 

Dopo di che, la lista sarebbe come questo:

Ora abbiamo notato l'elenco dei pezzi non sono ordinate per il loro indirizzo dopo queste operazioni! Se si desidera conservare l'ordine durante la disallocazione, chiamare pool<>::ordered_free() anziché pool<>::free() per riportare la memoria nell'elenco nella sua corretta sequenza. Ora che abbiamo conosciuto che cosa è l'ordine nel pool di memoria, cerchiamo di scavare nel codice sorgente di boost::pool<>::malloc e boost::pool<>::ordered_malloc:

void * malloc BOOST_PREVENT_MACRO_SUBSTITUTION() 
{ 
    if (!store().empty()) 
    return (store().malloc)(); 
    return malloc_need_resize(); 
} 

void * ordered_malloc() 
{ 
    if (!store().empty()) 
    return (store().malloc)(); 
    return ordered_malloc_need_resize(); 
} 

Come possiamo vedere, si differenziano solo quando non v'è alcun pezzo gratuitamente nella lista della memoria blocchi. In questo scenario, alloca un nuovo blocco di memoria, unisce la sua lista libera all'elenco gratuito del pool, la differenza tra questi due metodi è che boost::pool<>::ordered_malloc conserva l'ordine durante l'unione degli elenchi gratuiti.
Sopra è per la domanda 1.
Quindi, perché l'ordine è importante ?! Sembra che il pool di memoria funzioni perfettamente con i blocchi non ordinati!
Per prima cosa, se vogliamo trovare una sequenza contigua di n blocchi, la lista libera ordinata renderebbe più semplice.In secondo luogo, diamo uno sguardo alla classe derivata di boost::pool: boost::object_pool, fornisce la distruzione automatica di oggetti non deallocata sulla distruzione dell'oggetto object_pool mentre si può anche distruggere l'oggetto manualmente, ad esempio:

class X { … }; 

    void func() 
    { 
     boost::object_pool<X> alloc; 

     X* obj1 = alloc.construct(); 
     X* obj2 = alloc.construct(); 
     alloc.destroy(obj2); 
    } 

la il codice sopra è OK, nessuna perdita di memoria o doppia eliminazione! In che modo boost::object_pool fa questa magia? Troviamo l'attuazione di distruttore di boost::object_pool (ho spinta 1.48 sulla mia macchina):

template <typename T, typename UserAllocator> 
object_pool<T, UserAllocator>::~object_pool() 
{ 
#ifndef BOOST_POOL_VALGRIND 
    // handle trivial case of invalid list. 
    if (!this->list.valid()) 
    return; 

    details::PODptr<size_type> iter = this->list; 
    details::PODptr<size_type> next = iter; 

    // Start 'freed_iter' at beginning of free list 
    void * freed_iter = this->first; 

    const size_type partition_size = this->alloc_size(); 

    do 
    { 
    // increment next 
    next = next.next(); 

    // delete all contained objects that aren't freed. 

    // Iterate 'i' through all chunks in the memory block. 
    for (char * i = iter.begin(); i != iter.end(); i += partition_size) 
    { 
     // If this chunk is free, 
     if (i == freed_iter) 
     { 
     // Increment freed_iter to point to next in free list. 
     freed_iter = nextof(freed_iter); 

     // Continue searching chunks in the memory block. 
     continue; 
     } 

     // This chunk is not free (allocated), so call its destructor, 
     static_cast<T *>(static_cast<void *>(i))->~T(); 
     // and continue searching chunks in the memory block. 
    } 

    // free storage. 
    (UserAllocator::free)(iter.begin()); 

    // increment iter. 
    iter = next; 
    } while (iter.valid()); 

    // Make the block list empty so that the inherited destructor doesn't try to 
    // free it again. 
    this->list.invalidate(); 
#else 
    // destruct all used elements: 
    for(std::set<void*>::iterator pos = this->used_list.begin(); pos != this->used_list.end(); ++pos) 
    { 
     static_cast<T*>(*pos)->~T(); 
    } 
    // base class will actually free the memory... 
#endif 
} 

passa attraverso tutti i pezzi nella lista dei blocchi di memoria (list, il membro di dati di boost::pool<>, tiene le posizioni e le dimensioni di tutti i blocchi di memoria allocati dal sistema) per scoprire se anche qualsiasi blocco in esso contenuto viene visualizzato nell'elenco libero, in caso contrario chiama il distruttore dell'oggetto, quindi libera la memoria. Quindi è come ottenere l'intersezione di due set, proprio come fa std::set_intersection()! Se la lista è ordinata, sarebbe molto più veloce farlo. In realtà nel boost::object_pool<>, l'ordine è necessario, le funzioni membro pubbliche: boost::object_pool<>::malloc() e boost::object_pool<>::free() basta chiamare il boost::pool<>::ordered_malloc() e boost::pool<>::ordered_free() rispettivamente:

element_type * malloc BOOST_PREVENT_MACRO_SUBSTITUTION() 
{ //! Allocates memory that can hold one object of type ElementType. 
    //! 
    //! If out of memory, returns 0. 
    //! 
    //! Amortized O(1). 
    return static_cast<element_type *>(store().ordered_malloc()); 
} 
void free BOOST_PREVENT_MACRO_SUBSTITUTION(element_type * const chunk) 
{ //! De-Allocates memory that holds a chunk of type ElementType. 
    //! 
    //! Note that p may not be 0.\n 
    //! 
    //! Note that the destructor for p is not called. O(N). 
    store().ordered_free(chunk); 
} 

Così per il queston 2: Non è necessario utilizzare boost::pool<>::ordered_malloc nella maggior parte delle situazioni.