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

   比起那些用大嗓门筹划压抑天下的人，      让全天下都安静下来听你小声语言的人更可畏。        --- 韩寒 《告白与告别》---       

---

  
1 框架计划

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

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

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

1. //自由链表类
2. class FreeList
3. {
4. public:
5.         //进行头插
6.         void Push(void* obj)
7.         {
8.         }
9.         //头删
10.         void* Pop()
11.         {
12.         }
13.         //判断是否为空
14.         bool empty()
15.         {
16.         }
17. private:
18.         //内部是一个指针 指向头结点
19.         void* _freelist = nullptr;
20. };
22. //哈希映射规则类
23. class SizeClass
24. {
25. public:
26.         //计算对齐数
27.         static inline size_t RoundUp(size_t size)
28.         {
29.         }
30.         //计算映射的桶下标
31.         static inline size_t Index(size_t size)
32.         {
33.         }
34. };

复制代码

2. class ThreadCache
3. {
4. public:
5.         //申请空间
6.         void* Allocate(size_t size);
7.         //释放空间
8.         void Deallocate(void* ptr, size_t size);
9.         //向中心缓存申请空间
10.         void* FetchFromCentralCache(size_t  index, size_t alignSize);
11. private:
12.         //哈希映射表
13.         FreeList _freelist[LISTNUM];
14. };

复制代码

2 自由链表类和哈希规则

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

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

1. class FreeList
2. {
3. private:
4.         void* NextObj(void* obj)
5.         {
6.                 return *reinterpret_cast<void**>(obj);
7.         }
8. public:
9.         void Push(void* obj)
10.         {
11.                 //进行头插
12.                 void* next = NextObj(obj);
13.                 next = _freelist;
14.                 _freelist = obj;
15.         }
16.         void* Pop()
17.         {
18.                 //头删
19.                 void* obj = _freelist;
20.                 void* next = NextObj(_freelist);
21.                 _freelist = next;
22.                 return obj;
23.         }
24.         bool empty()
25.         {
26.                 return _freelist == nullptr;
27.         }
28. private:
29.         //内部是一个指针 指向头结点
30.         void* _freelist = nullptr;
31. };

复制代码

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来进行最终的计算，这个就好理解了，首先先减去前面的不同对齐数的空间大小 ，然后计算在该区间属于第几个自由链表，然后在加上前面不同对齐数的链表数！
  

1. class SizeClass
2. {
3. private:
4.         //普通算法
5.         //static inline size_t _RoundUp(size_t size , size_t alignNum)
6.         //{
7.         //        size_t alignsize;
8.         //        //需要向上对齐
9.         //        if (size % alignNum != 0)
10.         //        {
11.         //                alignsize = (size / alignNum + 1) * alignNum;  24 8
12.         //        }
13.         //        //已经对齐
14.         //        else
15.         //        {
16.         //                alignsize = size ;
17.         //        }
18.         //        return alignsize;
19.         //}
20.         //优秀算法
21.         static inline size_t _RoundUp(size_t size, size_t alignnum)
22.         {
23.                 return ~(alignnum - 1) & (size + alignnum - 1);
24.         }
25.         static inline size_t _Index(size_t bytes, size_t align_shift)
26.         {
27.                 //通过字节数返回对应的桶
28.                 //       （ 字节数 + 对齐数 - 1 ）/ 对齐数 - 1
29.                 return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;
30.         }
31. public:
32.         static inline size_t RoundUp(size_t size)
33.         {
34.                 assert(size < MAX_BYTES);
35.                 //通过若干个if语句进行处理
36.                 if (size <= 128)
37.                 {
38.                         //按照8字节对齐
39.                         return _RoundUp(size, 8);
40.                 }
41.                 else if (size <= 1024)
42.                 {
43.                         return _RoundUp(size, 16);
44.                 }
45.                 else if (size <= 8 * 1024)
46.                 {
47.                         return _RoundUp(size, 128);
48.                 }
49.                 else if (size <= 64 * 1024)
50.                 {
51.                         return _RoundUp(size, 1024);
52.                 }
53.                 else if (size <= 256 * 1024)
54.                 {
55.                         return _RoundUp(size, 8*1024);
56.                 }
57.                 else
58.                 {
59.                         assert(false);
60.                         return -1;
61.                 }
63.         }
64.         static inline size_t Index(size_t size)
65.         {
66.                 assert(size < MAX_BYTES);
67.                 int num[5] = { 16 , 56 , 56 , 56 , 24 };
68.                 //通过若干个if语句进行处理
69.                 if (size <= 128)
70.                 {
71.                         //按照8字节对齐
72.                         return _Index(size, 3);
73.                 }
74.                 else if (size <= 1024)
75.                 {
76.                         return _Index(size - 128 , 4) + num[0];
77.                 }
78.                 else if (size <= 8 * 1024)
79.                 {
80.                         return _Index(size - 1024 , 7) + num[0] + num[1];
81.                 }
82.                 else if (size <= 64 * 1024)
83.                 {
84.                         return _Index(size - 8 * 1024, 10) + num[0] + num[1] + num[2];
85.                 }
86.                 else if (size <= 256 * 1024)
87.                 {
88.                         return _Index(size - 64 * 1024, 13) + num[0] + num[1] + num[2] + num[3];
89.                 }
90.                 else
91.                 {
92.                         assert(false);
93.                         return -1;
94.                 }
95.         }
96. };

复制代码

3 实现线程缓存

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

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

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

1. //申请空间
2. void* ThreadCache::Allocate(size_t size)
3. {
4.         //根据RoundUp计算出对齐后的内存大小
5.         size_t alignSize = SizeClass::RoundUp(size);
6.         //根据Index找到对应桶
7.         size_t index = SizeClass::Index(size);
9.         //进行取出数据
10.         if (!_freelist[index].empty())
11.         {
12.                 return _freelist->Pop();
13.         }
14.         else
15.         {
16.                 //向CentralCache申请内存！
17.                 return FetchFromCentralCache(index, alignSize);
18.         }
19. }

复制代码

3.2 释放内存

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

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

复制代码

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

因为我们的项目是要在多线程情况下进行运行，以是要保证线程缓存支持多线程，还要保证线程安全。
现在有个问题：线程缓存是一个类，如何保证每个线程内部都有一个线程缓存！！！
首先肯定是要创建一个全局变量，制止重复构造。但如果只是在主线程中创建一个全局变量，那么就会导致多个线程竞争这个公共资源。那么有没有一种方法可以在线程中创建专属的全局变量，方便进行使用吗、呢？
固然有：TLS（ Thread Local Shortage 线程局部存储）无锁访问线程数据。通过这个我们就可以在线程中创建独属于该线程的全局变量。以是我们可以到场一个TSL全局变量;

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

复制代码

上层进行调用时，先判定pThreadCache是否为空，如果为空那么就创建一个哈希表。反之直接进行使用！这样就制止了使用锁来办理，不需要线程阻塞期待！效率大大提升啊！！！
5 运行测试

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

1. // 线程开辟空间函数
2. // 1. void* ConcurrentAlloc(size_t size)
3. // 2. void  ConcurrentFree(void* ptr)
4. //
5. void* ConcurrentAlloc(size_t size)
6. {
7.         //在该线程中进行内存的申请
8.         if (pThreadCache == nullptr)
9.         {
10.                 pThreadCache = new ThreadCache;
11.         }
12.         //进行开辟空间
13.         void * obj = pThreadCache->Allocate(size);
14.         cout << std::this_thread::get_id() << " : " << pThreadCache << endl;
15.         return obj;
16. }
17. void  ConcurrentFree(void* ptr , size_t size)
18. {
19.         assert(ptr);
20.         //回收空间
21.         pThreadCache->Deallocate(ptr, size);
22. }

复制代码

测试代码：

1. #include"ObjectPool.h"
2. #include"ThreadCache.h"
3. #include"ConcurrentAlloc.h"
4. #include<windows.h>
6. //-------- 线程缓存测试 -------
7. void Alloc1()
8. {
9.         for (size_t i = 0; i < 5; i++)
10.         {
11.                 Sleep(100);
12.                 //申请内存
13.                 ConcurrentAlloc(8);
14.         }
15. }
16. void Alloc2()
17. {
18.         for (size_t i = 0; i < 6; i++)
19.         {
20.                 //申请内存
21.                 ConcurrentAlloc(15);
22.                 Sleep(100);
23.         }
24. }
25. void ThreadCacheTest()
26. {
27.         cout << "---- ThreadCacheTest() Begin! ----" << endl;
28.         std::thread t1(Alloc1);
29.         std::thread t2(Alloc2);
31.         t1.join();
32.         t2.join();
34.         cout << "---- ThreadCacheTest() Done! ----" << endl;
35. }
37. //---------------------------
39. int main()
40. {
41.         //TestObjectPool();
42.         //ThreadCache tc;
43.         ThreadCacheTest();
44.         return 0;
45. }

复制代码

运行结果：

这样就看到每个线程都有对应的资自由链表数组！！！
非常好！！！接下来我们就来实现中心缓存！

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。