记得以前曾经两次谈到过内存对齐话题，一次在'也谈内存对齐'一文中，另一次则是'也谈内存对齐(续)'，今天下午和同事又谈到内存对齐的问题了，遂想继续挖掘下去，看看其背后的故事。

关于内存对齐的中文文章多在介绍对齐的'法则'，比如为什么sizeof(T)和我们估计的T的大小有出入呢等等，而对于内存对齐的本质少有介绍，我在Google上搜索了一阵后，在IBM开发社区上发现一篇叫'Data alignment: Straighten up and fly right'的文章，其中就有我想知道的关于'内存对齐背后的故事'，下面的很多内容都是来自那篇文章的。

很多书籍中都讲到：内存可以看成一个byte数组，我们通过编程语言提供的工具对这个'大数组'中的每个元素进行读写，比如在C中我们可以用指针一次读写一个或者更多个字节，这是我们一般程序员眼中的内存样子。但是从机器角度更具体的说从CPU角度看呢，CPU发出的指令是一个字节一个字节读写内存吗？答案是'否'。CPU是按照'块(chunk)'来读写内存的，块的大小可以是2bytes, 4bytes, 8bytes, 16bytes甚至是32bytes. 这个CPU访问内存采用的块的大小，我们可以称为'内存访问粒度'。

程序员眼中的内存样子：

———————————
| | | | | | | | | | | | | | | | |
———————————
 0 1 2 3 4 5 6 7 8 9 A B C D E F  (地址)

CPU眼中的内存样子：(以粒度＝4为例)
———————————————
| | | | |   | | | | |   | | | | |   | | | | |
———————————————
 0 1 2 3     4 5 6 7     8 9 A B     C D E F  (地址)

有了上面的概念，我们来看看粒度对CPU访问内存的影响。

假设这里我们需要的数据分别存储于地址0和地址1起始的连续4个字节的存储器中，我们目的是分别读取这些数据到一个4字节的寄存器中，

如果'内存访问粒度'为1，CPU从地址0开始读取，需要4次访问才能将4个字节读到寄存器中；
同样如果'内存访问粒度'为1，CPU从地址1开始读取，也需要4次访问才能将4个字节读到寄存器中；而且对于这种理想中的''内存访问粒度'为1的CPU，所有地址都是'aligned address'。

如果'内存访问粒度'为2，CPU从地址0开始读取，需要2次访问才能将4个字节读到寄存器中；每次访存都能从'aligned address'起始。
如果'内存访问粒度'为2，CPU从地址1开始读取，相当于内存中数据分布在1,2,3,4三个地址上，由于1不是'aligned address'，所以这时CPU要做些其他工作，由于这四个字节分步在三个chunk上，所以CPU需要进行三次访存操作，第一次读取chunk1(即地址0,1上两个字节，而且仅仅地址1上的数据有用)，第二次读取chunk2(即地址2,3上两个字节，这两个地址上的数据都有用)，最后一次读取chunk3(即地址5,6上两个字节，而且仅仅地址5上的数据有用)，最后CPU会将读取的有用的数据做merge操作，然后放到寄存器中。

同理可以推断如果'内存访问粒度'为4，那么从地址1开始读取，需要2次访问，访问后得到的结果merge后放到寄存器中。

是不是所有的CPU都会帮你这么做呢，当然不是。有些厂商的CPU发现你访问unaligned address，就会报错，或者打开调试器或者dump core，比如sun sparc solaris绝对不会容忍你访问unaligned address，都会以一个core结束你的程序的执行。所以一般编译器都会在编译时做相应的优化以保证程序运行时所有数据都是存储在'aligned address'上的，这就是内存对齐的由来。

我们可以指定按照何种粒度访问特定内存块儿：其中void *T为指向特定内存块的地址指针
char *p = (char*)T；每次操作一个字节
short *p = (short*)T；每次操作两个字节
int *p = (int*)T；每次操作4个字节
以此类推。

在'Data alignment: Straighten up and fly right'这篇文章中作者还得出一个结论那就是："如果访问的地址是unaligned的，那么采用大粒度访问内存有可能比小粒度访问内存还要慢"。

好久没有看技术类的书籍了，今晚恰看到以前不知什么时候下到的一本oreilly的叫’mastering algorithms with c’的书，从书名可以看出这是一本讲算法的书，不过由于是选用了C语言作为讲解语言，所以难免不说说C语言。其中看到一节讲指针和数组，恰好碰到书中说: a[i][j] <=> *(*(a+i) + j)，这个等价式看起来显而易见，但是还是有些东西值得挖掘一下的。

我们都知道C语言定义的多维数组是’行主序’的，这意味着越靠右边的下标变换越快。a[i][j]形象的可以看成一个i行j列的矩阵，但是实际在内存中存储时，a[i][j]肯定不是矩阵存储，因为存储器可是线性下来的，至于a[i][j]各元素的存储位置我们可以通过测试获得，结果也验证了’行主序’的规则。

以a[2][3]为例，

#include <stdio.h>

int main() {
 int a[2][3] = {{1,2,3}, {4,5,6}};
 int i;
 int j;
 int k;
 int *p;

 for (i = 0; i < 2; i++) {
  for (j = 0; j < 3; j++) {
   printf("a[%d][%d] = %d; addr = [0x%X]\n", i, j, a[i][j], &a[i][j]);
  }

 }

 return 0;
}

输出结果：

a[0][0] = 1; addr = [0x23FE94]
a[0][1] = 2; addr = [0x23FE98]
a[0][2] = 3; addr = [0x23FE9C]
a[1][0] = 4; addr = [0x23FEA0]
a[1][1] = 5; addr = [0x23FEA4]
a[1][2] = 6; addr = [0x23FEA8]

从结果addr的规律看得出: 先排行元素，再排列元素。也就是说第一行排完，再来排第二行。

我们再来分析一下上面提到的那个等价式：a[i][j] <=> *(*(a+i) + j)，其实这里不一定要用常理分析，我们通过实验能得出一些结论：

#include <stdio.h>

int main() {
 int a[2][3] = {{1,2,3}, {4,5,6}};
 int i;
 int j;
 int k;
 int *p;

 for (i = 0; i < 2; i++) {
  for (j = 0; j < 3; j++) {
   printf("a[%d][%d] = %d; addr = [0x%X]\n", i, j, a[i][j], &a[i][j]);
  }

 }

 p = a;
 
 for (k =0 ; k < 6; k++) {
  printf("p[%d] = %d\n", k, p[k]);
 }

 printf("a+1 = 0x%X\n", a+1);
 printf("*(a+1) = 0x%X\n", *(a+1));
 printf("*(*(a+1)+2) = %d\n", *(*(a+1)+2));
 printf("*(a+1)+2 = 0x%X\n", *(a+1)+2);
 return 0;

}

输出结果：

a[0][0] = 1; addr = [0x23FE94]
a[0][1] = 2; addr = [0x23FE98]
a[0][2] = 3; addr = [0x23FE9C]
a[1][0] = 4; addr = [0x23FEA0]
a[1][1] = 5; addr = [0x23FEA4]
a[1][2] = 6; addr = [0x23FEA8]
p[0] = 1
p[1] = 2
p[2] = 3
p[3] = 4
p[4] = 5
p[5] = 6
a+1 = 0x23FEA0
*(a+1) = 0x23FEA0
*(*(a+1)+2) = 6
*(a+1)+2 = 0x23FEA8

这里关键的就是a+1 = 0x23FEA0以及*(a+1) = 0x23FEA0，奇怪了吧，加不加’*'号结果一致；实际上 *(*(a+i) + j)中的a + i是为了取第i行的首地址，按照常理用a+i即可了。但是由于是多维数组，取数组中某一元素的值，不仅要行还要列，那这么写: *((a +i) +j )能行吗？这就是当时C的设计者要考虑到问题了。显然*((a +i) +j )这么做欠妥，依然以上面的例子为例，我们再输出些信息瞧瞧：

printf("*((a+1)+2) = 0x%X\n", *((a+1) +2));

输出结果：
*((a+1)+2) = 0x23FEB8

这显然不是a[1][2]的值，0x23FEB8是什么呢，实际上是第四行的行首地址，当然在我们的程序中只有两行在合法的范围之内。好了，问题既然出现了，当时的C设计者就考虑要区别于这种情况，遂就如是做了: *(*(a+1)+2)；这样结果正确了，*(*(a+1)+2) = 6。至于当时C设计者的真实考虑我无从而知，权当逗乐打趣吧。