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

まず、我々はブーストプールライブラリの基本的な考え方を知っている必要があります：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<>::free()の代わりにpool<>::ordered_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個のチャンクの連続したシーケンスを検索する場合、順序付きフリーリストを使用すると簡単になります。あなたはまた、例えば、手動でオブジェクトを破壊することができますが、それはobject_poolオブジェクトの破壊に非割り当て解除オブジェクトの自動破壊を提供し、boost::object_pool：：第二に、のはboost::poolの派生クラスを見てみましょう

class X { … }; 

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

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

上記のコードはOKで、メモリリークもダブルの削除もありません！ 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); 
} 

をそうqueston 2のために：あなたは、ほとんどの状況でboost::pool<>::ordered_mallocを使用する必要はありません。