boost - boost::pool<>::malloc 和 boost::pool<>::ordered_malloc 有什么区别，什么时候应该使用 boost::pool<>::ordered_malloc？

Question

我正在使用 boost.pool，但我不知道何时使用 boost::pool<>::malloc和 boost::pool<>::ordered_malloc ?

所以，

boost::pool<>::malloc 有什么区别？和 boost::pool<>::ordered_malloc ?

我什么时候应该使用boost::pool<>::ordered_malloc ?

Answer 1

首先，我们应该知道 Boost Pool 库背后的基本思想:simple_segregated_storage ，它类似于单链表，负责将内存块划分为固定大小的 block :


内存池保存一个空闲的内存块列表。所以我们提到了 block 和 block :内存池使用new或 malloc分配一个内存块并将其划分为许多具有相同大小的内存块。
假设地址是8对齐的，4个字节用于存储下一个 block 的地址，那么一个内存块(8字节* 32个 block )如下(内存地址只是为了说明问题，不是真实的):


现在，假设用户分配了两次 8 字节内存，因此使用了 block :[0xDD00,0xDD08)、[0xDD08,0xDD10)。一段时间后，用户在 [0xDD00,0xDD08) 处释放内存，因此该 block 将回到空闲列表。现在 block 是这样的:


之后用户在 [0xDD08,0xDD10) 处释放内存，将此 block 放回列表中的最简单方法是更新 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
}

之后，列表将如下所示:

现在我们注意到，在这些操作之后， block 列表并没有按它们的地址排序!
如果我们想在取消分配时保留顺序，请调用 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();
}

正如我们所看到的，它们仅在内存块列表中没有空闲 block 时有所不同。在这种情况下，它分配一个新的内存块，将其空闲列表合并到池的空闲列表中，这两种方法的区别在于 boost::pool<>::ordered_malloc在合并空闲列表时保留顺序。
以上是针对问题1。
那么，为什么顺序很重要？!似乎内存池与无序 block 完美配合!
首先，如果我们想找到 n 个 block 的连续序列，有序的空闲列表会更容易。二、我们看一下 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的析构函数的实现(我的机器上有 boost 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
}

它遍历内存块列表中的所有 block ( list， boost::pool<> 的数据成员，保存从系统分配的所有内存块的位置和大小)，以查找其中的任何 block 是否也显示在free list，如果没有，调用对象的析构函数，然后释放内存。所以它有点像得到两个集合的交集，就像 std::set_intersection()做!如果列表是排序的，这样做会快得多。其实在 boost::object_pool<> ，需要顺序，公共(public)成员函数: 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在大多数情况下。