Was ist der Unterschied zwischen boost :: pool <> :: malloc und boost :: pool <> :: ordered_malloc, und wann sollte ich boost :: pool <> :: ordered_malloc verwenden?

Question

Ich benutze boost.pool, aber ich weiß nicht wann boost::pool<>::malloc und boost::pool<>::ordered_malloc zu verwenden?

so,

1. was ist der Unterschied von boost::pool<>::malloc und boost::pool<>::ordered_malloc?

2. Wann sollte ich boost::pool<>::ordered_malloc verwenden?

Answer 1

Erstens haben wir die Grundidee hinter der Boost-Pool Bibliothek wissen sollten: simple_segregated_storage, ist es ähnlich wie eine einfach verkettete Liste, und verantwortlich für die Partitionierung eines Speicherblocks in fester Größe Brocken:

Ein Speicherpool enthält eine freie Liste von Speicherabschnitten. Also erwähnten wir Blöcke und Blöcke: Der Speicherpool verwendet new oder malloc, um einen Speicherblock zuzuweisen und teilt ihn in viele Speicherblöcke, die dieselbe Größe haben.
Angenommen, die Adresse ist um 8, 4 Bytes zum Speichern der Adresse des nächsten Chunk ausgerichtet, so ein Speicherblock (8 Bytes * 32 Chunks) ist wie folgt (die Speicheradresse dient nur zur Veranschaulichung der Frage, nicht eine echte) :

Angenommen nun, der Benutzer zweimal 8 Byte Speicher reserviert, so dass die Stücke: [0xDD00,0xDD08), [0xDD08,0xDD10) verwendet werden. Nach einer Weile gibt der Benutzer den Speicher bei [0xDD00,0xDD08] frei, so dass dieser Chunk zur freien Liste zurückkehrt. Nun ist die Block ist wie folgt:

Danach wird der Benutzer den Speicher an [0xDD08,0xDD10), der einfachste Weg, diese Klumpen zurück in der Liste zu platzieren ist, um die first zu aktualisieren, um es zu zeigen, konstante Zeit Komplexität. die simple_segregated_storage<T>::free() dies genau tut:

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 
} 

Danach würde die Liste wie folgt sein:

Jetzt bemerkten wir die Liste der Stücke zeichnen sich durch ihre Adresse nach diesen Operationen nicht bestellt! Wenn die Reihenfolge bei der Aufhebung der Zuordnung beibehalten werden soll, rufen Sie pool<>::ordered_free() anstelle von pool<>::free() auf, um den Speicher wieder in der richtigen Reihenfolge in die Liste aufzunehmen. Jetzt haben wir gewusst, was ist die Reihenfolge, in der Speicherpool, lassen Sie uns graben in den Quellcode von boost::pool<>::malloc und 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(); 
} 

Wie wir sehen können, sie unterscheiden sich nur, wenn es keinen freien Brocken in der Liste der Speicher Blöcke. In diesem Szenario wird ein neuer Speicherblock zugewiesen und die freie Liste mit der freien Liste des Pools zusammengeführt. Der Unterschied zwischen diesen beiden Methoden besteht darin, dass boost::pool<>::ordered_malloc die Reihenfolge beim Zusammenführen der freien Listen erhält.
Oben ist für Frage 1.
Also, warum ist die Reihenfolge wichtig ?! Es scheint, dass der Speicherpool perfekt mit den ungeordneten Blöcken zusammenarbeitet!
Erstens, wenn wir eine zusammenhängende Folge von n Chunks finden möchten, würde die geordnete freie Liste es einfacher machen.Zweitens Schauen wir uns die abgeleitete Klasse von boost::pool einen Blick: boost::object_pool bietet sie automatische Vernichtung von nicht-ausgeplanten Objekte auf Zerstörung des object_pool Objekt, während Sie auch manuell das Objekt zerstören, zum Beispiel:

class X { … }; 

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

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

die Code oben ist in Ordnung, kein Speicherverlust oder doppelte Löschung! Wie macht boost::object_pool diese Magie? Lassen Sie uns die Implementierung von destructor von boost::object_pool finden (ich habe Boost 1.48 auf meinem Rechner):

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 
} 

es alle Stücke in der Liste der Speicherblöcke (list, das Datenelement von boost::pool<> hält geht durch die Orte und Größen aller Speicherblöcke, die vom System zugewiesen wurden, um herauszufinden, ob ein Chunk darin in der freien Liste angezeigt wird, wenn nicht, ruft den Destruktor des Objekts auf und gibt dann den Speicher frei. Es ist also eine Kreuzung von zwei Sets, genau wie std::set_intersection()! Wenn die Liste sortiert ist, wäre das viel schneller. Eigentlich in der boost::object_pool<> ist die Reihenfolge, die öffentlichen Member-Funktionen erforderlich: boost::object_pool<>::malloc() und boost::object_pool<>::free() rufen Sie einfach die boost::pool<>::ordered_malloc() und boost::pool<>::ordered_free() jeweils:

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); 
} 

Also für die queston 2: Sie brauchen nicht boost::pool<>::ordered_malloc zu verwenden in den meisten Situationen.