发信人: law (游戏*人生), 信区: C
标 题: Re: 发句牢骚
发信站: 饮水思源 (Fri May 24 15:59:56 2002) , 转信
不对齐的数据存取在x86上是影响速度，
到了sparc或者MIPS上就是个bus error。
对齐原则一般是对应指令操作数据的长度。
例如*(int *)p = 1;
在MIPS上一般会被编译成sw(store word)指令
p要按照sizeof (int)对齐。
*(char *)p = 1.
对应sb指令，就不需要对齐了。
发信人: jackzhang (编程浪子), 信区: C
标 题: 对齐问题的小结和疑问
发信站: 饮水思源 (2002年05月24日21:15:32 星期五), 站内信件
假设所有的数据类型的长度都是2的n次方
(char[5] == 5个char)
假设编译器采用这种对齐策略:
"上一个"字段的地址(初始=0)
offset
"当前字段"
count
"当前"字段的类型
type(count)
"上一个"字段和"当前"字段之间填充长度
fillsize
假如满足
( offset + sizeof(type(count-1)) + fillsize) mod sizeof(type(count)) == 0
则认为是对齐的,前提当然是整个struct的基地址是"0"
如果不满足,那就在第(count)和第(count+1)字段之间填充
这些都是由编译器在编译的时候做的,但是不能保证在运行的时候
各个字段也是对齐的,关键在于struct的实际基地址
例如
struct A
{
WORD a1;
DWORD a2;
};
如果&a == 2,那么a.a2就没有对齐,那么对于运行时的分配策略来说,
只要struct的基地址能被struct中最大字段的长度(2的n次方)整除,
那么在运行时也是每个字段也是对齐的.
精确的说法是所有字段长度的最小公倍数整除,因为假设所有字段的
长度都是2的n次方,但是有个问题这里:struct本身也可以看成单一字
段,例如:
struct foo
{
WORD a1;
WORD a2;
WORD a3;
};
struct foo2
{
foo f1;
WDORD d;
};
就可以看成长度是6的字段
证明:用数学归纳法,
编译时的对齐等式中的offset换成base+offset,而由于base能被
最大的2的n次方整除,所以编译时的等式仍然成立.
对于win32的内存分配VirtualAlloc来说它的基地址必然是64K的
整数倍,那理论上用VirtualAlloc分配的struct运行时是对齐的.
因为可以认为没有比64K更大的字段类型了.
对于new(malloc)来说,它相当于管理VirtualAlloc分配的内存
进行内部再分配,当然分配算法不可能去找stuct中的最大的字
段长度,那对于32位计算机来说,struct基地址至少能被4整除,
猜想:
标志堆的使用情况的内部数据是32位的,例如某个内存块的使用
用下列结构描述
struct
{
DWORD len;
char buf[1];
};
所以导致buf(也就是new返回的地址)落在32位边界上.
当然c/c++的heap的管理肯定复杂的多.
总之在运行的时候不一定能保证全部对齐,因为一方面不是所有的
字段长度都是1,2,4,还有其他的例如6,除非base能被所有字段的最
小公倍数整除.
回家的路上想起为什么会没有对齐了,因为我的struct中有变长字
段,然后一块内存含有n个struct,这样这块内存中"下一个"struct
可能会没有对齐.
struct STRING
{
short len;
char buf[1];
};
解决的办法可以用law说的ReadWord()来做,但是效率低,一开始
我想到变为
struct STRING
{
short len;
char * buf;
};
然后把变长的内容放到"所有"的struct的后面,但是一方面在生
成内存存储的时候有一点繁琐(需要最后空闲位置指针),而且更
关键的是并没有解决对齐问题,换句话说,如果一个struct完全
是由WORD和DWORD组成,也不能保证"下一个"struct是对齐的,
例如
struct A
{
WORD a;
};
struct B
{
DWORD b;
};
如果内存中连续有A和B,那b.b不一定对齐.
因此我的解决办法是
规定struct必须全部由WORD组成(当然也可以全部由DWORD组成)
struct STRING
{
short len;
short xxx;
//...
char buf[1];
};
对于buf的实际长度必须是2的整数倍
len = strlen(str) + strlen(str) mod 2;
STRING * s = (STRING*)malloc(sizeof(STRING) + len - 1);
memcpy(s->buf, str, len);
发信人: law (游戏*人生), 信区: C
标 题: Re: 对齐问题的小结和疑问
发信站: 饮水思源 (2002年05月24日23:36:12 星期五), 站内信件
glibc的malloc策略大致是2*sizeof(size_t)对齐的，
这是因为它的内存头定义为这么大。
当你需要更大的
对齐字节数的时候，可以用memalign来分配，它的策略
是分配一块内存然后取对齐部分，并回收以前的零头。
一般的C库分配的内存至少是按sizeof(int)对齐的。
但对齐有时候会比较浪费，因为内碎片。
所以我曾经针对特定应用，
设计过更复杂的分配策略。
就是对于不需要对齐操作的小内存块用小内存头组织成
hash表来分配，
并放在单独的堆里，一般的操作还是2*sizeof(size_t)对齐，
更大的对齐操作用glibc的策略。
这其实是一种用时间换空间的策略。
当你的应用有大量零碎内存块的时候可以节省内存。
但因为内存头比较小，所以涉及一些位操作，可能会慢一点。
实际上编译器的对齐策略基本是一致的
在程序里找到不对齐的操作并不是一件难事，
因为有core dump。
