[C++]内存管理器--谈论如何自定义内存分配机制

memory pools, also called fixed-size blocks allocation, is the use of pools for memory management that allows dynamic memory allocation comparable to malloc or c++’s operator new. as those implementations suffer from fragmentation because of variable block sizes, it is not recommendable to use them in a real time system due to performance. a more efficient solution is preallocating a number of memory blocks with the same size called the memory pool. the application can allocate, access, and free blocks represented by handles at run time.
（from wikipedia.）

这段话介绍了内存池的作用。大概就是预先分配一段内存来进行操作，可以简化一个一个分配内存所消耗的时间。

问题产生

in c++ memory pool is abstract data structure for memory allocation in fixed-size block. you should know that, in c++, a new operation is “expensive” because the default std allocator will do the following two things:

call malloc function to allocate memory blocks which needs to traversal the free blocks of the system heap and choose the best blocks for allocation. call the constructor of the object.

it cost a lot of time for operation.

however, a memory pool, say a memory manager here, is a good opportunity for programmers to find out a solution to mange some “frequently” allocating memory blocks manually which is more efficient.

实际上就是说，使用new操作实际上是很低效的。因为编译要在内存空间寻找一块刚好适宜你使用的内存块。这个寻找是非常慢的。在本例中会导致超时。

背景知识

placement syntax

in the c++ programming language, placement syntax allows programmers to explicitly specify the memory management of inpidual objects — i.e. their “placement” in memory. normally, when an object is created dynamically, an allocation function is invoked in such a way that it will both allocate memory for the object, and initialize the object within the newly allocated memory. the placement syntax allows the programmer to supply additional arguments to the allocation function. a common use is to supply a pointer to a suitable region of storage where the object can be initialized, thus separating memory allocation from object construction.

正常的new运算实际上是把分配内存和初始化统一起来的。而占位new可以把这两个操作分隔开来。

the “placement” versions of the new and delete operators and functions are known as placement new and placement delete. a new expression, placement or otherwise, calls a new function, also known as an allocator function, whose name is operator new. similarly, a delete expression calls a delete function, also known as a deallocator function, whose name is operator delete.

就比如说：

char* ptr = new char[sizeof(t)]; // allocate memory
t* tptr = new(ptr) t;            // construct in allocated storage ("place")
tptr->~t();                      // destruct
delete[] ptr;                    // deallocate memory

（如果没有看明白，后面还有更详细的介绍。）

allocator

in c++ computer programming, allocators are an important component of the c++ standard library. the standard library provides several data structures, such as list and set, commonly referred to as containers. a common trait among these containers is their ability to change size during the execution of the program. to achieve this, some form of dynamic memory allocation is usually required. allocators handle all the requests for allocation and deallocation of memory for a given container. the c++ standard library provides general-purpose allocators that are used by default, however, custom allocators may also be supplied by the programmer.

usually, you will find a second parameter in stl containers such as vectror, list and etc. and the stl classes have a default allocator for the template parameter, you do not need to specify it usually. but this time, you need to write a allocator yourself indicate the class memory manager.

比如说以下的例子：

#include 
#include 

namespace mylib {
   template 
   class myalloc {
     public:
       // type definitions
       typedef t        value_type;
       typedef t*       pointer;
       typedef const t* const_pointer;
       typedef t&       reference;
       typedef const t& const_reference;
       typedef std::size_t    size_type;
       typedef std::ptrdiff_t difference_type;

       // rebind allocator to type u
       template 
       struct rebind {
           typedef myalloc other;
       };

       // return address of values
       pointer address (reference value) const {
           return &value;
       }
       const_pointer address (const_reference value) const {
           return &value;
       }

       /* constructors and destructor
        * - nothing to do because the allocator has no state
        */
       myalloc() throw() {
       }
       myalloc(const myalloc&) throw() {
       }
       template 
         myalloc (const myalloc&) throw() {
       }
       ~myalloc() throw() {
       }

       // return maximum number of elements that can be allocated
       size_type max_size () const throw() {
           return std::numeric_limits::max() / sizeof(t);
       }

       // allocate but don't initialize num elements of type t
       pointer allocate (size_type num, const void* = 0) {
           // print message and allocate memory with global new
           std::cerr << "allocate " << num << " element(s)"
                     << " of size " << sizeof(t) << std::endl;
           pointer ret = (pointer)(::operator new(num*sizeof(t)));
           std::cerr << " allocated at: " << (void*)ret << std::endl;
           return ret;
       }

       // initialize elements of allocated storage p with value value
       void construct (pointer p, const t& value) {
           // initialize memory with placement new
           new((void*)p)t(value);
       }

       // destroy elements of initialized storage p
       void destroy (pointer p) {
           // destroy objects by calling their destructor
           p->~t();
       }

       // deallocate storage p of deleted elements
       void deallocate (pointer p, size_type num) {
           // print message and deallocate memory with global delete
           std::cerr << "deallocate " << num << " element(s)"
                     << " of size " << sizeof(t)
                     << " at: " << (void*)p << std::endl;
           ::operator delete((void*)p);
       }
   };

   // return that all specializations of this allocator are interchangeable
   template 
   bool operator== (const myalloc&,
                    const myalloc&) throw() {
       return true;
   }
   template 
   bool operator!= (const myalloc&,
                    const myalloc&) throw() {
       return false;
   }
}

问题产生

在这个程序中我们要求分配十万级的内存，如果使用stl 默认的分配机制一定会超过1s（可以去掉注释看看效果。）所以要想不超时，方法就是自己定义分配机制。

#ifndef stack_alloc_h
#define stack_alloc_h

#include 
#include 

template 
struct stacknode_ {
  t data;
  stacknode_* prev;
};

/** t is the object to store in the stack, alloc is the allocator to use */
template  >
class stackalloc {
 public:
  typedef stacknode_ node;
  typedef typename alloc::template rebind::other allocator;

  /** default constructor */
  stackalloc() { head_ = 0; }
  /** default destructor */
  ~stackalloc() { clear(); }

  /** returns true if the stack is empty */
  bool empty() { return (head_ == 0); }

  /** deallocate all elements and empty the stack */
  void clear() {
    node* curr = head_;
    while (curr != 0) {
      node* tmp = curr->prev;
      allocator_.destroy(curr);
      allocator_.deallocate(curr, 1);
      curr = tmp;
    }
    head_ = 0;
  }

  /** put an element on the top of the stack */
  void push(t element) {
    node* newnode = allocator_.allocate(1);

    allocator_.construct(newnode, node());
    newnode->data = element;

    newnode->prev = head_;

    head_ = newnode;
  }

  /** remove and return the topmost element on the stack */
  t pop() {
    t result = head_->data;
    node* tmp = head_->prev;
    allocator_.destroy(head_);
    allocator_.deallocate(head_, 1);
    head_ = tmp;
    return result;
  }

  /** return the topmost element */
  t top() { return (head_->data); }

 private:
  allocator allocator_;
  node* head_;
};

#endif  // !stack_alloc_h

#include 
#include 
#include 
#include 

#include "memorymanager.hpp"
#include "stackalloc.hpp"

/* adjust these values depending on how much you trust your computer */
 #define elems 520000
#define reps 50

int main() {
  clock_t start;
//  int elems;
//  std::cin >> elems;
//   use the default allocator
//   stackalloc > stackdefault;
//    
//   start = clock();
//   for (int j = 0; j < reps; j++) {
//       
//     assert(stackdefault.empty());
//     for (int i = 0; i < elems / 4; i++) {
//       // unroll to time the actual code and not the loop
//       stackdefault.push(i);
//       stackdefault.push(i);
//       stackdefault.push(i);
//       stackdefault.push(i);
//     }
//     for (int i = 0; i < elems / 4; i++) {
//       // unroll to time the actual code and not the loop
//       stackdefault.pop();
//       stackdefault.pop();
//       stackdefault.pop();
//       stackdefault.pop();
//     }
//   }
//   std::cout << "default allocator time: ";
//   std::cout << (((double)clock() - start) / clocks_per_sec) << "\n\n";

  /* use memorymanager */
  stackalloc > stackpool;
  start = clock();
  for (int j = 0; j < reps; j++) {
    assert(stackpool.empty());

    for (int i = 0; i < elems / 4; i++) {
      // unroll to time the actual code and not the loop
      stackpool.push(i);

      stackpool.push(i);

      stackpool.push(i);

      stackpool.push(i);

    }

    for (int i = 0; i < elems / 4; i++) {
      // unroll to time the actual code and not the loop
      stackpool.pop();

      stackpool.pop();
      stackpool.pop();
      stackpool.pop();
    }
  }

  std::cout << "done processing allocation." << std::endl;
  std::cout << "you can run the program locally to check the difference "
               "between memorymanager and std::alloc"
            << std::endl;
   std::cout << "memorymanager allocator time: ";
   std::cout << (((double)clock() - start) / clocks_per_sec) << "\n\n";

  return 0;
}

补充知识

placement new

这里给出更详细的知识介绍。

placement new是重载operator new的一个标准、全局的版本，它不能被自定义的版本代替（不像普通的operator new和operator delete能够被替换成用户自定义的版本）。

它的原型如下：

void *operator new( size_t, void *p ) throw()  { return p; }

区别new、operator new、placement new

首先我们区分下几个容易混淆的关键词：new、operator new、placement new

new和delete操作符我们应该都用过，它们是对堆中的内存进行申请和释放，而这两个都是不能被重载的。要实现不同的内存分配行为，需要重载operator new，而不是new和delete。

看如下代码：

class myclass {…};

myclass * p=new myclass;

这里的new实际上是执行如下3个过程：

1调用operator new分配内存；

2调用构造函数生成类对象；

3返回相应指针。

operator new就像operator+一样，是可以重载的，但是不能在全局对原型为void operator new(size_t size)这个原型进行重载，一般只能在类中进行重载。如果类中没有重载operator new，那么调用的就是全局的::operator new来完成堆的分配。同理，operator new[]、operator delete、operator delete[]也是可以重载的，一般你重载了其中一个，那么最好把其余三个都重载一遍。

placement new是operator new的一个重载版本，只是我们很少用到它。如果你想在已经分配的内存中创建一个对象，使用new是不行的。也就是说placement new**允许你在一个已经分配好的内存中（栈或堆中）构造一个新的对象。原型中void*p实际上就是指向一个已经分配好的内存缓冲区的的首地址**。

我们知道使用new操作符分配内存需要在堆中查找足够大的剩余空间，这个操作速度是很慢的，而且有可能出现无法分配内存的异常（空间不够）。placement new就可以解决这个问题。我们构造对象都是在一个预先准备好了的内存缓冲区中进行，不需要查找内存，内存分配的时间是常数；而且不会出现在程序运行中途出现内存不足的异常。所以，placement new非常适合那些对时间要求比较高，长时间运行不希望被打断的应用程序。

使用方法如下：

缓冲区提前分配

可以使用堆的空间，也可以使用栈的空间，所以分配方式有如下两种：

class myclass {…}; 
char *buf=new char[n*sizeof(myclass)+ sizeof(int) ] ; 或者char buf[n*sizeof(myclass)+ sizeof(int) ];

对象的构造

myclass * pclass=new(buf) myclass;

对象的销毁

一旦这个对象使用完毕，你必须显式的调用类的析构函数进行销毁对象。但此时内存空间不会被释放，以便其他的对象的构造。

pclass->~myclass();

内存的释放

如果缓冲区在堆中，那么调用delete[] buf;进行内存的释放；如果在栈中，那么在其作用域内有效，跳出作用域，内存自动释放。

注意：

1)在c++标准中，对于placement operator new []有如下的说明： placement operator new[] needs implementation-defined amount of additional storage to save a size of array. 所以我们必须申请比原始对象大小多出sizeof(int)个字节来存放对象的个数，或者说数组的大小。

2)使用方法第二步中的new才是placement new，其实是没有申请内存的，只是调用了构造函数，返回一个指向已经分配好的内存的一个指针，所以对象销毁的时候不需要调用delete释放空间，但必须调用析构函数销毁对象。

---

实际上是可以显式调用构造函数和析构函数的。

这有什么用？

有时候，在对象的生命周期结束前，想先结束这个对象的时候就会派上用场了。

new的时候，其实做了两件事，一是：调用malloc分配所需内存，二是：调用构造函数。

delete的时候，也是做了两件事，一是：调用析造函数，二是：调用free释放内存。

int _tmain(int argc, _tchar* argv[])
{
    myclass* pmyclass = (myclass*)malloc(sizeof(myclass));
     pmyclass->myclass();
    // …
}

编译pmyclass->myclass()出错：

error c2273: ‘function-style cast’ : illegal as right side of ‘->’operator

天啊，它以为myclass是这个类型。

解决办法有两个：

第一：pmyclass->myclass::myclass();

第二：new(pmyclass)myclass();

第二种用法涉及c++ placement new 的用法 。

placement new的作用就是：创建对象(调用该类的构造函数)但是不分配内存，而是在已有的内存块上面创建对象。用于需要反复创建并删除的对象上，可以降低分配释放内存的性能消耗。请查阅placement new相关资料。

显示调用构造函数有什么用？

有时候，你可能由于效率考虑要用到malloc去给类对象分配内存，因为malloc是不调用构造函数的，所以这个时候会派上用场了。

另外下面也是可以的，虽然内置类型没有构造函数。

int* i = (int*)malloc(sizeof(int));
new (i) int();

感觉这些奇奇怪怪的用法最好在写代码库时，为了达到某个目时去使用，不推荐应用开发时使用。

#include 
using namespace std;

class myclass
{
public:
    myclass()
    {
        cout << "constructors" << endl;
    }
    ~myclass()
    {
        cout << "destructors" << endl;
    }

};

int _tmain(int argc, _tchar* argv[])
{
   myclass* pmyclass =  new myclass;
   pmyclass->~myclass();
   delete pmyclass;

}

 

问题解决

#define __stl_nothrow throw()
#include 

template 
class memorymanager {
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;

    template 
    struct rebind {
        typedef memorymanager<_tp1> other;
    };

    memorymanager() __stl_nothrow : _m_pool(null) {}
    memorymanager(const memorymanager&) __stl_nothrow : _m_pool(null) {}
    template 
    memorymanager(const memorymanager<_tp1>&) __stl_nothrow {}
    ~memorymanager() __stl_nothrow {
        chunk_pointer_ curr = _m_pool;
        while (curr != null) {
            chunk_pointer_ prev = curr->next;
            operator delete(reinterpret_cast(curr));
            curr = prev;
        }
    }

    pointer address(reference __x) const { return &__x; }
    const_pointer address(const_reference __x) const { return &__x; }

    _tp* allocate(size_type __n, const void* = 0) {
        if (_m_pool == null) {
            allocateblock();
        }
        pointer result = reinterpret_cast(_m_pool);
        _m_pool = _m_pool->next;
        return result;
    }

    // __p is not permitted to be a null pointer.
    void deallocate(pointer __p, size_type __n) {
        if (__p != null) {
            reinterpret_cast(__p)->next = _m_pool;
            _m_pool = reinterpret_cast(__p);
        }
    }

    size_type max_size() const __stl_nothrow { return size_t(-1) / sizeof(_tp); }

    void construct(pointer __p, const _tp& __val) { new (__p) _tp(__val); }

    void destroy(pointer __p) { __p->~_tp(); }

private:
    union chunk {
        value_type element;
        chunk* next;
    };

    typedef chunk* chunk_pointer_;
    typedef chunk chunk_type_;

    chunk_pointer_ _m_pool;

    void allocateblock() {
        chunk_pointer_ temp =
        reinterpret_cast(operator new(sizeof(_tp)));
        temp->next = _m_pool;
        _m_pool = temp;
    }
};

bool operator==(memorymanager __m_1_,
                memorymanager __m_2_) {
    return true;
}

bool operator!=(memorymanager __m_1_,
                memorymanager __m_2_) {
    return false;
}

总结

对于此题的memorymanager，实际上只在增加元素时分配内存，而不会在删除元素时释放内存，直到最后才一起释放内存。（每删除一个元素，memorymanager的根节点往前移。）在最后，stack还会调用析构函数，把没有删除的匀速删除，经由memorymanager的析构函数一起释放内存。从而避免了内存泄露。直接使用new会因为要找到合适的内存位置而耗费时间，但如果只是选取合适大小的内存位置却不需要太多的时间，从而节省了开销，此题就可以顺利完成。