我想提高 list 和 map 的特定用法的性能,其中项目的数量有大约 100000 的硬限制。STL 默认分配器显然不是这种情况下的最佳选择,因为清理所有成千上万的小物体都需要很长时间(> 10秒!)。更不用说所有其他潜在问题了。
所以很明显,为了改善这一点,我可以预先分配正确的内存量来包含所有列表/映射节点。到目前为止,我已经能够实现默认分配器的工作版本(通过从 std::allocator_traits 派生),它为每个节点使用 alloc/free。但我正在努力找出如何修改它以允许“有状态”使用,例如,我非常简单的堆栈:
using namespace std;
class MemPoolStack
{
public:
size_t Size;
size_t Mult;
size_t Total;
size_t Top;
size_t Last;
unique_ptr<byte[]> Data;
unique_ptr<size_t[]> Nexts;
MemPoolStack(size_t size, size_t mult) :
Size(size),
Mult(mult),
Total(size * mult),
Top(0),
Last(0),
Data(new byte[Total]),
Nexts(new size_t[Size])
{
}
size_t& Next(size_t i)
{
return *(Nexts.get() + i);
}
void* Pop()
{
byte* p = nullptr;
if(Top<Size)
{
p = Data.get() + (Top * Mult);
bool last = (Top==Last);
size_t next = last ? Top+1 : Next(Top);
if(last) Next(Top) = next;
Top = next;
if(Top>Last) Last=Top;
}
else
{
p = nullptr;
}
return p;
}
bool Push(void* p)
{
ptrdiff_t diff = (byte*)p - Data.get();
size_t index = ((size_t)diff / Mult);
if(diff>=0 && index<Size)
{
Next(index) = Top;
Top = index;
return true;
}
return false;
}
};
template <class T> struct MemPool
{
typedef T value_type;
MemPool() throw() {}
template <class U> MemPool (const MemPool<U>&) throw() {}
template <class U> struct rebind { typedef MemPool<U> other; }; //off-topic: why doesn't allocator_traits define this?
T* allocate (size_t n)
{
return static_cast<T*>(malloc(n*sizeof(T)));
}
void deallocate (T* p, size_t n)
{
free(p);
}
};
template <class T, class U>
bool operator== (const MemPool<T>&, const MemPool<U>&) throw()
{return true;}
template <class T, class U>
bool operator!= (const MemPool<T>&, const MemPool<U>&) throw()
{return false;}
我正在实例化我的列表和地图,如下所示:
list<TKey, MemPool<TKey>> Keys;
map<TKey, MapType, less<TKey>, MemPool<MapType>> Map;
它MemPoolStack
本身并不是真正的问题,它可能有错误,但这只是为了举例。关键是MemPoolStack
该类将 a 存储unique_ptr
到预分配的内存中,以及一些其他成员变量。
那里的问题是我需要MemPoolStack
在MemPool
类中对我有一些引用,以便 Visual C++11 映射或列表可以构造我的分配器的所有不同方式都以MemPoolStack
每个列表或映射一个实例结束。然后我可以使用MemPoolStack::Pop()
inMemPool::allocate()
和MemPoolStack::Push()
in MemPool::deallocate()
。
我还需要一种方法来最初构造我的分配器,指定大小。我尝试放入shared_ptr<MemPoolStack>
,MemPool
但当列表决定调用分配器的默认构造函数时它最终迷路了......
我也愿意放弃所有这些代码,以获得原始问题的良好替代解决方案。