bit::Shadow✧(≖ ◡ ≖✿目录嵌入定长内存池大于256KB处理龙级Bug分析性能分析测试性能窗口调出流程调用方/被调用方火焰图更加形象、清晰优化前的性能测试基数树优化二级基数树二级基数树图示项目结果提效不足项目复盘ConCurrentAlloc()全流程ConCurrentFree()全流程gitee链接优化完整版高并发内存池复习时同步博客复习嵌入定长内存池使用定长内存池的New()和Delete()用于取代使用new、free的堆申请释放。在PageCache内新定义成员ObjectPoolSpan obPol;像void* ConCurrentAlloc(size_t size) { //size_t a SizeClass::Index(256 * 1024);//a207 if (!pTLSThreadCache) { //优化1.使用定长内存池取代堆new ObjectPoolThreadCache obPol; pTLSThreadCache obPol.New(); //pTLSThreadCache- } return pTLSThreadCache-Alloc(size); }三级缓冲区GetSpans(size_t pageNum)Span* PageCache::GetSpans(size_t pageNum) { if (pageNum 128) { //大于128页堆申请 //优化1.使用定长内存池取代堆new Span* span obPol.New(); void* ptr SizeClass::SystemAlloc(pageNum); span-_n pageNum; span-_pageId (PAGE_ID)ptr PAGE_SHIFT; _IDSpanMap.set(span-_pageId, span);//用于大于128的回收 return span; }//是否应该将此Span加入Map?无用——不涉及合并使用 //三级缓冲区获取span (128) //1.直接定位 2.向下找 3.VirtualAlloc()堆区申请 Span* span PageCache::GetInstance()-_spanList[pageNum].Begin(); if (span-_nextSpan ! span) { //PageCache拥有span非空链表 //SpanList的头删 PageCache::GetInstance()-_spanList[pageNum].ErasePos(span); span-_isUse true; return span;//这也是ErasePos内不能delete的原因。要向上供给,这块内存属于 } //[pageNum]下没有span //2.在PageCache内向下找 for(int i pageNum1;i 129;i) { Span* _span PageCache::GetInstance()-_spanList[i].Begin(); if (_span-_nextSpan ! _span) { // 找到了需pageNum块多出了i-pageNum块 // 考虑到此部分代码在3.情况下的复用可以额外封装也可以使用巧妙的递归解决。 // 头删 PageCache::GetInstance()-_spanList[i].ErasePos(_span); //分割与插入 /*Span* insertSpan (Span*)((PAGE_ID)_span pageNum PAGE_SHIFT); insertSpan-_nextSpan insertSpan; insertSpan-_prevSpan insertSpan;*/ //强制类型转换造成的内存越界访问 Span* insertSpan obPol.New();//堆申请!!! 照应本文件line[121] ///为什么要堆申请 //// 堆申请的作用1.改变了生命周期(可被址定位替代)2.额外空间由堆(多线程一个进程区域)提供 //// 若使用址定位无法访问类内部空间解决办法是... //// 不使用堆函数结束后insertSpan无法被访问。 insertSpan-_n i - pageNum; insertSpan-_pageId _span-_pageIdpageNum; for (PAGE_ID j 0; j insertSpan-_n; j) { //仅头尾_n初始化即可 PageCache::GetInstance()-_IDSpanMap.set(insertSpan-_pageId j, insertSpan); } PageCache::GetInstance()-_spanList[i - pageNum].HeadInsert(insertSpan);//剩余块头插 _span-_n pageNum; //_span-_pageId pageNum;//你加你妈呢 for (PAGE_ID j 0; j _span-_n; j) { //仅头尾_n初始化即可 PageCache::GetInstance()-_IDSpanMap.set(_span-_pageId j, _span); } _span-_isUse true; return _span; } } //3.[i]向下全空向系统申请128页--128*8K void* ptr SizeClass::SystemAlloc(128);//无需检查失败VirtualAlloc() //Span* test new Span; Span* m128span obPol.New(); //Span* m128span (Span*)ptr;//调用自动生成的拷贝赋值无法自己指向自己 //// //m128span-_nextSpan m128span; //m128span-_prevSpan m128span; //m128span-_n 128; //m128span-_pageId (PAGE_ID)m128span PAGE_SHIFT; m128span-_pageId (PAGE_ID)ptr PAGE_SHIFT; m128span-_n 128; _spanList[128].HeadInsert(m128span); for(int i 0;i 128;i) PageCache::GetInstance()-_IDSpanMap.set(m128span-_pageIdi, m128span); return GetSpans(pageNum); }大于256KB处理256KB相当于32*8KB32页所以存在弹性区间若是(32, 128]直接向三级缓冲区申请与释放若是大于128页及以上就应该向堆直接申请与回收。完善后的Allocsize_t sizevoid* ThreadCache::Alloc(size_t size) { //线程申请指定字节数 1.对齐数2.获取空间自自由链表/FetchFromCentralCache assert(size 0);//为0及负数不申请 //对齐找桶 //不对Index的确定是基于对齐数那么你当初在设计时就无需考虑余数情景 size_t AlignSize SizeClass::RoundUp(size); void* ret nullptr; if (size (1 18)) { // 256KB //1. 128*8KB 找三级缓冲区切割、合并、返回到三级缓冲区、向前、向后合并 //2. 128*8KB系统堆申请、返还 size_t npage SizeClass::NumMovePage(SizeClass::RoundUp(size)); PageCache::GetInstance()-_mtx.lock(); Span* span PageCache::GetInstance()-GetSpans(npage); PageCache::GetInstance()-_mtx.unlock(); //return (void*)span; ret (void*)((PAGE_ID)span-_pageId PAGE_SHIFT); } else { size_t i SizeClass::Index(size); //256KB申请 if (!_freeList[i].empty()) { //自由链表非空 ret _freeList[i].Pop(); } else { //二级缓存获取 ret FetchFromCentralCache(i, AlignSize); } } ////优化2.去除Free时必须传入size的毛病 //unordered_mapvoid*, size_t rtMap.Push(ret, size); return ret; }完善后的ConCurrentFree(void* ptr):void ConCurrentFree(void* ptr) { // 256KB //1. 128*8KB 找三级缓冲区切割、合并、返回到三级缓冲区、向前、向后合并 //2. 128*8KB系统堆申请、返还 Span* span PageCache::GetInstance()-MapGetSpan((PAGE_ID)ptr PAGE_SHIFT); ///为什么不需要加锁因为线程独立虽然使用了PageCache内的Map其内部的定位因为ptr一定是先前Alloc过的。 if (span-_n 32) { //释放空间 pTLSThreadCache-DeAlloc(ptr);//暂时性实现size后期无 return; } else { std::mutex mtx; std::lock_guardstd::mutex lock(mtx); if (span-_n 32)//256KB { if (span-_n 128)//三级缓冲区回收 PageCache::GetInstance()-RetSpan2Page(span); else//系统堆回收 SizeClass::SystemDealloc(ptr); } } }龙级Bug分析注这是项目结束后的测试阶段测出的bug。反思在能够跑通时就应该立即进行尽可能充分的测试“不充分的测试就相当于没有测试”。一现象双向带头链表内无限循环寻找位于二级缓冲区内的特定Span块。[108] void CentralCache::RetList2Spans(FreeList _freeList, size_t size);解决方案在二级缓冲区满后应该先Erase后插入三级缓冲区。抓栈帧、条件断点执行。调用堆栈用于监视位于断点发生之上的函数块内的监视变量条件断点指专门为特殊情况设立的一个断点当满足此情况该断点才会成立。Span* PageCache::MapGetSpan(PAGE_ID pgID) { //条件断点 if (!_IDSpanMap[pgID]) { int a 0; //此处加断点 } if (_IDSpanMap.find(pgID) _IDSpanMap.end()) assert(false); return (Span*)_IDSpanMap.get(pgID);//课件中页号为什么右移 必须右移源于_pageID的形成 }性能分析1.Debug下分析2.不能凭感觉对项目各模块分析。而是要使用性能分析工具。3.性能瓶颈点一般在特定的某个点4.测试性能的例子一定要选择好测试完整测试/测试哪个模块就要调用哪个测试逻辑。测试性能窗口调出流程处理警告⚠️配置链接器属性调用方/被调用方进入“调用方/被调用方”模块查看以函数为单位的调用消耗左侧“正在调用的函数”指明当前模块被调用的函数占整体权重自main开始的测试用例调用整体的百分比。中央“当前函数”分为当前函数占总体比当前函数体块向下调用函数不被计入占整体比。因此第二个参数永远小于等于第一个参数右侧“调用的函数”指当前函数内的向下调用函数占总体之比。即右侧占比之和中央“函数体”占比正在调用函数占整体之比我们自main进入实际是ConcurrentPool.exe进入查看得知CentralCache::FetchListNodes()占比最大。FetchListNodes内可见“函数体”结构占比最大说明当前函数消耗大的原因很大程度上是自身的设计而非向下调用的销毁导致的。因此我们对其内部分析得知是锁的原因优化此锁就成为了优化此项目的重要着力点。火焰图更加形象、清晰清晰的展示了调用流程下的调用逻辑与各模块占比也很容易分析出CentralCache::FetchList内的消耗就是优化重点。优化前的性能测试测试结果是208 140 142倍的提速。实际上若我们再提高测试轮次将尽可能的踩中“同一个span上的重叠存活span的归还”实际上我们设计的高并发内存池是优于malloc下的申请释放逻辑的本项目下大概率超越malloc、free的内存管理。基数树优化网上找的模板手动改造二级基数树template int BITS//19 51 class CardinalTree2 { private: // Put 32 entries in the root and (2^BITS)/32 entries in each leaf. static const int ROOT_BITS 5; static const int ROOT_LENGTH 1 ROOT_BITS; static const int LEAF_BITS BITS - ROOT_BITS;//19-5 51-5 static const int LEAF_LENGTH 1 LEAF_BITS;//2^14/46 // Leaf node struct Leaf { //此处void*保留即可模板 void* values[LEAF_LENGTH];//二级区指针数组低14/46位 32Nodes下各子节点14位/46位 }; Leaf* root_[ROOT_LENGTH]; // 一级区高5位 Pointers to 32 child nodes //void* (*allocator_)(size_t); // 函数指针声明它声明了一个指向函数的指针 public: typedef uintptr_t Number;//uintptr_t:安全地 指针-整数 转换类型 /*explicit CardinalTree2(void* (*allocator)(size_t)) { allocator_ allocator; memset(root_, 0, sizeof(root_)); }*/ explicit CardinalTree2() { memset(root_, 0, sizeof(root_)); PreallocateMoreMemory(); } void* get(Number k) const { const Number i1 k LEAF_BITS;// 14 仅计_pgId高5位 const Number i2 k (LEAF_LENGTH - 1);// 仅保留传入地址k的低13位 if ((k BITS) 0 || root_[i1] nullptr) return nullptr; return root_[i1]-values[i2]; } 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; } bool Ensure(Number start, size_t n) { for (Number key start; key start n - 1;) { const Number i1 key LEAF_BITS; // Check for overflow if (i1 ROOT_LENGTH) return false; // Make 2nd level node if necessary if (root_[i1] nullptr) { ObjectPoolLeaf obp; Leaf* leaf obp.New(); if (leaf nullptr) return false; memset(leaf, 0, sizeof(*leaf)); root_[i1] leaf; } // Advance key past whatever is covered by this leaf node key ((key LEAF_BITS) 1) LEAF_BITS; } return true; } void PreallocateMoreMemory() { // Allocate enough to keep track of all possible pages Ensure(0, 1 BITS); } };二级基数树图示将全部的_IDSpanMap替换为这样一颗基数树有效map查询低下的问题。项目结果提效v.push_back(ConCurrentAlloc((16 i) % 8192 1)); //alloc数动态变化尽量减少重复4个线程并发执行10轮次每轮申请2000~9000次提效300%(±50%)4个线程并发执行10轮次每轮释放2000~9000次提效3000%(±50%)。综合提效在400%~500%的动态区间。不足当申请次数4线程并发申请10轮每轮申请/释放一万次95%及以上次数有概率出现崩溃主要原因是Span块在定长内存池的回收与GetSpans中切分时_n的标记矛盾问题。此时的整体本项目旨在提高管理内存的效率所以说稳定性的重要程度要大于效率的提升的重要程度此项目的问题在于极高并发下的崩溃问题主要问题在于Span的并发问题。但是并发越高此内存池带来的效率提升越明显甚至达到了10000%倍的效率提升。做此项目的目的在于思考设计逻辑体会工程级项目的设计流程查缺补漏。项目复盘1.各个模块要做到鲁棒性极强。不要造成看似无关的设计像双向链表删除的悬挂2.设计原则高内聚、低耦合代码的健壮性 少量的效率优化(像仅首尾页标注)带来的收益。3.锁分析。亮点1三级缓存架构 线程局部缓存Thread Local Storage→ 线程自己缓存对象无锁分配只有缓存不足才加锁去Central Cache亮点2慢启动 批量交换还记得 min 和 NumMoveSize 吗→ 从拿1个开始逐渐翻倍到上限512个减少锁竞争又不浪费亮点3Central Cache 的 Span 切割与回收哈希桶双向链表双端CAS→ 空闲Span从头部拿非空闲从尾部拿减少碎片亮点4Page Cache 的基数树反查CardinalTree2→ 释放对象时 O(1) 找到所属 Span惰性分配节省内存并发内存池C11约 1000 行三级缓存架构Thread CacheTLS 无锁分配→ Central Cache互斥锁批量交换→ Page Cache大块内存切割与回收将 malloc 分配耗时降低约 300%慢启动 批量获取机制动态调整单次获取对象数量减少锁竞争基于哈希桶 双向链表管理 Span空闲/非空闲双端出队降低内存碎片基数树2级 radix tree实现 pageId→Span 的 O(1) 反查惰性分配节省内存通过 Valgrind/ASan 无泄漏检查多线程压测无崩溃感谢支持长期连载欢迎关注