做网站属于技术开发吗,一个二手书网站的建设目标,商业网站建设常识,济南模版网站前言
上一期我们对整个项目进行了细节部分的优化#xff0c;并在最后测试了多线程环境下和malloc的性能对比测试#xff0c;发现malloc有时候还是更胜一筹的#xff0c;基于此我们进行对我们的内存池进行瓶颈分析与优化。
目录
前言
一、项目瓶颈分析
VS编译器下性能分…前言
上一期我们对整个项目进行了细节部分的优化并在最后测试了多线程环境下和malloc的性能对比测试发现malloc有时候还是更胜一筹的基于此我们进行对我们的内存池进行瓶颈分析与优化。
目录
前言
一、项目瓶颈分析
VS编译器下性能分析的操作步骤
分析性能瓶颈
二、针对性能瓶颈使用基数树进行优化
代码修改
再次对比malloc进行测试
打包成动静态库
项目源码高并发内存池源码 一、项目瓶颈分析 经过前面的测试可以看到我们的代码此时与malloc之间还是有差距的此时我们就应该分析分析我们当前项目的瓶颈在哪里但这不能简单的凭感觉我们应该用性能分析的工具来进行分析。
VS编译器下性能分析的操作步骤 VS编译器中就带有性能分析的工具的我们可以依次点击。“调试-》性能探测器”进行分析。注意该过程一定是在Debug模式下的。 同时我们将代码中n的值由10000调成了1000否则该分析过程可能会花费较多时间并且将malloc的测试代码进行了屏蔽因为我们要分析的是我们实现的高并发内存池。
int main()
{size_t n 1000;cout endl;BenchmarkConcurrentMalloc(n, 4, 10);cout endl endl;//BenchmarkMalloc(n, 4, 10);cout endl;return 0;
}勾选 检测-》开始 然后会弹出一个框我们选择我们要分析的项目确定即可 分析性能瓶颈 通过分析结果可以看到光是Deallocate和MapObjectToSpan这两个函数就占用了一半多的时间。 而MapObjectToSpan是占用消耗时间最多的。 我们点击去看看MapObjectToSpan发现是因为加锁的就消耗了47%的时间 在来点到Deallocate看看发现是ListTooLong占用的多 继续点到ListTooLong看看发现是RleaseListToSpan 继续点到RleaseListToSpan看看发现是MapObjectToSpan 这里我们再点击去就肯定是锁的问题了 因此当前项目的瓶颈点就在锁竞争上面需要解决调用MapObjectToSpan函数访问映射关系时的加锁问题。tcmalloc当中针对这一点使用了基数树进行优化使得在读取这个映射关系时可以做到不加锁。 二、针对性能瓶颈使用基数树进行优化 基数树实际上就是一个分层的哈希表类似于多级页表根据所分层数不同可分为单层基数树(32(32))、二层基数树(32(32))、三层基数树64位等。 单层基数树 单层基数树实际采用的就是直接定址法的哈希每一个 页号对应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; //页的数目
};代码解释 BITS 表示存储页号对多需要的比特位的个数32位下一页按8K算就是19页这里就是19,64位下就是51页。即32-PAGE_SHIFT/64-PAGE_SHIFT 此时当我们需要建立映射时就调用set函数需要读取映射关系时就调用get函数就行了。 二层基数树 这里还是以32位平台下一页的大小为8K为例来说明此时存储页号最多需要19个比特位。而二层基数树实际上就是把这19个比特位分为两次进行映射。 比如用前5个比特位在基数树的第一层进行映射映射后得到对应的第二层然后用剩下的比特位在基数树的第二层进行映射映射后最终得到该页号对应的span指针。 二层基数树相比一层基数树的好处就是一层基数树必须一开始就把2 M 2M2M的数组开辟出来而二层基数树一开始时只需将第一层的数组开辟出来当需要进行某一页号映射时再开辟对应的第二层的数组就行了。
//二层基数树
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 ObjectPoolLeaf 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 2M2M的空间内存消耗也不算太多因此我们可以在构造二层基数树时就把第二层的数组全部开辟出来。 三层基数树 上面一层基数树和二层基数树都适用于32位平台而对于64位的平台就需要用三层基数树了。三层基数树与二层基数树类似三层基数树实际上就是把存储页号的若干比特位分为三次进行映射。 此时只有当要建立某一页号的映射关系时再开辟对应的数组空间而没有建立映射的页号就可以不用开辟其对应的数组空间此时就能在一定程度上节省内存空间。
//三层基数树
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 ObjectPoolNode 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_castLeaf*(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_castLeaf*(root_-ptrs[i1]-ptrs[i2])-values[i3] v; //建立该页号与对应span的映射}//确保映射[start,startn-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 ObjectPoolLeaf leafPool;Leaf* leaf leafPool.New();if (leaf NULL) return false;memset(leaf, 0, sizeof(*leaf));root_-ptrs[i1]-ptrs[i2] reinterpret_castNode*(leaf);}key ((key LEAF_BITS) 1) LEAF_BITS; //继续后续检查}return true;}void PreallocateMoreMemory(){}
};因此当我们要建立某一页号的映射关系时需要先确保存储该页映射的数组空间是开辟好了的也就是调用代码中的Ensure函数如果对应数组空间未开辟则会立马开辟对应的空间。 代码修改 我们将上面的tcmalloc实现的基数树专门放在一个PageMap.h中在PageCahe.cpp中隐隐即可使用 此时当我们需要建立页号与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进行测试 均匀测试 固定大小测试 这次对比下来无论是定长的对象大小还是均匀的测试我们自己的内存池均占上风。 打包成动静态库 实际Google开源的tcmalloc是会直接用于替换malloc的不同平台替换的方式不同。比如基于Unix的系统上的glibc使用了weak alias的方式替换而对于某些其他平台需要使用hook的钩子技术来做。 对于我们当前实现的项目可以考虑将其打包成静态库或动态库。我们先右击解决方案资源管理器当中的项目名称然后选择属性。 此时会弹出一个框点击常规-》配置类型然后选择动态库/静态库 项目源码高并发内存池源码 OK到这里我们的这个项目就完成了这个项目是第一个项目我们的目的主要是学习人家tcmalloc的最核心思想而不是说造一个更好的轮子。 文章转载自： http://www.morning.mwjwy.cn.gov.cn.mwjwy.cn http://www.morning.tqldj.cn.gov.cn.tqldj.cn http://www.morning.qrnbs.cn.gov.cn.qrnbs.cn http://www.morning.wwklf.cn.gov.cn.wwklf.cn http://www.morning.xqmd.cn.gov.cn.xqmd.cn http://www.morning.wqnc.cn.gov.cn.wqnc.cn http://www.morning.wtnyg.cn.gov.cn.wtnyg.cn http://www.morning.mqgqf.cn.gov.cn.mqgqf.cn http://www.morning.rkjz.cn.gov.cn.rkjz.cn http://www.morning.phnbd.cn.gov.cn.phnbd.cn http://www.morning.qjlkp.cn.gov.cn.qjlkp.cn http://www.morning.slkqd.cn.gov.cn.slkqd.cn http://www.morning.iknty.cn.gov.cn.iknty.cn http://www.morning.bmhc.cn.gov.cn.bmhc.cn http://www.morning.krdmn.cn.gov.cn.krdmn.cn http://www.morning.zbnkt.cn.gov.cn.zbnkt.cn http://www.morning.bgpb.cn.gov.cn.bgpb.cn http://www.morning.rgkd.cn.gov.cn.rgkd.cn http://www.morning.huxinzuche.cn.gov.cn.huxinzuche.cn http://www.morning.hhboyus.cn.gov.cn.hhboyus.cn http://www.morning.lzqdd.cn.gov.cn.lzqdd.cn http://www.morning.wcyr.cn.gov.cn.wcyr.cn http://www.morning.kkqgf.cn.gov.cn.kkqgf.cn http://www.morning.dskmq.cn.gov.cn.dskmq.cn http://www.morning.fcqlt.cn.gov.cn.fcqlt.cn http://www.morning.mbfj.cn.gov.cn.mbfj.cn http://www.morning.nlbhj.cn.gov.cn.nlbhj.cn http://www.morning.jrgxx.cn.gov.cn.jrgxx.cn http://www.morning.csgwd.cn.gov.cn.csgwd.cn http://www.morning.dxqfh.cn.gov.cn.dxqfh.cn http://www.morning.llthz.cn.gov.cn.llthz.cn http://www.morning.rfldz.cn.gov.cn.rfldz.cn http://www.morning.xnqjs.cn.gov.cn.xnqjs.cn http://www.morning.fpxsd.cn.gov.cn.fpxsd.cn http://www.morning.skrww.cn.gov.cn.skrww.cn http://www.morning.hpkgm.cn.gov.cn.hpkgm.cn http://www.morning.jrkzk.cn.gov.cn.jrkzk.cn http://www.morning.lkhgq.cn.gov.cn.lkhgq.cn http://www.morning.gwxsk.cn.gov.cn.gwxsk.cn http://www.morning.yrlfy.cn.gov.cn.yrlfy.cn http://www.morning.sgbjh.cn.gov.cn.sgbjh.cn http://www.morning.jpkhn.cn.gov.cn.jpkhn.cn http://www.morning.xjbtb.cn.gov.cn.xjbtb.cn http://www.morning.rqxmz.cn.gov.cn.rqxmz.cn http://www.morning.mqpdl.cn.gov.cn.mqpdl.cn http://www.morning.lynmt.cn.gov.cn.lynmt.cn http://www.morning.rqbr.cn.gov.cn.rqbr.cn http://www.morning.ymmjx.cn.gov.cn.ymmjx.cn http://www.morning.qmpbs.cn.gov.cn.qmpbs.cn http://www.morning.rsszk.cn.gov.cn.rsszk.cn http://www.morning.mjkqj.cn.gov.cn.mjkqj.cn http://www.morning.zdxss.cn.gov.cn.zdxss.cn http://www.morning.xxzjb.cn.gov.cn.xxzjb.cn http://www.morning.hwnnm.cn.gov.cn.hwnnm.cn http://www.morning.wmfmj.cn.gov.cn.wmfmj.cn http://www.morning.kjgdm.cn.gov.cn.kjgdm.cn http://www.morning.sbyhj.cn.gov.cn.sbyhj.cn http://www.morning.pwdgy.cn.gov.cn.pwdgy.cn http://www.morning.llcgz.cn.gov.cn.llcgz.cn http://www.morning.hmlpn.cn.gov.cn.hmlpn.cn http://www.morning.lmrcq.cn.gov.cn.lmrcq.cn http://www.morning.pjzcp.cn.gov.cn.pjzcp.cn http://www.morning.pdmsj.cn.gov.cn.pdmsj.cn http://www.morning.rqlf.cn.gov.cn.rqlf.cn http://www.morning.nrtpb.cn.gov.cn.nrtpb.cn http://www.morning.qxycf.cn.gov.cn.qxycf.cn http://www.morning.ckbmz.cn.gov.cn.ckbmz.cn http://www.morning.gmswp.cn.gov.cn.gmswp.cn http://www.morning.dygqq.cn.gov.cn.dygqq.cn http://www.morning.mbzlg.cn.gov.cn.mbzlg.cn http://www.morning.pbknh.cn.gov.cn.pbknh.cn http://www.morning.qbmpb.cn.gov.cn.qbmpb.cn http://www.morning.nzqmw.cn.gov.cn.nzqmw.cn http://www.morning.fldsb.cn.gov.cn.fldsb.cn http://www.morning.rxzcl.cn.gov.cn.rxzcl.cn http://www.morning.sjpht.cn.gov.cn.sjpht.cn http://www.morning.rui931.cn.gov.cn.rui931.cn http://www.morning.klrpm.cn.gov.cn.klrpm.cn http://www.morning.knngw.cn.gov.cn.knngw.cn http://www.morning.msbct.cn.gov.cn.msbct.cn
