1, Memory pool introduction

1. Introduction to C + + memory pool

Memory pool is a kind of memory allocation method. It is to apply for allocating a certain number of memory blocks of equal size (generally) for standby before using memory. When there is a new memory demand, a part of the memory block is separated from the memory pool. If the memory block is not enough, continue to apply for new memory.

The disadvantages of general memory allocation and release are as follows:

(1) When using malloc/new to apply for heap memory allocation, the system needs to find a free memory in the memory free block table according to the first matching, optimal matching or other algorithms; When using free/delete to free heap memory, the system may need to merge free memory blocks, resulting in additional overhead.

(2) Frequent use will produce a large number of memory fragments, which will reduce the efficiency of the program.

(3) Cause a memory leak.

Memory pool is a common method for memory management instead of directly calling malloc/free and new/delete. When applying for memory space, it will find the appropriate memory block from the memory pool instead of directly applying to the operating system.

The advantages of memory pool technology are as follows:

(1) Heap memory fragmentation is low.
(2) Memory request / release is faster than malloc/new.
(3) Check whether any pointer is in the memory pool.
(4) Write a heap dump to the hard disk.
(5) Memory leak detection: when the allocated memory is not released, the memory pool will throw an assertion.

Memory pools can be divided into variable length memory pools and fixed length memory pools. Typical implementations of variable length memory pools include APR in Apache Portable Runtime_ Pool and obstack in GNU lib C, while the implementation of fixed length memory pool has boost_pool, etc. For variable length memory pools, there is no need to create different memory pools for different data types. Its disadvantage is that the allocated memory cannot be recycled into the pool; For a fixed length memory pool, you can return the memory to the memory pool after use, but you need to create different memory pools for different types of data structures. When you need memory, you need to apply for memory from the corresponding memory pool.

2. Common implementation schemes of C + + memory pool

(1) Fixed size buffer pool
Fixed size buffer pool is suitable for frequent allocation and release of fixed size objects.

(2)dlmalloc

dlmalloc is a memory allocator, written by Doug Lea since 1987. At present, the latest version is 2.8.3. It is widely used and studied because of its high efficiency and other characteristics.

ftp://g.oswego.edu/pub/misc/malloc.c
(3) SGI STL memory allocator

SGI STL allocator is one of the best designed C + + memory allocators at present. Its internal free_ The list [16] array is responsible for managing memory blocks (chunk s) of different sizes from {8 bytes to 128 bytes. Each memory block is composed of consecutive fixed size block s and connected with a pointer linked list.

(4) Loki small object allocator
The Loki allocator uses vector to manage the array. You can specify the size of the fixed size block. free blocks are distributed in a continuous large memory block. free chunks # can automatically increase and reduce the appropriate number according to the usage, so as to avoid too much or too little memory allocation.
(5)Boost object_pool
Boost object_pool can allocate memory blocks according to the size of the user's specific application class, and can be managed by maintaining a linked list of free nodes. The initial memory block of nodes can be increased by 32 times each time. object_ The memory block managed by pool ， needs to be returned to ， system heap when its object is destroyed.
(6)ACE_Cached_Allocator and ACE_Free_List

ACE framework includes a allocator that can maintain fixed size memory blocks_ Cached_ Free is defined in allocator_ List linked list to manage a continuous large memory block. The memory block contains multiple free chunk s of fixed size, and ACE is used at the same time_ unbounded_ Set maintains used chunks.

(7)TCMalloc

Google's open source project gperftools provides a memory pool implementation scheme. https://code.google.com/p/gperftools/

TCMalloc replaces the malloc of the system, which is more optimized at the bottom and has better performance.

3. STL memory allocator

Allocator is a component of C + + standard library. It is mainly used to allocate and release the memory of all given containers (vector, list, map, etc.). The C + + standard library provides a general allocator std::allocator used by default, but developers can customize the allocator.

In addition to the default allocator, GNU STL also provides__ pool_alloc,__ mt_alloc,array_allocator,malloc_allocator memory allocator.

__ pool_alloc: SGI memory pool allocator

__ mt_alloc: multithreaded memory pool allocator

array_allocator: global memory allocation. It is only allocated but not released. It is left to the system for release

malloc_allocator: encapsulation of heap std::malloc and std::free

2, STL allocator

1. Introduction to STL allocator

new will allocate memory and execute the object constructor, and delete will execute the object destructor and free memory. If you separate memory allocation from object construction, you can allocate large blocks of memory first and really execute the object constructor only when needed.

STL provides an allocator class in the header file memory, which allows the separation of allocation and object construction, providing better performance and more flexible memory management. In order to define an allocator object, you must specify the object type that an allocator can assign. When allocator allocates memory, it will determine the appropriate memory size and alignment position according to the given object type.

2. STL allocator interface

The standard interfaces of STL allocator are as follows:

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; };

According to the C + + Standard Specification, the external interface and member variables of the allocator in STL are the same, but the internal implementation of the interface is different.

Allocator is implemented in the template class new_ In 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

}

The default allocator for containers in STL is STD:: allocator<_ TP >, the internal implementation of allocate and deallocate interfaces for memory allocation and release only encapsulates:: operator new and:: operator delete without special processing.

3. STL allocator instance

#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;
    //Apply for three units of Test memory, uninitialized
    Test *pt = alloc.allocate(3);
    {
        //Construction objects, using default values
        alloc.construct(pt, Test());
        //Call copy constructor
        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. Custom allocator

To implement Allocator, you only need to implement allocate and deallocate to implement your own memory allocation strategy.

#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() {  }
    //Different types of allcator s can copy each other
    template <typename V> Allocator(const Allocator<V> &other) { }
    ~Allocator() throw() {  }

    //Maximum number that can be allocated
    size_type max_size() const throw()
    {
        return std::numeric_limits<size_type>::max() / sizeof(T);
    }

    //Allocate memory and return a pointer of this type
    pointer allocate(size_type num)
    {
        return (pointer)(::operator new(num * sizeof(T)));
    }

    //Execute the constructor to build an object
    void construct(pointer p, const T &value)
    {
        new ((void*)p) T(value);
    }

    //Destroy object
    void destroy(pointer p)
    {
        p->~T();
    }

    //Free memory
    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

Test code:

#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[])
{
    //Specify allocator when defining container
    vector<string, Allocator<string> > vec(10, "haha");
    vec.push_back("foo");
    vec.push_back("bar");
    //Assign Test2 type using Test allocator
    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) is a memory allocator supporting multi-threaded applications in STL extension library. It is a fixed size (power of 2) memory allocator designed for multi-threaded applications. At present, it performs equally well in single threaded applications.

mt allocator consists of three parts: parameters describing the characteristics of memory pool; Associate the memory pool to the policy class of the general or special scheme; The actual memory allocator class inherited from the policy class.

(1) Thread support parameter template class

template<bool _Thread>  class __pool;

Indicates whether threads are supported, and then makes explicit specialization for multithreading (bool==true) and single threading (bool==false). Developers can use custom parameters instead.

(2) Memory pool Policy class

General memory pool policy:

__ common_pool_policy implements a general memory pool. Even if the allocated object types are different (such as char and long), the same memory pool is used. It is the default policy.

template<bool _Thread>
struct __common_pool_policy;

Private policy class:

__ per_type_pool_policy will implement a separate memory pool for each object type, so different object types will use different memory pools, and some types can be adjusted separately.

template<typename _Tp, bool _Thread>
struct __per_type_pool_policy;

(3) Memory allocator

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) Memory pool characteristic parameter adjustment

mt allocator provides nested classes for adjusting memory pool parameters_ 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;//Byte alignment
    size_t    _M_max_bytes;//The memory of more than 128 bytes is directly allocated with new
    size_t    _M_min_bin;//The minimum memory block size that can be allocated is 8 bytes
    size_t    _M_chunk_size;//The size of each memory block requested from the os is 4080 bytes
    size_t    _M_max_threads;//The maximum number of threads that can be supported is 4096
    size_t    _M_freelist_headroom;//The percentage of free blocks that can be saved by a single thread is 10%
    bool      _M_force_new;//Whether to directly use new and delete depends on whether to set getenv("GLIBCXX_FORCE_NEW")
};

_ The setting and obtaining interfaces of Tune parameters are as follows:

const _Tune& _M_get_options() const
{
    return _M_options;
}

void _M_set_options(_Tune __t)
{
    if (!_M_init)
        _M_options = __t;
}

Memory pool parameters must be adjusted before any memory allocation action.

Examples of mt allocator are as follows:

#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;
}

If the allocated memory is greater than the value set by the memory pool characteristic parameter, an exception will be thrown or a segment error will be caused.

3, Boost memory pool

1,pool

Pool is a memory pool of Object Usage. Each memory pool is an object that can be created and destroyed. Once the memory pool is destroyed, all its allocated memory will be released, and NULL will be returned in case of overflow.

Pool memory pool is the most basic fixed length memory pool, which can only be used for the allocation of embedded data types (such as int, char, etc.), but not for complex classes and objects. Pool memory pool simply allocates memory without calling the class constructor. For complex classes and objects, object should be used_ Pool memory pool.

The boost::pool interface functions are as follows:

bool release_memory();   

Release all free blocks to the operating system. pool's criterion for idle block is that all chunk s in the block are in the idle linked list and the idle linked list is in order

bool purge_memory(); 

Release all blocks to the operating system, regardless of whether the chunk block in the block is allocated or not; The pool destructor will call to complete the memory release

size_type get_next_size() const;

Gets the size of the next allocated block

size_type set_next_size(const size_type nnext_size);

Set the size of the next allocated block

size_type get_requested_size();

Get the size of each memory block; In bytes

void * malloc();

Allocate a chunk; If there is no space left in the pool for allocation, a new block will be requested from the operating system

void * ordered_malloc();

Allocate a chunk; If there is not enough space for allocation, pool will apply to the operating system for a new block and divide the block into blocks, and then sort the block linked list to ensure the order of memory blocks

void * ordered_malloc(size_type n);

Request n blocks of memory with continuous physical addresses from the memory pool, which can be used to allocate the memory array; The function requires the chunk linked list in a block to be in order. Otherwise, even if there is continuous memory, it is still possible to allocate a new block of memory that fails to be applied for again. Request in memory pool_ Size (the memory block size specified during memory pool initialization) is less than size_type(void *), instead of allocating n chunks, the memory pool allocates ceil(n*request_size/size_type(void *)) chunks of memory

void free(void * const chunk); 

Return the memory requested by malloc to the memory pool

void ordered_free(void * const chunk);

Return the memory applied by malloc to the memory pool and ensure that the free chunk linked list is in order

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

Returns n consecutive blocks of memory starting with chunk to the memory pool

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

Return n consecutive blocks of memory starting with chunk to the memory pool and keep the free chunk linked list in order

bool is_from(void * const chunk) const;  

Judge whether the chunk is released by the memory pool

#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 is a memory pool of Object Usage. Each memory pool is an object that can be created and destroyed. Once the memory pool is destroyed, all its allocated memory will be released, and NULL will be returned in case of overflow.

object_pool object memory pool is applicable to the allocation and release of complex objects. In addition to allocating and releasing memory, object_pool calls the constructor and destructor of the object.

object_ The memory allocation algorithm of pool memory pool is different from that of pool_ The allocation and release of pool memory pool is much slower than that of pool.

object_ The pool interface is as follows:

element_type * malloc();

Allocate a piece of memory and call ordered of pool_ Malloc function;

void free();  

Release a piece of memory and call ordered of pool_ Free function

element_type * construct(); 

Allocate a block of memory and call the constructor

void destroy(element_type * const chunk); 

Destruct an object and return its memory to the memory pool

#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 is a Singleton Usage memory pool. Each memory pool is a statically allocated object that will not be destroyed until the end of the program. NULL will be returned when overflowing.

singleton_ The pool memory pool is thread safe and only release can be used_ Memory or purge_memory method to free memory.

 singleton_pool is the implementation of a singleton mode of pool. Its interface is the same as pool, and the thread safety is guaranteed through the method of mutual exclusion.

4,pool_alloc

pool_alloc is a memory pool of Singleton Usage. An exception is thrown when overflow occurs.

pool_alloc provides two allocators for standard container types: pool_allocator and fast_pool_allocator. However, STL standard container provides its own memory allocator. Generally, STL standard memory allocator should be used for memory allocation instead of pool_ Memory allocator provided by alloc.