boost :: pool<> :: malloc和boost :: pool<> :: ordered_malloc有什么区别，什么时候应该使用boost :: pool<> :: ordered_malloc? [英] what's the difference between boost::pool<>::malloc and boost::pool<>::ordered_malloc, and when should I use boost::pool<>::ordered_malloc?
问题描述
我正在使用boost.pool，但是我不知道何时使用boost::pool<>::malloc和boost::pool<>::ordered_malloc?
I'm using boost.pool, but I don't know when to use boost::pool<>::malloc and boost::pool<>::ordered_malloc?
所以
-
boost::pool<>::malloc和boost::pool<>::ordered_malloc有什么区别?
我什么时候应该使用boost::pool<>::ordered_malloc?
推荐答案
首先，我们应该了解Boost Pool库背后的基本思想:simple_segregated_storage，它类似于单链表，并负责对内存进行分区分成固定大小的块:
First, we should know the basic idea behind the Boost Pool library: simple_segregated_storage, it is similar to a singly linked list, and responsible for partitioning a memory block into fixed-size chunks:
一个内存池保留一个空闲的内存块列表.因此，我们提到了块和块:内存池使用new或malloc分配一个内存块，并将其划分为许多大小相同的内存块.
假设该地址按8对齐，则4个字节用于存储下一个块的地址，因此一个存储块(8字节* 32个块)如下所示(该存储地址仅用于说明问题，不是实际的): br>
A memory pool keeps a free list of memory chunks. So we mentioned blocks and chunks: the memory pool uses new or malloc to allocate a memory block and divides it into many memory chunks which have same size.
Assume the address is aligned by 8, 4 bytes for storing the address of next chunk, so a memory block(8 bytes * 32 chunks) is as below(the memory address is just for illustrating the question, not a real one):
现在，假设用户两次分配了8个字节的内存，因此使用了块[0xDD00,0xDD08)，[0xDD08,0xDD10).稍后，用户释放[0xDD00,0xDD08)的内存，因此该块将返回到空闲列表.现在，代码块是这样的:
Now, suppose the user allocates 8 bytes memory twice, so the chunks: [0xDD00,0xDD08), [0xDD08,0xDD10) are used. After a while, the user releases the memory at [0xDD00,0xDD08), so this chunk will go back to the free list. Now the block is like this:
之后，用户以[0xDD08,0xDD10)释放内存，将此块放回列表的最简单方法是更新first指向它，这是恒定的时间复杂性. simple_segregated_storage<T>::free()正是在这样做:
Afterwards the user releases the memory at [0xDD08,0xDD10), the simplest way to place this chunk back in the list is to update the first to point to it, constant time complexity. the simple_segregated_storage<T>::free() is doing this exactly:
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的源代码:
After that, the list would be like this:
Now we noticed the list of chunks are not ordered by their address after these operations!
If we want to preserve the order while de-allocating, call pool<>::ordered_free() instead of pool<>::free() to places the memory back in the list in its proper order. Now we've known what's the order in the memory pool, let's dig into the source code of boost::pool<>::malloc and 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对象时自动销毁未分配对象的功能，同时还可以手动销毁对象，例如:
As we can see, they differ only when there is no free chunk in the list of memory blocks. In this scenario, it allocates a new memory block, merges its free list to pool's free list, the difference between these two methods is that boost::pool<>::ordered_malloc preserves order while merging the free lists.
Above is for question 1.
So, why does the order matter?! It seems the memory pool works perfectly with the unordered chunks!
First, if we want to find a contiguous sequence of n chunks, the ordered free list would make it easier. Second, Let's have a look at the derived class of boost::pool: boost::object_pool, it provides automatic destruction of non-deallocated objects on destruction of the object_pool object while you can also destroy the object manually, for example:
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):
the code above is OK, no memory leak or double delete! How does boost::object_pool do this magic? Let's find the implementation of destructor of boost::object_pool(I have boost 1.48 on my machine):
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
}
它遍历内存块列表中的所有块(boost::pool<>的数据成员list，保存从系统分配的所有内存块的位置和大小)，以查找其中是否还有块在空闲列表中显示，如果没有，则调用对象的析构函数，然后释放内存.因此，这有点像是两个集合的交集，就像 std :: set_intersection()做！如果列表已排序，则这样做会更快.实际上，在boost::object_pool<>中需要顺序，公共成员函数:boost::object_pool<>::malloc()和boost::object_pool<>::free()分别分别调用boost::pool<>::ordered_malloc()和boost::pool<>::ordered_free():
it goes through all the chunks in the list of memory blocks(list, the data member of boost::pool<>, holds the locations and sizes of all memory blocks allocated from the system) to find whether any chunk in it also shows in the free list, if not, calls the destructor of the object, then free the memory. So it's kind of getting the intersection of two sets, just as std::set_intersection() does! If the list is sorted, it would be much faster to do that. Actually in the boost::object_pool<>, the order is required, the public member functions: boost::object_pool<>::malloc() and boost::object_pool<>::free() just call the boost::pool<>::ordered_malloc() and boost::pool<>::ordered_free() respectively:
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.
So for the queston 2: You needn't use boost::pool<>::ordered_malloc in most situations.
这篇关于boost :: pool<> :: malloc和boost :: pool<> :: ordered_malloc有什么区别，什么时候应该使用boost :: pool<> :: ordered_malloc?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
