Jaka jest różnica między boost :: pool <> :: malloc i boost :: pool <> :: ordered_malloc, a kiedy powinienem użyć boost :: pool <> :: ordered_malloc?

Question

Używam boost.pool, ale nie wiem, kiedy używać boost::pool<>::malloc i boost::pool<>::ordered_malloc?

tak,

1. jaka jest różnica boost::pool<>::malloc i boost::pool<>::ordered_malloc?

2. Kiedy należy używać boost::pool<>::ordered_malloc?

Answer 1

Po pierwsze, powinniśmy wiedzieć Podstawową ideą biblioteki doładowania Basen: simple_segregated_storage, że jest podobny do pojedynczo połączonej listy, a odpowiedzialny za podział bloku pamięci do stałej wielkości kawałki:

Pula pamięci utrzymuje wolną listę porcji pamięci. Wspomnieliśmy więc o blokach i porcjach: pula pamięci używa new lub malloc do przydzielenia bloku pamięci i podzielenia go na wiele porcji pamięci o tym samym rozmiarze.
Założono, że adres jest wyrównany o 8, 4 bajty dla przechowywania adresu następnej porcji, więc blok pamięci (8 bajtów * 32 porcje) jest jak poniżej (adres pamięci służy jedynie zilustrowaniu pytania, a nie rzeczywistemu) :

teraz załóżmy, że użytkownik przydziela pamięć 8 bajtów dwa razy, więc kawałki: [0xDD00,0xDD08) [0xDD08,0xDD10) są stosowane. Po chwili użytkownik zwalnia pamięć w [0xDD00,0xDD08], więc ten fragment powróci do wolnej listy. Teraz blok jest tak:

Następnie użytkownik zwalnia pamięć w [0xDD08,0xDD10), najprostszym sposobem, aby umieścić ten kawałek z powrotem na liście jest, aby zaktualizować first się wskazywać na to, stała czasowa złożoność. simple_segregated_storage<T>::free() robi to dokładnie:

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 
} 

Po tym, lista byłaby tak:

Teraz zauważyliśmy listę kawałki nie są sortowane według adresu po tych operacjach! Jeśli chcemy zachować zamówienie przy jego rozdzielaniu, zadzwoń pod numer pool<>::ordered_free() zamiast pool<>::free(), aby umieścić pamięć z powrotem na liście w odpowiedniej kolejności. Teraz już wiadomo, jaka jest kolejność w puli pamięci, niech kopać w kodzie źródłowym boost::pool<>::malloc i 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(); 
} 

Jak widzimy, różnią się one tylko wtedy, gdy nie ma wolnego kawałek w liście pamięci Bloki. W tym scenariuszu alokuje nowy blok pamięci, scala swoją wolną listę na wolną listę puli, różnica między tymi dwiema metodami polega na tym, że boost::pool<>::ordered_malloc zachowuje porządek podczas łączenia wolnych list.
Powyższe jest dla pytania 1.
Dlaczego więc zamówienie ma znaczenie ?! Wygląda na to, że pula pamięci działa doskonale z nieuporządkowanymi fragmentami!
Po pierwsze, jeśli chcemy znaleźć ciągłą sekwencję n porcji, uporządkowana wolna lista ułatwi.Po drugie, Rzućmy okiem na klasy pochodnej z boost::pool: boost::object_pool, zapewnia automatyczne zniszczenie non-dealokowane przedmiotów na zniszczenie obiektu object_pool natomiast można również zniszczyć obiekt ręcznie, na przykład:

class X { … }; 

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

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

się powyższy kod jest OK, brak wycieku pamięci lub podwójne usuwanie! Jak robi to magia boost::object_pool? Przekonajmy wdrażania destruktora boost::object_pool (mam impuls 1,48 na moim komputerze):

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 
} 

przechodzi przez wszystkie kawałki na liście bloków pamięci (list, członek danych boost::pool<>, posiada lokalizacje i rozmiary wszystkich bloków pamięci przydzielonych z systemu), aby sprawdzić, czy jakaś część w nim występuje również na wolnej liście, jeśli nie, wywołuje destruktor obiektu, a następnie zwalnia pamięć. Tak więc jest to uzyskanie przecięcia dwóch zestawów, tak jak robi to std::set_intersection()! Jeśli lista zostanie posortowana, będzie to o wiele szybsze. Właściwie w boost::object_pool<>, kolejność jest wymagane, funkcje członków publicznych: boost::object_pool<>::malloc() i boost::object_pool<>::free() zadzwoń odpowiednio boost::pool<>::ordered_malloc() i boost::pool<>::ordered_free():

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

Tak dla Queston 2: Nie musisz używać boost::pool<>::ordered_malloc w większości sytuacji.