【项目设计】高并发内存池(七)[性能测试和提升]

红太狼 2024-04-20 06:50 62阅读 0赞

> **?C++学习历程：入门**
> 
> --------------------
> 
>  *  **博客主页：**[一起去看日落吗][Link 1]
>  *  **持续分享博主的C++学习历程**
>  *  **`博主的能力有限，出现错误希望大家不吝赐教`**
>  *  **分享给大家一句我很喜欢的话：** 也许你现在做的事情，暂时看不到成果，但不要忘记，树?成长之前也要扎根，也要在漫长的时光?中沉淀养分。静下来想一想，哪有这么多的天赋异禀，那些让你羡慕的优秀的人也都曾默默地翻山越岭?。
> 
> --------------------
> 
> ![在这里插入图片描述][eabca17da9704379a5f15832a495b4cc.jpeg_pic_center]

? ? ? ?

--------------------

#### 目录 ####

*  ?1. 性能瓶颈分析
 *  ?2. 针对性能瓶颈使用基数树进行优化
 *  ?3. 使用基数树进行优化代码实现

## ?1. 性能瓶颈分析 ##

经过前面的测试可以看到，我们的代码此时与malloc之间还是有差距的，此时我们就应该分析分析我们当前项目的瓶颈在哪里，但这不能简单的凭感觉，我们应该用性能分析的工具来进行分析。

*  **VS编译器下性能分析的操作步骤**

VS编译器中就带有性能分析的工具的，我们可以依次点击“调试→性能和诊断”进行性能分析，注意该操作要在Debug模式下进行。

同时我们将代码中n的值由10000调成了1000，否则该分析过程可能会花费较多时间，并且将malloc的测试代码进行了屏蔽，因为我们要分析的是我们实现的高并发内存池。

在点击了“调试→性能和诊断”后会弹出一个提示框，我们直接点击“开始”进行了。

![在这里插入图片描述][56038f69a2aa4ac7874633f7763a1953.png]  
然后会弹出一个选项框，这里我们选择的是第二个，因为我们要分析的是各个函数的用时时间，然后点击下一步。

出现以下选项框继续点击下一步。

最后点击完成，就可以等待分析结果了。

*  **分析性能瓶颈**

通过分析结果可以看到，光是Deallocate和MapObjectToSpan这两个函数就占用了一半多的时间。

![在这里插入图片描述][b0f147488a2442ebb8c2001d65e9bc7e.png]  
而在Deallocate函数中，调用ListTooLong函数时消耗的时间是最多的。

![在这里插入图片描述][411361fa366c45e7aec8c4638d983acf.png]  
在ListTooLong函数中，调用ReleaseListToSpans函数时消耗的时间是最多的。

![在这里插入图片描述][d8ff2b8b19e840ec9391672193c516bd.png]

在ReleaseListToSpans函数中，调用MapObjectToSpan函数时消耗的时间是最多的。

![在这里插入图片描述][a3b1589bb19d4554bbb71bf11eab3a1a.png]

也就是说，最终消耗时间最多的实际就是MapObjectToSpan函数，我们这时再来看看为什么调用MapObjectToSpan函数会消耗这么多时间。通过观察我们最终发现，调用该函数时会消耗这么多时间就是因为锁的原因。

![在这里插入图片描述][e9d755ada6374af78d0a1fb5034822a0.png]  
因此当前项目的瓶颈点就在锁竞争上面，需要解决调用MapObjectToSpan函数访问映射关系时的加锁问题。tcmalloc当中针对这一点使用了基数树进行优化，使得在读取这个映射关系时可以做到不加锁。

--------------------

## ?2. 针对性能瓶颈使用基数树进行优化 ##

基数树实际上就是一个分层的哈希表，根据所分层数不同可分为单层基数树、二层基数树、三层基数树等。

*  **单层基数树**

单层基数树实际采用的就是直接定址法，每一个页号对应span的地址就存储数组中在以该页号为下标的位置。

![在这里插入图片描述][ffcc630b2f0e4ef8a32e6cc594d1afb0.png]

最坏的情况下我们需要建立所有页号与其span之间的映射关系，因此这个数组中元素个数应该与页号的数目相同，数组中每个位置存储的就是对应span的指针。

//单层基数树
    template <int BITS>
    class TCMalloc_PageMap1
    {
        
    public:
    	typedef uintptr_t Number;
    	explicit TCMalloc_PageMap1()
    	{
        
    		size_t size = sizeof(void*) << BITS; //需要开辟数组的大小
    		size_t alignSize = SizeClass::_RoundUp(size, 1 << PAGE_SHIFT); //按页对齐后的大小
    		array_ = (void**)SystemAlloc(alignSize >> PAGE_SHIFT); //向堆申请空间
    		memset(array_, 0, size); //对申请到的内存进行清理
    	}
    	void* get(Number k) const
    	{
        
    		if ((k >> BITS) > 0) //k的范围不在[0, 2^BITS-1]
    		{
        
    			return NULL;
    		}
    		return array_[k]; //返回该页号对应的span
    	}
    	void set(Number k, void* v)
    	{
        
    		assert((k >> BITS) == 0); //k的范围必须在[0, 2^BITS-1]
    		array_[k] = v; //建立映射
    	}
    private:
    	void** array_; //存储映射关系的数组
    	static const int LENGTH = 1 << BITS; //页的数目
    };

此时当我们需要建立映射时就调用set函数，需要读取映射关系时，就调用get函数就行了。

代码中的非类型模板参数BITS表示存储页号最多需要比特位的个数。在32位下我们传入的是32-PAGE\_SHIFT，在64位下传入的是64-PAGE\_SHIFT。而其中的LENGTH成员代表的就是页号的数目，即 22BITS

比如32位平台下，以一页大小为8K为例，此时页的数目就是232 / 213 = 2 19 , 因此存储页号最多需要19个比特位，此时传入非类型模板参数的值就是 32 − 13 = 19。由于32位平台下指针的大小是4字节，因此该数组的大小就是219 *x* 4 = 2M ,内存消耗不大，是可行的。但如果是在64位平台下，此时该数组的大小是251 *x* 8 = 224G,这显然是不可行的，实际上对于64位的平台，我们需要使用三层基数树。

*  **二层基数树**

这里还是以32位平台下，一页的大小为8K为例来说明，此时存储页号最多需要19个比特位。而二层基数树实际上就是把这19个比特位分为两次进行映射。

比如用前5个比特位在基数树的第一层进行映射，映射后得到对应的第二层，然后用剩下的比特位在基数树的第二层进行映射，映射后最终得到该页号对应的span指针。

![在这里插入图片描述][50c86581f4c44663bd1132fae796947f.png]  
在二层基数树中，第一层的数组占用25 *x* = 27 Byte 空间，第二层的数组最多占用25 *x* 214 *x* 4 = 221 = 2M。二层基数树相比一层基数树的好处就是，一层基数树必须一开始就把 2M 的数组开辟出来，而二层基数树一开始时只需将第一层的数组开辟出来，当需要进行某一页号映射时再开辟对应的第二层的数组就行了。

//二层基数树
    template <int BITS>
    class TCMalloc_PageMap2
    {
        
    private:
    	static const int ROOT_BITS = 5;                //第一层对应页号的前5个比特位
    	static const int ROOT_LENGTH = 1 << ROOT_BITS; //第一层存储元素的个数
    	static const int LEAF_BITS = BITS - ROOT_BITS; //第二层对应页号的其余比特位
    	static const int LEAF_LENGTH = 1 << LEAF_BITS; //第二层存储元素的个数
    	//第一层数组中存储的元素类型
    	struct Leaf
    	{
        
    		void* values[LEAF_LENGTH];
    	};
    	Leaf* root_[ROOT_LENGTH]; //第一层数组
    public:
    	typedef uintptr_t Number;
    	explicit TCMalloc_PageMap2()
    	{
        
    		memset(root_, 0, sizeof(root_)); //将第一层的空间进行清理
    		PreallocateMoreMemory(); //直接将第二层全部开辟
    	}
    	void* get(Number k) const
    	{
        
    		const Number i1 = k >> LEAF_BITS;        //第一层对应的下标
    		const Number i2 = k & (LEAF_LENGTH - 1); //第二层对应的下标
    		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; //建立该页号与对应span的映射
    	}
    	//确保映射[start,start_n-1]页号的空间是开辟好了的
    	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函数，当需要建立某一页号与其span之间的映射关系时，需要先调用该Ensure函数确保用于映射该页号的空间是开辟了的，如果没有开辟则会立即开辟。

而在32位平台下，就算将二层基数树第二层的数组全部开辟出来也就消耗了 2 M 2M 2M的空间，内存消耗也不算太多，因此我们可以在构造二层基数树时就把第二层的数组全部开辟出来。

*  **三层基数树**

上面一层基数树和二层基数树都适用于32位平台，而对于64位的平台就需要用三层基数树了。三层基数树与二层基数树类似，三层基数树实际上就是把存储页号的若干比特位分为三次进行映射。

![在这里插入图片描述][bf9a126a8c3d494c97609346d0e607de.png]  
此时只有当要建立某一页号的映射关系时，再开辟对应的数组空间，而没有建立映射的页号就可以不用开辟其对应的数组空间，此时就能在一定程度上节省内存空间。

//三层基数树
    template <int BITS>
    class TCMalloc_PageMap3
    {
        
    private:
    	static const int INTERIOR_BITS = (BITS + 2) / 3;       //第一、二层对应页号的比特位个数
    	static const int INTERIOR_LENGTH = 1 << INTERIOR_BITS; //第一、二层存储元素的个数
    	static const int LEAF_BITS = BITS - 2 * INTERIOR_BITS; //第三层对应页号的比特位个数
    	static const int LEAF_LENGTH = 1 << LEAF_BITS;         //第三层存储元素的个数
    	struct Node
    	{
        
    		Node* ptrs[INTERIOR_LENGTH];
    	};
    	struct Leaf
    	{
        
    		void* values[LEAF_LENGTH];
    	};
    	Node* NewNode()
    	{
        
    		static ObjectPool<Node> nodePool;
    		Node* result = nodePool.New();
    		if (result != NULL)
    		{
        
    			memset(result, 0, sizeof(*result));
    		}
    		return result;
    	}
    	Node* root_;
    public:
    	typedef uintptr_t Number;
    	explicit TCMalloc_PageMap3()
    	{
        
    		root_ = NewNode();
    	}
    	void* get(Number k) const
    	{
        
    		const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS);         //第一层对应的下标
    		const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH - 1); //第二层对应的下标
    		const Number i3 = k & (LEAF_LENGTH - 1);                    //第三层对应的下标
    		//页号超出范围，或映射该页号的空间未开辟
    		if ((k >> BITS) > 0 || root_->ptrs[i1] == NULL || root_->ptrs[i1]->ptrs[i2] == NULL)
    		{
        
    			return NULL;
    		}
    		return reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3]; //返回该页号对应span的指针
    	}
    	void set(Number k, void* v)
    	{
        
    		assert(k >> BITS == 0);
    		const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS);         //第一层对应的下标
    		const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH - 1); //第二层对应的下标
    		const Number i3 = k & (LEAF_LENGTH - 1);                    //第三层对应的下标
    		Ensure(k, 1); //确保映射第k页页号的空间是开辟好了的
    		reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3] = v; //建立该页号与对应span的映射
    	}
    	//确保映射[start,start+n-1]页号的空间是开辟好了的
    	bool Ensure(Number start, size_t n)
    	{
        
    		for (Number key = start; key <= start + n - 1;)
    		{
        
    			const Number i1 = key >> (LEAF_BITS + INTERIOR_BITS);         //第一层对应的下标
    			const Number i2 = (key >> LEAF_BITS) & (INTERIOR_LENGTH - 1); //第二层对应的下标
    			if (i1 >= INTERIOR_LENGTH || i2 >= INTERIOR_LENGTH) //下标值超出范围
    				return false;
    			if (root_->ptrs[i1] == NULL) //第一层i1下标指向的空间未开辟
    			{
        
    				//开辟对应空间
    				Node* n = NewNode();
    				if (n == NULL) return false;
    				root_->ptrs[i1] = n;
    			}
    			if (root_->ptrs[i1]->ptrs[i2] == NULL) //第二层i2下标指向的空间未开辟
    			{
        
    				//开辟对应空间
    				static ObjectPool<Leaf> leafPool;
    				Leaf* leaf = leafPool.New();
    				if (leaf == NULL) return false;
    				memset(leaf, 0, sizeof(*leaf));
    				root_->ptrs[i1]->ptrs[i2] = reinterpret_cast<Node*>(leaf);
    			}
    			key = ((key >> LEAF_BITS) + 1) << LEAF_BITS; //继续后续检查
    		}
    		return true;
    	}
    	void PreallocateMoreMemory()
    	{
        }
    };

因此当我们要建立某一页号的映射关系时，需要先确保存储该页映射的数组空间是开辟好了的，也就是调用代码中的Ensure函数，如果对应数组空间未开辟则会立马开辟对应的空间。

--------------------

## ?3. 使用基数树进行优化代码实现 ##

*  **代码更改**

现在我们用基数树对代码进行优化，此时将PageCache类当中的unorder\_map用基数树进行替换即可，由于当前是32位平台，因此这里随便用几层基数树都可以。

//单例模式
    class PageCache
    {
        
    public:
    	//...
    private:
    	//std::unordered_map<PAGE_ID, Span*> _idSpanMap;
    	TCMalloc_PageMap1<32 - PAGE_SHIFT> _idSpanMap;
    };

此时当我们需要建立页号与span的映射时，就调用基数树当中的set函数。

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

而当我们需要读取某一页号对应的span时，就调用基数树当中的get函数。

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

并且现在PageCache类向外提供的，用于读取映射关系的MapObjectToSpan函数内部就不需要加锁了。

//获取从对象到span的映射
    Span* PageCache::MapObjectToSpan(void* obj)
    {
        
    	PAGE_ID id = (PAGE_ID)obj >> PAGE_SHIFT; //页号
    	Span* ret = (Span*)_idSpanMap.get(id);
    	assert(ret != nullptr);
    	return ret;
    }

*  **为什么读取基数树映射关系时不需要加锁？**

当某个线程在读取映射关系时，可能另外一个线程正在建立其他页号的映射关系，而此时无论我们用的是C++当中的map还是unordered\_map，在读取映射关系时都是需要加锁的。

因为C++中map的底层数据结构是红黑树，unordered\_map的底层数据结构是哈希表，而无论是红黑树还是哈希表，当我们在插入数据时其底层的结构都有可能会发生变化。比如红黑树在插入数据时可能会引起树的旋转，而哈希表在插入数据时可能会引起哈希表扩容。此时要避免出现数据不一致的问题，就不能让插入操作和读取操作同时进行，因此我们在读取映射关系的时候是需要加锁的。

而对于基数树来说就不一样了，基数树的空间一旦开辟好了就不会发生变化，因此无论什么时候去读取某个页的映射，都是对应在一个固定的位置进行读取的。并且我们不会同时对同一个页进行读取映射和建立映射的操作，因为我们只有在释放对象时才需要读取映射，而建立映射的操作都是在page cache进行的。也就是说，读取映射时读取的都是对应span的\_useCount不等于0的页，而建立映射时建立的都是对应span的\_useCount等于0的页，所以说我们不会同时对同一个页进行读取映射和建立映射的操作。

*  **再次对比malloc进行测试**

还是同样的代码，只不过我们用基数树对代码进行了优化，这时测试固定大小内存的申请和释放的结果如下：

![在这里插入图片描述][002598ab6ccb4685b9930b4e502f093b.png]

可以看到，这时就算申请释放的是固定大小的对象，其效率都是malloc的两倍。下面在申请释放不同大小的对象时，由于central cache的桶锁起作用了，其效率更是变成了malloc的好几倍。

![在这里插入图片描述][1e38fa93a4d14244ba4e766146f89e08.png]

--------------------

[Link 1]: https://blog.csdn.net/m0_60338933?type=blog
[eabca17da9704379a5f15832a495b4cc.jpeg_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/6b66c4c45d0440eeb23c16f6c2ae5f8d.jpeg
[56038f69a2aa4ac7874633f7763a1953.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/6b6b46e81b164ba994471cfc765090b7.png
[b0f147488a2442ebb8c2001d65e9bc7e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/095b5436ba0447639e8f658e6d9f39e3.png
[411361fa366c45e7aec8c4638d983acf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/00598f0061f9479f9dc952dcb22a3499.png
[d8ff2b8b19e840ec9391672193c516bd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/cf509d6e50874321bdd66196c5c1e10a.png
[a3b1589bb19d4554bbb71bf11eab3a1a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/56e5824472c141cb97ff202d1695069c.png
[e9d755ada6374af78d0a1fb5034822a0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/5c4907b603bc422bb361fd8bb9a832f4.png
[ffcc630b2f0e4ef8a32e6cc594d1afb0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/de2d7069514c45b19eebc26fece4f1b5.png
[50c86581f4c44663bd1132fae796947f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/a989149dbd524951911d6dfc6bf76ed6.png
[bf9a126a8c3d494c97609346d0e607de.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/8083611c5ed84596a95b8f3864b16c84.png
[002598ab6ccb4685b9930b4e502f093b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/29ce32f4b0994b1aa0c65bfa37706f08.png
[1e38fa93a4d14244ba4e766146f89e08.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/b845d5d04dc644b2ab8a5e9ab4652af1.png