一、项目介绍

本项目实现的是一个高并发的内存池，其原型是Google的开源项目tcmalloc，tcmalloc全称Thread-Caching Malloc，即线程缓存malloc，实现了高效的多线程内存管理，用于替换系统的内存分配相关函数malloc和free

tcmalloc的知名度也是非常高的，不少公司都在用它，比如Go语言就直接用它做了内存分配器

本项目是将tcmalloc最核心的框架简化后拿出来，模拟实现出一个高并发内存池，目的是为了学习tcamlloc的精华

该项目主要涉及C/C++、数据结构（链表、哈希桶）、操作系统内存管理、单例模式、多线程、互斥锁等方面的技术

二、内存池的初步认识

2.1 池化技术

池化技术，就是程序先向系统申请过量的资源，然后自行进行管理，以备不时之需

之所以要申请过量的资源，是因为申请和释放资源都有较大的开销，不如提前申请一些资源放入"池"中，当需要资源时则可以直接从"池"中获取，不需要时就将该资源重新放回"池"中即可。这样使用时就会变得较为快捷，可以达到提高程序的运行效率的目的

在计算机中，有很多地方都使用了"池"这种技术，如连接池、线程池、对象池等。以服务器上的线程池为例，其主要思想就是：先启动若干数量的线程，让它们处于睡眠状态。当接收到客户端的请求时，再唤醒池中某个睡眠的线程，让它来处理客户端的请求，当处理完这个请求后，线程又进入睡眠状态

2.2 内存池

内存池是指程序预先向操作系统申请一块足够大的内存.此后，当程序中需要申请内存的时候，不需直接向操作系统申请，而是直接从内存池中获取；同理，当释放内存的时候，并不是真正将内存返回给操作系统，而是将内存返回给内存池。当程序退出时（或某个特定时间），内存池才将之前申请的内存真正释放

内存池所解决问题

内存池主要解决的就是效率的问题，其能够避免程序频繁的向系统申请和释放内存。其次，内存池作为系统的内存分配器，还需要尝试解决内存碎片的问题

内存碎片分为内部碎片和外部碎片：

外部碎片是一些空闲的小块内存区域，由于这些内存空间不连续，以至于合计的内存足够，但是不能满足一些内存分配申请需求

内部碎片是由于一些对齐的需求，导致分配出去的空间中一些内存无法被利用

注意： 内存池尝试解决的是外部碎片的问题，同时也尽可能的减少内部碎片的产生

2.3 malloc

C语言中动态申请内存并不是直接向堆申请的，而是通过malloc函数去申请的；C++中的new实际上也是封装了malloc函数

申请内存块时是先调用malloc，malloc再去向操作系统申请内存。malloc实际就是一个内存池，malloc相当于向操作系统"批发"了一块较大的内存空间，然后"零售"给程序用，当全部"售完"或程序有大量的内存需求时，再根据实际需求向操作系统"进货"

malloc的实现方式有很多种，一般情况下不同编译器平台用的是不同的。比如Windows的VS系列中的malloc就是微软自行实现的，而Linux下的gcc用的是glibc中的ptmalloc

三、定长内存池

malloc其实是一个通用的内存池，在什么场景下都适用，但也意味着malloc在什么场景下都不会具有很高的性能，因为malloc并不是针对某种场景专门设计的

定长内存池则是针对固定大小内存块的申请和释放的内存池，由于定长内存池只需要支持固定大小内存块的申请和释放，因此性能可以达到极致，并且在实现定长内存池时不需要考虑内存碎片等问题，因为申请/释放的都是固定大小的内存块

通过实现定长内存池可以熟悉对简单内存池的控制，其次，这个定长内存池也会在后面会作为高并发内存池的一个基础组件(代替new操作符)

实现定长

在实现定长内存池时要做到"定长"有许多方式，比如可以使用非类型模板参数，使得在该内存池中申请到的对象的大小都是N

template<size_t N>
class ObjectPool
{};

定长内存池也可以被称为"对象池"。在创建对象池时，对象池可以根据传入的对象类型的大小来实现"定长"，比如创建定长内存池时传入对象类型int，那么该内存池就只支持 sizeof(int) 字节大小内存的申请和释放

template<class T>
class ObjectPool
{};

向堆区申请内存

既然是内存池，那么首先得向系统申请一块内存空间，然后对其进行管理。要想直接向堆申请内存空间，在Windows下可以调用VirtualAlloc()系统接口；在Linux下可以调用brk()或mmap()系统接口

#ifdef WIN32
  #include <windows.h>
#else
  #include <sys/mman.h>
  #include <unistd.h>
#endif
inline static void* SystemAlloc(size_t kpage)//按页申请内存
{
#ifdef _WIN32
  void* ptr = VirtualAlloc(0, kpage << 13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
  //Linux下brk mmap等
#endif
  if (ptr == nullptr) throw std::bad_alloc();
  return ptr;
}

通过条件编译将对应平台下向堆区申请内存的函数进行封装，此后就不必再关心当前所在平台，当需要直接向堆区申请内存时直接调用封装后的SystemAlloc()函数即可

定长内存池中的成员变量

对于向堆区申请到的大块内存，可以用一个指针来对其进行管理，但仅用一个指针肯定不够，还需要一个变量来记录这块内存的长度

由于此后需要将这块内存进行切分，为了方便切分操作，指向这块内存的指针最好是字符指针，因为指针的类型决定了指针的步长以及查看数据的大小。对于字符指针而言，当需要向后移动n个字节时，直接对字符指针进行加n操作即可

使用完后释放回来的定长内存块也需被管理，可以将这些释放回来的定长内存块链接成一个链表。管理释放回来的内存块的链表被称为自由链表，为了能找到这个自由链表，因此还需要一个指向自由链表的指针

char* _memory = nullptr;//char*便于切割分配内存 指向大块内存
void* _freeList = nullptr;//自由链表 管理归还的内存块
size_t _remainBytes = 0;//记录剩余字节数

管理被释放内存块的具体方案

对于回收的定长内存块，可以使用自由链表将其链接起来，但并不需要为其专门定义链式结构，可以让内存块的前4个字节（32位平台）或8个字节（64位平台）存储后面内存块的起始地址

指针在32位平台上占用4个字节，在64位平台上占用8个字节，那么如何写出既适应32位平台也适应64位平台的代码呢？

当需要访问一个内存块的前4/8个字节时，可以先该内存块的首地址强转为二级指针，由于二级指针存储的是一级指针的地址，二级指针解引用能向后访问一个指针的大小（在32位下为4个字节、64位平台为8个字节，自动适应了环境），此时就访问到了该内存块的前4/8个字节，即下一个内存块的首地址

void*& NextObj(void* ptr) { return *(void**)ptr; }

申请对象

申请对象时，内存池应该优先把还回来的内存块对象再次重复利用，因此若自由链表中有内存块的话，就直接从自由链表中头删一个内存块直接返回即可

若自由链表中没有空闲内存块，那么就在大块内存中切出定长的内存块进行返回。当内存块切出后及时更行 _memory 指针的指向，以及 _remainBytes 的值即可

若大块内存已经不足以切分出一个对象时，就应该调用封装的SystemAlloc()函数，再次向堆申请一块内存空间，此时也要及时更新_memory指针的指向，以及_remainBytes的值（可能存在浪费内存，即所剩内存不足以切出一个对象但_memory却有了新的指向）

由于当内存块释放时需要将内存块链接到自由链表当中，因此必须保证切出来的对象至少能够存储得下一个地址，所以当对象的大小小于当前所在平台指针的大小时，需要按指针的大小进行内存块的切分，即需向上对齐

T* New()
{
  T * obj = nullptr;
  if (_freeList != nullptr)//优先使用分配过的内存
  {
    obj = (T*)_freeList;
    _freeList = *(void**)_freeList;//强转为void**后解引用为void*,即在32位系统下可以看到4个字节，64位系统下可以看到8个字节
  }
  else
  {
    size_t objSize = sizeof(T) > sizeof(void*) ? sizeof(T) : sizeof(void*);//确保至少能存储一个指针大小
    if (_remainBytes < objSize)//大块内存空间不足
    {
      _remainBytes = 128 * 1024;
      _memory = (char*)SystemAlloc(_remainBytes >> 13);
    }
    obj = (T*)_memory;
    _memory += objSize;
    _remainBytes -= objSize;
  }
  new(obj)T;//定位new 调用对象构造函数初始化
  return obj;
}

注意：这是一个定长对象内存池，当内存块切分出来后，应使用定位new，显示调用该对象的构造函数对其进行初始化

释放对象

注意：在释放对象时，应该显示调用该对象的析构函数清理该对象，因为该对象可能还管理着其他某些资源，若不对其进行清理那么这些资源将无法被释放，就会导致内存泄漏

析构后将该内存块头插入_freeList中即可

完整代码

#pragma once
#include <iostream>
using std::cout;
using std::endl;
#ifdef WIN32
  #include <windows.h>
#else
  #include <sys/mman.h>
  #include <unistd.h>
#endif
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32
  void* ptr = VirtualAlloc(0, kpage << 13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
  // linux下brk mmap等
#endif
  if (ptr == nullptr) throw std::bad_alloc();
  return ptr;
}
template <class T>
class ObjectPool
{
public:
  T* New()
  {
    T * obj = nullptr;
    if (_freeList != nullptr)//优先使用分配过的内存
    {
      obj = (T*)_freeList;
      _freeList = *(void**)_freeList;//强转为void**后解引用为void*,即在32位系统下可以看到4个字节，64位系统下可以看到8个字节
    }
    else
    {
      size_t objSize = sizeof(T) > sizeof(void*) ? sizeof(T) : sizeof(void*);//确保至少能存储一个指针大小
      if (_remainBytes < objSize)//大块内存空间不足
      {
        _remainBytes = 128 * 1024;
        _memory = (char*)SystemAlloc(_remainBytes >> 13);
      }
      obj = (T*)_memory;
      _memory += objSize;
      _remainBytes -= objSize;
    }
    new(obj)T;//定位new 调用对象构造函数初始化
    return obj;
  }
  void Delete(T* obj)
  {
    obj->~T();//调用对象析构函数
    *(void**)obj = _freeList;//头插
    _freeList = obj;
  }
private:
  char* _memory = nullptr;//char*便于切割分配内存 指向大块内存
  void* _freeList = nullptr;//自由链表 管理归还的内存块
  size_t _remainBytes = 0;//记录剩余字节数
};

性能对比

在只创建定长对象的情况下，使用下面的代码对new/delete和定长内存池进行性能对比

#include "Object_pool.h"
#include <vector>
#include <ctime>
using std::vector;
struct TreeNode
{
  int _val;
  TreeNode* _left;
  TreeNode* _right;
  TreeNode() :_val(0), _left(nullptr), _right(nullptr) {}
};
void TestObjectPool()
{
  const size_t Rounds = 3;// 申请释放的轮次
  const size_t N = 1000000;// 每轮申请释放多少次
  std::vector<TreeNode*> v1;
  v1.reserve(N);
  size_t begin1 = clock();
  for (size_t j = 0; j < Rounds; ++j)
  {
    for (int i = 0; i < N; ++i) v1.push_back(new TreeNode);
    for (int i = 0; i < N; ++i) delete v1[i];
    v1.clear();
  }
  size_t end1 = clock();
  std::vector<TreeNode*> v2;
  v2.reserve(N);
  ObjectPool<TreeNode> TNPool;
  size_t begin2 = clock();
  for (size_t j = 0; j < Rounds; ++j)
  {
    for (int i = 0; i < N; ++i) v2.push_back(TNPool.New());
    for (int i = 0; i < N; ++i) TNPool.Delete(v2[i]);
    v2.clear();
  }
  size_t end2 = clock();
  cout << "new cost time:" << end1 - begin1 << endl;
  cout << "object pool cost time:" << end2 - begin2 << endl;
}
int main()
{
  TestObjectPool();
  return 0;
}

不难发现，定长内存池消耗的时间比malloc/free消耗的时间要短。这是因为malloc是一个通用的内存池，而定长内存池是专门针对申请定长对象而设计的，因此在这种特殊场景下定长内存池的效率更高

四、整体框架设计介绍

如今很多的开发环境都是多核多线程，因此在申请内存的时，必然存在激烈的锁竞争问题。malloc本身其实已经很优秀了，但是在并发场景下可能会因为频繁的加锁和解锁导致效率有所降低，而该项目的原型tcmalloc实现的就是一种在多线程高并发场景下更胜一筹的内存池

在实现内存池时一般需要考虑到效率问题和内存碎片的问题，但对于高并发内存池来说，还需要考虑在多线程环境下的锁竞争问题

thread_cache： 线程缓存是每个线程独有的，用于小于等于256KB的内存分配，每个线程独享一个thread_cache

central_cache： 中心缓存是所有线程所共享的，当thread_cache需要内存时会按需从central _cache中获取内存，而当thread_cache中的内存满足一定条件时，central_cache也会在合适的时机对其进行回收

page_cache： 页缓存中存储的内存是以页为单位进行存储及分配的，当central_cache需要内存时，page_cache会分配出一定数量的页分配给central_cache，而当central_cache中的内存满足一定条件时，page_cache也会在合适的时机对其进行回收，并将回收的内存尽可能的进行合并，组成更大的连续内存块，缓解内存碎片的问题

解释:

每个线程都有一个属于自己的thread cache，也就意味着线程在thread_cache申请内存时是不需加锁的，而一次性申请大于256KB内存的情况是很少的，因此大部分情况下申请内存时都是无锁的，这也是高并发内存池高效的地方

每个线程的thread cache会根据自己的情况向central cache申请或归还内存，这避免了出现单个线程的thread cache占用太多内存，而其余thread cache出现内存吃紧的问题

多线程的thread cache可能会同时找central cache申请内存，此时就会涉及线程安全的问题，因此在访问central cache时是需要加锁的，但central cache实际上是一个哈希桶的结构，只有当多个线程同时访问同一个桶时才需要加锁，所以这里的锁竞争也不会很激烈

各个模块的作用

thread_cache主要解决锁竞争的问题，每个线程独享thread_cache，当自己的thread_cache中有内存时该线程不会去和其他线程进行竞争，每个线程只要在各自的thread_cache申请内存就行了

central_cache主要起到一个居中调度的作用，每个线程的thread_cache需要内存时从central _cache获取，而当thread_cache的内存多了就会将内存还给central_cache，其作用类似于一个中枢，因此取名为中心缓存

page_cache就负责提供以页为单位的大块内存，当central_cache需要内存时就会去向page_cache申请，而当page_cache没有内存了就会直接去找系统，也就是直接去堆上按页申请内存块