C++性能优化（七）——内存池技术_c++内存池

一、内存池简介

1、C++内存池简介

内存池(Memory Pool)是一种内存分配方式，是在真正使用内存前，先申请分配一定数量的、大小相等(一般情况下)的内存块留作备用。当有新的内存需求时，就从内存池中分出一部分内存块，若内存块不够再继续申请新的内存。

通用内存分配和释放的缺点如下：

（1）使用malloc/new申请分配堆内存时系统需要根据最先匹配、最优匹配或其它算法在内存空闲块表中查找一块空闲内存；使用free/delete释放堆内存时，系统可能需要合并空闲内存块，因此会产生额外开销。

（2）频繁使用时会产生大量内存碎片，从而降低程序运行效率。

（3）造成内存泄漏。

内存池（Memory Pool)是代替直接调用malloc/free、new/delete进行内存管理的常用方法，当申请内存空间时，会从内存池中查找合适的内存块，而不是直接向操作系统申请。

内存池技术的优点如下：

（1）堆内存碎片很少。
（2）内存申请/释放比malloc/new方式快。
（3）检查任何一个指针是否在内存池中。
（4）写一个堆转储(Heap-Dump)到硬盘。
（5）内存泄漏检测(memory-leak detection)，当没有释放分配的内存时，内存池(Memory Pool)会抛出一个断言(assertion)。

内存池可以分为不定长内存池和定长内存池两类。不定长内存池的典型实现包括Apache Portable Runtime中的apr_pool和GNU lib C中的obstack，而定长内存池的实现则有boost_pool等。对于不定长内存池，不需要为不同的数据类型创建不同的内存池，其缺点是无法将分配出的内存回收到池内；对于定长内存池，在使用完毕后，可以将内存归还到内存池中，但需要为不同类型的数据结构创建不同的内存池，需要内存的时候要从相应的内存池中申请内存。

2、常见C++内存池实现方案

（1）固定大小缓冲池
 固定大小缓冲池适用于频繁分配和释放固定大小对象的情况。

（2）dlmalloc

dlmalloc 是一个内存分配器，由Doug Lea从1987年开始编写，目前最新版本为2.8.3，由于其高效率等特点被广泛使用和研究。

ftp://g.oswego.edu/pub/misc/malloc.c
（3） SGI STL内存分配器

 SGI STL allocator 是目前设计最优秀的 C++ 内存分配器之一，其内部free_list[16] 数组负责管理从 8 bytes到128 bytes不同大小的内存块（ chunk ），每一个内存块都由连续的固定大小（ fixed size block ）的很多 chunk 组成，并用指针链表连接。

（4）Loki小对象分配器
Loki 分配器使用vector管理数组，可以指定 fixed size block 的大小。free blocks分布在一个连续的大内存块中，free chunks 可以根据使用情况自动增长和减少合适的数目，避免内存分配得过多或者过少。
（5）Boost object_pool
Boost object_pool 可以根据用户具体应用类的大小来分配内存块，通过维护一个free nodes的链表来管理。可以自动增加nodes块，初始32个nodes，每次增加都以两倍数向system heap要内存块。object_pool 管理的内存块需要在其对象销毁的时候才返还给 system heap 。
（6）ACE_Cached_Allocator 和 ACE_Free_List

ACE 框架中包含一个可以维护固定大小的内存块的分配器，通过在 ACE_Cached_Allocator 中定义Free_list 链表来管理一个连续的大内存块，内存块中包含多个固定大小的未使用内存区块（ free chunk），同时使用ACE_unbounded_Set维护已使用的chuncks 。

（7）TCMalloc

Google开源项目gperftools提供了内存池实现方案。https://code.google.com/p/gperftools/

TCMalloc替换了系统的malloc，更加底层优化，性能更好。

3、STL内存分配器

分配器(allocator))是C ++标准库的一个组件, 主要用来处理所有给定容器(vector，list，map等)内存的分配和释放。C ++标准库提供了默认使用的通用分配器std::allocator，但开发者可以自定义分配器。

GNU STL除了提供默认分配器，还提供了__pool_alloc、__mt_alloc、array_allocator、malloc_allocator 内存分配器。

__pool_alloc ：SGI内存池分配器

__mt_alloc ： 多线程内存池分配器

array_allocator ： 全局内存分配，只分配不释放，交给系统来释放

malloc_allocator ：堆std::malloc和std::free进行的封装

二、STL allocator

1、STL allocator简介

new会分配内存并执行对象构造函数，delete会执行对象析构函数并释放内存。如果将内存分配和对象构造分离，可以先分配大块内存，只在需要时才真正执行对象构造函数。

STL在头文件memory中提供了一个allocator类，允许将分配和对象构造分离，提供更好的性能和更灵活的内存管理能力。为了定义一个allocator对象，必须指明allocator可以分配的对象类型。当allocator分配内存时，会根据给定的对象类型来确定恰当的内存大小和对齐位置。

2、STL allocator接口

STL allocator的标准接口如下：

typedef size_t     size_type; 
typedef ptrdiff_t  difference_type;
typedef _Tp*       pointer; 
typedef const _Tp* const_pointer;
typedef _Tp&       reference;
typedef const _Tp& const_reference;
typedef _Tp        value_type;
 
void construct(pointer __p, const _Tp& __val) { ::new((void *)__p) value_type(__val); }
void destroy(pointer __p) { __p->~_Tp(); }
size_type max_size() const _GLIBCXX_USE_NOEXCEPT { return size_t(-1) / sizeof(_Tp); }
address(const_reference __x) const _GLIBCXX_NOEXCEPT
deallocate(pointer, size_type);
allocate(size_type __n, const void* = 0);
template<typename _Tp1>
struct rebind { typedef allocator<_Tp1> other; };

根据C++标准规范，STL中分配器的对外接口、成员变量都一样，只是接口内部实现有区别。

allocator实现在模板类new_allocator中：

namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION
 
    template<typename _Tp>
    class new_allocator
    {
    public:
      typedef _Tp*       pointer;
      typedef const _Tp* const_pointer;
 
      // 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 (__n > this->max_size())
          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); }
    }
 
_GLIBCXX_END_NAMESPACE_VERSION
 
}

STL中容器默认分配器为std::allocator<_Tp>，内存分配和释放的接口allocate和deallocate内部实现只是将::operator new和::operator delete进行封装，没用做特殊处理。

3、STL allocator实例

#include <iostream>
#include <string>
#include <vector>
#include <memory>
using namespace std;
 
class Test
{
public:
    Test()
    {
        cout << "Test Constructor" << endl;
    }
 
    ~Test()
    {
        cout << "Test DeConstructor" << endl;
    }
 
    Test(const Test &t)
    {
        cout << "Copy Constructor" << endl;
    }
};
 
int main(int argc, const char *argv[])
{
    allocator<Test> alloc;
    //申请三个单位的Test内存，未经初始化
    Test *pt = alloc.allocate(3);
    {
        // 构造对象，使用默认值
        alloc.construct(pt, Test());
        // 调用拷贝构造函数
        alloc.construct(pt + 1, Test());
        alloc.construct(pt + 2, Test());
    }
 
    alloc.destroy(pt);
    alloc.destroy(pt + 1);
    alloc.destroy(pt + 2);
 
    alloc.deallocate(pt, 3);
    return 0;
}
 
 
 
// output:
//Test Constructor
//Copy Constructor
//Test DeConstructor
//Test Constructor
//Copy Constructor
//Test DeConstructor
//Test Constructor
//Copy Constructor
//Test DeConstructor
//Test DeConstructor
//Test DeConstructor
//Test DeConstructor

4、自定义allocator

实现Allocator只需要实现allocate和deallocate，来实现自己的内存分配策略。

#ifndef ALLOCATOR_HPP
#define ALLOCATOR_HPP
 
#include <stddef.h>
#include <limits>
 
template <typename T>
class Allocator
{
public:
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;
    typedef T*  pointer;
    typedef const T* const_pointer;
    typedef T& reference;
    typedef const T& const_reference;
    typedef T value_type;
 
    //Allocator::rebind<T2>::other
    template <typename V>
    struct rebind
    {
        typedef Allocator<V> other;
    };
 
    pointer address(reference value) const
    {
        return &value;
    }
 
    const_pointer address(const_reference value) const
    {
        return &value;
    }
 
    Allocator() throw() {   }
    Allocator(const Allocator &) throw() {  }
    //不同类型的allcator可以相互复制
    template <typename V> Allocator(const Allocator<V> &other) { }
    ~Allocator() throw() {  }
 
    //最多可以分配的数目
    size_type max_size() const throw()
    {
        return std::numeric_limits<size_type>::max() / sizeof(T);
    }
 
    //分配内存，返回该类型的指针
    pointer allocate(size_type num)
    {
        return (pointer)(::operator new(num * sizeof(T)));
    }
 
    //执行构造函数，构建一个对象
    void construct(pointer p, const T &value)
    {
        new ((void*)p) T(value);
    }
 
    //销毁对象
    void destroy(pointer p)
    {
        p->~T();
    }
 
    //释放内存
    void deallocate(pointer p, size_type num)
    {
        ::operator delete((void *)p);
    }
};
 
template <typename T, typename V>
bool operator==(const Allocator<T> &, const Allocator<V> &) throw()
{
    return true;
}
 
template <typename T, typename V>
bool operator!=(const Allocator<T> &, const Allocator<V> &) throw()
{
    return false;
}
 
#endif

测试代码：

#include "Allocator.hpp"
#include <string>
#include <vector>
#include <iostream>
using namespace std;
 
class Test
{
public:
    Test()
    {
       cout << "Test Constructor" << endl;
    }
 
    Test(const Test& other)
    {
       cout << "Test Copy Constructor" << endl;
    }
 
    ~Test()
    {
       cout << "Test DeConstructor" << endl;
    }
};
 
class Test2
{
public:
    Test2()
    {
       cout << "Test2 Constructor" << endl;
    }
 
    Test2(const Test2& other)
    {
       cout << "Test2 Copy Constructor" << endl;
    }
 
    ~Test2()
    {
       cout << "Test2 DeConstructor" << endl;
    }
};
 
int main(int argc, char const *argv[])
{
    // 定义容器时指定分配器
    vector<string, Allocator<string> > vec(10, "haha");
    vec.push_back("foo");
    vec.push_back("bar");
    // 使用Test分配器分配Test2类型
    Allocator<Test>::rebind<Test2>::other alloc;
    Test2 *pTest = alloc.allocate(5);
    alloc.construct(pTest, Test2());
    alloc.construct(pTest + 1, Test2());
    alloc.construct(pTest + 2, Test2());
 
    alloc.destroy(pTest);
    alloc.destroy(pTest + 1);
    alloc.destroy(pTest + 2);
 
    alloc.deallocate(pTest, 3);
 
    return 0;
}

5、mt allocator

mt allocator（__gnu_cxx::__mt_alloc）是STL扩展库的支持多线程应用的内存分配器，是为多线程应用程序设计的固定大小（2的幂）内存的分配器，目前在单线程应用程序表现一样出色。

mt allocator由3个部分组成：描述内存池特征的参数；关联内存池到通用或专用方案的policy类；从policy类继承的实际内存分配器类。

（1）线程支持参数模板类

template<bool _Thread>  class __pool;

表示是否支持线程，然后对多线程（bool==true）和单线程（bool==false）情况进行显式特化，开发者可以使用定制参数替代。

（2）内存池Policy类

通用内存池策略:

__common_pool_policy实现了一个通用内存池，即使分配的对象类型不同（比如char和long）也使用同一个的内存池，是默认策略。

template<bool _Thread>
struct __common_pool_policy;

专用策略类：

__per_type_pool_policy会对每个对象类型都实现一个单独的内存池，因此不同对象类型会使用不同的内存池，可以对某些类型进行单独调整。

template<typename _Tp, bool _Thread>
struct __per_type_pool_policy;

（3）内存分配器

template<typename _Tp, typename _Poolp = __default_policy>
class __mt_alloc : public __mt_alloc_base<_Tp>,  _Poolp
template<typename _Tp,
         typename _Poolp = __common_pool_policy<__pool, __thread_default> >
class __mt_alloc : public __mt_alloc_base<_Tp>
{
public:
    typedef size_t                            size_type;
    typedef ptrdiff_t                         difference_type;
    typedef _Tp*                              pointer;
    typedef const _Tp*                        const_pointer;
    typedef _Tp&                              reference;
    typedef const _Tp&                        const_reference;
    typedef _Tp                               value_type;
    typedef _Poolp                            __policy_type;
    typedef typename _Poolp::pool_type        __pool_type;
 
    template<typename _Tp1, typename _Poolp1 = _Poolp>
    struct rebind
    {
        typedef typename _Poolp1::template _M_rebind<_Tp1>::other pol_type;
        typedef __mt_alloc<_Tp1, pol_type> other;
    };
 
    __mt_alloc() _GLIBCXX_USE_NOEXCEPT { }
    __mt_alloc(const __mt_alloc&) _GLIBCXX_USE_NOEXCEPT { }
    template<typename _Tp1, typename _Poolp1>
    __mt_alloc(const __mt_alloc<_Tp1, _Poolp1>&) _GLIBCXX_USE_NOEXCEPT { }
    ~__mt_alloc() _GLIBCXX_USE_NOEXCEPT { }
    pointer allocate(size_type __n, const void* = 0);
 
    void deallocate(pointer __p, size_type __n);
 
    const __pool_base::_Tune
    _M_get_options()
    {
        // Return a copy, not a reference, for external consumption.
        return __policy_type::_S_get_pool()._M_get_options();
    }
 
    void _M_set_options(__pool_base::_Tune __t)
    {
        __policy_type::_S_get_pool()._M_set_options(__t);
    }
};

（4）内存池特征参数调整

mt allocator提供了用于调整内存池参数的嵌套类_Tune。

struct _Tune
{
    enum { _S_align = 8 };
    enum { _S_max_bytes = 128 };
    enum { _S_min_bin = 8 };
    enum { _S_chunk_size = 4096 - 4 * sizeof(void*) };
    enum { _S_max_threads = 4096 };
    enum { _S_freelist_headroom = 10 };
 
    size_t    _M_align;// 字节对齐
    size_t    _M_max_bytes;// 128字节以上的内存直接用new分配
    size_t    _M_min_bin;//可分配的最小的内存块大小8字节
    size_t    _M_chunk_size;//每次从os申请的内存块的大小为4080字节
    size_t    _M_max_threads;//可支持的最多的线程数是4096
    size_t    _M_freelist_headroom;//单线程能保存的空闲块的百分比为10%
    bool      _M_force_new;//是否直接使用new和delete 根据 是否设置 getenv("GLIBCXX_FORCE_NEW")
};

_Tune参数的设置和获取接口如下：

const _Tune& _M_get_options() const
{
    return _M_options;
}
 
void _M_set_options(_Tune __t)
{
    if (!_M_init)
        _M_options = __t;
}

内存池参数调整必须在任何内存分配动作前。

mt allocator实例如下：

#include <ext/mt_allocator.h>
#include <string.h>
 
class Test
{
public:
    Test(int id = 0)
    {
        memset(this, 0, sizeof(Test));
        this->id = id;
    }
private:
    int id;
    char name[32];
};
 
typedef __gnu_cxx::__mt_alloc<Test> TestAllocator;
typedef __gnu_cxx::__pool_base::_Tune TestAllocatorTune;
 
int main()
{
    TestAllocator pool;
    TestAllocatorTune t_defaut;
    TestAllocatorTune t_opt(16, 5120, 32, 5120, 20, 10, false);
    TestAllocatorTune t_single(16, 5120, 32, 5120, 1, 10, false);
 
    TestAllocatorTune t;
    t = pool._M_get_options();
    pool._M_set_options(t_opt);
    t = pool._M_get_options();
    // allocate
    TestAllocator::pointer p1 = pool.allocate(sizeof(Test));
    TestAllocator::pointer p2 = pool.allocate(5120);
 
    // free
    pool.deallocate(p1, sizeof(Test));
    pool.deallocate(p2, 5120);
    
    return 0;
}

如果分配内存大于内存池特征参数设置的值，将会抛出异常或导致段错误。

三、Boost内存池

1、pool

pool是一个Object Usage的内存池，每个内存池都是一个可以创建和销毁的对象，一旦内存池被销毁则其所分配的所有内存都会被释放，溢出时返回NULL。

pool内存池是最基本的的定长内存池，只可用于内嵌数据类型（如int，char等）的分配，而不适合用于复杂的类和对象。pool内存池只简单地分配内存而不调用类构造函数，对于复杂的类和对象，则应该使用object_pool内存池。

boost::pool接口函数如下：

bool release_memory();   

释放所有空闲block给操作系统。pool对空闲block的判断标准是：block中所有的chunk都在空闲链表中并且空闲链表有序

bool purge_memory(); 

  释放所有的block给操作系统，不管block中的chunk块有没有被分配；pool析构函数会调用完成内存释放

size_type get_next_size() const;

   获取下一次要分配的block的大小

size_type set_next_size(const size_type nnext_size);

   设置下一次要分配的block的大小

size_type get_requested_size();

    获取每个内存块的大小；以Byte为单位

void * malloc();

    分配一个chunk块；如果pool中没有剩余空间供分配，则会向操作系统申请一块新的block

void * ordered_malloc();

    分配一个chunk块；如果没有足够的空间进行分配，那么pool向操作系统申请新的block并将block分块后，会进行block链表的排序以保证内存块有序

void * ordered_malloc(size_type n);

   从内存池中请求物理地址连续的n块内存，可以用来进行内存数组的分配；函数要求某个block中的chunk链表是有序的，否则，即使有连续内存存在，仍然有可能分配失败从而再申请的新的block内存块。在内存池的request_size（内存池初始化时指定的内存块大小）小于size_type(void *)时，内存池并不会分配n块chunk，而是分配ceil(n*request_size/size_type(void *))块内存

void free(void * const chunk); 

 将malloc申请到的内存返回给内存池

void ordered_free(void * const chunk);

  将malloc申请到的内存返回给内存池并保证空闲chunk链表有序

void free(void * const chunks, const size_type n);

   返回chunk开头的连续n块内存给内存池

void ordered_free(void * const chunks, const size_type n);

    返回chunk开头的连续n块内存给内存池并保持空闲chunk链表有序

bool is_from(void * const chunk) const;  

 判断chunk是否由本内存池所释放的

#include <boost/pool/pool.hpp>
#include <iostream>
 
using namespace std;
 
int main()
{
    boost::pool<> testpool(sizeof(int));
    for(int i = 0; i < 1000; i++)
    {
        int* pn = (int*)testpool.malloc();
        *pn = i + 1;
        cout << *pn << endl;
    }
 
    return 0;
}
 
g++ test.cpp -o test -lboost_system

2、object_pool

Pool是一个Object Usage的内存池，每个内存池都是一个可以创建和销毁的对象，一旦内存池被销毁则其所分配的所有内存都会被释放，溢出时返回NULL。

object_pool对象内存池适用于对复杂对象的分配和释放，除了分配释放内存外，object_pool会调用对象的构造函数和析构函数。

object_pool内存池的内存分配算法与pool不同，object_pool内存池的分配和释放要比pool慢的多。

object_pool接口如下：

element_type * malloc();

    分配一块内存，调用pool的ordered_malloc函数；

void free();  

  释放一块内存，调用pool的ordered_free函数

element_type * construct(); 

   分配一块内存并调用构造函数

void destroy(element_type * const chunk); 

  析构一个对象并将其内存返回给内存池

#include <boost/pool/object_pool.hpp>
#include <iostream>
 
class Test
{
public:
    Test(int id = 0)
    {
        this->id = id;
    }
    int id;
};
 
using namespace std;
 
int main()
{
    boost::object_pool<Test> testpool;
    Test* pTest1 = testpool.malloc();
    cout << pTest1->id << endl;
    Test* pTest2 = testpool.construct();
    cout << pTest2->id << endl;
    testpool.free(pTest1);
    return 0;
}
 
g++ test.cpp -o test -lboost_system

3、singleton_pool

singleton_pool是一个Singleton Usage的内存池，每个内存池都是一个被静态分配的对象，直至程序结束才会被销毁，溢出时返回NULL。

singleton_pool内存池是线程安全的，只有使用release_memory或者 purge_memory方法才能释放内存。

 singleton_pool则是pool的一个单例模式的实现，其接口和pool相同，并且通过互斥量的方法来保证线程安全。

4、pool_alloc

pool_alloc是一个Singleton Usage的内存池，溢出时抛出异常。

pool_alloc提供了两个用于标准容器类型的分配器：pool_allocator和fast_pool_allocator。但STL标准容器提供了自己的内存分配器，通常应当使用STL标准的内存分配器进行内存分配，而不要使用pool_alloc提供的内存分配器。