• ThreadCache线程缓存

    一.ThreadCache整体结构

    1.基本结构

    定长内存池利用一个自由链表管理释放回来的固定大小的内存obj。
    ThreadCache需要支持申请和释放不同大小的内存块，因此需要多个自由链表来管理释放回来的内存块.即ThreadCache实际上一个哈希桶结构，每个桶中存放的都是一个自由链表。

    2.对齐规则和下标索引

    规定ThreadCache支持<=256KB内存的申请，如果我们将每种字节数的内存块都用一个自由链表进行管理的话，那么此时我们就需要20多万个自由链表，光是存储这些自由链表的头指针就需要消耗大量内存，这显然是得不偿失的。  
    这时可以选择做一些平衡的牺牲，让一定区间内的字节数统一为某个size,
    然后用一个桶的自由链表来管理.
    即按照某种规则进行内存对齐(但同时产生内碎片问题)

    二.函数调用层次结构

    //小于等于MAX_BYTES，就找thread cache申请
    //大于MAX_BYTES，就直接找page cache或者系统堆申请
    static const size_t MAX_BYTES = 256 * 1024;
    //thread cache和central cache自由链表哈希桶的表大小
    static const size_t NFREELISTS = 208;

    三.FreeList的封装

    NextObj管理内存obj的前4/8个字节,用来指向下一块内存
        size_t _maxSize = 1;//此时一次申请的最大obj个数
        size_t _size = 0;//自由链表中的内存obj的个数

    1. static void*& NextObj(void* obj)
    2. {
    3. 	return *(void**)obj;
    4. }
    5. // 管理切分好的小对象的自由链表
    6. class FreeList
    7. {
    8. public:
    9. 	void Push(void* obj)
    10. 	{
    11. 		assert(obj);
    12. 		// 头插
    13. 		NextObj(obj) = _freeList;
    14. 		_freeList = obj;
    15.  
    16. 		++_size;
    17. 	}
    18. 	void PushRange(void* start, void* end, size_t n)
    19. 	{
    20. 		NextObj(end) = _freeList;
    21. 		_freeList = start;
    22. 		_size += n;
    23. 	}
    24. 	void PopRange(void*& start, void*& end, size_t n)
    25. 	{
    26. 		assert(n <= _size);
    27. 		start = _freeList;
    28. 		end = start;
    29.  
    30. 		for (size_t i = 0; i < n - 1; ++i)
    31. 		{
    32. 			end = NextObj(end);
    33. 		}
    34.  
    35. 		_freeList = NextObj(end);
    36. 		NextObj(end) = nullptr;
    37. 		_size -= n;
    38. 	}
    39. 	void* Pop()
    40. 	{
    41. 		assert(_freeList);
    42.  
    43. 		// 头删
    44. 		void* obj = _freeList;
    45. 		_freeList = NextObj(obj);
    46. 		--_size;
    47.  
    48. 		return obj;
    49. 	}
    50. 	bool Empty()
    51. 	{
    52. 		return _freeList == nullptr;
    53. 	}
    54. 	size_t& MaxSize()
    55. 	{
    56. 		return _maxSize;
    57. 	}
    58. 	size_t Size()
    59. 	{
    60. 		return _size;
    61. 	}
    62.  
    63. private:
    64. 	void* _freeList = nullptr;
    65. 	size_t _maxSize = 1;//此时一次申请的最大obj个数
    66. 	size_t _size = 0;//自由链表中的内存obj的个数
    67. };

    四.字节数向上对齐规则RoundUp

    1.RoundUp基本逻辑

    1. static inline size_t RoundUp(size_t size)
    2. {
    3. 	if (size <= 128)
    4. 		return _RoundUp(size, 8);
    5. 	else if (size <= 1024)
    6. 		return _RoundUp(size, 16);
    7. 	else if (size <= 8 * 1024)
    8. 		return _RoundUp(size, 128);
    9. 	else if (size <= 64 * 1024)
    10. 		return _RoundUp(size, 1024);
    11. 	else if (size <= 256 * 1024)
    12. 		return _RoundUp(size, 8 * 1024);
    13. 	else
    14. 		return _RoundUp(size, 1 << PAGE_SHIFT);
    15. 	}

    2.子函数_RoundUp

    1. 	size_t _RoundUp(size_t size, size_t alignNum)
    2. 	{
    3. 		size_t alignSize;
    4. 		if (size % alignNum != 0)
    5. 		{
    6. 			alignSize = (size / alignNum + 1)*alignNum;
    7. 		}
    8. 		else
    9. 		{
    10. 			alignSize = size;
    11. 		}
    12.  
    13. 		return alignSize;
    14. 	}

    3.优化为位运算

    1. static inline size_t _RoundUp(size_t bytes, size_t alignNum)
    2. {
    3. 	return ((bytes + alignNum - 1) & ~(alignNum - 1));
    4. }

    五.字节数映射哈希桶下标Index

    1.Index基本逻辑

    1. 	// 计算映射的哪一个自由链表桶
    2. 	static inline size_t Index(size_t bytes)
    3. 	{
    4. 		assert(bytes <= MAX_BYTES);
    5.  
    6. 		// 每个区间有多少个链
    7. 		static int group_array[4] = { 16, 56, 56, 56 };
    8. 		if (bytes <= 128) {
    9. 			return _Index(bytes, 3);
    10. 		}
    11. 		else if (bytes <= 1024) {
    12. 			return _Index(bytes - 128, 4) + group_array[0];
    13. 		}
    14. 		else if (bytes <= 8 * 1024) {
    15. 			return _Index(bytes - 1024, 7) + group_array[1] + group_array[0];
    16. 		}
    17. 		else if (bytes <= 64 * 1024) {
    18. 			return _Index(bytes - 8 * 1024, 10) + group_array[2] + group_array[1] + group_array[0];
    19. 		}
    20. 		else if (bytes <= 256 * 1024) {
    21. 			return _Index(bytes - 64 * 1024, 13) + group_array[3] + group_array[2] + group_array[1] + group_array[0];
    22. 		}
    23. 		else {
    24. 			assert(false);
    25. 		}
    26.  
    27. 		return -1;
    28. 	}

    2.子函数_Index

    1.     size_t _Index(size_t bytes, size_t alignNum)
    2. 	{
    3. 		if (bytes % alignNum == 0)
    4. 		{
    5. 			return bytes / alignNum - 1;
    6. 		}
    7. 		else
    8. 		{
    9. 			return bytes / alignNum;
    10. 		}
    11. 	}

    3.优化为位运算

    1. 	static inline size_t _Index(size_t bytes, size_t align_shift)
    2. 	{
    3. 		return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;
    4. 	}

    六.Allocate申请内存实现

     在ThreadCache申请对象时，通过所给字节数计算出对应的哈希桶下标，如果桶中自由链表不为空，则从该自由链表中pop一个对象进行返回即可；但如果此时自由链表为空，那么我们就需要从CentralCache进行获取了，即FetchFromCentralCache函数

    1. void* ThreadCache::Allocate(size_t size)
    2. {
    3. 	assert(size <= MAX_BYTES);
    4. 	//1.计算对齐后所需内存
    5. 	size_t alignSize = SizeClass::RoundUp(size);
    6. 	//2.计算要挂接的桶的下标
    7. 	size_t index = SizeClass::Index(size);
    8.  
    9. 	if (!_freeLists[index].Empty())
    10. 	{
    11. 		return _freeLists[index].Pop();
    12. 	}
    13. 	else
    14. 	{
    15. 		return FetchFromCentralCache(index, alignSize);
    16. 	}
    17. }

    七.FetchFromCentralCache

    每次ThreadCache向CentralCache申请对象时，我们先通过慢开始反馈调节算法计算出本次应该申请的对象的个数

      如果ThreadCache最终申请到对象的个数就是一个，那么直接将该对象返回即可。
    当ThreadCache中没有对象时,会向CentralCache中获取一个批量的内存obj(避免频繁申请)

    ThreadCache最终申请到的是多个对象，将第一个对象返回后，还需要将剩下的对象挂到ThreadCache对应的哈希桶当中。

    1. void* ThreadCache::FetchFromCentralCache(size_t index, size_t size)
    2. {
    3. 	// 慢开始反馈调节算法
    4. 	// 1、最开始不会一次向CentralCache一次批量要太多，因为要太多了可能用不完
    5. 	// 2、如果你不要这个size大小内存需求，那么batchNum就会不断增长，直到上限
    6. 	// 3、size越大，一次向CentralCache要的batchNum就越小
    7. 	// 4、size越小，一次向CentralCache要的batchNum就越大
    8. 	size_t batchNum = min(_freeLists[index].MaxSize(), SizeClass::NumMoveSize(size));
    9. 	if (_freeLists[index].MaxSize() == batchNum)
    10. 	{
    11. 		_freeLists[index].MaxSize() += 1;
    12. 	}
    13.  
    14. 	void* start = nullptr, * end = nullptr;
    15. 	size_t actualNum = CentralCache::GetInstance()->FetchRangeObj(start, end, batchNum, size);
    16. 	assert(actualNum >= 1);
    17.  
    18. 	if (actualNum == 1)
    19. 	{
    20. 		assert(start == end);
    21. 		return start;
    22. 	}
    23.  
    24. 	_freeLists[index].PushRange(NextObj(start), end, actualNum - 1);
    25. 	return start;
    26. }

    NumMoveSize的实现

    1. 	// 一次thread cache从中心缓存获取多少个
    2. 	static size_t NumMoveSize(size_t size)
    3. 	{
    4. 		assert(size > 0);
    5.  
    6. 		// [2, 512]，一次批量移动多少个对象的(慢启动)上限值
    7. 		// 小对象一次批量上限高
    8. 		// 小对象一次批量上限低
    9. 		int num = MAX_BYTES / size;
    10. 		if (num < 2)
    11. 			num = 2;
    12. 		//[0.5kb,128kb]
    13. 		if (num > 512)
    14. 			num = 512;
    15.  
    16. 		return num;
    17. 	}

    八.Deallocate释放内存实现

     当某个线程申请的对象不用了，可以将其释放给ThreadCache，然后ThreadCache将该对象插入到对应哈希桶的自由链表当中即可。

      但是随着线程不断的释放，对应自由链表的长度也会越来越长，这些内存堆积在一个thread cache中就是一种浪费，我们应该将这些内存还给CentralCache，
    这样一来，这些内存对其他线程来说也是可申请的，因此当ThreadCache某个桶当中的自由链表太长时我们可以进行一些处理。  
    当ThreadCache某个桶当中自由链表的长度超过它一次批量向CentralCache申请的对象个数，那么此时我们就要把该自由链表当中的这些对象还给CentralCache

    1. void ThreadCache::Deallocate(void* obj, size_t size)
    2. {
    3. 	assert(obj);
    4. 	assert(size <= MAX_BYTES);
    5.  
    6. 	//1.将释放的内存还到_freeLists对应的桶中
    7. 	size_t index = SizeClass::Index(size);
    8. 	_freeLists[index].Push(obj);
    9.  
    10. 	//2._freeLists[index]挂的桶数大于最近的一个批量就还给CentralCache
    11. 	if (_freeLists[index].Size() >= _freeLists[index].MaxSize())
    12. 	{
    13. 		//3.从桶中获取一个批量的对象+还给CentralCache
    14. 		ListTooLong(_freeLists[index], size);
    15. 	}
    16. }

    ListTooLong获取内存块批量

    1. void ThreadCache::ListTooLong(FreeList& list, size_t size)
    2. {
    3. 	assert(size > 0);
    4. 	void* start, * end = nullptr;
    5. 	//[begin,end]即为取出的批量
    6. 	//将批量还给CentralCache对应的span
    7. 	list.PopRange(start, end, list.MaxSize());
    8.  
    9. 	CentralCache::GetInstance()->ReleaseListToSpans(start, size);
    10. }

    九.ThreadCacheTLS线程局部存储

      每个线程都有一个自己独享的thread cache，那应该如何创建这个thread cache呢？我们不能将这个thread cache创建为全局的，因为全局变量是所有线程共享的，这样就不可避免的需要锁来控制，增加了控制成本和代码复杂度。  

    要实现每个线程无锁的访问属于自己的thread cache，我们需要用到线程局部存储TLS(Thread Local Storage),使用该存储方法的变量在它所在的线程是全局可访问的，但是不能被其他线程访问到，这样就保持了数据的线程独立性。

    1. //TLS - Thread Local Storage
    2. static _declspec(thread) ThreadCache* pTLSThreadCache = nullptr;

    十.ThreadCache.cpp

    1. #include "ThreadCache.h"
    2. #include "CentralCache.h"
    3.  
    4. void* ThreadCache::FetchFromCentralCache(size_t index, size_t size)
    5. {
    6. 	// 慢开始反馈调节算法
    7. 	// 1、最开始不会一次向CentralCache一次批量要太多，因为要太多了可能用不完
    8. 	// 2、如果你不要这个size大小内存需求，那么batchNum就会不断增长，直到上限
    9. 	// 3、size越大，一次向CentralCache要的batchNum就越小
    10. 	// 4、size越小，一次向CentralCache要的batchNum就越大
    11. 	size_t batchNum = min(_freeLists[index].MaxSize(), SizeClass::NumMoveSize(size));
    12. 	if (_freeLists[index].MaxSize() == batchNum)
    13. 	{
    14. 		_freeLists[index].MaxSize() += 1;
    15. 	}
    16.  
    17. 	void* start = nullptr, * end = nullptr;
    18. 	size_t actualNum = CentralCache::GetInstance()->FetchRangeObj(start, end, batchNum, size);
    19. 	assert(actualNum >= 1);
    20.  
    21. 	if (actualNum == 1)
    22. 	{
    23. 		assert(start == end);
    24. 		return start;
    25. 	}
    26.  
    27. 	_freeLists[index].PushRange(NextObj(start), end, actualNum - 1);
    28. 	return start;
    29. }
    30.  
    31. void* ThreadCache::Allocate(size_t size)
    32. {
    33. 	assert(size <= MAX_BYTES);
    34. 	//1.计算对齐后所需内存
    35. 	size_t alignSize = SizeClass::RoundUp(size);
    36. 	//2.计算要挂接的桶的下标
    37. 	size_t index = SizeClass::Index(size);
    38.  
    39. 	if (!_freeLists[index].Empty())
    40. 	{
    41. 		return _freeLists[index].Pop();
    42. 	}
    43. 	else
    44. 	{
    45. 		return FetchFromCentralCache(index, alignSize);
    46. 	}
    47. }
    48.  
    49. void ThreadCache::Deallocate(void* obj, size_t size)
    50. {
    51. 	assert(obj);
    52. 	assert(size <= MAX_BYTES);
    53.  
    54. 	//1.将释放的内存还到_freeLists对应的桶中
    55. 	size_t index = SizeClass::Index(size);
    56. 	_freeLists[index].Push(obj);
    57.  
    58. 	//2._freeLists[index]挂的桶数大于最近的一个批量就还给CentralCache
    59. 	if (_freeLists[index].Size() >= _freeLists[index].MaxSize())
    60. 	{
    61. 		//3.从桶中获取一个批量的对象+还给CentralCache
    62. 		ListTooLong(_freeLists[index], size);
    63. 	}
    64. }
    65.  
    66. void ThreadCache::ListTooLong(FreeList& list, size_t size)
    67. {
    68. 	assert(size > 0);
    69. 	void* start, * end = nullptr;
    70. 	//[begin,end]即为取出的批量
    71. 	//将批量还给CentralCache对应的span
    72. 	list.PopRange(start, end, list.MaxSize());
    73.  
    74. 	CentralCache::GetInstance()->ReleaseListToSpans(start, size);
    75. }

  • 相关阅读:
    Spring Boot实现通用 Auth 认证的 4 种方式
    六、Vue基础之六
    相爱相杀六年，Elastic终与AWS就商标问题达成共识
    tokenizers总结
    【C语言刷LeetCode】687. 最长同值路径(M)
    大数据项目之电商数仓、Flume安装（完整版）
    【机器学习算法】神经网络与深度学习-8 1.1.1 CNN卷积神经网络（Convolutional neural Networks ）详解
    09.JavaWeb-MyBatis
    选择工业交换机的外壳有什么要求？
    Unity转换字符串中文繁简体
  • 原文地址：https://blog.csdn.net/lzfnb666/article/details/139563462