搜狗收录网站,网站制作费用预算表,网络服务公司经营范围,网站建设案例ppt前言 因为偶然的机会#xff0c;我通过同学那里知道这个google有一个开源项目tcmalloc#xff0c;他讲的头头是道#xff0c;而我也对其非常感兴趣。 这个tcmalloc呢#xff0c;全称Thread-Caching Malloc#xff0c;通过名字就能看出跟线程相关#xff0c;也确实如此我通过同学那里知道这个google有一个开源项目tcmalloc他讲的头头是道而我也对其非常感兴趣。 这个tcmalloc呢全称Thread-Caching Malloc通过名字就能看出跟线程相关也确实如此它就叫线程缓存的malloc其中实现了高效的多线程内存管理用于替代系统的内存分配相关的函数(malloc、free)。由于new和delete底层也是通过malloc和free实现的所以这个项目很有意义。 而这个项目是由google的C/C高手写出来的高手出手不同凡响。google是一个老牌的C/C大厂这个公司里写出来的项目对我们的技术方面肯定有不小提升我们也可以通过这个项目与当初写tcmalloc的程序员来一次跨越时间的会面了解真正的大佬是如何进行程序开发的。 我们这个项目是把tcmalloc最核心的框架简化了之后再去实现模拟实现出一个属于自己的高并发内存池简单的来说目的就是学习tcmalloc的精华。 tcmalloc源代码
项目要求的知识储备和难度 这个项目需要用到C/C、数据结构(链表、哈希桶)、操作系统的内存管理、单例模式、多线程、互斥锁等这方面的知识。 难度的话是有的并且还不低。不过这对于正在奋斗向上迎难而上的C/C程序员来说不过是些许风霜罢了。 因为我想要学习这个项目阅读了很多别人写的博客所以我了解博客写的不详细对看的人来说是很难受的我也想希望别人通过阅读这篇博客从而对我思想和知识方面提出些疑问让我们继续共同进步。区区拙作望能斧正。
一、是什么是内存池
1.池化技术 举个例子以前我过年回老家的村子上去我二舅家那时候还没有家家户户通自来水我经常口渴所以缠着长辈们想喝水他们就带我去他们家里的厨房角落里有一个大大的陶制水缸他们就从那里舀水给我喝(当然提醒大家喝水还是建议喝烧开的水为好)喝下去我就不渴了。然而我这时突然想这水是怎么来的 带着疑问来到了第二天我看到了我二舅推着一个很大的推车推车上有一个大大的蓝色的铁皮罐子还需要后面跟着我的几位哥哥齐步推着当他们把水倒入到家里的几个水缸时我就在想弄一次水好辛苦啊真该一次性弄多一些要不然隔三岔五跑一会多耽误人的时间。 所以我们一次弄够足够多的水在家里以备不时之需当然是把水弄得多多的。这样效率才是足够多。如果我们想喝水还得此次跑去水站去接水我们把接来的水使用一个容器来装起来也就是大大的陶制水缸这样我们用水时只需从水缸里舀水即可。 池 是在计算机技术中经常使用的一种设计模式其内涵在于将程序中需要经常使用的核心资源先申请出来放到一个池内由程序自己管理这样可以提高资源的使用效率也可以保证本程序占有的资源数量。 经常使用的池技术包括内存池、线程池和连接池等其中尤以内存池和线程池使用最多。
2.内存池 内存池(Memory Pool) 是一种动态内存分配与管理技术。 通常情况下程序员习惯直接使用 new、delete、malloc、free 等API申请分配和释放内存这样导致的后果是当程序长时间运行时由于所申请内存块的大小不定频繁使用时会造成大量的内存碎片从而降低程序和操作系统的性能。内存池则是在真正使用内存之前先申请分配一大块内存(内存池)留作备用当程序员申请内存时从池中取出一块动态分配当程序员释放内存时将释放的内存再放入池内再次申请池可以再取出来使用并尽量与周边的空闲内存块合并。若内存池不够时则自动扩大内存池从操作系统中申请更大的内存池。 二、为什么要使用内存池 1.主要就是效率问题 再举个例子我们现在还是学生生活费还得爸爸妈妈要而如果我们买一份中午饭12块钱拿起微信问妈妈要餐厅窗口工作人员得等着你后面排队的学生也要等着你你也要等着妈妈来给你钱都等在那里那就是太糟糕的情况了只能幸亏电脑的二进制没有情绪不然走不出这个程序他们就会杀掉你开个玩笑。所以我们每次问妈妈要足够的钱到你的微信账户上再每次付钱的时候用你自己微信账户上的钱付钱没钱了再要一笔钱这样效率就会大大提升了计算机同样也是如此程序就像是上学的童鞋操作系统就像父母频繁申请内存的场景下每次需要内存都像系统申请效率必然有影响。 2.内存碎片问题 我们每次申请内存是在内存的是什么地方呢是在一个叫堆的地方如下图linux下进程地址空间 而当我释放时因为申请内存空间的释放是自由的就会导致下图情况 而一部分释放了一部分还在保持着导致内存碎片化再想要申请大内存空间就可能申请不下来了。 补充 内存碎片有两种碎片 1.外碎片就是上面这种情况 2.内碎片因为各种数据结构内存对齐的原因导致一些内存用不上空着。 3.malloc C/C中我们要动态申请内存都是通过malloc去申请内存但是我们要知道实际我们不是直接去堆获取内存的而malloc就是一个内存池。malloc() 相当于向操作系统“批发”了一块较大的内存空间然后“零售”给程序用。当全部“售完”或程序有大量的内存需求时再根据实际需求向操作系统“进货”。malloc的实现方式有很多种一般不同编译器平台用的都是不同的。比如windows的vs系列用的微软自己写的一套 linux gcc用的glibc中的ptmalloc。 三、设计一个定长的内存池 作为C/C程序员我们知道申请内存使用的是mallocmalloc在任何场景下都很通用但是一个问题是在什么场景下都可以使用就意味着什么场景下都可能不会有很高的性能。下面我们先通过设计一个定长内存池来简答熟悉一下简单内存池是如何控制的第二它会作为我们后面内存池的一个基础组件。
从 到 进行改进
1.定长内存池设计 如果我们申请一大块空间因为内存的释放是不存在分期付款的需要一次性释放。
如果一次性归还那这个内存池就太low了我们只能申请一次。所以我们申请固定大小的内存这个申请的内存容量固定大小肯定是合适的不会太大那么我们肯定不止需要一份我们需要很多份。
所以我们需要一个_freeList链表来对这些空间进行管理即可。
固定大小内存申请释放需求特点
性能达到极致不考虑内存碎片问题 我们先建立一个头文件ObjectPool.h
注以下代码有一个问题最后统一改同学们可以先找找是哪的错提示一下是关于类型强转以达到固定长度空间的问题。
2.详细步骤 1.先申请一个大的内存_memory每次我们需要使用内存时只需要切一个固定长度的内存来使用不断使用不断切直到大块内存_memory使用完成后让_memory再去系统申请即可。 2.而当我们切的这些块我们归还回来后我们该怎么管理呢 我们可以使用链式结构把这些内存管理起来 我们可以把这些申请的块看成一个个结点每个结点存下一个结点的地址再用一个_freelist指向最开始的结点即可。 3.假如有一个T类型的对象要申请一块空间我们让obj指向_memory指向的同一个地方让_memory向后移动sizeof(T)大小的距离这就可以分配给obj一个定长大小sizeof(T)的内存了。 大家来看这份初始的New内存的代码有什么问题吗 如果obj将最后一份空间也申请走了,_memorysizeof(T),这时已经没有像系统申请的空间了但是_memory不为空。 所以我们这样做 但是这样依旧不好因为T类型有很多种有intdoublefloat还有自定义类型等当我们的obj申请sizeof(T)的内存时到了最后剩余的内存小于sizeof(T)这样依旧会出现问题。所以最后应该这么改 4.当我想要释放某个内存时我可以将内存回收通过结点头部的4个字节或8个字节(根据自己的系统是32位还是64位为准)指向下一个结点让自由链表的最后一个结点头部指向空。 下面这断代码当自由链表为空时通过使指针指向的内存块前4个字节或者前8个字节内容为空意为下一个结点为空。 但是当64为系统下时int*强转后解引用依旧是4个字节而64为系统下指针是8个字节。 所以这里通过将obj强转成void**再解引用这里不管什么void**还是int**都可以。 int*解引用是个int就取一个int的大小的空间。 void**解引用是个void*就一个指针大小的空间指针大小32位是464位是8.这样就符合要求了。 那如果我们在一个已经存在结点的自由链表中怎么插入呢难道要尾插吗大可不必因为结点就是一个内存块毫无意义直接头插即可 我们释放的内存也可以回收使用啊所以先判断自由链表中有无结点如果有因为是定长内存池所以每一个分配的内存大小一致所以就可以给用户继续使用。 我们定义一个next类型的指针指向自由链表中结点的内容也就是第二个结点可以就可以实现头删操作从而顺利的将内存交到用户手中。 避免因为int或char字节数过小而导致freelist无法使用所以统一定成指针大小的空间。 size_t objSize sizeof(T) sizeof(void*) ? sizeof(void*) : sizeof(T); 好了这个New就没什么问题了。 前面的问题在于 3.代码
#pragma once#include iostream//使用using namespace std;会导致污染在项目中把常用的展开即可
using std::cout;
using std::endl;#ifdef _WIN32#include windows.h
#else//Linux
#endif方案一定长N大小的内存池
//templatesize_t N
//class ObjectPool
//{
//};//直接去堆上按页申请空间,脱离malloc
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32void* ptr VirtualAlloc(0, kpage 13 /*8KB*/, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else// linux下brk mmap等
#endifif (ptr nullptr)throw std::bad_alloc();return ptr;
}//方案二获取的对象每次都是一个T对象T的大小是固定的所以内存池申请的内存也是固定的
templateclass T
class ObjectPool
{
public:T* New(){T* obj nullptr;//换回来的内存可以重复使用//优先把换回来的内存再次重复利用if (_freeList ! nullptr){void* next *(void**)_freeList;obj (T*)_freeList;_freeList next;}else{//T类型有很多种有intdoublefloat还有自定义类型等当我们的obj申请sizeof(T)的内存时到了最后剩余的内存小于sizeof(T)这样依旧会出现问题。//当剩余内存不够一个对象大小时那么重新开空间。if (_remainBytes sizeof(T)){_remainBytes 128 * 1024;//_memory (char*)malloc(_remainBytes); //申请一个固定大小256KB的空间_memory (char*)SystemAlloc(_remainBytes 13);if (_memory nullptr){throw std::bad_alloc();}}obj (T*)_memory;//避免因为int或char字节数过小而导致freelist无法使用所以统一定成指针大小的空间。size_t objSize sizeof(T) sizeof(void*) ? sizeof(void*) : sizeof(T);_memory objSize;_remainBytes - objSize;}//定位new显式调用obj的构造初始化new(obj)T;return obj;}void Delete(T* obj){//显式调用obj的析构函数obj-~T();//if (_freeList nullptr)//{// _freeList obj;// //通过结点头部的4个字节或8个字节(根据自己的系统是32位还是64位为准)指向下一个结点让自由链表的最后一个结点头部指向空。// //*(int*)obj nullptr; // 32位可以64位不行 int*解引用的大小是一个4字节的而64位系统下指针要求8位4// *(void**)obj nullptr; // 这里不管void**、int**还是其它的只要把它转换为二级指针就可以//}//else//{// //头插// *(void**)obj _freeList;// _freeList obj;//}//因为链表中有无结点都无所谓所以直接可以头插。* (void**)obj _freeList;_freeList obj;}
private://指向的大块内存指针void*不能解引用不能,因为它没有意义。所以这里我们使用一个char*,一个char就是一个字节使用多少字节就加多少字节即可char* _memory nullptr; //C11新特性默认缺省值size_t _remainBytes 0; //大块内存被切分的剩余内存字节数//把这些申请的块看成一个个结点每个结点存下一个结点的地址再用一个_freelist指向最开始的结点void* _freeList nullptr; //还回来的内存管理指针
};
四、高并发内存池整体框架设计 现代很多的开发环境都是多核多线程在申请内存的场景下必然存在激烈的锁竞争问题。malloc本身其实已经很优秀那么我们项目的原型tcmalloc就是在多线程高并发的场景下更胜一筹所以这次我们实现的内存池需要考虑以下几方面的问题。
性能问题。多线程环境下锁竞争问题。内存碎片问题。
concurrent memory pool主要由以下3个部分构成
thread cache线程缓存是每个线程独有的用于小于256KB的内存的分配线程从这里申请内存不需要加锁每个线程独享一个cache这也就是这个并发线程池高效的地方。central cache中心缓存是所有线程所共享thread cache是按需从central cache中获取的对象。central cache合适的时机回收thread cache中的对象避免一个线程占用了太多的内存而其他线程的内存吃紧达到内存分配在多个线程中更均衡的按需调度的目的。central cache是存在竞争的所以从这里取内存对象是需要加锁首先这里用的是桶锁其次只有thread cache的没有内存对象时才会找central cache所以这里竞争不会很激烈。page cache页缓存是在central cache缓存上面的一层缓存存储的内存是以页为单位存储及分配的central cache没有内存对象时从page cache分配出一定数量的page并切割成定长大小 的小块内存分配给central cache。当一个span的几个跨度页的对象都回收以后page cache会回收central cache满足条件的span对象并且合并相邻的页组成更大的页缓解内存碎片 的问题。 五、高并发内存池--thread cache 前面我们实现了一个基于对象类型固定长度的定长内存池它的每次申请的内存都是一样大的但是这和我们的需求还是不否因为我想要一个更大的内存你给不上我要一个小的内存你又太大的造成了内碎片过多。所以我们干脆这么想搞出多个定长内存池以满足不同申请内存的需求我们的thread cache线程缓存只需小于256KB的内存块我们不可能每一KB都给弄一个定长内存池所以间隔一些大小的内存设计一个定长内存池而这些内存池用什么进行管理呢可以使用哈希桶进行管理。 1.thread cache设计 thread cache是哈希桶结构每个桶是一个按桶位置映射大小的内存块对象的自由链表。每个线程都会有一个thread cache对象这样每个线程在这里获取对象和释放对象时是无锁的。 2.详细步骤
我们先定义ThreadCache.h 和 ThreadCache.cpp 两个文件越到后面我们的头文件也就越多所以我们定义一个Common.h头文件来放这个项目相同的东西比如头文件共用类等。 1.我们先设计ThreadCache.h这个文件中的类时避免不了要管理多个自由链表所以我们在Common.h文件中定义一个类FreeList里面用于管理切分好的小对象的自由链表FreeList 头插头删的逻辑与定长内存池里的类似此处不便赘述。 2.在ThreadCache.h文件里定义一个ThreadCache的类里面封装一个FreeList的数组对象而这个数组的大小就得看这个哈希表的映射规则了。 我们就需要一个类在common.h中定义SizeClass这个类专门来计算对象大小的对齐映射规则。 我们采取大小最小为8字节因为4字节在32为系统下是可以的但是在64位系统下是不行的64位系统下指针的大小是8字节。但是如果我们这个哈希表数组按照8字节去对齐的话还是不行也不是不行来看一段数据 我们这个ThreadCache能申请的内存大小最大为256KB256KB 262144Byte262144/832768也就是说如果按照8字节对齐我们就需要32768个桶那位程序员来表演一下怕是不行哦写完菜都凉了。 所以我们采取如下的映射规则 验证(我们尽量选取分母小的整数来进行运算这样结果能更大一些) 1-128字节内 (8 - 1) / (18) 0.78 注因为我们最低要求内存需8字节 129-1024字节内 (15) / (12915) 0.10 1025-8*1024字节内 (127) / (1025127) 0.11 8193-64*1024字节内 (1023) / (81931023) 0.11 65537-256*1024字节内 (8191) / (655378191) 0.11 经过计算可以看出这种映射规则普遍情况更优只有10%左右的内碎片浪费率。 ------------------------------------------------------------------------------------------------------------------------- 这里上图所写的8byte对齐、16byte对齐...所写的意思是在左边这个区间里按这个对齐数的倍数来计算而这个区间里的对齐数我们还需要通过下面这份代码来计算。 而获取这个对齐数的方法_RoundUp,有两个方案 我们先不看高手写的先看这种大多数人的想法 原理就是先算出数据大小和这个区间的对齐数的除数再向上取整乘上这个区间的对齐数。 然而我们最后该怎么映射进哪个桶呢 MAX_BYTES 256. 这里的意思就是1到128字节的按照8字节对齐可以划分128 / 8 1616个范围也就是16个桶129 到1024字节的先用1024 - 128/ 16 5656个范围也就是这个区间有56个桶同理下面我就不详细展开了。每个范围都有独特设计的对齐方式经过每种计算方式下得到的桶的数所以我们最后总共需要208个桶。group_array指的是每个范围区间有多少桶。 里面的if条件控制与求对齐数一致,不过传值的时候,bytes小于等于128,那就传bytes和对齐数的对2的指数,如果大于128小于等于1024.那就传字节数-128,4,最后还要加上前面128区间的桶做桶序号. 比如1-8我选个7 传过来 align_shift 传的是8 2^3这个3先让13887-131, 1-1 0,所以最后下标为0 3.TLS--thread local storage线程局部存储TLS是一种变量的存储方法这个变量在它所在的线程内是全局可访问的但是不能被其他线程访问到这样就保持了数据的线程独立性。而熟知的全局变量是所有线程都可以访问的这样就不可避免需要锁来控制增加了控制成本和代码复杂度。 所以我们在ThreadCache.h文件中加上这句全局代码,就可以让每个线程独有这个指针 我们创建一个新的文件ComcurrentAlloc.h来专门申请内存和释放内存 我们顺便打印每个线程和它对应的TLS测试代码和结果如下 我们最后再来设计ThreadCache类中Deallocate这个释放对象内存的函数 就这样我们thread cache大概的框架已经完成后面还需跟其它的结果进行联系细节还需改动后面再说。 六、高并发内存池--central cache 我们这个项目分为3层每个线程没有内存后它们首先向thread cache申请内存每个线程独享一个thread cache如果这个线程申请的内存根据内存大小去它这个线程里的哈希表映射后的地方头删一个内存块分配给这个线程。如果映射的地方没有那么我们就去先下一层central cache里申请 1.central cache设计 central cache也是一个哈希桶结构他的哈希桶的映射关系跟thread cache是一样的。不同的是他的每个哈希桶位置挂是SpanList链表结构不过每个映射桶下面的span中的大内存块被按映射关系切成了一个个小内存块对象挂在span(跨度)的自由链表中。span管理以页为单位的大块内存 这里是要使用锁的使用的是桶锁每个桶都要有一个锁。 如果线程1映射到16号桶下申请内存线程2也映射到16号桶下申请内存那么两个线程就回去下一层cetral cache申请内存它们就会同时访问如果不加锁那么并发访问就会导致数据不一致问题。 申请内存
当thread cache中没有内存时就会批量向central cache申请一些内存对象这里的批量获取对 象的数量使用了类似网络tcp协议拥塞控制的慢开始算法central cache也有一个哈希映射的 spanlistspanlist中挂着span从span中取出对象给thread cache这个过程是需要加锁的不过这里使用的是一个桶锁尽可能提高效率。central cache映射的spanlist中所有span的都没有内存以后则需要向page cache申请一个新的span对象拿到span以后将span管理的内存按大小切好作为自由链表链接到一起。然后从span中取对象给thread cache。central cache的中挂的span中use_count记录分配了多少个对象出去分配一个对象给thread cache就use_count
释放内存
1. 当thread_cache过长或者线程销毁则会将内存释放回central cache中的释放回来时-- use_count。当use_count减到0时则表示所有对象都回到了span则将span释放回page cache page cache中会对前后相邻的空闲页进行合并。 central cache和thread_cache里结构相似都是哈希桶但不同于thread cache里的哈希桶下直接挂自由链表central cache哈希桶下挂着是一个一个的span。span是什么东西呢span是大块内存就是哈希桶下面挂着多个页当thread cache向central cache层要内存时span就会提前把大块内存切好比如时16字节span会给上一层很多16字节的内存块一次性给多一点。如果一个span不够上一层使用他就会继续申请span在桶后面后面挂着。如果thread cahce过长就会将内存释放回central cache里这里还有一个重点的概念 use_count每个span都有一个use_count表示这个span分配出多少内存块假如由下一层分配给central cache的页大小为8KBthread_cache需要8字节的空间中心缓存就会把页切成1024块use_count就为0申请出去use_count释放回来就--use_count等到use_count减到0时就把这个页重新还给页缓存那一层。use_count加到1024后就重新向页缓存申请页。这个就是均衡调度。 span被设计成双向链表如果中间的span的小块内存全被释放回来了那就要把这个span归还到page cache里形成大页内存。 2.详细步骤 1.在common.h中我们需要设计一个span类里面需要有页号为什么需要有页号呢 假如一页8KB32位系统2^32 / 2^13 2^19个页64位系统2^64 / 2^13 2^51个页。 定义页号的类型时因为如下原因需要先声明_WIN64. span的结构 2.再定义一个SpanList的类这个是结点为span的双向带头循环链表 然后在Central cache里定义一个哈希桶桶数与thread_thread相同 因为central cache里会出现多线程并发访问的问题所以我们还需再SpanList这个类定义一个成员变量锁。 3.我们将CentralCache这个类设计成单例模式下的懒汉模式 注意这个_sInit 不要在.h头文件中实现否则多个头文件链接时会出问题所以我们将它在CentralCache.cpp文件中实现。 4.我们ThreadCache有一个功能还没有实现就是当thread cache哈希桶没有内存资源时需向central cache层去申请内存那这个过程该去怎么去申请呢 因为central cache给thread cache层分配切分好的内存块分配的越多越好这样效率高但是大块内存需要分配多吗。所以小块内存分配多些大块内存分配少些这样子就是慢开始的反馈调节算法。在common.h文件中SizeClass这个类中再加入一个静态成员函数NumMoveSize。用来计算一次thread cache从中心缓存获取多少个内存块。 在Common.h文件中FreeList这个类中再定义一个成员变量_maxSize和一个成员函数MaxSize batchNum就是一批的自由链表连接的内存块 通过这样 最开始不会一次向central cache一次批量要太多内存块因为要太多了可能用不完如果你不要这个size大小内存需求那么batchNum会不断增长直到上限size越大一次向central cache申请的内存块数batch就越少size越小一次向central cache申请的内存块数batchNum就会越来越大因为需求大。 FetchRangObj就是从SpanList或者page cache获取一个非空的spanstart就是这个链表的起始块end就是最后一个块。从central cache申请到了内存块如果是一个就把这个返回去给申请的人使用如果申请了多个把第一个返回去其它的挂到线程缓存的哈希桶的桶上进行头插。 5.接下来我们来实现CentralCache.cpp里的FetchRangeObj函数这里肯定是要加锁的防止多线程并发访问。中间处就是申请span上的内存块了这里多种情况一种是span上刚好有一定数量的内存块就把这些个内存块头块给start尾块给end将这个链表通过输出型参数传到TreadCache里的FetchFromCentralCache的函数中。 这中间的代码设计 1.假如batchNum 3这个_freeList长度为4那么可以这样让start指向_freeList让end先指向start向后走batchNum-1个让_freeList指向end的下一个让end的next指向空。 2假如batchNum5_freeList长度为4那就有可能end指空造成野指针问题 改进后逻辑如下 七、高并发内存池--page cache
1.page cache设计 page cache跟上面两层设计类似也是哈希桶每个桶挂着一个又一个的span不过跟以往的不同的是这里的桶号是直接定址法就是1-128号桶每个桶里的span也有所不同这里的span就是大块的页是按页数去映射不需要被切分。 思考一下为什么这里最大的桶定到了128 我们申请单个内存最大容量256KB假设一页8KB那么128*8 1M可以切4个256KB。已经足够了 申请内存
当central cache向page cache申请内存时page cache先检查对应位置有没有span如果没有 则向更大页寻找一个span如果找到则分裂成两个。比如申请的是4页page4页page后面没 有挂span则向后面寻找更大的span假设在10页page位置找到一个span则将10页page span分裂为一个4页page span和一个6页page span。如果找到_spanList[128]都没有合适的span则向系统使用mmap、brk或者是VirtualAlloc等方式 申请128页page span挂在自由链表中再重复1中的过程。需要注意的是central cache和page cache 的核心结构都是spanlist的哈希桶但是他们是有本质 区别的central cache中哈希桶是按跟thread cache一样的大小对齐关系映射的他的spanlist 中挂的span中的内存都被按映射关系切好链接成小块内存的自由链表。而page cache 中的 spanlist则是按下标桶号映射的也就是说第i号桶中挂的span都是i页内存。
释放内存
如果central cache释放回一个span则依次寻找span的前后page id的没有在使用的空闲span 看是否可以合并如果合并继续向前寻找。这样就可以将切小的内存合并收缩成大的span减少 内存碎片。 2.详细设计 1.先新建两个文件PageCache.h和PageCache.cpp当然我们在PageCache.h里定义的PageCache类也是一个单例模式确保多线程并发访问不会带来的数据不一致问题。 老样子不必多说。NPAGES是定义的哈希桶数 所以这里不好用桶锁因为是在整个哈希表进行检索。 3.完善central cache结构中GetOneSpan函数从SpanList或者page cache获取一个非空的span。 而要是映射进central cache的span都为空那么我们就要从page cache里去申请页块了。 如果单个内存块是16byte那么 16byte* 512 8KB8KB / 8KB 1页 就是这么算页数 4申请下这个页后我们就要给它切分了我们先算出它的地址来页号 PAGE_SHIFT 把地址变成一个一个的char后char的访问是1字节的有利于切分 我们在这里进行一个尾插因为尾插空间是连续的有利于CPU高速缓存的命中率 然而走到这里还有一种情况就是最开始的时候page cache哈希桶上都没有页 接下来就是捋清楚这里面的逻辑 这是central cache先检查中心缓存的spanlist还有空闲的span如果没有就要向page cache申请一大块页内存 这是page cache里的申请内存如果自己的哈希桶上还有页块就把这个页给中心缓存如果没有先向后找找到了先把它切分把k的大小的页给中心缓存剩余的重新计算位置并把它放到这个哈希桶上。如果找遍了整个哈希桶都没有页比如第一次那就要向系统重新申请一个大小为128KB的页再递归函数复用上面的逻辑将合适的页给中心缓存剩余的重新挂接到spanlist这个哈希桶上 这其中有一些细节就是central cache从page cache里获取到页以后通过 其余的没什么好说 接下来就是桶锁的问题这个page cache的锁应该在哪里加如果在每个桶上加锁那就会造成每次访问一个桶都要进行加锁解锁等待这样一个过程会极大的影响效率而我们的page cache里的这个哈希桶不是向cetnral cache 里的那样一次只用访问一个桶我们page cache是要经常访问大部分桶而从central cache里对page cache哈希桶的访问就已经开始了所以我们究竟在哪里进行加锁和解锁呢。 注意看 我们在central cache里给thread cache里给内存块时调用刚才的GetOneSpan函数这个就是要从central cache 和page cache里拿取span这里面我们是要加锁的而当我们进入GetOneSpan函数中去是带着外面的锁进去的而这个锁解了为好因为每个线程都可能要往GetOneSpan函数中要内存块所以在GetOneSpan开头直接进行解锁。而这个解锁的位置应该是在前往page cache前解锁在访问central cache后解锁如果其它对象释放内存回来不会阻塞。 这里是central cache里的GetOneSpan函数 最后在list.push_front(span);前也需要加锁 申请流程done
八、申请流程串联调试
1.我需要申请6个字节的内存块因为我们这是一个线程所以不使用并行监视 2.计算出在线程缓存中内存对齐后总共给8个字节的内存块桶号为0 3.因为一开始线程缓存中并没有内存所以就去中心缓存申请内存采取了慢开始的方法一次就申请一个span内存块 4.在中心缓存查看自己的哈希桶是否有内存块时因为一开始所以为空 5.因为中心缓存哈希桶为空所以我们就要去页缓存中申请页块我们一次要的内存块大小4096字节还不够一页所以就要1页 6.中心缓存哈希桶没有所以我们就去页缓存申请页缓存查看自己的哈希桶有无页块因为是一开始所以都没有_spanList[k].Empty()为空 7. 通过页号算取指针地址因为我们整个哈希桶都没有页块所以我们就要向系统申请一个128KB的大页块。在这里我们可以使用页块号来计算指针的地址。一页8KB页号和页数相乘就是页指针的地址 8.将128页进行切分1页8KB给central cache切上一页剩余的127页插入进页号为127的桶里
刚才重新调了一下ptr指针改变了所以重新查看了ptr的地址 我们这个start的起始地址与申请的128KB的页的其实地址相同 9.在CentralCache里的GetOneSpan从page cache获取到的页块会立即进行切分我在这里加一个i用于计数看它切了几次 10.接下来就可以走下一个了下一个就没必要去走全部的路程了只需将关键的展示出来即可
11.因为第一次我们申请的页块因为慢增长第一次只拿一块thread cache即去既用了剩余的span全在中心缓存当中所以我们只需到中心缓存中取页块第二次我们就可以直接拿2块内存块了 12.这一次的中心缓存就是非空了我们就可以直接去拿两块内存块 我们实际当中拿走了两块走到了else里 13.而当我们第三次申请内存块中因为前一次申请了两个块所以这次的直接从thread cache拿走内存块 对齐数也是8桶号也是0所以_freelist不为空所以直接拿 14.如果将这些申请的内存指针地址打印一下这些指针的地址刚好是连续的 因为这是16进制08到10刚好是08 09 0a 0b 0c 0d 0e 10 ,加起来刚好是8个。
当然这只是开始申请的时候内存连续。 九、回收多余的内存块 这个多余是相对的如果thread cache里桶的块数量大于一次从central cache申请的块数量MaxSize那就要回收。如果central cache给thread cache的内存块都被还回来了那就要把这个内存还给page central以合并更大的页内存。 1.我们就要现在thread cache进行返回多余的内存块这时就需要在添加一个函数在ThreadCache.h中声明一个ListTooLong函数在.cpp文件中实现在自由链表FreeList结构体中还有定义一个函数PopRange一次回收size长度个的内存块 2.common.h中FreeList结构体中添加一个PopRange的函数逻辑如下先让start和end都指向_freeList再让end走size - 1步让_freelist指向end的下一个end的next指向空 最后_size - size; 当前thread cache的释放内存的逻辑就走通了。 至此thread cache所有的回收内存给上层的工作都已完成 3.从central cache哈希桶上拿一个span给thread cache但是从thread cache回收回来时我们并不清楚这个内存块是属于哪一个span那么该如何解决这个问题呢 假设我们的页的页号是2000那么它左移13位就可以得到它的地址。下图验证 如果2000页中间的内存除以8KB就可以直接得到它的页号。 4.我们就需要在PageCache类定义一个成员函数 通过对象地址右移13位算出它的页号再通过哈希map的映射出页号和spanlist这个头节点的地址从而实现回收工作 这里访问central cache里的哈希桶时还是需要加锁的通过上面那个函数计算出span的地址进行头插工作如果span结点里的usecount减到0时就说明span的内存块全部的回收回来了。 5.我们就要在page cache里定义一个函数ReleaseSpanToPageCache用于回收central cache里的span 在central cache的ReleaseListToSpans回收函数里是这样体现的 不能动页号和页数页号和页数可以用于计算整个页的起始地址 然后就是锁的问题因为这个线程已经到page cache了我们就是把这个桶锁解掉让下一格线程释放内存或者申请内存都可以进来然后我们在进入page cache这一层时我们也要加上page cache的大锁。 6.接下来就是要处理page cache的回收span的工作了 这里要是简单回收很简单但是我们目的是要缓解内存碎片问题所以我们需要对span的前后的页进行合并。 我们还需在span这个结构体中加入一个isuse的标识符防止映射到正在使用的span 然后在page cache向下切分页时将留下的页进行映射还是那个哈希map 向前向后合并页块 向前合并 这是向后合并的代码 两个都是逻辑类似。 十、释放流程串联调试
1.还是之前申请的内存不过这次加了释放 桶是0号桶0号桶这时有2个 2.释放第二个内存时size就变成了3个0号桶的_freeList的地址也增长了8 3.当释放第三个内存时这是size等于maxsize就要把同上maxsize个内存块释放还给central cache 4.在listtoolong中将thread cache0号桶上的内存块全给弹走这时0号桶位空maxsize依旧为4 5.验证start能否算出页号 6.验证从page cache 从central cache回收span并合并页块
这里到这个合并前页这里 向后合并时发现后面有页 最后计算span的页数量为128 十一、优化
1. 大于256KB的大块内存申请问题
我们申请内存是先通过线程缓存去申请内存线程缓存没有那就去中心缓存申请span的内存块中心缓存没有那就去页缓存去申请页块内存页缓存没有那就要去系统去申请内存。申请内存大致有三种情况
申请的内存小于等于256KB这里走的就是正常的三层路线。申请的内存大于256KB呢256/8 32页
如果申请的内存大于256KB小于等于128页也就是128*8KB这里就可以直接去找页缓存去申请大页块如果申请的内存大于128页那就要找系统堆了
我们就要进行改造了
现在对齐数这里我们把对最后一个判断的直接把对齐数设为8KB 在ConcurrentAlloc这个申请内存的函数中我们要申请大于256KB的内存可以不经过thread cache层和central cache层直接去往page cache层算出这个内存的对齐数和它的页数直接让page cache处理 在page cache里的NewSpan函数里加一个如果k大于128页直接去系统申请申请好后直接给到用户使用。并且将当前申请的页存进哈希map中。 当然还有释放的逻辑
在ConcurrentFree这个用户直接释放的函数中我们算取span在这个哈希map中直接取page cache层直接调用PageCahe类中的释放函数。 调用win32底下的SystemFree函数直接将大于128页的内存归还给系统。 2. 使用定长内存池配合脱离使用new。
在每个类中定义一个变量用内存池中的New和Delete
3.释放对象时优化为不传对象大小 我们正常的free和delete在释放对象时是不需要传递空间大小的而这里我们为了简便操作所以在释放对象内存时加上了内存大小接下来我们就要优化一下这里面的问题。
1.方案一 在PageCache这个类中我们可以添加一个哈希map。用于存取页号和size的映射从而记录内存块大小。因为我们在这里申请页块的逻辑一个页块肯定切不出不同的大小。 2.方案二 可以在span这个结构体中添加一个成员变量记录当前内存块的大小。还是一样的道理一个页块肯定切不出不同的大小。
在pagecache获取到这个span时顺手记录当前内存块的大小。 这样你这个要释放的内存块是属于哪个span那你这个span下的内存块大小肯定是一致的。 当然如果申请的是大块内存大于128页的内存也可以通过span来记录当前页块的大小。 十二、性能测试
1.多线程环境下对比malloc测试
//ntimes ,一轮申请释放的次数 nworks线程数 rounds轮次
void BenchmarkMalloc(size_t ntimes, size_t nworks, size_t rounds)
{std::vectorstd::thread vthread(nworks);size_t malloc_costtime 0;size_t free_costtime 0;for (size_t k 0; k nworks; k){vthread[k] std::thread([, k]() {std::vectorvoid* v;v.reserve(ntimes);for (size_t j 0; j rounds; j){size_t begin1 clock();for (size_t i 0; i ntimes; i){v.push_back(malloc(16));//v.push_back(malloc((16 i) % 8192 1));}size_t end1 clock();size_t begin2 clock();for (size_t i 0; i ntimes; i){free(v[i]);}size_t end2 clock();v.clear();malloc_costtime (end1 - begin1);free_costtime (end2 - begin2);}});}for (auto t : vthread){t.join();}printf(%u个线程并发执行%u轮次每轮次malloc %u次: 花费%u ms\n,nworks, rounds, ntimes, malloc_costtime);printf(%u个线程并发执行%u轮次每轮次free %u次: 花费%u ms\n,nworks, rounds, ntimes, free_costtime);printf(%u个线程并发mallocfree %u次总计花费%u ms\n,nworks, nworks * rounds * ntimes, malloc_costtime free_costtime);
}// 单轮次申请释放次数 线程数 轮次
void BenchmarkConcurrentMalloc(size_t ntimes, size_t nworks, size_t rounds)
{std::vectorstd::thread vthread(nworks);size_t malloc_costtime 0;size_t free_costtime 0;for (size_t k 0; k nworks; k){vthread[k] std::thread([]() {std::vectorvoid* v;v.reserve(ntimes);for (size_t j 0; j rounds; j){size_t begin1 clock();for (size_t i 0; i ntimes; i){v.push_back(ConcurrentAlloc(16));//v.push_back(ConcurrentAlloc((16 i) % 8192 1));}size_t end1 clock();size_t begin2 clock();for (size_t i 0; i ntimes; i){ConcurrentFree(v[i]);}size_t end2 clock();v.clear();malloc_costtime (end1 - begin1);free_costtime (end2 - begin2);}});}for (auto t : vthread){t.join();}printf(%u个线程并发执行%u轮次每轮次concurrent alloc %u次: 花费%u ms\n,nworks, rounds, ntimes, malloc_costtime);printf(%u个线程并发执行%u轮次每轮次concurrent dealloc %u次: 花费%u ms\n,nworks, rounds, ntimes, free_costtime);printf(%u个线程并发concurrent allocdealloc %u次总计花费%u ms\n,nworks, nworks * rounds * ntimes, malloc_costtime free_costtime);
}
int main()
{size_t n 10000;cout endl;BenchmarkConcurrentMalloc(n, 4, 10);cout endl endl;BenchmarkMalloc(n, 4, 10);cout endl;return 0;
}运行后的结果发现还是差强人意。还得需要优化在vs下性能检测锁消耗了大量的时间 十三、
实际中我们测试了当前实现的并发内存池比malloc/free是更加高效的那么我们能否替换到系 统调用malloc呢实际上是可以的。
不同平台替换方式不同。 基于unix的系统上的glibc使用了weak alias的方式替换。具体来说是因为这些入口函数都被定义成了weak symbols再加上gcc支持 alias attribute所以替换就变成了这种通用形式
void* malloc(size_t size) THROW attribute__ ((alias (tc_malloc))) 因此所有malloc的调用都跳转到了tc_malloc的实现。
