1.深入内存对齐

为什么需要内存对齐呢？我们定义一个变量后，就会为该变量在某内存地址处分配一个空间。举例如下：

struct A

{

int d;

char c;

long l;

}

A a={0};//定义一个变量a.

设a 的地址为0，则a.d地址为0，a.c为4，a.l为5。如果空间真的是这样分配的话，会造成一个问题，在X86体系机器上，CPU的一次访存是直接取出32位的值。当我们写出类似 long tmp = a.l 的代码，那么，CPU将会从 a.l 这个地址开始，取出四个字节的数据。先假设内存的设计是，允许从任意地址取值，但若按“规整”的方式取值，效率更高一些。若从 内存地址 5 处开始取值，则会产生两次取值： 第一次取567三个字节的数据，第二次取8字节处的数据。因为，0123，4567，...每四个字节为一个单元，跨单元取值需要多次取。

解决这个问题的方法就是内存对齐。设想，如果任何变量均可以在一次取值内完毕，或者，每一次取值的效率都达到了百分之百（即，每次取值没有浪费的功，没有取白费的数据，如，取32个字节的数据，分为四次取，每次取8字节，这就是效率达到了百分之百），将使程序运行速度得到很大程度的加快。那么，这个过程往往需要人工的干预，即，人为的控制变量在内存中的地址。有2字节对齐，4字节对齐，8字节对齐，等等。你当然可以按任何字节来对齐，但如果要达到访存高效，就要按照内存的访问规律来对齐。之所以会出现，让人手动地指定内存对齐大小，是因为考虑到程序的移植性。多数情况下，编写的程序可能不仅仅在一种平台上运行，还可能在其它不同的平台上运行，内存分布可能不同，各个变量相对地址都可能不同（当然，整个内存模型都可能不同，模型也是从基础的字节构建起来的，我们在此只考虑内存分布细节）。但如果我们限制各个变量的摆放规则，可以使得在不同平台上内存中的变量分布都按一套规则规整化，增强了程序的移植性。这么做还有一个附带的好处，就是规整化，规律化的内存分布，加快内存访问。

现在保证了每次取一个变量都能尽可能地一次取出，由于内存访存时每次是从边界开始访存，有固定的模式，不可随机跳到“任意地址”。所以必须尽可能地将变量的开始地址置于边界，访存边界即对齐值的整数倍地址处（注意是尽可能，并不是每一个变量都对齐到了访存边界）。下面是访存的内存模型, n 是实际内存对齐数。

处理器眼里的内存

处理器访存时，只能从 xn, (x+1)n, (x+2)n ... 等 n 的整数倍地址处开始访存，且处理器一次能读出 n 个字节。

详细分析内存对齐前，先给出几个概念，

1)数据类型自身的对齐值：即类型的大小。

2)指定对齐值：人工指定的内存对齐值，如C语言可以使用#pragma pack (value)时的指定对齐值value。

3)结构体或者类的自身对齐值：其成员中自身对齐值最大的那个值。

4)数据成员、结构体和类的有效对齐值：自身对齐值和指定对齐值中较小的那个值。

最终编译器会使用有效对齐值来对齐内存。为什么不始终按机器的位数来对齐呢？这样做不是能更快速地访存吗？不，要考虑到移植性，在32位机器上使用4字节对齐当然是最快的访存方式，但在64位机器上8字节才是最快的访存方式。而又为什么，当自身对齐值小于指定对齐值时，取自身对齐值为有效对齐值呢。这是因为，指定对齐值一旦超过了结构体中最大的成员的大小，那将是毫无意义的，反之来说，最大的成员完全能够安置在一个对齐单元内，那为何不让这个对齐单元尽量小，以节约空间呢？所以要取它们的较小值来对齐。

还有一个问题，这个身身对齐值有何含义呢？它其实是编译器对成员进行内存对齐时给出的一种建议，即按最大成员来对齐，这样可以保证每个成员都可以在一次寻址中取出数据。但这个对齐大小不一定是合适的。举个例子。

struct B

{

char c1;

struct C sc;//大小为1024字节

}

如果按照规则来，则B的自身对齐大小为1024字节，若按1024字节来对齐是非常不合理的，对齐后的内存分布如下图所示，每一行表示对齐位宽（1024位），第一行的空间利用率均只有千分之一，第二行为 100%；

这样巨大的空间浪费，只获得了访存B中sc成员效率，这是相当不划算的。有两种解决方案，一个是可以存在一个算法来自动获得最佳有效对齐内存大小，但这个算法本身也会消耗巨大，因为对于任何一个类，一个结构体都将执行这个算法。另一个是通过人工来干预。人工指定一个对齐的大小，然后在自身对齐大小与这个指定的值之间选一个较小的值进行对齐，这样即照顾了效率，又避免了空间的较大浪费。

当指定的值比自身对齐值小时，取指定的对齐值是因为，编译器不应该改变用户希望的行为，虽然编译器知道这种行为是坏的，但编译器假定了人的行为是经过思考的，是人自己保证的。

通过一个例子来说明在32位Intel机器上（即 int 占4个字节，long long 8 字节，double 8 字节，float 4 字节，char 1 字节等），且采用小端模式，内存对齐时空间分布：

struct C

{

int d;

long long l;

char c;

   struct A

{

char c;

int a;

} sa;

}sc

按2字节对齐的内存示意图如下， sa 作为一个结构体，它也要被对齐。它对齐后，占有的大小至少为 5 字节，显然不能被全部放在 sc.c 的后面 三个字节。但可以把 sa.c 这一个字节放在 sc.c 后面。仔细看下图， sc.sa.c 与 sc.c 中间隔着一个字节，它似乎是不需要的，因为即使将 sc.sa.c 紧随 sc.c 后排布，也不影响 sc.sa.c 在一次访存中取出。那么这是为什么呢？实际上，这是为了让 sc.sa 结构体的起始地址位于 2 整数倍地址处，加速访存。

2 字节对齐

按4字节对齐，如下图， 为保证 sc.sa.c 位于 4 的整数倍地址处，选择新的 4 个字节起头放置 sc.sa.c。

4 字节对齐

按8字节对齐，如图，d 后面空了 4 个字节是为了让 l 从 8 的整数倍地址开始放置。另外， sc.sa.c 刚好位于 8 整数倍地址处。

8 字节对齐

再次强调上面红色字体的问题。我们知道，结构体的第一个成员放置的位置必是内存边界，而内存边界是 n 的整数倍，n 与人工规定的对齐数和自身对齐数相关，具体而言，它取较小值。知道了这点，就不难理解，在 2 字节对齐时， 此时 sc.sa 这个结构体的有效对齐数为 2 sc.sa.c 与 sc.c 相隔一个字节，这样的排布方式使用是 sc.sa.c 位于 2 的整数倍地址处。而当 8 字节对齐时， sc.sa 结构体的有效对齐数为 4，所以，只相对 sc.c 往后统称 4 个字节排布 sc.sa.c。

最后一个内存对齐没有提到的问题是 C++  中的类继承时的内存对齐。当没有继承时，class 的内存布局与 struct 一样，但发生继承时，应该别当别论。

看下面两个类：

class Base

{

int a;

char c;

}

class Drived : public Base

{

char d;

}

有下面两种内存模型，

第一种内存布局

第二种内存布局

正确的只有一种，那就是第二种。多少你会有点意外，你会想，如果用 struct 来定义上面的关系，则是：

struct S_Base

{

int a ;

char c;

struct S_Drived

{

char d;

}sd;

}

此时的内存布局是上面的第一种。因为 S_Drived 有效对齐为 1 字节，所以它可以直接排在 S_Base.c 后面。

所不同的是：当发生继承时，子类中可能有这样一个构造函数，

Drived b(const Base &d);

以一个 Base 引用去构造一个 Drived ，此时就会发生麻烦。我们知道 Drived 相比 Base 多了一个成员d，在上面的赋值中，d 不应该被赋值，因为上面的构造函数不包含这样的语义，它很可能只希望用 Drived 与 Base 公有的部分去初始化对应的部分，而第一种内存分布会有副作用，因为 Base 和 Drived 都展现出了 "bitwise copy semantic"，编译器不会为这两个类合成拷贝构造函数，原因在于，直接将 Base 或 Drived 的内存块按位拷贝就能解决问题。

sizeof(Base) 和 sizeof(Drived) 都是 8 个字节，所以，当使用一个 Base 构造一个 Drived 时，直接将这 8 个字节拷贝作为 Drived 的内存即可，而此时，Drived 的 d 成员的内存在 Base.c 的后面一个字节，这个字节原本的内容不是 Base 关心的。现在这个字节作为了 Drived.d 的内存，即相当于，这个成员从原本“废墟”的地方取值，这个值明显不会是我们预期的，可能会导致 BUG。当然，除非你自己定制这个默认的“拷贝构造函数”，严正声明如何去拷贝方能解决这个问题。

关于 "bitwise copy semantic"，见于我的另一篇文章：《当没有编写时，编译器一定会生成拷贝构造函数，赋值函数 吗？》

数学推理：

下面关于内存对齐的数理推理是引自http://www.360doc.com/content/12/0804/11/3725126_228273988.shtml的。

对于两个正整数 x, n 总存在整数 q, r 使得x = nq + r, 其中  0<= r <n   //最小非负剩余

q, r 是唯一确定的。q = [x/n], r = x - n[x/n]. 这个是带余除法的一个简单形式。在 c 语言中， q, r 容易计算出来： q = x/n, r = x % n.
所谓把 x 按 n 对齐指的是：若 r=0, 取 qn, 若 r>0, 取 (q+1)n. 这也相当于把 x 表示为：
x = nq + r‘, 其中 -n < r‘ <=0                //最大非正剩余   
nq 是我们所求。关键是如何用 c 语言计算它。由于我们能处理标准的带余除法，所以可以把这个式子转换成一个标准的带余除法，然后加以处理：
x+n = qn + (n+r‘)，其中 0<n+r‘<=n            //最大非正剩余
x+n-1 = qn + (n+r‘-1), 其中 0<= n+r‘-1 <n    //最小非负剩余
所以 qn = [(x+n-1)/n]n. 用 c 语言计算就是：
((x+n-1)/n)*n
若 n 是 2 的方幂, 比如 2^m，则除为右移 m 位，乘为左移 m 位。所以把 x+n-1 的最低 m 个二进制位清 0就可以了。得到：
(x+n-1) & (~(n-1))。

内存对齐