为了速度和正确性,请对齐你的数据.
概述:对于所有直接操作内存的程序员来说,数据对齐都是很重要的问题.数据对齐对你的程序的表现甚至能否正常运行都会产生影响.就像本文章阐述的一样,理解了对齐的本质还能够解释一些处理器的"奇怪的"行为.
内存存取粒度
程序员通常倾向于认为内存就像一个字节数组.在C及其衍生语言中,char * 用来指代"一块内存",甚至在JAVA中也有byte[]类型来指代物理内存.
Figure 1. 程序员是如何看内存的
然而,你的处理器并不是按字节块来存取内存的.它一般会以双字节,四字节,8字节,16字节甚至32字节为单位来存取内存.我们将上述这些存取单位称为内存存取粒度.
Figure 2. 处理器是如何看内存的
高层(语言)程序员认为的内存形态和处理器对内存的实际处理方式之间的差异产生了许多有趣的问题,本文旨在阐述这些问题.
如果你不理解内存对齐,你编写的程序将有可能产生下面的问题,按严重程度递增:
程序运行速度变慢
应用程序产生死锁
操作系统崩溃
你的程序会毫无征兆的出错,产生错误的结果(silently fail如何翻译?)
内存对齐基础
为了说明内存对齐背后的原理,我们考察一个任务,并观察内存存取粒度是如何对该任务产生影响的.这个任务很简单:先从地址0读取4个字节到寄存器,然后从地址1读取4个字节到寄存器.
首先考察内存存取粒度为1byte的情况:
Figure 3. 单字节存取
这迎合了那些天真的程序员的观点:从地址0和地址1读取4字节数据都需要相同的4次操作.现在再看看存取粒度为双字节的处理器(像最初的68000处理器)的情况:
Figure 4. 双字节存取
从地址0读取数据,双字节存取粒度的处理器读内存的次数是单字节存取粒度处理器的一半.因为每次内存存取都会产生一个固定的开销,最小化内存存取次数将提升程序的性能.
但从地址1读取数据时由于地址1没有和处理器的内存存取边界对齐,处理器就会做一些额外的工作.地址1这样的地址被称作非对齐地址.由于地址1是非对齐的,双字节存取粒度的处理器必须再读一次内存才能获取想要的4个字节,这减缓了操作的速度.
最后我们再看一下存取粒度为4字节的处理器(像68030,PowerPC® 601)的情况:
Figure 5. 四字节存取
在对齐的内存地址上,四字节存取粒度处理器可以一次性的将4个字节全部读出;而在非对齐的内存地址上,读取次数将加倍.
既然你理解了内存对齐背后的原理,那么你就可以探索该领域相关的一些问题了.
懒惰的处理器
处理器对非对齐内存的存取有一些技巧.考虑上面的四字节存取粒度处理器从地址1读取4字节的情况,你肯定想到了下面的解决方法:
Figure 6. 处理器如何处理非对齐内存地址
处理器先从非对齐地址读取第一个4字节块,剔除不想要的字节,然后读取下一个4字节块,同样剔除不要的数据,最后留下的两块数据合并放入寄存器.这需要做很多工作.
有些处理器并不情愿为你做这些工作.
最初的68000处理器的存取粒度是双字节,没有应对非对齐内存地址的电路系统.当遇到非对齐内存地址的存取时,它将抛出一个异常.最初的Mac OS并没有妥善处理这个异常,它会直接要求用户重启机器.悲剧.
随后的680x0系列,像68020,放宽了这个的限制,支持了非对齐内存地址存取的相关操作.这解释了为什么一些在68020上正常运行的旧软件会在68000上崩溃.这也解释了为什么当时一些老Mac编程人员会将指针初始化成奇数地址.在最初的Mac机器上如果指针在使用前没有被重新赋值成有效地址,Mac会立即跳到调试器.通常他们通过检查调用堆栈会找到问题所在.
所有的处理器都使用有限的晶体管来完成工作.支持非对齐内存地址的存取操作会消减"晶体管预算",这些晶体管原本可以用来提升其他模块的速度或者增加新的功能.
以速度的名义牺牲非对齐内存存取功能的一个例子就是MIPS.为了提升速度,MIPS几乎废除了所有的琐碎功能.
PowerPC各取所长.目前所有的PowPC都硬件支持非对齐的32位整型的存取.虽然牺牲掉了一部分性能,但这些损失在逐渐减少.
另一方面,现今的PowPC处理器缺少对非对齐的64-bit浮点型数据的存取的硬件支持.当被要求从非对齐内存读取浮点数时,PowerPC会抛出异常并让操作系统来处理内存对齐这样的杂事.软件解决内存对齐要比硬件慢得多.
psting 1. 每次处理一个字节
void Munge8( void *data, uint32_t size ){
uint8_t *data8 = (uint8_t*)data;
uint8_t *data8End = data8 +size;
while( data8 != data8End ){
*data8++ = -*data8;
}
}
运行这个函数需要67364微秒,现在修改成每次处理2个字节,这将使存取次数减半:
psting 2.每次处理2个字节
void Munge16( void *data, uint32_t size ){
uint16_t *data16 = (uint16_t*)data;
uint16_t *data16End = data16 + (size>> 1); /* Divide size by 2. */
uint8_t *data8 = (uint8_t*)data16End;
uint8_t *data8End = data8 + (size& 0x00000001); /* Strip upper 31 bits. */
while( data16 != data16End ){
*data16++ = -*data16;
}
while( data8 != data8End ){
*data8++ = -*data8;
}
}
如果处理的内存地址是对齐的话,上述函数处理同一个缓冲区需要48765微秒--比Munge8快38%.如果缓冲区不是对齐的,处理时间会增加到66385微秒--比对齐情况下慢了27%.下图展示了对齐内存和非对齐内存之间的性能对比.
速度
下面编写一些测试来说明非对齐内存对性能造成的损失.过程很简单:从一个10MB的缓冲区中读取,取反,并写回数据.这些测试有两个变量:
处理缓冲区的处理粒度,单位bytes. 一开始每次处理1个字节,然后2个字节,4个字节和8个字节.
缓冲区的对准. 用每次增加缓冲区的指针来交错调整内存地址,然后重新做每个测试.
这些测试运行在800MHz的PowerBook G4上.为了最小化中断引起的波动,这里取十次结果的平均值.第一个是处理粒度为单字节的情况:
psting 1. 每次处理一个字节
void Munge8( void *data, uint32_t size ){
uint8_t *data8 = (uint8_t*)data;
uint8_t *data8End = data8 +size;
while( data8 != data8End ){
*data8++ = -*data8;
}
}
运行这个函数需要67364微秒,现在修改成每次处理2个字节,这将使存取次数减半:
psting 2.每次处理2个字节
void Munge16( void *data, uint32_t size ){
uint16_t *data16 = (uint16_t*)data;
uint16_t *data16End = data16 + (size>> 1); /* Divide size by 2. */
uint8_t *data8 = (uint8_t*)data16End;
uint8_t *data8End = data8 + (size& 0x00000001); /* Strip upper 31 bits. */
while( data16 != data16End ){
*data16++ = -*data16;
}
while( data8 != data8End ){
*data8++ = -*data8;
}
}
如果处理的内存地址是对齐的话,上述函数处理同一个缓冲区需要48765微秒--比Munge8快38%.如果缓冲区不是对齐的,处理时间会增加到66385微秒--比对齐情况下慢了27%.下图展示了对齐内存和非对齐内存之间的性能对比.
Figure7. 单字节存取 vs.双字节存取
第一个让人注意到的现象是单字节存取结果很均匀,且都很慢.第二个是双字节存取时,每当地址是单数时,变慢的27%就会出现.
下面加大赌注,每次处理4个字节:
psting 3. 每次处理4个字节
void Munge32( void *data, uint32_t size ){
uint32_t *data32 = (uint32_t*)data;
uint32_t *data32End = data32 + (size>> 2); /* Divide size by 4. */
uint8_t *data8 = (uint8_t*)data32End;
uint8_t *data8End = data8 + (size& 0x00000003); /* Strip upper 30 bits. */
while( data32 != data32End ){
*data32++ = -*data32;
}
while( data8 != data8End ){
*data8++ = -*data8;
}
}
对于对齐的缓冲区,函数需要43043微秒;对于非对齐的缓冲区,函数需要55775微秒.因此,在所测试的机器上,非对齐地址的四字节存取速度比对齐地址的双字节存取速度要慢.
Figure8. 单字节vs.双字节vs.四字节存取
现在来最恐怖的:每次处理8个字节:
psting 4.每次处理8个字节
void Munge64( void *data, uint32_t size ){
double *data64 = (double*)data;
double *data64End = data64 + (size>> 3); /* Divide size by 8. */
uint8_t *data8 = (uint8_t*)data64End;
uint8_t *data8End = data8 + (size& 0x00000007); /* Strip upper 29 bits. */
while( data64 != data64End ){
*data64++ = -*data64;
}
while( data8 != data8End ){
*data8++ = -*data8;
}
}
Munge64处理对齐的缓冲区需要39085微秒--大约比对齐的Munge32快10%.但是,在非对齐缓冲区上的处理时间是让人惊讶的1841155微秒--比对齐的慢了两个数量级,慢了足足4610%.
怎么回事?因为我们现今所使用的PowerPC缺少对存取非对齐内存的浮点数的硬件支持.对每次非对齐内存的存取,处理器都抛出一个异常.操作系统获取该异常并软件实现内存对齐.下图显示了非对齐内存存取带来的不利后果.
Figure 9. 多字节存取对比
单字节,双字节和四字节的细节都被掩盖了.或许去除顶部以后的图形,如下图,更清晰:
Figure 10. 多字节存取对比 #2
在这些数据背后还隐藏着一个微妙的现象.比较8字节粒度时边界是4的倍数的内存的存取速度:
Figure10. 多字节存取对比 #3
你会发现8字节粒度时边界为4和12字节的内存存取速度要比相同情况下的4和2字节粒度的慢.即使PowerPC硬件支持4字节对齐的8字节双浮点型数据的存取,你还是要承担额外的开销造成的损失.诚然,这种损失绝不会像4610%那么大,但还是不能忽略的.这个实验告诉我们:存取非对齐内存时，大粒度的存取可能会比小粒度存取还要慢