peakflys原创作品,转载请保留原作者和源链接
项目中和自己代码中大量使用了STL的容器,平时也没怎么关注alloc的具体实现细节,主观认识上还停留在侯捷大师的《STL源码剖析》中的讲解。
以下为书中摘录截图:详见书中2.2.4节内容
前段时间项目中出了一个内存问题,在追查问题的过程中查看了对应的源码(版本为libstdc++-devel-4.1.2)
源码文件c++allocator.h中定义了默认的Alloc:#ifndef _CXX_ALLOCATOR_H
#define _CXX_ALLOCATOR_H 1
// Define new_allocator as the base class to std::allocator.
#include <ext/new_allocator.h>
#define __glibcxx_base_allocator __gnu_cxx::new_allocator
#endif
查看new_allocator.h文件,发现new_allocator仅仅是对operator new和operator delete的简单封装(感兴趣的朋友可自行查看)。
众所周知libstdc++中STL的大部分实现是取自SGI的STL,而《STL源码剖析》的源码是Cygnus C++ 2.91则是SGI STL的早期版本,下载源码看了一下allocator的实现确实如书中所言。
不知道从哪个版本起,SGI的STL把默认的Alloc替换成了new_allocator,有兴趣的同学可以查一下。
知道结果后,可能很多人和我一样都不禁要问:Why?
以下是两个版本的源码实现:
1、new_allocator
// NB: __n is permitted to be 0. The C++ standard says nothing
// about what the return value is when __n == 0.
pointer
allocate(size_type __n, const void* = 0)
{
if (__builtin_expect(__n > this->max_size(), false))
std::__throw_bad_alloc();
return static_cast<_Tp*>(::operator new(__n * sizeof(_Tp)));
}
// __p is not permitted to be a null pointer.
void
deallocate(pointer __p, size_type)
{ ::operator delete(__p); }
2、__pool_alloc
template<typename _Tp>
_Tp*
__pool_alloc<_Tp>::allocate(size_type __n, const void*)
{
pointer __ret = 0;
if (__builtin_expect(__n != 0, true))
{
if (__builtin_expect(__n > this->max_size(), false))
std::__throw_bad_alloc();
// If there is a race through here, assume answer from getenv
// will resolve in same direction. Inspired by techniques
// to efficiently support threading found in basic_string.h.
if (_S_force_new == 0)
{
if (getenv("GLIBCXX_FORCE_NEW"))
__atomic_add(&_S_force_new, 1);
else
__atomic_add(&_S_force_new, -1);
}
const size_t __bytes = __n * sizeof(_Tp);
if (__bytes > size_t(_S_max_bytes) || _S_force_new == 1)
__ret = static_cast<_Tp*>(::operator new(__bytes));
else
{
_Obj* volatile* __free_list = _M_get_free_list(__bytes);
lock sentry(_M_get_mutex());
_Obj* __restrict__ __result = *__free_list;
if (__builtin_expect(__result == 0, 0))
__ret = static_cast<_Tp*>(_M_refill(_M_round_up(__bytes)));
else
{
*__free_list = __result->_M_free_list_link;
__ret = reinterpret_cast<_Tp*>(__result);
}
if (__builtin_expect(__ret == 0, 0))
std::__throw_bad_alloc();
}
}
return __ret;
}
template<typename _Tp>
void
__pool_alloc<_Tp>::deallocate(pointer __p, size_type __n)
{
if (__builtin_expect(__n != 0 && __p != 0, true))
{
const size_t __bytes = __n * sizeof(_Tp);
if (__bytes > static_cast<size_t>(_S_max_bytes) || _S_force_new == 1)
::operator delete(__p);
else
{
_Obj* volatile* __free_list = _M_get_free_list(__bytes);
_Obj* __q = reinterpret_cast<_Obj*>(__p);
lock sentry(_M_get_mutex());
__q ->_M_free_list_link = *__free_list;
*__free_list = __q;
}
}
}
从源码中可以看出new_allocator基本就没有什么实现,仅仅是对operator new和operator delete的封装,而__pool_alloc的实现基本和《STL源码剖析》中一样,所不同的是加入了多线程的支持和强制operator new的判断。
无论从源码来看,还是实际的测试(后续会附上我的测试版本),都可以看出__pool_alloc比new_allocator更胜一筹。
同很多人讨论都不得其解,网上也很少有关注这个问题的文章和讨论,倒是libstdc++的官网文档有这么一段:
(peakflys注:文档地址:https://gcc.gnu.org/onlinedocs/libstdc++/manual/memory.html#allocator.default)
从文档的意思来看,选择new_allocator是基于大量测试,不幸的是文档中链接的测试例子均无法访问到……不过既然他们说基于测试得出的结果,我就随手写了一个自己的例子:
#include <map>
#include <vector>
#ifdef _POOL
#include <ext/pool_allocator.h>
#endif
static const unsigned int Count = 1000000;
using namespace std;
struct Data
{
int a;
double b;
};
int main()
{
#ifdef _POOL
map<int, Data, less<int>, __gnu_cxx::__pool_alloc<pair<int, Data> > > mi;
vector<Data, __gnu_cxx::__pool_alloc<Data> > vi;
#else
map<int, Data> mi;
vector<Data> vi;
#endif
for(int i = 0; i < Count; ++i)
{
Data d;
d.a = i;
d.b = i * i;
mi[i] = d;
vi.push_back(d);
}
mi.clear();
#ifdef _POOL
vector<Data, __gnu_cxx::__pool_alloc<Data> >().swap(vi);
#else
vector<Data>().swap(vi);
#endif
for(int i = 0; i < Count; ++i)
{
Data d;
d.a = i;
d.b = i * i;
mi[i] = d;
vi.push_back(d);
}
return 0;
}
因为当数据大于128K时,__pool_alloc同new_allocator一样直接调用operator,所以例子中构造出的Data小于128K,来模拟两个分配器的不同。同时如libstdc++官网中说的,我们同时使用了sequence容器vector和associate容器map。
例子中模拟了两种类型容器的插入-删除-插入的过程,同时里面包含了元素的构造、析构以及内存的分配和回收。
以下是在我本地机器上运行的结果:
1、-O0的版本:
2、-O2的版本:
多线程的测试例子我就不贴了,测试结果大致和上面相同,大家可以自行测试。
从多次运行的结果来看__pool_alloc的性能始终是优于new_allocator的。
又回到那个问题,为什么SGI STL的官方把默认的Alloc从__pool_alloc变为new_allocator。
本篇文章不能给大家一个答案,官方网站上也未看到解释,自己唯一可能的猜测是
1、__pool_alloc不利于使用者自定义operator new和operator delete(其实这条理由又被我自己推翻了,因为通过源码可以知道置位_S_force_new即可解决)
2、malloc性能的提升以及硬件的更新导致使用默认的operator new即可。
如果大家有更好,更权威的答案请告诉我(peakflys@gmail.com)或者留言,谢谢。
by peakflys 16:49:49 Wednesday, January 14, 2015