boost - 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

まず、Boost Pool ライブラリの背後にある基本的な考え方を知っておく必要があります。simple_segregated_storageこれは単方向リンク リストに似ており、メモリ ブロックを固定サイズのチャンクに分割する役割を果たします。

メモリ プールは、メモリ チャンクの空きリストを保持します。ブロックとチャンクについて説明しました。メモリ プールはnew、 またはを使用mallocしてメモリ ブロックを割り当て、それを同じサイズの多くのメモリ チャンクに分割します。
次のチャンクのアドレスを格納するためにアドレスが 8, 4 バイトでアラインされていると仮定すると、メモリ ブロック (8 バイト * 32 チャンク) は次のようになります (メモリ アドレスは質問を説明するためのものであり、実際のものではありません)。

ここで、ユーザーが 8 バイトのメモリを 2 回割り当てると仮定すると、[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();
}

ご覧のとおり、メモリ ブロックのリストに空きチャンクがない場合にのみ異なります。このシナリオでは、新しいメモリ ブロックを割り当て、そのフリー リストをプールのフリー リストにマージします。これら 2 つの方法の違いは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()と同じように、2 つのセットの交差を取得するようなものです! リストがソートされている場合、それを行う方がはるかに高速です。実際には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);
}

boost::pool<>::ordered_mallocしたがって、質問 2 については、ほとんどの状況で使用する必要はありません。