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

🎇C++学习历程：入门

---

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

---

🍁 🍃 🍂 🌿

目录

🌿1. 性能瓶颈分析

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

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

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

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

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

然后会弹出一个选项框，这里我们选择的是第二个，因为我们要分析的是各个函数的用时时间，然后点击下一步。

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

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

• 分析性能瓶颈

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

而在Deallocate函数中，调用ListTooLong函数时消耗的时间是最多的。

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

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

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

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

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

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

• 单层基数树

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

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

//单层基数树template<int BITS>classTCMalloc_PageMap1{public:typedef uintptr_t Number;explicitTCMalloc_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]{returnNULL;}return array_[k];//返回该页号对应的span}voidset(Number k,void* v){assert((k >> BITS)==0);//k的范围必须在[0, 2^BITS-1]
        array_[k]= v;//建立映射}private:void** array_;//存储映射关系的数组staticconstint 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字节，因此该数组的大小就是219x 4 = 2M ,内存消耗不大，是可行的。但如果是在64位平台下，此时该数组的大小是251x 8 = 224G,这显然是不可行的，实际上对于64位的平台，我们需要使用三层基数树。

• 二层基数树

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

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

在二层基数树中，第一层的数组占用25x = 27 Byte 空间，第二层的数组最多占用25x 214x 4 = 221 = 2M。二层基数树相比一层基数树的好处就是，一层基数树必须一开始就把 2M 的数组开辟出来，而二层基数树一开始时只需将第一层的数组开辟出来，当需要进行某一页号映射时再开辟对应的第二层的数组就行了。

//二层基数树template<int BITS>classTCMalloc_PageMap2{private:staticconstint ROOT_BITS =5;//第一层对应页号的前5个比特位staticconstint ROOT_LENGTH =1<< ROOT_BITS;//第一层存储元素的个数staticconstint LEAF_BITS = BITS - ROOT_BITS;//第二层对应页号的其余比特位staticconstint LEAF_LENGTH =1<< LEAF_BITS;//第二层存储元素的个数//第一层数组中存储的元素类型structLeaf{void* values[LEAF_LENGTH];};
    Leaf* root_[ROOT_LENGTH];//第一层数组public:typedef uintptr_t Number;explicitTCMalloc_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)//页号值不在范围或没有建立过映射{returnNULL;}return root_[i1]->values[i2];//返回该页号对应span的指针}voidset(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]页号的空间是开辟好了的boolEnsure(Number start, size_t n){for(Number key = start; key <= start + n -1;){const Number i1 = key >> LEAF_BITS;if(i1 >= ROOT_LENGTH)//页号超出范围returnfalse;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;//继续后续检查}returntrue;}voidPreallocateMoreMemory(){Ensure(0,1<< BITS);//将第二层的空间全部开辟好}};

因此在二层基数树中有一个Ensure函数，当需要建立某一页号与其span之间的映射关系时，需要先调用该Ensure函数确保用于映射该页号的空间是开辟了的，如果没有开辟则会立即开辟。

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

• 三层基数树

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

此时只有当要建立某一页号的映射关系时，再开辟对应的数组空间，而没有建立映射的页号就可以不用开辟其对应的数组空间，此时就能在一定程度上节省内存空间。

//三层基数树template<int BITS>classTCMalloc_PageMap3{private:staticconstint INTERIOR_BITS =(BITS +2)/3;//第一、二层对应页号的比特位个数staticconstint INTERIOR_LENGTH =1<< INTERIOR_BITS;//第一、二层存储元素的个数staticconstint LEAF_BITS = BITS -2* INTERIOR_BITS;//第三层对应页号的比特位个数staticconstint LEAF_LENGTH =1<< LEAF_BITS;//第三层存储元素的个数structNode{
        Node* ptrs[INTERIOR_LENGTH];};structLeaf{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;explicitTCMalloc_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){returnNULL;}returnreinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3];//返回该页号对应span的指针}voidset(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]页号的空间是开辟好了的boolEnsure(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)//下标值超出范围returnfalse;if(root_->ptrs[i1]==NULL)//第一层i1下标指向的空间未开辟{//开辟对应空间
                Node* n =NewNode();if(n ==NULL)returnfalse;
                root_->ptrs[i1]= n;}if(root_->ptrs[i1]->ptrs[i2]==NULL)//第二层i2下标指向的空间未开辟{//开辟对应空间static ObjectPool<Leaf> leafPool;
                Leaf* leaf = leafPool.New();if(leaf ==NULL)returnfalse;memset(leaf,0,sizeof(*leaf));
                root_->ptrs[i1]->ptrs[i2]=reinterpret_cast<Node*>(leaf);}
            key =((key >> LEAF_BITS)+1)<< LEAF_BITS;//继续后续检查}returntrue;}voidPreallocateMoreMemory(){}};

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

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

• 代码更改

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

//单例模式classPageCache{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进行测试

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

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