常用的几种内存池技术

几乎所有应用程序中都会有内存的分配和释放，而频繁的分配和释放内存无疑会产生内存碎片，降低系统性能，尤其对性能要求较高的程序比较明显。下面介绍几种常见的内存池技术。

    一  环形缓存

    环形缓存的基本原理如图：

    初始化状态(wpos_ = rpos_)：

    写了部分数据，同时读了一部分数据（wpos_ > rpos_）：

    wpos_写数据到尾部后，又从头开始，rpos_还读到尾部（wpos_ < rpos_）：

    rpos_读了N（N>= 1）圈后，赶上了wpos_,也就是说没有数据可读了(wpos_ < rpos_)：

   综合起来，看起来像这样子：

 需要注意的是：

    #1    wpos_ < rpos_的情况下，rpos_ 读数据一直读到尾部，然后又从头部开始，数据拼接一块即可；

    #2    如果 | wpos_ -  rpos |  < cnt,即没有足够的数据可来写的时候，需要重写分配内存，具体分配多少，根据你的程序来定，额外大小或者1.5倍原大小；

    部分实现代码如下：

#define EXTRA_BUFFER_SIZE        64

namespace easy
{
    template<class _Type,class _Alloc >
    class EasyRingbuffer
    {
    public:
        typedef _Alloc allocator_type;

        explicit EasyRingbuffer(size_t size):
        size_(size),
            wpos_(0),
            rpos_(0)
        {
            buffer_ = _allocate(size_);
        }

        ~EasyRingbuffer() { _deallocate(buffer_,size_); }

        template<typename T> void append(T val)
        {
            append((easy_uint8*)&val,sizeof(val));
        }

        void append(const easy_uint8* src, size_t cnt)
        {
            if (!cnt)
            {
                return;
            }

            //    case 1: rpos_ <= wpos_
            if (rpos_ <= wpos_)
            {
                if (size_ - wpos_ >= cnt)
                {
                    memmove(buffer_ + wpos_,src,cnt);
                    wpos_ += cnt;
                    return;
                }
                else
                {
                    if (size_ - wpos_ + rpos_ > cnt)    // >= is ok>
                    {
                        memmove(buffer_ + wpos_, src, size_ - wpos_);
                        memmove(buffer_, src + size_ - wpos_, cnt - (size_ - wpos_));
                        wpos_ = cnt - (size_ - wpos_);
                        return;
                    }
                    else
                    {
                        _Type* new_buffer = _allocate(size_ + cnt - (size_ - wpos_));
                        memmove(new_buffer,buffer_,wpos_);
                        memmove(new_buffer + wpos_, src, cnt);
                        _deallocate(buffer_,size_);
                        size_ = size_ + cnt - (size_ - wpos_);
                        wpos_ += cnt;
                        buffer_ = new_buffer;
                        return;
                    }
                }
            }
            //    case 2: rpos_ > wpos_
            else if(rpos_ > wpos_)
            {
                if (rpos_ - wpos_ > cnt)    // >= is ok ?
                {
                    if (rpos_ - wpos_ > cnt)
                    {
                        memmove(buffer_ + wpos_,src,cnt);
                        wpos_ += cnt;
                        return;
                    }
                    else
                    {
                        _Type* new_buffer = _allocate(size_ + cnt - (rpos_ - wpos_) + EXTRA_BUFFER_SIZE);
                        memmove(new_buffer,buffer_,wpos_);
                        memmove(new_buffer + wpos_,src,cnt);
                        memmove(new_buffer + wpos_ + cnt - (rpos_ - wpos_) + EXTRA_BUFFER_SIZE,buffer_ + rpos_,size_ - rpos_);
                        _deallocate(buffer_,size_);
                        rpos_ += cnt - (rpos_ - wpos_) + EXTRA_BUFFER_SIZE;
                        wpos_ += cnt;
                        size_ = size_ + cnt - (rpos_ - wpos_) + EXTRA_BUFFER_SIZE;
                        buffer_ = new_buffer;
                        return;
                    }
                }
            }
        }

        EasyRingbuffer& operator << (easy_bool val)
        {
            append<easy_bool>(val);
            return *this;
        }

        EasyRingbuffer& operator << (easy_uint8 val)
        {
            append<easy_uint8>(val);
            return *this;
        }

        EasyRingbuffer& operator << (easy_uint16 val)
        {
            append<easy_uint16>(val);
            return *this;
        }

        EasyRingbuffer& operator << (easy_uint32 val)
        {
            append<easy_uint32>(val);
            return *this;
        }

        EasyRingbuffer& operator << (easy_uint64 val)
        {
            append<easy_uint64>(val);
            return *this;
        }

        EasyRingbuffer& operator << (easy_int8 val)
        {
            append<easy_int8>(val);
            return *this;
        }

        EasyRingbuffer& operator << (easy_int16 val)
        {
            append<easy_int16>(val);
            return *this;
        }

        EasyRingbuffer& operator << (easy_int32 val)
        {
            append<easy_int32>(val);
            return *this;
        }

        EasyRingbuffer& operator << (easy_int64 val)
        {
            append<easy_int64>(val);
            return *this;
        }

        EasyRingbuffer& operator << (easy_float val)
        {
            append<easy_float>(val);
            return *this;
        }

        EasyRingbuffer& operator << (easy_double val)
        {
            append<easy_double>(val);
            return *this;
        }

        EasyRingbuffer& operator << (const std::string& val)
        {
            append((easy_uint8 const*)val.c_str(),val.length());
            return *this;
        }

        EasyRingbuffer& operator << (const char* val)
        {
            append((easy_uint8 const *)val, val ? strlen(val) : 0);
            return *this;
        }

        template<typename T> T read()
        {
            T r;
            read((easy_uint8*)&r,sizeof(T));
            return r;
        }

        void read(easy_uint8* des,size_t len)
        {
            if (_read_finish())
            {
                return;
            }
            if (rpos_ < wpos_)
            {
                if (wpos_ - rpos_ >= len)
                {
                    memmove(des,buffer_ + rpos_,len);
                    rpos_ += len;
                }
                //    else just skip
            }
            else if (rpos_ > wpos_)
            {
                if (size_ - rpos_ >= len)
                {
                    memmove(des,buffer_ + rpos_,len);
                    rpos_ += len;
                }
                else
                {
                    memmove(des,buffer_ + rpos_, size_ - rpos_);
                    memmove(des + size_ - rpos_, buffer_, len - (size_ - rpos_));
                    rpos_ = len - (size_ - rpos_);
                }
            }
        }

        EasyRingbuffer& operator >> (easy_bool& val)
        {
            val = read<easy_bool>();
            return *this;
        }

        EasyRingbuffer& operator >> (easy_uint8& val)
        {
            val = read<easy_uint8>();
            return *this;
        }

        EasyRingbuffer& operator >> (easy_uint16& val)
        {
            val = read<easy_uint16>();
            return *this;
        }

        EasyRingbuffer& operator >> (easy_uint32& val)
        {
            val = read<easy_uint32>();
            return *this;
        }

        EasyRingbuffer& operator >> (easy_uint64& val)
        {
            val = read<easy_uint64>();
            return *this;
        }

        EasyRingbuffer& operator >> (easy_int8& val)
        {
            val = read<easy_int8>();
            return *this;
        }

        EasyRingbuffer& operator >> (easy_int16& val)
        {
            val = read<easy_int16>();
            return *this;
        }

        EasyRingbuffer& operator >> (easy_int32& val)
        {
            val = read<easy_int32>();
            return *this;
        }

        EasyRingbuffer& operator >> (easy_int64& val)
        {
            val = read<easy_int64>();
            return *this;
        }

        EasyRingbuffer& operator >> (easy_float& val)
        {
            val = read<easy_float>();
            return *this;
        }

        EasyRingbuffer& operator >> (easy_double& val)
        {
            val = read<easy_double>();
            return *this;
        }

        size_t size() const { return size_; }

        size_t rpos() const { return rpos_; }

        size_t wpos() const { return wpos_; }

    private:
        _Type* _allocate(size_t size)
        {
            _Type* res = 0;
            res = static_cast<_Type*>(alloc_type_.allocate(size));
            return res;
        }

        void _deallocate(void* p,size_t size)
        {
            alloc_type_.deallocate(p,size);
        }

        void _reallocate(void* p,size_t old_size,size_t new_size) { alloc_type_.reallocate(p,old_size,new_size); }

        easy_bool _read_finish() { return wpos_ == rpos_; }

    private:
        EasyRingbuffer ( const EasyRingbuffer& );
        EasyRingbuffer& operator = ( const EasyRingbuffer& );
    private:
        size_t            size_;

        _Type*            buffer_;

        size_t            wpos_;

        size_t            rpos_;

        allocator_type    alloc_type_;
    };
}

 

  二 空闲列表

    空闲列表的原理比较简单，一般用于比较大的对象，可预分配一定数量的对象，需要时直接空闲列表中取，使用完后收回，如果空闲列表中已空，则需要重新设置大小了；也可使用时分配，使用完后收回。实现代码如下：

// use stl
    template<typename _Type, typename _Lock,typename _StorageType /*= std::list<_Type*>*/>
    class lock_queue
    {
        typedef typename _Type::_Key                _Key;

        static const size_t MAX_POOL_SIZE = _Type::MAX_POOL_SIZE;

    public:
        _Type* allocate(_Key __key)
        {
            _Type* __ret = 0;
            if (free_list_.empty())
            {
                __ret = new _Type(__key);
            }
            else
            {
                lock_.acquire_lock();
                __ret = free_list_.back();
                free_list_.pop_back();
                lock_.release_lock();
            }
            return __ret;
        }

        void deallcate(_Type* __val)
        {
            if (!__val)
            {
                return;
            }
            if (MAX_POOL_SIZE < free_list_.size())
            {
                delete __val;
                return;
            }
            lock_.acquire_lock();
            free_list_.push_back(__val);
            lock_.release_lock();
        }

        size_t free_size() /*const*/
        {
            size_t __size = 0;
            lock_.acquire_lock();
            __size = free_list_.size();
            lock_.release_lock();
            return __size;
        }

        void clear()
        {
            lock_.acquire_lock();
            for (typename _StorageType::iterator __it = free_list_.begin(); __it != free_list_.end(); ++__it)
            {
                if ((*__it))
                {
                    delete (*__it);
                    (*__it) = NULL;
                }
            }
            free_list_.clear();
            _StorageType().swap(free_list_);
            lock_.release_lock();
        }

        ~lock_queue()
        {
            clear();
        }
    private:
        _Lock                        lock_;
        _StorageType                free_list_;
    };

//anther way,use use stl
template < typename T, int DEFAULT_BLOCK_NUM = 1024 >
class CMemoryPool
{
public:
    static VOID* operator new ( std::size_t nAllocLength )
    {
        Assert( sizeof(T) == nAllocLength );
        Assert( sizeof(T) >= sizeof(UCHAR*) );
        if ( !m_sNewPointer )
        {
            allocBlock();
        }
        UCHAR* ucReturnPointer = m_sNewPointer;
        //the head of 4 bytes is explain the next pointer of memory force,
        //and m_NewPointer just point the next block of memory,when used the next allocation
        m_sNewPointer = *reinterpret_cast<UCHAR**>( ucReturnPointer);
        return ucReturnPointer;
    }

    static VOID operator delete( void* vpDeletePointer )
    {
        *reinterpret_cast<UCHAR**>( vpDeletePointer) = m_sNewPointer;
        m_sNewPointer = static_cast<UCHAR*>(vpDeletePointer);
    }

    static VOID allocBlock()
    {
        m_sNewPointer = new UCHAR[sizeof(T) * DEFAULT_BLOCK_NUM];
        //casting dual pointer force,that will change the meaning of the head of 4 byte memory
        UCHAR **ppCurent = reinterpret_cast<UCHAR**>( m_sNewPointer );
        UCHAR *ppNext = m_sNewPointer;
        for( int i = 0; i < DEFAULT_BLOCK_NUM-1; i++ )
        {
            ppNext += sizeof(T);
            *ppCurent = ppNext;
            //the head of 4 bytes is explain the next pointer of memory force,a memory list in form.
            ppCurent = reinterpret_cast<UCHAR**>( ppNext );
        }
        //if the last memory bock, the head of 4 byte is null
        *ppCurent = 0;
    }

protected:
    virtual ~CMemoryPool()
    {

    }
private:
    static UCHAR *m_sNewPointer;
};

template<class T, int BLOCK_NUM >
UCHAR *CMemoryPool<T, BLOCK_NUM >::m_sNewPointer;

    三  stl的二级分配器

    stl内部实现的分配器分两种情况：一种是大于128byte的分配，直接使用系统的内存分配函数malloc/free;另外一种为小于128byte的，也就是上面说的二级分配器，它采用了某些技术来管来内存，避免频繁分配释放。简 单的说，就是将内存按8字节对齐，分别建立固定值倍数大小的内存池，如8, 8*2 ,8*3..., 当需要分配内存时，根据分配内存的大小，算出所需内存大小的内存池索引，然后根据这个索引找到那块内存池，并从中取出一块返回；同样，内存使用完后，按类 似的方法回收。这种方案一般适用于比较小的内存分配的情况，大的可以考虑其他的方案。其流程如下：


下面是具体代码：

template< bool threads, int inst >
    class __default_alloc_template
    {
        enum {_ALIGN = 8};
        enum {_MAX_BYTES = 128};
        enum {_NFREELISTS = 16}; // _MAX_BYTES/_ALIGN

        static size_t _S_round_up(size_t __bytes) { return (((__bytes) + (size_t) _ALIGN-1) & ~((size_t) _ALIGN - 1)); }

        static  size_t _S_freelist_index(size_t __bytes) { return (((__bytes) + (size_t)_ALIGN-1)/(size_t)_ALIGN - 1); }

        union _Obj
        {
            union _Obj* _M_free_list_link;
            char _M_client_data[1]; /* The client sees this. */
        };
        static _Obj* volatile _S_free_list[_NFREELISTS];

        // Returns an object of size __n, and optionally adds to size __n free list.
        static void* _S_refill(size_t __n);

        // Allocates a chunk for nobjs of size size. nobjs may be reduced
        // if it is inconvenient to allocate the requested number.
        static char* _S_chunk_alloc(size_t __size, int& __nobjs);

        static void* reallocate(void* __p, size_t __old_sz, size_t __new_sz);

        // Chunk allocation state.
        static char*    _S_start_free;
        static char*    _S_end_free;
        static size_t    _S_heap_size;

    public:
        static void* allocate(size_t __n)
        {
            void* __ret = 0;
            if (__n > (size_t) _MAX_BYTES)
            {
                __ret = malloc_alloc::allocate(__n);
            }
            else
            {
                mutex_lock    __lock;
                __lock.acquire_lock();
                _Obj* volatile* __my_free_list = _S_free_list + _S_freelist_index(__n);
                _Obj* volatile __result = *__my_free_list;
                if (__result == 0)
                {
                    __ret = _S_refill(_S_round_up(__n));
                }
                else
                {
                    *__my_free_list = __result -> _M_free_list_link;
                    __ret = __result;
                }
                __lock.release_lock();
            }
            return __ret;
        }

        /* __p may not be 0 */
        static void deallocate(void* __p, size_t __n)
        {
            if (__n > (size_t) _MAX_BYTES)
            {
                 malloc_alloc::deallocate(__p, __n);
            }
            else
            {
                mutex_lock    __lock;
                __lock.acquire_lock();
                  _Obj* volatile* __my_free_list = _S_free_list + _S_freelist_index(__n);
                  _Obj* __q = (_Obj*)__p;
                  __q -> _M_free_list_link = *__my_free_list;
                 *__my_free_list = __q;
                  __lock.release_lock();
            }
        }
    };

    template <bool __threads, int __inst>
    inline bool operator==(const __default_alloc_template<__threads, __inst>&,
        const __default_alloc_template<__threads, __inst>&)
    {
        return true;
    }

    template <bool __threads, int __inst>
    inline bool operator!=(const __default_alloc_template<__threads, __inst>&,
        const __default_alloc_template<__threads, __inst>&)
    {
        return false;
    }

    /* We allocate memory in large chunks in order to avoid fragmenting */
    /* the malloc heap too much. */
    /* We assume that size is properly aligned. */
    /* We hold the allocation lock. */
    template <bool __threads, int __inst>
    char*    __default_alloc_template<__threads, __inst>::_S_chunk_alloc(size_t __size, int& __nobjs)
    {
        //::_set_new_handler(_out_of_memory);
        char* __result;
        size_t __total_bytes = __size * __nobjs;
        size_t __bytes_left = _S_end_free - _S_start_free;
        //    enough memory to alloc
        if (__bytes_left >= __total_bytes)
        {
            __result = _S_start_free;
            _S_start_free += __total_bytes;
            return(__result);
        }
        //    only more than __size can be alloc
        else if (__bytes_left >= __size)
        {
            __nobjs = (int)(__bytes_left/__size);
            __total_bytes = __size * __nobjs;
            __result = _S_start_free;
            _S_start_free += __total_bytes;
            return(__result);
        }
        else
        {
            size_t __bytes_to_get = 2 * __total_bytes + _S_round_up(_S_heap_size >> 4);
            // Try to make use of the left-over piece.
            if (__bytes_left > 0)
            {
                _Obj* volatile* __my_free_list = _S_free_list + _S_freelist_index(__bytes_left);
                ((_Obj*)_S_start_free) -> _M_free_list_link = *__my_free_list;
                *__my_free_list = (_Obj*)_S_start_free;
            }
            //    alloc __bytes_to_get again
            _S_start_free = (char*)malloc(__bytes_to_get);

            //    alloc failed
            if (0 == _S_start_free)
            {
                size_t __i;
                _Obj* volatile* __my_free_list;
                _Obj* __p;
                // Try to make do with what we have. That can't
                // hurt. We do not try smaller requests, since that tends
                // to result in disaster on multi-process machines.
                for (__i = __size; __i <= (size_t) _MAX_BYTES; __i += (size_t) _ALIGN)
                {
                    __my_free_list = _S_free_list + _S_freelist_index(__i);
                    __p = *__my_free_list;
                    if (0 != __p)
                    {
                        *__my_free_list = __p -> _M_free_list_link;
                        _S_start_free = (char*)__p;
                        _S_end_free = _S_start_free + __i;
                        return(_S_chunk_alloc(__size, __nobjs));
                        // Any leftover piece will eventually make it to the
                        // right free list.
                    }
                }
                _S_end_free = 0;    // In case of exception.
                _S_start_free = (char*) malloc(__bytes_to_get);
                // This should either throw an
                // exception or remedy the situation. Thus we assume it
                // succeeded.
            }
            _S_heap_size += __bytes_to_get;
            _S_end_free = _S_start_free + __bytes_to_get;
            return(_S_chunk_alloc(__size, __nobjs));
        }
    }

    /* Returns an object of size __n, and optionally adds to size __n free list.*/
    /* We assume that __n is properly aligned. */
    /* We hold the allocation lock. */
    template <bool __threads, int __inst>
    void* __default_alloc_template<__threads, __inst>::_S_refill(size_t __n)
    {
        int __nobjs = 20;
        char* __chunk = _S_chunk_alloc(__n, __nobjs);
        _Obj* volatile* __my_free_list;
        _Obj* __result;
        _Obj* __current_obj;
        _Obj* __next_obj;
        int __i;

        if (1 == __nobjs)
        {
            return(__chunk);
        }
        __my_free_list = _S_free_list + _S_freelist_index(__n);

        /* Build free list in chunk */
        __result = (_Obj*)__chunk;
        *__my_free_list = __next_obj = (_Obj*)(__chunk + __n);
        for (__i = 1; ; __i++)
        {
            __current_obj = __next_obj;
            __next_obj = (_Obj*)((char*)__next_obj + __n);
            if (__nobjs - 1 == __i)
            {
                __current_obj -> _M_free_list_link = 0;
                break;
            }
            else
            {
                __current_obj -> _M_free_list_link = __next_obj;
            }
        }
        return(__result);
    }

    template <bool threads, int inst>
    void* __default_alloc_template<threads, inst>::reallocate(void* __p, size_t __old_sz, size_t __new_sz)
    {
        mutex_lock    __lock;
        __lock.acquire_lock();
        void* __result;
        size_t __copy_sz;

        if (__old_sz > (size_t) _MAX_BYTES && __new_sz > (size_t) _MAX_BYTES)
        {
            __lock.release_lock();
            return(realloc(__p, __new_sz));
        }
        if (_S_round_up(__old_sz) == _S_round_up(__new_sz))
        {
            __lock.release_lock();
            return(__p);
        }
        __result = allocate(__new_sz);
        __copy_sz = __new_sz > __old_sz? __old_sz : __new_sz;
        memcpy(__result, __p, __copy_sz);
        deallocate(__p, __old_sz);
        __lock.release_lock();
        return(__result);
    }

    template< bool threads, int inst >
    char* __default_alloc_template<threads, inst>::_S_start_free = 0;

    template< bool threads, int inst >
    char* __default_alloc_template<threads, inst>::_S_end_free = 0;

    template< bool threads, int inst >
    size_t __default_alloc_template<threads, inst>::_S_heap_size = 0;

    template <bool __threads, int __inst>
    typename __default_alloc_template<__threads, __inst>::_Obj* volatile
        __default_alloc_template<__threads, __inst> ::_S_free_list[_NFREELISTS] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, };

 参考：
    sqi stl