【项目日记】高并发内存池---实现线程缓存

在这里插入图片描述

比起那些用大嗓门企图压制世界的人，

让全世界都安静下来听你小声说话的人更可畏。

--- 韩寒《告白与告别》---

高并发内存池项目---实现线程缓存

1 框架设计
2 自由链表类和哈希规则
- 2.1 自由链表类
- 2.2 映射规则
3 实现线程缓存
- 3.1 申请内存
- 3.2 释放内存
4 多线程优化
5 运行测试

1 框架设计

我们需要实现的是一个这样的效果：线程缓存（256KB）中每个空间位置映射到在哈希表上，对应一个自由链表，申请空间时从自由链表中取出一个对象，没有就去中心缓存进行申请！

看起来很容易，但是这一句话之中引出了：

自由链表：这需要我们来设计，可以仿照定长池的回收链表来设计。
哈希映射规则：哈希映射需要很巧妙的进行设计，需要在一个数组中映射出一个大空间中！
多线程优化：因为项目是针对多线程来进行的优化，所以要保证在多线程情况下可以保证效率！
线程缓存类：需要可以申请空间，释放空间，空间不足向上申请空间。

所以大致我们需要设计三个类：自由链表类，哈希规则类，线程缓存类。自由链表类和哈希规则类设置为公有类，方便中心缓存和页缓存使用。

//自由链表类
class FreeList
{
public://进行头插void Push(void* obj){}//头删void* Pop(){}//判断是否为空bool empty(){}
private://内部是一个指针 指向头结点void* _freelist = nullptr;
};//哈希映射规则类
class SizeClass
{
public://计算对齐数static inline size_t RoundUp(size_t size){}//计算映射的桶下标static inline size_t Index(size_t size){}
};


class ThreadCache
{
public://申请空间void* Allocate(size_t size);//释放空间void Deallocate(void* ptr, size_t size);//向中心缓存申请空间void* FetchFromCentralCache(size_t  index, size_t alignSize);
private://哈希映射表FreeList _freelist[LISTNUM];
};

2 自由链表类和哈希规则

我们先来实现自由链表类和哈希规则，这两个类都写入到Common.h头文件中，每个文件都可以进行访问!

2.1 自由链表类

自由链表类主要就是插入和删除。自由链表中每个节点都有一个指针的空间，可以指向后面的节点。通过这个我们就可以写出插入删除的大致逻辑！

class FreeList
{
private:void* NextObj(void* obj){return *reinterpret_cast<void**>(obj);}
public:void Push(void* obj){//进行头插void* next = NextObj(obj);next = _freelist;_freelist = obj;}void* Pop(){//头删void* obj = _freelist;void* next = NextObj(_freelist);_freelist = next;return obj;}bool empty(){return _freelist == nullptr;}
private://内部是一个指针 指向头结点void* _freelist = nullptr;
};

2.2 映射规则

首先我们需要明确如何来进行映射，256KB的空间如果全是8字节对齐的对象，会产生三万多个这可不行！！！
所以需要进行一些特殊处理：并且保证整体最多10%左右的内碎片（由对齐规则导致的内存碎片）浪费：

空间范围	对齐规则	链表中对应位置	个数
[1 , 128]	8 byte对齐	freelist[0,16)	16
[128+1 , 1024]	16 byte对齐	freelist[16,72)	56
[1024+1 , 8*1024]	128 byte对齐	freelist[72,128)	56
[8 * 1024+1 , 64 * 1024]	1024 byte对齐	freelist[128,184)	56
[64 * 1024+1 , 256 *1024]	8*1024 byte对齐	freelist[184,208)	24

我们可以来计算一下内存的浪费率：

申请129字节时，按照对齐规则实际需要144字节的空间，那么就是浪费了15字节，
此时的空间浪费率是 15 / 144 = 0.10。此时是该区间内最坏的情况，

申请8 * 1024 + 1字节时，按照对齐规则需要9216字节的空间，那么就是浪费了1023字节，
此时空间浪费率是1023 / 9216 = 0.11，此时是该区间内最坏的情况，

所以综合来看，空间浪费率是在10%左右！

按照对齐规则可以将[0 , 256 *1024]的空间大小都能够映射到一个自由链表中去申请对齐后的空间。并且这样只需要208个自由链表，远比30000+少多了奥！！！并且我们还保证了10%左右的空间浪费率！

接下来我们就将这段逻辑写成代码：

RoundUp函数：这个函数是用来计算对齐后需要申请空间的大小，按照我们的几个分类写成若干个if条件判断语句，然后再通过子函数_RoundUp来进行最终的计算。进行对齐的计算为：
- 如果不能整除就需要向上对齐（申请空间大小 / 对齐数 + 1）* 对齐数
- 能整除就直接是申请空间大小
- 这里有一种非常巧妙的方法：（对齐数 - 1）取反 &（申请空间大小 + 对齐数 - 1）。
  原理是对齐数 - 1取反后会得到对齐数对应大小的比特位右边的位置全为0！然后申请空间大小 + 对齐数 - 1会得到向上对齐的最大大小，在取交集，就会得到8的倍数的对齐空间大小了！
Index函数：这个函数是用来找到申请空间大小对应的自由链表！同样也按几个分类写出若干个if条件判断语句，然后通过子函数_Index来进行最终的计算，这个就好理解了，首先先减去前面的不同对齐数的空间大小，然后计算在该区间属于第几个自由链表，然后在加上前面不同对齐数的链表数！

class SizeClass
{
private://普通算法//static inline size_t _RoundUp(size_t size , size_t alignNum)//{//	size_t alignsize;//	//需要向上对齐//	if (size % alignNum != 0)//	{//		alignsize = (size / alignNum + 1) * alignNum;  24 8//	}//	//已经对齐//	else//	{//		alignsize = size ;//	}//	return alignsize;//}//优秀算法static inline size_t _RoundUp(size_t size, size_t alignnum){return ~(alignnum - 1) & (size + alignnum - 1);}static inline size_t _Index(size_t bytes, size_t align_shift){//通过字节数返回对应的桶//       （ 字节数 + 对齐数 - 1 ）/ 对齐数 - 1return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;}
public:static inline size_t RoundUp(size_t size){assert(size < MAX_BYTES);//通过若干个if语句进行处理if (size <= 128){//按照8字节对齐return _RoundUp(size, 8);}else if (size <= 1024){return _RoundUp(size, 16);}else if (size <= 8 * 1024){return _RoundUp(size, 128);}else if (size <= 64 * 1024){return _RoundUp(size, 1024);}else if (size <= 256 * 1024){return _RoundUp(size, 8*1024);}else{assert(false);return -1;}}static inline size_t Index(size_t size){assert(size < MAX_BYTES);int num[5] = { 16 , 56 , 56 , 56 , 24 };//通过若干个if语句进行处理if (size <= 128){//按照8字节对齐return _Index(size, 3);}else if (size <= 1024){return _Index(size - 128 , 4) + num[0];}else if (size <= 8 * 1024){return _Index(size - 1024 , 7) + num[0] + num[1];}else if (size <= 64 * 1024){return _Index(size - 8 * 1024, 10) + num[0] + num[1] + num[2];}else if (size <= 256 * 1024){return _Index(size - 64 * 1024, 13) + num[0] + num[1] + num[2] + num[3];}else{assert(false);return -1;}}
};

3 实现线程缓存

我们做好了自由链表和哈希规则之后我们来进行线程缓存的实现！

3.1 申请内存

申请内存的逻辑很简单，首先先通过哈希规则得到对齐后的空间大小和对应桶的下标，有了这两个元素我们就可以来进行申请空间！

该空间大小对应的自由链表中有对象，我们就Pop出来一个就可以了！
该空间大小对应的自由链表中没有对象，就需要向中心内存进行申请一个对齐后看空间大小的空间！

//申请空间
void* ThreadCache::Allocate(size_t size)
{//根据RoundUp计算出对齐后的内存大小size_t alignSize = SizeClass::RoundUp(size);//根据Index找到对应桶size_t index = SizeClass::Index(size);//进行取出数据if (!_freelist[index].empty()){return _freelist->Pop();}else{//向CentralCache申请内存！return FetchFromCentralCache(index, alignSize);}
}

3.2 释放内存

释放内存的逻辑更加简单，将需要释放的对象空间直接Push到空间大小对应的自由链表中就可以了

//释放空间
void ThreadCache::Deallocate(void* ptr, size_t size)
{assert(ptr);assert(size < MAX_BYTES);//根据Index找到对应桶size_t index = SizeClass::Index(size);_freelist[index].Push(ptr);}

这样我们就实现了线程缓存的部分！！！向中心缓存申请的部分还要等到完成中心缓存才可以进行联动！

4 多线程优化

因为我们的项目是要在多线程环境下进行运行，所以要保证线程缓存支持多线程，还要保证线程安全。
现在有个问题：线程缓存是一个类，如何保证每个线程内部都有一个线程缓存！！！
首先肯定是要建立一个全局变量，避免重复构造。但如果只是在主线程中建立一个全局变量，那么就会导致多个线程竞争这个公共资源。那么有没有一种方法可以在线程中建立专属的全局变量，方便进行使用吗、呢？

当然有：TLS（ Thread Local Shortage 线程局部存储）无锁访问线程数据。通过这个我们就可以在线程中建立独属于该线程的全局变量。所以我们可以加入一个TSL全局变量;

//TLS（ Thread Local Shortage 线程局部存储）无锁访问线程数据
//该写法仅限于VS系列编译器
_declspec(thread) static ThreadCache* pThreadCache = nullptr;

上层进行调用时，先判断pThreadCache是否为空，如果为空那么就创建一个哈希表。反之直接进行使用！这样就避免了使用锁来解决，不需要线程阻塞等待！效率大大提升啊！！！

5 运行测试

为了保证项目的没有BUG，我们要及时进行测试，我们完成了线程缓存，就要保证线程缓存没有问题：
我们先写一下高并发内存池申请内存的接口，将线程缓存使用起来！

// 线程开辟空间函数
// 1. void* ConcurrentAlloc(size_t size)
// 2. void  ConcurrentFree(void* ptr)
// 
void* ConcurrentAlloc(size_t size)
{//在该线程中进行内存的申请if (pThreadCache == nullptr){pThreadCache = new ThreadCache;}//进行开辟空间void * obj = pThreadCache->Allocate(size);cout << std::this_thread::get_id() << " : " << pThreadCache << endl;return obj;
}
void  ConcurrentFree(void* ptr , size_t size)
{assert(ptr);//回收空间pThreadCache->Deallocate(ptr, size);
}

测试代码：

#include"ObjectPool.h"
#include"ThreadCache.h"
#include"ConcurrentAlloc.h"
#include<windows.h>//-------- 线程缓存测试 -------
void Alloc1()
{for (size_t i = 0; i < 5; i++){Sleep(100);//申请内存ConcurrentAlloc(8);}
}
void Alloc2()
{for (size_t i = 0; i < 6; i++){//申请内存ConcurrentAlloc(15);Sleep(100);}
}
void ThreadCacheTest()
{cout << "---- ThreadCacheTest() Begin! ----" << endl;std::thread t1(Alloc1);std::thread t2(Alloc2);t1.join();t2.join();cout << "---- ThreadCacheTest() Done! ----" << endl;
}//---------------------------int main()
{//TestObjectPool();//ThreadCache tc;ThreadCacheTest();return 0;
}