В чем разница между boost :: pool <> :: malloc и boost :: pool <> :: ordered_malloc, и когда следует использовать boost :: pool <> :: ordered_malloc?

Question

Я использую boost.pool, но не знаю, когда использовать boost::pool<>::malloc и boost::pool<>::ordered_malloc?

так,

1. что разница boost::pool<>::malloc и boost::pool<>::ordered_malloc?

2. Когда я должен использовать boost::pool<>::ordered_malloc?

Answer 1

Во-первых, мы должны знать основную идею библиотеки подталкивания Pool: simple_segregated_storage, он похож на односвязный список, и отвечает за разбиение блока памяти в фиксированного размера кусков:

Пул памяти содержит свободный список фрагментов памяти. Поэтому мы упоминали блоки и фрагменты: пул памяти использует new или malloc для выделения блока памяти и делит его на многие блоки памяти, имеющие одинаковый размер.
Предположим, что адрес выровнен на 8,4 байта для хранения адреса следующего фрагмента, поэтому блок памяти (8 байтов * 32 куска) выглядит так: (адрес памяти предназначен только для иллюстрации вопроса, а не для реального) :

Теперь предположим, что пользователь выделяет 8 байт памяти в два раза, так что куски: [0xDD00,0xDD08), [0xDD08,0xDD10) используются. Через некоторое время пользователь освобождает память на [0xDD00,0xDD08), поэтому этот кусок вернется в свободный список. Теперь блок выглядит так:

Затем пользователь освобождает память на [0xDD08,0xDD10), самый простой способ поместить этот кусок обратно в список, чтобы обновить first, чтобы указать на него, постоянная времени сложность. simple_segregated_storage<T>::free() делает это точно:

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 
} 

После этого, список будет выглядеть так:

Теперь мы заметили, список кусков не упорядочены по их адресу после этих операций! Если мы хотим сохранить заказ при де-распределении, вызовите pool<>::ordered_free() вместо pool<>::free(), чтобы вернуть память в список в правильном порядке. Теперь мы знаем, что это порядок в пуле памяти, давайте углубимся в исходный код boost::pool<>::malloc и 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(); 
} 

Как мы можем видеть, что они только отличаются, когда нет свободного фрагмента в списке памяти блоки. В этом случае он выделяет новый блок памяти, объединяет его свободный список с свободным списком пула, разница между этими двумя методами заключается в том, что boost::pool<>::ordered_malloc сохраняет заказ при объединении свободных списков.
Выше приведено к вопросу 1.
Итак, почему дело касается вопроса ?! Кажется, пул памяти отлично работает с неупорядоченными кусками!
Во-первых, если мы хотим найти непрерывную последовательность n кусков, упорядоченный бесплатный список упростит его.Во-вторых, давайте посмотрим на производный класс boost::pool: boost::object_pool, он обеспечивает автоматическое уничтожение без освобождаться объектов по уничтожению object_pool объекта в то время как вы можете также уничтожить объект вручную, например:

class X { … }; 

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

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

в код выше в порядке, утечка памяти или двойное удаление! Как делает boost::object_pool эту магию? Найдем реализацию деструктора boost::object_pool (у меня есть импульс 1,48 на моей машине):

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 
} 

она проходит через все куски в списке блоков памяти (list, члене данных boost::pool<>, имеет место и размеры всех блоков памяти, выделенных из системы), чтобы определить, показывает ли какой-либо фрагмент в нем в свободном списке, если нет, вызывает деструктор объекта, а затем освобождает память. Таким образом, это похоже на пересечение двух наборов, так же, как std::set_intersection()! Если список отсортирован, было бы намного быстрее сделать это. На самом деле в boost::object_pool<>, порядок требуется, в функции-члены: boost::object_pool<>::malloc() и boost::object_pool<>::free() просто называют boost::pool<>::ordered_malloc() и 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); 
} 

Так что для Queston 2: Вам не нужно использовать boost::pool<>::ordered_malloc в большинстве ситуаций.