目录

1️⃣项目介绍

🍙项目概述

🍙知识储备

2️⃣内存池介绍

🍙池化技术

🍙内存池

🍙内存池主要解决的问题

🍥内碎片

🍥外碎片

🍙malloc

3️⃣ 定长内存池设计

4️⃣ 项目整体框架实现

5️⃣Thread Cache设计

🍙自由链表

🍙对齐映射规则设计

🍥对齐大小计算

🍥映射桶号计算

🍙ThreadCache类

🍥 申请内存

🍣慢开始反馈调节算法

🍥释放内存

🍥TLS(thread local storage)无锁访问 

6️⃣Central Cache设计

🍙SpanList链表结构设计

🍙Central Cache类

🍥申请内存

🍥释放内存

7️⃣Page Cache设计

🍙Page Cache类

🍥映射查找Span

🍥申请内存

🍥释放内存

8️⃣申请释放联调

🍙申请内存联调

🍙释放内存联调

9️⃣大于256Kb大块内存申请释放问题

🍙大块内存申请问题

🍙大块内存释放问题

🔟性能对比及基数树优化

🍙性能对比

🍙性能瓶颈分析

🍙基数树优化

1️⃣项目介绍

🍙项目概述

        本项目设计一个高并发内存池（Concurrent Memory Pool），基于Google开源项目tcmalloc（Thread-Caching Malloc），即线程缓存的malloc，实现了高效的多线程内存管理，可用于替代系统的内存分配函数（malloc、free），Go语言还把tcmalloc做了自己的内存分配器。

        本项目旨在把tcmalloc的核心精华框架部分简化后拿来，自己模拟实现出一个学习版的高并发内存池。

🍙知识储备

2️⃣内存池介绍

🍙池化技术

🍙内存池

🍙内存池主要解决的问题

        内存池首先主要解决效率的问题，系统调用的性能开销是比较大的，当程序对堆的操作比较频繁时，这样做的结果会严重影响程序的性能，所以可以实现一个内存池对内存进行管理，而不是交给内核去进行系统调用。

        其次分配内存时，还要解决内存碎片的问题，内存碎片分为内碎片和外碎片。

🍥内碎片

        内碎片的产生是因为申请内存空间时根据设计的对齐规则导致分配出去的空间有可能会有部分空间未被利用，这些在已经分配出去但未被使用的内存空间就是内碎片。

🍥外碎片

        外碎片的产生是因为2段空间不连续，碎片化，即使有足够的内存空间，也无法申请出来。

🍙malloc

malloc的底层实现（ptmalloc）_z_ryan的博客-CSDN博客

3️⃣ 定长内存池设计

设计一个定长的内存池，为了将申请和释放与malloc分开，本项目要和malloc进行性能比较，那么各处实现就不能调用malloc以及对应的free，new和delete是C++的一个关键字，其底层调用了malloc和free，所以我们要避开使用C++的关键字，自己实现一个New和Delete。

定长内存池设计结构如下：

//定长内存池
template<class T>
class ObjectPool {
public:
	T* New()
	{
		T* obj = nullptr;
		//如果有还回的内存，直接使用还回的内存块
		if (_freeList)
		{
			obj = (T*)_freeList;
			_freeList = *(void**)obj;//内存块中首个指针大小（头4/8字节）存的是下一个还回内存块的地址
		}
		else
		{
			//如果内存块为空或者剩余的内存块不足以继续申请T对象
			if (_remainbytes < sizeof(T))
			{
				_remainbytes = 128 * 1024;//128kb
				_memory = (char*)SystemAlloc(_remainbytes>>PAGE_SHIFT);
				if (_memory == nullptr)
				{
					throw std::bad_alloc();
				}
			}
			obj = (T*)_memory;
			size_t objsize = sizeof(T) < sizeof(void*) ? sizeof(void*) : sizeof(T);
			_memory += objsize;
			_remainbytes -= objsize;
		}
		//使用定位new调用对象的构造函数创建对象，不会自动分配内存
		new(obj)T;
		return obj;
	}

	void Delete(T* obj)
	{
		//因为定位new不会管理内存释放，必须显示调用对象的析构函数
		obj->~T();
		//头插到freeList
		*(void**)obj = _freeList;
		_freeList = obj;
	}
private:
	char* _memory = nullptr;//指向内存块的指针
	void* _freeList = nullptr;//管理还回内存的自由链表 
	int _remainbytes = 0;//内存块中剩余的字节数
};

自由链表取到下一个内存块的地址设计在Thread Cache设计中自由链表模块有详细介绍，定长内存池在Windows下使用系统调用（VirtualAlloc）从堆中申请内存，在Linux下使用brk或mmap。

//堆上申请内存
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32
	void* ptr = VirtualAlloc(0, kpage * (1 << PAGE_SHIFT),
		MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
	// brk mmap等
#endif
	if (ptr == nullptr)
		throw std::bad_alloc();
	return ptr;
}

有了内存还需要创建对象，这里采用定位new来调用对象的构造函数进行创建对象，因为定位new不会管理内存释放，所以我们在释放的时候要显示调用对象的析构函数，对资源进行清理，并且我们的释放实际上并不归还内存，而只是释放资源然后将内存挂在自由链表进行管理。

4️⃣ 项目整体框架实现

高并发内存池（Concurrent Memory Pool）三级缓存：

        ⭐线程缓存（Thread Cache）——无锁

        ⭐中心缓存（Central Cache）——桶锁

        ⭐页缓存（Page Cache）       ——整体锁

设计：Thread Cache分配对象最大256Kb，根据定义的对齐映射规则计算出Thread Cache和Central Cache总桶数为208，Page Cache桶数（按页数）设计为129（0号桶不参与），采取线性映射，最大页数为128，假设1页8Kb，128*8Kb=1Mb,完全够给最大字节256Kb分4个。

static const size_t MAX_BYTES = 256 * 1024;//threadcache最大256kb
static const size_t NFREELISTS = 208;//使用static const代替define，208是根据定义的字节对齐算出的总共桶数
static const size_t NPAGES = 129;//总共Page桶数，128为最大页数，假设1页有8Kb，128*8Kb=1Mb，完全够给最大字节256Kb分4个
static const size_t PAGE_SHIFT = 13;//2^13 页大小8k

5️⃣Thread Cache设计

🍙自由链表

        自由链表管理释放回来的小内存块和中心缓存中分配的未使用的小内存块，结构如下：

         因为自由链表是用来管理小内存块的，所以其必须能够指向下一块小内存，那么当对象的大小＜当前平台指针大小时，需要按指针的大小进行划分。

        关于不同平台的问题，32位平台 指针大小4Byte，64位平台 指针大小8Byte。那么如何设计获取指针大小呢？

*(void**)    获取指针大小地址

//获取结点obj存的下一个结点地址（前4/8字节）,加static仅当前文件可见，防止重定义
static void*& NextObj(void* obj)
{
	return *(void**)obj;
}

        * 解引用本质上是对地址区间进行获取类型大小的内容，比如int*，对int*进行 * 解引用，实际上是获取int类型大小的地址内容，也就是4Byte的内容。

        void**是指针的指针，*（void**），就是对获取void*类型大小的地址内容，此时如果是32位平台就获得了4Byte大小内容，如果是64位平台就获得了8Byte大小内容。

        在Thread Cache中哈希桶每个桶就是一个自由链表，自由链表中一定会有插入、删除、判空等操作，并且我们还可以记录个数_size，_maxSize这个桶最多能挂多少个，那么这么多个自由链表就需要被管理，我们设计一个管理自由链表的结构：

//管理切好的小对象自由链表
class FreeList
{
public:
	void Push(void* obj)
	{
		//头插
		NextObj(obj) = _freeList;
		_freeList = obj;
		++_size;
	}
	void PushRange(void* start, void* end,size_t n)
	{
		NextObj(end) = _freeList;
		_freeList = start;
		_size += n;
	}
	void PopRange(void*& start, void*& end, size_t n)
	{
        //头删
		assert(n >= _size);
		start = _freeList;
		end = start;

		for (size_t i = 0; i < n - 1; i++)
		{
			end = NextObj(end);
		}
		_freeList = NextObj(end);
		NextObj(end) = nullptr;
		_size -= n;
	}
	void* Pop( )
	{
        //头删
		void* obj = _freeList;
		_freeList = NextObj(obj);
		--_size;
		return obj;
	}
	bool Empty()
	{
		return _freeList == nullptr;
	}
	size_t Size()
	{
		return _size;
	}
	size_t& MaxSize()
	{
		return _maxSize;
	}
private:
	void* _freeList = nullptr;
	size_t _maxSize = 1;//自由链表最大个数
	size_t _size = 0;
};

🍙对齐映射规则设计

🍥对齐大小计算

        该设计规则除了第一个桶的内碎片浪费大，保证其他桶内碎片浪费整体保证在10%左右。

        （内碎片浪费率=浪费的字节/分配的字节），比如现在有129字节，就要分配144字节，只使用第一个16byte对齐桶的1个字节，浪费15字节，但总共分配了128+16=144字节，所以内碎片浪费率=15/144=10.4%

        根据设计规则，通过传入参数（字节数），进行简单逻辑判断跳转至子函数_RoundUp进行对齐后的字节数计算。

//对齐大小计算
	static inline size_t RoundUp(size_t bytes)
	{
		assert(bytes <= MAX_BYTES);
		if (bytes <= 128)
		{
			return _RoundUp(bytes, 8);
		}
		else if (bytes <= 1024)
		{
			return _RoundUp(bytes, 16);
		}
		else if (bytes <= 8 * 1024)
		{
			return _RoundUp(bytes, 128);

		}
		else if (bytes <= 64 * 1024)
		{
			return _RoundUp(bytes, 1024);
		}
		else if (bytes <= 256 * 1024)
		{
			return _RoundUp(bytes, 8*1024);
		}
		else
		{
			assert(false);
		}
		return -1;
	}

        对齐后的字节数计算函数（_RoundUp）设计我们学习参考tcmalloc的实现，采用位运算的方式进行，该设计思路十分巧妙，值得我们去学习使用。

	//计算对齐后的bytes大小
	static inline size_t _RoundUp(size_t bytes, size_t alignNum)
	{
		return (bytes + alignNum - 1) & ~(alignNum - 1);
	}

🌰例子:

         bytes=7   alignNum=8
         alignNum-1=7        0000 0111
         ~(alignNum-1)       1111 1000
         7+8-1=15               0000 1111
         &                            0000 1000 = 8 = 对齐后所占大小
       
         bytes=9        alignNum=8
         9+8-1=16               0001 0000
         &                            0001 0000 = 16 = 对齐后所占大小

🍥映射桶号计算

        首先根据上面设计的对齐映射规则，我们可以计算得到对应桶号的区间，利用数组将区间桶号保存，再使用简单逻辑判断进入子函数（_Index）计算当前所在区间映射到的桶号，最终对齐映射的桶号=区间前的桶数+当前区间桶号

//计算映射在哪一个桶
	static inline size_t Index(size_t bytes)
	{
		assert(bytes <= MAX_BYTES);
		//每个字节对齐数区间的最大链数（桶数）
		static int group[4] = { 16,56,56,56 };
		if (bytes <= 128) {
			return _Index(bytes, 3);
		}
		else if (bytes <= 1024) {
			return _Index(bytes - 128, 4) + group[0];
		}
		else if (bytes <= 8 * 1024) {
			return _Index(bytes - 1024, 7) + group[1] + group[0];
		}
		else if (bytes <= 64 * 1024) {
			return _Index(bytes - 8 * 1024, 10) + group[2] + group[1] + group[0];
		}
		else if (bytes <= 256 * 1024) {
			return _Index(bytes - 64 * 1024, 13) + group[3] + group[2] + group[1] + group[0];
		}
		else {
			assert(false);
		}
		return -1;
	}

        同样的在这里学习参考tcmalloc的设计，巧妙使用位运算进行当前区间桶号计算，位运算比算术运算更加高效。

//计算当前对齐大小对应的所在桶号
	static inline size_t _Index(size_t bytes, size_t align_shift)
	{
		return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;
	}

🌰例子：

        [1,8]    align_shift=3    1<<3=8
        ((1+8-1)>>3)-1=0    0号桶
        ...
        ((8+8-1)>>3)-1=0    0号桶
        [9,16]    align_shift=3    1<<3=8
        ((9+8-1)>>3)-1=1    1号桶
        ...
        ((16+8-1)>>3)-1=0    1号桶
        bytes=129    抛去bytes=128前的桶，只剩1bytes，再分配16字节对齐的0号桶,
        总桶号就是前128bytes桶号+当前16bytes的桶号

🍙ThreadCache类

class ThreadCache
{
public:
	// 申请和释放内存对象
	void* Allocate(size_t size);
	void Deallocate(void* ptr, size_t size);

	// 从中心缓存获取对象
	void* FetchFromCentralCache(size_t index, size_t size);

	//释放对象时，链表过长时，回收内存回到中心缓存
	void ListTooLong(FreeList& list, size_t size);

private:
	FreeList _freeLists[NFREELISTS];
};

//TLS——无锁使变量在线程与线程之间独立
static __declspec(thread) ThreadCache* TLS_ThreadCache = nullptr;

🍥 申请内存

//申请内存
void* ThreadCache::Allocate(size_t size)
{
	assert(size <= MAX_BYTES);
	size_t alignSize = AMSize::RoundUp(size);
	size_t index = AMSize::Index(size);

	if (!_freeLists[index].Empty())
	{
		return _freeLists[index].Pop();
	}
	else
	{
		//去中心缓存取
		return FetchFromCentralCache(index,alignSize);
	}
}

//头删
void* Pop( )
	{
		void* obj = _freeList;
		_freeList = NextObj(obj);
		--_size;
		return obj;
	}

void* ThreadCache::FetchFromCentralCache(size_t index,size_t alignSize)
{
	size_t batchNum = min(_freeLists[index].MaxSize(), AMSize::NumMoveSize(alignSize));
	if (_freeLists[index].MaxSize() == batchNum)
	{
		//想修改返回值所以使用引用作为MaxSize返回值
		_freeLists[index].MaxSize() += 1;
	}

	void* start = nullptr;
	void* end = nullptr;
	size_t actualNum = CentralCache::GetInstance()->FetchRangeObj(start, end, batchNum, alignSize);
	assert(actualNum >= 1);

	if (actualNum == 1)
	{
		assert(start == end);
		return start;
	}
	else
	{
		//返回1个(start)，剩下的(从start下一个开始)挂接到桶上
		_freeLists[index].PushRange(NextObj(start), end,actualNum-1);
		return start;
	}
}

     对于需求不同字节大小，从Central Cache获取的分配个数又需要考虑性能， 对于分配8bytes，可以多分配一些（但要有上限），对于256*1024bytes，则少分配些（但要有下限）
采用慢开始反馈调节算法
    1.最开始不会一次向Central Cache一次批量要太多，因为要太多可能用不完
    2.如果不要这个size大小内存需求，那么betchNum就会不断增长直到上限。
    3.size越大，一次向Central Cache要的batchNum就越小
    4.size越小，一次向Central Cache要的batchNum就越大 

🍣慢开始反馈调节算法

// 一次从中心缓存获取多少个
	static size_t NumMoveSize(size_t size)
	{
		assert(size > 0);
		// [2, 512]，一次批量移动多少个对象的(慢启动)上限值
		// 小对象一次批量上限高
		// 小对象一次批量上限低
		int num = MAX_BYTES / size;
		if (num < 2)
			num = 2;
		if (num > 512)
			num = 512;
		return num;
	}

🌰如果只需要8Byte大小，从Central Cache获取批量数就是256*1024/8，其结果大于512，返回512个；如果需要256Kb大小，从Central Cache获取批量数就是256Kb/256Kb=1，其结果小于2，返回2个。

        这样设计批量在于确定上下限，不会使得从中心缓存获取的小块内存过多或过少，如果获取过多，一直不使用，达到一定数量时又会回收给Central Cache，多此一举，所以确定上下限。计算结果在上下限之间的就返回计算个数。

🍥释放内存

//释放内存
void ThreadCache::Deallocate(void* ptr, size_t size)
{
	assert(ptr);
	assert(size <= MAX_BYTES);

	//找到映射的自由链表桶，对象插入进去
	size_t index = AMSize::Index(size);
	_freeLists[index].Push(ptr);

	//当链表长度大于一次批量申请的内存时就开始还一段list给CentralCache 
	if (_freeLists[index].Size() >= _freeLists[index].MaxSize())
	{
		ListTooLong(_freeLists[index], size);
	}
}

void ThreadCache::ListTooLong(FreeList& list, size_t size)
{
	void* start = nullptr;
	void* end = nullptr;
	list.PopRange(start, end, list.MaxSize());

	CentralCache::GetInstance()->ReleaseListToSpans(start, size);
}

start和end在PopRange中是输出型参数，进入PopRange中进行头删将待回收的链表内存对象拿出来返还给Central Cache 。

🍥TLS(thread local storage)无锁访问 

        我们在设计中要求每一个线程都有一个独属于自己的ThreadCache类，如果我们把他ThreadCache类实现为全局的，那么必然每个线程共享这个类，势必会发生竞争问题，需要加锁。

        频繁的控制锁的加锁和解锁会增加时间成本，这显然和我们要的高性能不相符，所以这里提出一个变量存储方法TLS，线程局部存储TLS，该方法下：变量在当前线程下是全局可访问的，在线程和线程之间是独立局部的，这有效的实现了每个线程独属于自己的类，避免加锁。

//TLS——无锁使变量在线程与线程之间独立
static __declspec(thread) ThreadCache* TLS_ThreadCache = nullptr;

我们使用TLS机制，创建一个ThreadCache类指针，进行多线程下创建线程独立的类。该指针在申请和释放联调过程中调用。

6️⃣Central Cache设计

🍙SpanList链表结构设计

Span管理以页为单位大小的大内存块

Span是以页为单位，那么就涉及到一个问题，页号在32位下，最高（2^32）/（2^13）=2^19，2^19我们需要4字节大小来表示，可以用size_t类型可以表示，但如果是64位下，页号最高（2^64）/（2^8）=2^51，我们需要8字节大小来表示，可以用unsigned long long类型。所以我们使用条件编译进行判断使用何种变量：

#ifdef _WIN64
	typedef unsigned long long PAGE_ID;
#elif _WIN32
	typedef size_t PAGE_ID;
#else
	//linux
#endif

细节：64位系统下，包含了宏_WIN32和_WIN64；如果把_WIN32放在最开始判断，那么就无法识别出64位系统，会一直识别为32位，所以我们将_WIN64放在最开始判断64位系统

但实际上size_t在64位下是unsigned long long 或者unsigned _int64类型（范围：[0,2^64 -1]），32位下是unsigned int类型。如果想要编写可移植的代码，应该避免直接使用int或long类型，而是要使用size_t类型。

 所以你也可以简化为：

#ifdef _WIN32
	typedef size_t PAGE_ID;//64位下也有宏_WIN32
#else
	//linux
#endif

Span里存储页号、页数、前后指针、切分小块内存的大小（用于释放的时候传参）、切分好的小块内存的数目（回收对象，如果Span内切分出去的对象全部回收，即_useCount=0，回收Span给PageCache进行页合并）、切好小块内存的自由链表、该Span是否被使用（用以合并Span判断）

struct Span
{
	PAGE_ID _pageId= 0;//大块内存起始页的页号
	size_t _n = 0;//页的数量,本质和PageCache中的SpanList数组（桶）下标一致，可以用来寻找挂接的桶位置

	Span* _next = nullptr;
	Span* _prev = nullptr;

	size_t _objSize = 0;//切好的对象大小
	size_t _useCount = 0;//切好小块内存,分配个thread_cache的计数
	void* _freeList = nullptr;//切好小块内存的自由链表

	bool _isUse = false;//判断是否被使用
};

SpanList带头双向循环链表，其结构如下：（一个头结点以及桶锁）

//带头双向循环链表
class SpanList
{
public:
	SpanList()
	{
		_head = new Span;
		_head->_prev = _head;
		_head->_next = _head;
	}
	Span* Begin()
	{
		return _head->_next;
	}
	Span* End()
	{
		return _head;
	}
	void PushFront(Span* span)
	{
		Insert(Begin(), span);
	}
	void Insert(Span* pos, Span* newSpan)
	{
		assert(pos);
		Span* prev = pos->_prev;

		prev->_next = newSpan;
		newSpan->_prev = prev;
		pos->_prev = newSpan;
		newSpan->_next = pos;
	}
	Span* PopFront( )
	{
		Span* span = _head->_next;
		Erase(span);
		return span;
	}
	void Erase(Span* pos)
	{
		assert(pos);
		assert(pos != _head);//不能删带头结点

		Span* prev = pos->_prev;
		Span* next = pos->_next;

		prev->_next = next;
		next->_prev = prev;
	}
	bool Empty()
	{
		return _head->_next == _head;
	}
private:
	Span* _head;
public:
	std::mutex _mtx;
};

🍙Central Cache类

        Central Cache是所有线程共享的，所以只设计1个，并且当程序运行的时候我们就要创建出来，所以我们用单例模式的饿汉模式。

#pragma once
#include"Common.h"

//因为所有线程对象共用一个CentralCache，
//所以设计成单例模式
class CentralCache
{
public:
	static CentralCache* GetInstance()
	{
		return _pInst;
	}

	//获取一个非空的span
	Span* GetOneSpan(SpanList& list, size_t size);

	//从中心缓存获取一定数量的对象给Thread Cache
	size_t FetchRangeObj(void*& start, void*& end, size_t batchNum, size_t size);

	// 将一定数量的对象释放到span跨度
	void ReleaseListToSpans(void* start, size_t size);


private:
	SpanList _spanLists[NFREELISTS];
private:
	//构造函数私有
	CentralCache()
	{}
	//禁止拷贝构造函数
	CentralCache(const CentralCache&) = delete;
	static CentralCache* _pInst;//声明
};

🍥申请内存

//从中心缓存获取一定数量的对象给Thread Cache
size_t CentralCache::FetchRangeObj(void*& start, void*& end, size_t batchNum, size_t size)
{
	size_t index = AMSize::Index(size);
	_spanLists[index]._mtx.lock();//加桶锁

	Span* span = GetOneSpan(_spanLists[index], size);
	assert(span);
	assert(span->_freeList);

	//从span中获取batchNum个对象，如果不够batchNum个，有多少拿多少
	end = start = span->_freeList;
	size_t i = 0;
	size_t actualNum = 1;
	while (i < batchNum - 1 && NextObj(end) != nullptr)
	{
		end = NextObj(end);
		++i;
		++actualNum;
	}
	//span中内存的自由链表指向分出后的余下内存结点
	span->_freeList = NextObj(end);
	//分出的最后个结点指向空
	NextObj(end) = nullptr;
	span->_useCount += actualNum;

	_spanLists[index]._mtx.unlock();

	return actualNum;
}

        这里使用桶锁，防止多个线程同时访问一个桶，造成线程安全问题。

        并且从Central Cache中的span切分（在GetOne中切分）batchNum对象给Thread Cache，但是可能实际上span并没剩下那么多，只能将剩下的分配给Thread Cache，所以需要统计一个实际值actualNum，_useCount+=actualNum更新span中切分出去的对象，保证回收不会出错。

        返回实际分配到的对象数目，在Thread Cache中返回1个使用，剩余的actualNum头插挂接到Central Cache对应的桶上。

//获取一个非空的span
Span* CentralCache::GetOneSpan(SpanList& list, size_t size)
{
	//查看当前的spanlist这时是否有 未分配对象的span
	Span* it = list.Begin();
	while (it != list.End())
	{
		if (it->_freeList != nullptr)
		{
			return it;
		}
		else
		{
			it = it->_next;
		}
	}
	//先把CentralCache的桶锁解掉，这样如果其他线程释放内存对象回来，不会阻塞
	list._mtx.unlock();

	//走到此说明没有空闲span了，只能找PageCache要
	PageCache::GetInstance()->_pageMtx.lock();
	Span* span=PageCache::GetInstance()->NewSpan(AMSize::NumMovePage(size));
	span->_isUse = true;
	span->_objSize = size;//(小于256Kb)三级缓存中一定是从PageCache中去拿，存储对象大小
	PageCache::GetInstance()->_pageMtx.unlock();

	//切分span并挂接到桶，此时不需要加锁，因为这会其他线程访问不到这个span
	//计算span的大块内存的起始地址和大块内存的大小（字节数）
	char* start = (char*)(span->_pageId << PAGE_SHIFT);
	size_t bytes = span->_n << PAGE_SHIFT;
	char* end = start + bytes;

	//把大块内存切成自由链表链接起来
	//先切一块下来做头，方便尾插，尾插是为了保存地址顺序
	span->_freeList = start;
	start += size;
	void* tail = span->_freeList;

	while (start < end)
	{
		NextObj(tail) = start;
		tail = NextObj(tail);
		start += size;
	}
	//最后一个span内的小内存块指向空
	NextObj(tail) = nullptr;

	//切好span后，挂接到桶需要加锁
	list._mtx.lock();
	list.PushFront(span);

	return span;
}

	static size_t NumMovePage(size_t size)
	{
		size_t num = NumMoveSize(size);
		size_t npage = num * size;	//算出需要的总Byte大小
		npage >>= PAGE_SHIFT;		//总Byte大小/页大小=需要的页数
		if (npage == 0)
			npage = 1;
		return npage;
	}

        从Page Cache中获取到span后，我们通过上面的概念，可以计算出该span的起始地址和尾地址，我们再根据对象大小进行切分，因为内存物理上其实是连续的，而我们这里要在抽象的把他形成链式结构，我们就需要通过尾插来保证地址的连续。切好后将该span挂在Central Cache的桶。

🍥释放内存

// 将一定数量的对象释放到span跨度
void CentralCache::ReleaseListToSpans(void* start, size_t size)
{
	//找到在哪个桶上
	size_t index = AMSize::Index(size);
	_spanLists[index]._mtx.lock();//加锁，因为有桶锁防止多线程竞争
	//回收到span
	while (start)
	{
		void* next = NextObj(start);
		//找到对应的span，小内存（自由链表）头插
		Span* span = PageCache::GetInstance()->MapObjToSpan(start);
		NextObj(start) = span->_freeList;
		span->_freeList = start;
		span->_useCount--;

		//如果为0，说明span切分出的小块内存都回来了，这个span可以再回收给PageCache，再尝试去前后页合并
		if (span->_useCount == 0)
		{
			//从桶里拿掉这个span
			_spanLists[index].Erase(span);
			//知道span的页号就可以知道span的起始地址从而找到整块span，不需要考虑小块内存链表_freeList了
			span->_freeList = nullptr;
			span->_next = nullptr;
			span->_prev = nullptr;

			_spanLists[index]._mtx.unlock();//已经拿掉span了，可以释放桶锁给别人

			PageCache::GetInstance()->_pageMtx.lock();
			PageCache::GetInstance()->ReleaseSpanToPageCache(span);
			PageCache::GetInstance()->_pageMtx.unlock();

			_spanLists[index]._mtx.lock();
		}

		start = next;
	}
	_spanLists[index]._mtx.unlock();
}

🍙Page Cache类

Page Cache我们在设计中也是只有一个， 所以设置成单例模式。

        并且在Page Cache中我们桶的映射规则与上面2级缓存不同，这里采用直接定址法，i号桶挂i页内存。

        桶的个数根据需求而定，我们申请内存最大是256Kb，页大小为8K，也就是说我们要想申请一个256Kb的对象就必须要（256/8=32）32页的span，那么我们可以多分配一些，设置桶个数为128，128页可以申请4个256Kb对象。实际上128页就是1Mb大小。

        页缓存中主要对页进行操作，所以我们有必要对页和span建立一个映射关系，方便我们查找管理，所以使用哈希表unordered_map<PAGE_ID,Span*>

        对页缓存的访问需求实际上很少，所以我们使用一个整体锁来进行管理线程安全即可，避免频繁调用锁，消耗时间。

        在创建Span中，我们使用了最开始设计的定长内存池来申请和释放对象，与new和delete分离。

#pragma once

#include"Common.h"
#include"ObjectPool.h"
//单例模式
class PageCache
{
public:
	static PageCache* GetInstance()
	{
		return _pInst;
	}

	//获取从对象到span的映射
	Span* MapObjToSpan(void* obj);

	//获取一个K页Span
	Span* NewSpan(size_t k);

	// 释放空闲span回到Pagecache，并合并相邻的span
	void ReleaseSpanToPageCache(Span* span);

	std::mutex _pageMtx;//全局锁

private:
	SpanList _spanLists[NPAGES];//页数作桶的映射下标
	std::unordered_map<PAGE_ID, Span*>_idSpanMap;

	ObjectPool<Span>_spanPool;
private:
	PageCache()
	{}
	PageCache(const PageCache&) = delete;
	static PageCache* _pInst;

};

🍥映射查找Span

        根据Central Cache申请内存部分引入的概念，我们可以得知页的起始地址*页大小=页号，我们可以通过这个公式得到页号，然后在哈希表中查找到对应的span。

        这里我们使用RAII原则的unique_lock，构造时加锁，出作用域对象解锁，防止程序异常退出导致死锁，优化代码。

//通过页的起始地址找到页，从而映射找到span
Span* PageCache::MapObjToSpan(void* obj)
{
	//算页号
	PAGE_ID id = (PAGE_ID)obj >> PAGE_SHIFT;

	std::unique_lock<std::mutex>lock(_pageMtx);//RAII思想，构造时加锁，出作用域对象销毁调用析构函数解锁
	查找
	auto ret = _idSpanMap.find(id);
	if (ret != _idSpanMap.end())
	{
		return ret->second;
	}
	else
	{
		assert(false);
		return nullptr;
	}
}

🍥申请内存

//获取一个k页的span
Span* PageCache::NewSpan(size_t k)
{
	assert(k > 0);
	if (k > NPAGES - 1)
	{
		//页数大于128，直接向堆申请
		void* ptr = SystemAlloc(k);
		//Span* span = new Span;
		Span* span=_spanPool.New();
		//页号*页大小=该页的起始地址
		span->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
		span->_n = k;

		_idSpanMap[span->_pageId] = span;//记录pageId和span映射关系,方便释放的时候通过页找到span
		//_idSpanMap.set(span->_pageId, span);//基数树优化
		return span;
	}
	//先检查第k个桶里面有没有span
	if (!_spanLists[k].Empty())
	{
		Span* kSpan= _spanLists[k].PopFront();
		
		//建立id和span的映射，方便CentralCache回收小块内存时，查找对应的span
		for (PAGE_ID i = 0; i < kSpan->_n; i++)
		{
			_idSpanMap[kSpan->_pageId + i] = kSpan;
			//_idSpanMap.set(kSpan->_pageId + i, kSpan);//基数树优化
		}
		return kSpan;//kSpan页返回给CentralCache
	}

	//检查后面桶里有没有span
	for (size_t i = k + 1; i < NPAGES; ++i)
	{
		if (!_spanLists[i].Empty())
		{
			Span* nSpan = _spanLists[i].PopFront();
			//Span* kSpan = new Span;
			Span* kSpan = _spanPool.New();

			//在nSpan的头部切下k页
			//k页span返回给CentralCache；nSpan再挂接到对应映射的位置
			kSpan->_pageId = nSpan->_pageId;
			kSpan->_n = k;

			nSpan->_pageId += k;//更新编号
			nSpan->_n -= k;//既是剩余页数也是映射位置

			_spanLists[nSpan->_n].PushFront(nSpan);//挂接

			//存储nSpan的首尾页号跟nSpan映射，方便PageCache回收内存时进行合并查找
			_idSpanMap[nSpan->_pageId] = nSpan;
			_idSpanMap[nSpan->_pageId + nSpan->_n - 1] = nSpan;//nSpan最后一个页号
			//_idSpanMap.set(nSpan->_pageId, nSpan);
			//_idSpanMap.set(nSpan->_pageId + nSpan->_n - 1, nSpan);//基数树优化

			//建立id和span的映射，方便CentralCache回收小块内存时，查找对应的span
			for (PAGE_ID i = 0; i < kSpan->_n; i++)
			{
				_idSpanMap[kSpan->_pageId+i] = kSpan;
				//_idSpanMap.set(kSpan->_pageId + i, kSpan);//基数树优化
;			}
			return kSpan;//kSpan页返回给CentralCache
		}
	}
	//走到这说明后面没有大页的span，这时需要去堆要一个128页的span
	//Span* bigSpan = new Span;
	Span* bigSpan = _spanPool.New();

	void* ptr = SystemAlloc(NPAGES - 1);
	bigSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
	bigSpan->_n = NPAGES - 1;

	_spanLists[bigSpan->_n].PushFront(bigSpan);

	return NewSpan(k);
}

void PageCache::ReleaseSpanToPageCache(Span* span)
{
	//大于128页，直接还给堆
	if (span->_n > NPAGES - 1)
	{
		void* ptr = (void*)(span->_pageId << PAGE_SHIFT);
		SystemFree(ptr);
		//delete span;
		_spanPool.Delete(span);
		return;
	}
	//尝试span前后页合并，缓解内存外碎片问题
	while (1)
	{
		PAGE_ID prevId = span->_pageId - 1;
		auto ret = _idSpanMap.find(prevId);
		//如果没有前面的页号,不合并了
		if (ret == _idSpanMap.end())
		{
			break;
		}
		//如果前面的相邻页span在使用，不合并了
		Span* prevSpan = ret->second;

		/*auto ret =(Span*) _idSpanMap.get(prevId);
		if (ret == nullptr)
		{
			break;
		}
		Span* prevSpan = ret;*///基数树优化
		if (prevSpan->_isUse == true)
		{
			break;
		}

		//如果合并超过128页的span，没办法管理，不合并了
		if (prevSpan->_n + span->_n > NPAGES - 1)
		{
			break;
		}
		//合并
		span->_pageId = prevSpan->_pageId;
		span->_n += prevSpan->_n;

		//合并了要删除挂接在桶上的prevSpan
		_spanLists[prevSpan->_n].Erase(prevSpan);
		//delete prevSpan;
		_spanPool.Delete(prevSpan);
	}
	while (1)
	{
		PAGE_ID nextId = span->_pageId + span->_n;
		auto ret = _idSpanMap.find(nextId);
		if (ret == _idSpanMap.end())
		{
			break;
		}
		Span* nextSpan = ret->second;

		/*auto ret = (Span*)_idSpanMap.get(nextId);
		if (ret == nullptr)
		{
			break;
		}
		Span* nextSpan = ret;*///基数树优化

		if (nextSpan->_isUse == true)
		{
			break;
		}
		if (span->_n + nextSpan->_n > NPAGES - 1)
		{
			break;
		}
		//合并
		span->_n += nextSpan->_n;

		_spanLists[nextSpan->_n].Erase(nextSpan);
		//delete nextSpan;
		_spanPool.Delete(nextSpan);
	}
	//前后页合并后的span或者无法合并的span挂接到在PageCache对应桶
	_spanLists[span->_n].PushFront(span);
	span->_isUse = false;
	_idSpanMap[span->_pageId] = span;
	_idSpanMap[span->_pageId + span->_n - 1] = span;
	/*_idSpanMap.set(span->_pageId, span);
	_idSpanMap.set(span->_pageId + span->_n - 1, span);*///基数树优化
}

8️⃣申请释放联调

🍙申请内存联调

        接口ConcurrentAlloc联调程序申请内存 ：

static void* ConcurrentAlloc(size_t size)
{

		if (TLS_ThreadCache == nullptr)
		{
			//TLS_ThreadCache = new ThreadCache;
			static ObjectPool<ThreadCache>tcPool;
			TLS_ThreadCache = tcPool.New();
		}
		//cout << std::this_thread::get_id() << ";" << TLS_ThreadCache << endl;
		return TLS_ThreadCache->Allocate(size);
	}
}

🍙释放内存联调

        接口ConcurrentFree联调程序释放内存： 

static void ConcurrentFree(void* ptr)
{
	Span* span = PageCache::GetInstance()->MapObjToSpan(ptr);//通过映射关系找到span
	size_t size = span->_objSize;
	assert(TLS_ThreadCache);
	TLS_ThreadCache->Deallocate(ptr, size);
}

9️⃣大于256Kb大块内存申请释放问题

🍙大块内存申请问题

我们三级缓存的设计主要考虑的是小于256Kb的对象，那如果大于256Kb我们如何处理呢？

• 在Page Cache中我曾提到256Kb需要32页，但我们Page Cache设计的最大有128页。所以如果申请对象大于32页小于等于128页，我们可以直接向Page Cache申请内存
• 如果大于128页，我们就需要向系统堆空间申请内存

修改联调程序：大于256Kb我们就直接去Page Cache

Page Cache中大于128页向堆申请内存，小于等于则继续按逻辑获取页内存。

🍙大块内存释放问题

• 大于128页，直接向堆释放内存
• 小于等于128页则继续走Page Cache逻辑页合并

修改释放联调程序：在这里能看出MapObjToSpan的价值，通过地址就可以映射找到span，并且为了获取存储对象大小，在span结构中增添_objSize。

Page Cache大于128页向堆释放内存。

        并且在申请和释放的对象的过程中，我们使用了定长内存池创建释放对象，不使用new和delete使得可以和malloc进行性能比较。

🔟性能对比及基数树优化

🍙性能对比

        对比多线程下设计的高并发内存池和malloc的性能：分别对相同大小内存和不同大小内存进行申请和释放。

#include"ConcurrentAlloc.h"

void BenchmarkMalloc(size_t ntimes, size_t nworks, size_t rounds)
{
	std::vector<std::thread> vthread(nworks);
	std::atomic<size_t> malloc_costtime = 0;
	std::atomic<size_t> free_costtime = 0;
	for (size_t k = 0; k < nworks; ++k)
	{
		vthread[k] = std::thread([&, k]() {
			std::vector<void*> v;
			v.reserve(ntimes);
			for (size_t j = 0; j < rounds; ++j)
			{
				size_t begin1 = clock();
				for (size_t i = 0; i < ntimes; i++)
				{
					v.push_back(malloc(16));//固定大小内存
					//v.push_back(malloc((16 + i) % 8192 + 1));//不同大小内存
				}
				size_t end1 = clock();
				size_t begin2 = clock();
				for (size_t i = 0; i < ntimes; i++)
				{
					free(v[i]);
				}
				size_t end2 = clock();
				v.clear();
				malloc_costtime += (end1 - begin1);
				free_costtime += (end2 - begin2);
			}
			});
	}
	for (auto& t : vthread)
	{
		t.join();
	}
	printf("%u个线程并发执行%u轮次，每轮次malloc %u次: 花费：%u ms\n",
		nworks, rounds, ntimes, (unsigned int)malloc_costtime);
	printf("%u个线程并发执行%u轮次，每轮次free %u次: 花费：%u ms\n",
		nworks, rounds, ntimes, (unsigned int)free_costtime);
	printf("%u个线程并发malloc&free %u次，总计花费：%u ms\n",
		nworks, nworks * rounds * ntimes, (unsigned int)(malloc_costtime + free_costtime));
}

void BenchmarkConcurrentMalloc(size_t ntimes, size_t nworks, size_t rounds)
{
	std::vector<std::thread> vthread(nworks);
	std::atomic<size_t> malloc_costtime = 0;
	std::atomic<size_t> free_costtime = 0;
	for (size_t k = 0; k < nworks; ++k)
	{
		vthread[k] = std::thread([&]() {
			std::vector<void*> v;
			v.reserve(ntimes);
			for (size_t j = 0; j < rounds; ++j)
			{
				size_t begin1 = clock();
				for (size_t i = 0; i < ntimes; i++)
				{
					//v.push_back(ConcurrentAlloc(16));
					v.push_back(ConcurrentAlloc((16 + i) % 8192 + 1));
				}
				size_t end1 = clock();
				size_t begin2 = clock();
				for (size_t i = 0; i < ntimes; i++)
				{
					ConcurrentFree(v[i]);
				}
				size_t end2 = clock();
				v.clear();
				malloc_costtime += (end1 - begin1);
				free_costtime += (end2 - begin2);
			}
			});
	}
	for (auto& t : vthread)
	{
		t.join();
	}
	printf("%u个线程并发执行%u轮次，每轮次concurrent alloc %u次: 花费：%u ms\n",
		nworks, rounds, ntimes, (unsigned int)malloc_costtime);
	printf("%u个线程并发执行%u轮次，每轮次concurrent dealloc %u次: 花费：%u ms\n",
		nworks, rounds, ntimes, (unsigned int)free_costtime);
	printf("%u个线程并发concurrent alloc&dealloc %u次，总计花费：%u ms\n",
		nworks, nworks * rounds * ntimes, (unsigned int)(malloc_costtime + free_costtime));
}

int main()
{
	size_t n = 1000;
	cout << "==========================================================" << endl;
	BenchmarkConcurrentMalloc(n, 4, 10);
	cout << endl << endl;
	BenchmarkMalloc(n, 4, 10);
	cout << "==========================================================" << endl;
	return 0;
}

• ntimes：单轮申请、释放次数
• nworks：线程数
• rounds：轮次数
• 线程内部使用lambda表达式（C++11新特性），用于定义匿名函数，以值传递捕获k，以引用传递捕获其他父作用域的变量
• 使用原子变量atomic（C++11新特性），不会导致多线程下数据竞争，注意：printf没法直接大于atomic类型对象，需要强转。

测试结果：性能有待优化

🍙性能瓶颈分析

我们使用VS自带的性能探查器进行时间检测。

根据检测结果，我们发现性能瓶颈点在MapObjToSpan的锁竞争上。

🍙基数树优化

        在tcmalloc中实际上在释放内存中对该处使用了基数树优化，那我们也学习使用基数树对我们的程序进行优化。

        单层基数树是直接地址映射法进行直接哈希，也就是说页号与span直接对应。

// 一层基数树（直接哈希）
template <int BITS>
class TCMalloc_PageMap1 {
private:
	static const int LENGTH = 1 << BITS;//页数目，BITS是存储页号需要多少位，假设一页8K=2^13；32位下存储页号需要=(32-13)=19位
	void** array_;//指针数组
public:
	typedef uintptr_t Number;
	explicit TCMalloc_PageMap1( ) {
		size_t bytes = sizeof(void*) << BITS;//需要开辟的字节数
		size_t alignSize = AMSize::_RoundUp(bytes, 1 << PAGE_SHIFT);//bytes>2^18（256*1024），按页大小对齐
		array_ = (void**)SystemAlloc(alignSize >> PAGE_SHIFT);//按页分配内存

		memset(array_, 0, sizeof(void*) << BITS);
	}

	//返回映射值
	void* get(Number k) const {
		if ((k >> BITS) > 0) {//页号不在页数目范围
			return NULL;
		}
		return array_[k];
	}

	//建立映射
	void set(Number k, void* v) {
		array_[k] = v;
	}
};

        非类型模板参数BITS表示存储页号最多需要比特位的个数，32位下最大页号2^19次，此时BITS就是19，数组个数就是2^19，每个存储1个指针，所以数组总大小2^21=2M。

        64位下最大页号2^51次，此时BITS就是51，数组个数就是2^19，每个存储1个指针，所以数字总大小2^54=2^24G，这实在是太大了，所以我们需要继续分层。

        二层基数树实际上就是把BITS进行分层映射，在32位下，用前5比特位映射第一层，得到2^5个，后14位映射到第二层得到该页的span指针。总共占用大小2^5 * 2^14 * 4 =2^21=2M。和一层基数树开辟的大小是一样的，但是二层基数树最开始只需要开辟第一层，当需要某一页号进行映射再开辟第二层，而一层基数树一开始直接开辟全部。

//二层基数树（分层哈希）
template <int BITS>
class TCMalloc_PageMap2 {
private:
	static const int ROOT_BITS = 5;//前5个比特位
	static const int ROOT_LENGTH = 1 << ROOT_BITS;//2^5第一层存储元素个数
	static const int LEAF_BITS = BITS - ROOT_BITS;//19-5=14,剩下14个比特位
	static const int LEAF_LENGTH = 1 << LEAF_BITS;//2^14第二层存储元素个数
	// Leaf node
	struct Leaf {
		void* values[LEAF_LENGTH];
	};
	Leaf* root_[ROOT_LENGTH];

	typedef uintptr_t Number;
	explicit TCMalloc_PageMap2( ) {	
		memset(root_, 0, sizeof(root_));//第一层空间清理
		PreallocateMoreMemory();
	}
	void* get(Number k) const {
		const Number i1 = k >> LEAF_BITS;//k低19位存储页号（合法的高位都是0），右移14位，获取19位中的前5位（[18,14]）确定第一层的下标
		const Number i2 = k & (LEAF_LENGTH - 1);//获取后13位与k与运算获得第二层的下标
		if ((k >> BITS) > 0 || root_[i1] == NULL)// 页号值超过范围或者页号映射的空间未开辟
		{
			return NULL;
		}
		return root_[i1]->values[i2];//返回映射的span指针
	}
	void set(Number k, void* v) {
		const Number i1 = k >> LEAF_BITS;
		const Number i2 = k & (LEAF_LENGTH - 1);
		assert(i1 < ROOT_LENGTH);
		root_[i1]->values[i2] = v;//建立映射
	}
	bool Ensure(Number start, size_t n) {
		for (Number key = start; key <= start + n - 1;) {
			const Number i1 = key >> LEAF_BITS;
			// 检查是否超出第一层下标范围
			if (i1 >= ROOT_LENGTH)
				return false;
			// 开辟空间
			if (root_[i1] == NULL)//第一层i1指向的空间未开辟 
			{
				static ObjectPool<Leaf>LeafPool;
				Leaf* leaf = (Leaf*)LeafPool.New();
				memset(leaf, 0, sizeof(*leaf));
				root_[i1] = leaf;
			}
			//推进叶节点的地址
			key = ((key >> LEAF_BITS) + 1) << LEAF_BITS;//移到下一页空间首地址
		}
		return true;
	}
	void PreallocateMoreMemory() {
		//将第二层空间全部开好
		Ensure(0, 1 << BITS);
	}
};

        设计Ensure函数进行需要页号时再开辟第二层空间，并且全部开辟内存消耗也不多，所以我们在构造的时候就全部开辟出来。

         32位可以使用一层和二层基数树，64位下需要使用三层基数树，分析过程和二层实际一样，省略。   

        本项目只在32位平台使用基数数优化，我们使用单层基数树优化代码：

当我们需要建立映射关系时就调用基数树函数set：

_idSpanMap.set(span->_pageId, span);

当我们需要读取映射关系时就调用基数树函数get：

auto ret = (Span*)_idSpanMap.get(id);

MapObjToSpan函数此时无需加锁：

//通过页的起始地址找到页，从而映射找到span
Span* PageCache::MapObjToSpan(void* obj)
{
	//算页号
	PAGE_ID id = (PAGE_ID)obj >> PAGE_SHIFT;

	auto ret = (Span*)_idSpanMap.get(id);
	assert(ret != nullptr);
	return ret;
}

为什么无需加锁？

MapObjToSpan在进行读操作。

1.只有这两个函数中会去建立id和span的映射，也就是说会去写操作

2.基数树，写之前会提取开好空间，写数据过程中，不会动结构。

3.读写是分离的。线程1对这个位置读写操作时，线程2不可能对这个位置进行读写操作。

        我们不会同时对同一个页进行读取映射和建立映射的操作，因为我们只有在释放对象时才需要读取映射，但是在这个位置地方进行读操作也绝不会进行写操作，因为我们在开始开辟这个位置的时候就已经写操作写好映射了，而建立映射的写操作都是在page cache进行的（页缓存中我们加了一把大锁，更不可能出现写操作的竞争）；也不可能2个线程对同一个位置进行读操作，因为读操作是在释放对象过程中，这期间有桶锁，所以也不可能产生竞争。

再次性能测试，优化结果：多线程场景下性能比malloc好。

本项目最终性能优化后只实现了在32位下运行，如若64位下则不应使用基数树优化。

源码：

https://gitee.com/hao-welcome/ConcurrentMemoryPool