SGI STL中默认Allocator为何变为new_allocator?

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

posted on 2015-01-14 16:50 peakflys 阅读(4251) 评论(8)  编辑 收藏 引用 所属分类: C++

评论

# re: SGI STL中默认Allocator为何变为new_allocator? 2015-01-15 00:12 egmkang

跟硬件没关系,malloc性能提升.因为malloc本身在thread上面就有一个pool.
而且高性能的分配器越来越多,比如tcmalloc/jemalloc,已经没有任何必要再提供一个pool allocator  回复  更多评论   

# re: SGI STL中默认Allocator为何变为new_allocator? 2015-01-15 09:12 苹果汁

楼主好学 赞一个  回复  更多评论   

# re: SGI STL中默认Allocator为何变为new_allocator?[未登录] 2015-01-15 13:01 chipset

pool不拼接内存,一块大内存被分割成很多相等的小块,此时调用分配一块较大内存可能失败,不是因为内存不够用,而是因为全是分割成小碎块不拼接导致的。这是Pool的致命伤。再者Pool的效率也高不到哪里,以不拼接小块换速度的做法不值得提倡。  回复  更多评论   

# re: SGI STL中默认Allocator为何变为new_allocator? 2015-01-15 17:42 xxoo

楼上的,内存池的作用不就是这个吗?你申请一块内存,可以做到物理不连续?  回复  更多评论   

# re: SGI STL中默认Allocator为何变为new_allocator? 2015-01-15 19:23 peakflys

如果我没记错的话malloc自始至终都有自己的一套pool策略,所以我所说的malloc性能提升并非指的这个。
不过第三方稳定高效的allocator实现可能是标准库作者放弃pool的一个原因@egmkang
  回复  更多评论   

# re: SGI STL中默认Allocator为何变为new_allocator? 2015-01-15 19:31 peakflys

说的不错,pool的方式存在的问题是挺多。不过对于pool的效率高不到哪去的观点我不敢认同,针对大量小数据的分配,有时候还必须得使用pool的方式,不然ptmalloc、tcmalloc、jemalloc等不会维护复杂的内存分配方式@chipset  回复  更多评论   

# re: SGI STL中默认Allocator为何变为new_allocator? 2015-01-20 15:24 juegoskizi

我很喜欢,很不错的职位。  回复  更多评论   

# re: SGI STL中默认Allocator为何变为new_allocator?[未登录] 2016-03-07 14:09 JAKE

楼主,有个问题请教下:
我有个应用场景,即线程A使用obj_pool分配了一个对象obj,线程B用完obj后归还给pool。 这里肯定会有线程同步隐患。

目前我使用两个lockfree队列完美解决这个问题,但很繁琐。

我想问的是
使用tcmalloc的话,能解决我上边所说的问题吗?  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2015年1月>
28293031123
45678910
11121314151617
18192021222324
25262728293031
1234567

导航

统计

公告

人不淡定的时候,就爱表现出来,敲代码如此,偶尔的灵感亦如此……

常用链接

留言簿(4)

随笔分类

随笔档案

文章档案

搜索

最新评论

阅读排行榜

评论排行榜