C语言 面向对象内存池构想
边界对齐
开始之前先简单讲讲边界对齐。之前的专栏介绍了C语言中malloc()分配的内存对齐问题,一般情况下为半字对齐,即在64位机中调用malloc()分配内存时如果没有达到半字字长(32位),那么就会自动填充到32位,这样一来就造成了很大的开销。不过这样设计可以减少访问内存的次数,一次访存就能取出数据,如下图:
从王道计组第47页的内容来看,存储器提供了按字节,半字和字寻址的多种寻址方式,假设存储字长为32位的话，按字节寻址一次只能读出8位,按半字寻址一次能读出16位,按字寻址一次能读出32位。如果按字节寻址,读出一个字需要读4次,这不得累死。那么肯定是一次存取能读得越多越好啊,假设按字寻址,一次可以读出32位数据,但如果数据是short类型(16位),就会产生16位的开销,浪费了16位空间。再比如数据是char类型(8位),就浪费了24位空间。
假设存储字长是64位,且按照字边界对齐方式存储,那么char类型的开销就达到了56位。可见边界对齐并不是越大越好的,空间开销会成倍增长。这是一种空间换时间的思想,空间代价太大换来的时间就不划算了,那么就取一个平均值,半字对齐。
这样一来,取1字节的小数据开销不会太大,取8字节的大数据,大数据又不常用,用两个周期取存取也没多大影响。
如果不按照边界对齐存储会怎么样呢？
像图2.11 因为没有对齐,所以导致字1被分成了两行,这时你要想取字1(字1-1和字1-2)时就需要访存两次。
由于存储器存储字长为32位,访存采用字寻址方式,所以每次只能4个字节4个字节的去读取,要读字1时只能先读高32位,再读低32位,然后再把这两组数据拼接起来,十分的阴间啊。
值得一提的是,王道在此节最后还介绍了精简指令集架构的处理器例如ARM采用边界对齐方式,而复杂指令集架构的处理器如x86对齐和不对齐都支持。而在对齐方式下取指令的时间相同,可以适应指令流水。
C语言中的内存对齐
在C语言malloc()的对齐中,不再按照半字,字节等单位进行边界对齐了,转而使用指针长度为单位(64位机下指针长度为8字节)。原理简单说明下,调用malloc()会分配空间并返回一个指针,而在C语言中访存指针,也就是先做64位地址寻址后,再把内存空间中的值拿出来。
看过我上篇博客的都知道,win10 64位的内存对齐系数是16字节,最小分配空间是32字节,那么以分配34字节为例子,malloc(34),理论上大小应该是头部+数据=8+34=42字节,超过了32字节,系统会进行内存对齐,对齐到48字节。但如果不对齐呢,就按照42字节去访问会怎么样?假设按字寻址,每次读8字节,最好的情况下需要访问6次内存,最坏的情况下需要访问7次内存。但是对齐之后48字节,只需要访问6次,这样一来虽然增加了开销,但是减少了访存次数。
改进
既然C语言malloc()会额外产生这么大的内存开销(包括头部开销和对齐开销)有没有一种办法能既不影响内存对齐又不产生过多的开销呢？答案是肯定的,通过内存池。
首先先用malloc()分配一块504字节的空间作为内存池的初始大小,后续内存池的扩容也以504字节为单位。malloc(504)不会产生任何开销,加上头部8字节刚好是512,是16的整数倍。
再额外分配64字节(512bit 1bit可表示0和1)的空间来记录内存池存储单元的占用情况,为1表示被使用,为0表示可用。
这样算下来,总共分配了512+64=576字节,只多了13%的开销。
而直接使用malloc()进行分配,由于存在最小分配空间的限制,最小也要分配32字节,会产生极大的开销。再加上每次分配都会产生的的16字节内存对齐开销,stm32看了简直要落泪啊。
内存池初始化完毕后,怎么进行分配和管理呢？
先看内存池存储单元的结构设计:
存储单元分为两部分:
DATA 数据区: 长度最小为1字节
NEXT下地址: 占用1字节(0-256),表示与此存储单元相连接的下一块内存单元地址。可用于连接256对碎片空间(共512个空间)
结构非常简单,创建数据仅额外占用1字节开销用于连接碎片空间,最小长度为2字节。
例如需要创建48字节空间,那么就需要内存池中有49字节的连续空间。
若有足够连续空间,则直接分配并返回头指针(额外开销1字节)
若有足够非连续的空间,则按碎片块的大小依次分配并连接,每次连接碎片块将产生1字节下地址开销。
最坏情况下(内存池中全是2字节大小的碎片空间),那就需要连接48对内存碎片(共96个碎片空间),额外开销达到2N=96字节。在这种情况下,使用内存池碎片分配产生的开销远远大于直接malloc(48)分配的开销(64字节),那么就不从内存池碎片分配,而对内存池进行扩容,分配一块新的512字节连续内存空间,再在这块空间中分配内存给用户。
非最坏情况下(开销小于直接malloc()的开销),那么就按碎片块的大小依次分配并连接,每次连接碎片块将产生1字节下地址。
若无足够空间,则对内存池进行扩容,分配一块新的512字节连续内存空间后再从这块空间中分配内存给用户。
经过这样的设计,不会过多开销,唯一的问题就是碎片内存的使用。要知道像传统的malloc()法分配内存空间都是返回一个指向连续内存空间的指针,而碎片空间虽然在逻辑上连续,但是实际上采用指针是访问不了下地址的。例如:
若用指针操作:
char* A= memPoolAlloc(); //从内存池分配空间
for(int i=0;i<5;i++) printf("%c ",*A);
这样是无法把完整的字符数组A打印出来的
所以我转变思路,直接采用对象来代替指针,用对象封装底层的逻辑内存和实际内存的转换,熟知的读取,仅将数据读取接口提供给用户,通过调用此接口即可代替用户使用指针来完成数据的读取,下面我将演示一个大体的构想:
//Bytes是一个结构体(基本类型),注意不是结构体指针!
Bytes bytes=new(Bytes,27); //从内存池中分配27个字节空间,类型为字节集合
char data1=bytes.getByte(5); //获取字节集合索引值为5的字节类型数据
char* data2=bytes.getString(24); //获取字节集合索引值为24的字符串数据
int data3=bytes.getInteger(10);//获取字节集合索引值为10的整型数据
这样一来,部署了此内存池之后,由于内存碎片整理的问题,用户不能用指针去正确访问内存池的数据,但是通过引入面向对象的机制,来规避对底层指针的依赖。
此专栏仅仅是对近期学习的总结和对曾经内存池设计的设想方案,有生之年我将会将此方案实现并分享。
