В чем разница между boost::pool<>::malloc и boost::pool<>::order_malloc, и когда мне следует использовать boost::pool<>::order_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

Во-первых, мы должны знать основную идею библиотеки Boost 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);
}

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