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池庫背後的基本思想是：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。