深入理解计算机系统笔记

1.1 嵌套的数组

当我们创建数组的数组时，数组分配和引用的一般原则也是成立的。

例如，声明 int A[5][3];

等价于下面的声明

typedef int row3_t[3];

row3_t A[5]

要访问多维数组的元素，编译器会以数组起始为基地址， (可能需要经过伸缩的）偏移量为索引，产生计算期望的元素的偏移量，然后使用某种 MOV指令。通常来说，对于一个 声明如下的数组：

T D[R][C];

它的数组元素D[i][j]的内存地址为

&D[i][j]= Xd +L(C*i+ j)

这里L是数据类型T以字节为单位的大小。

1.2定长数组

C语言编译器能够优化定长多维数组上的操作代码。这里我们展示优化等级设置为 -01时GCC采用的一些优化。假设我们用如下方式将数据类型fixjnatrix声明为 16X16 的整型数组：

#define N 16;

typedef int fix_matrix[N][N];

这样做的好处是，如果需要修改这个值只需要简单的修改这个# define声明就可以了。

1.3 变长数组

历史上，C语言只支持大小在编译时就能确定的多维数组（对第一维可能有些例外）。 程序员需要变长数组时不得不用malloc或calloc这样的函数为这些数组分配存储空间，而且不得不显式地编码，用行优先索引将多维数组映射到一维数组，ISO C99引入了一种功能，允许数组的维度是表达式，在数组被分配的时候才计算出来。

在变长数组的C版本中，我们可以将一个数组声明如下：

int  A[expr1] [expr2];

它可以作为一个局部变量，也可以作为一个函数的参数，然后在遇到这个声明的时候，通过对表达式和求值来确定数组的维度。

因此，例如要访问 n *n 数组的元素 I ,j，我们可以写一个如下的函数：

int var_ele(long n, int A[n][n], long i, long j){

return A[i][j]; }

参数n必须在参数A[n][n]之前，这样函数就可以在遇到这个数组的时候计算出数组的维度。

GCC为这个引用函数产生的代码如下所示：

int var_ele(long n, int A[n][n], long i, long j)

n in %rdi, A in %rsi, i in %rdx, j in %rcx

1  var_ele:

2  imulq %rdx, %rdi

3  leaq (%rsi,%rdi*4), %rax

4  movl (%rax,%rcx,4), %eax

5  ret

这 个地址的计算类似于定长数组的地址计算，不同点在于

1)由于增加了参数 n, 寄存器的使用变化了；

2)用了乘法指令来计算n * i(第2行），而不是用leaq指令来计算3i 。因此引用变长数组只需要对定长数组做一点儿概括。

动态的版本必须用乘法指令对 i 伸缩n倍，而不能用一系列的移位和加法。在一些处理器中，乘法会招致严重的性能处 罚，但是在这种情况中无可避免。

2.1异质的数据结构

C语言提供了两种将不同类型的对象组合到一起创建数据类型的机制：结构（structure)，用关键字 struct 来声明，将多个对象集合到一个单位中；联合（union)，用关键 字union 来声明，允许用几种不同的类型来引用一个对象

2.2结构

C语言的struct声明创建一个数据类型，将可能不同类型的对象聚合到一个对象中。 用名字来引用结构的各个组成部分。类似于数组的实现，结构的所有组成部分都存放在内存中一段连续的区域内，而指向结构的指针就是结构第一个字节的地址。编译器维护关于每个结构类型的信息，指示每个字段（field)的字节偏移。它以这些偏移作为内存引用指令中的位移，从而产生对结构元素的引用。

2.3联合

联合提供了一种方式，能够规避C语言的类型系统，允许以多种类型来引用一个对 象。联合声明的语法与结构的语法一样，只不过语义相差比较大。它们是用不同的字段来引用相同的内存块。

考虑下面的声明： struct S3{

char c;

int i[2];

double v;

}；

union U3{

char c;

int i[2];

double v; 

};

在一台x86-64Lmux机器上编译时，字段的偏移量、数据类型S3和U3的完整大小如下:

在一些下上文中，联合十分有用。但是，它也能引起一些讨厌的错误，因为它们绕过 了C语言类型系统提供的安全措施。一种应用情况是，我们事先知道对一个数据结构中的两个不同字段的使用是互斥的，那么将这两个字段声明为联合的一部分，而不是结构的一 部分，会减小分配空间的总量。

2.4数据对齐

许多计算机系统对基本数据类型的合法地址做出了一些限制，要求某种类型对象的地 址必须是某个值K(通常是2、4或8)的倍数。这种对齐限制简化了形成处理器和内存系统 之间接口的硬件设计。

例如，假设一个处理器总是从内存中取8个字节，则地址必须为8 的倍数。如果我们能保证将所有的double类型数据的地址对齐成8的倍数，那么就可以 用一个内存操作来读或者写值了。否则，我们可能需要执行两次内存访问，因为对象可能被分放在两个8字节内存块中。

对齐原则是任何K字节的基本对象的地址必须是K•的倍数。可以 看到这条原则会得到如下对齐：

确保每种数据类型都是按照指定方式来组织和分配，即每种类型的对象都满足它的对齐限制，就可保证实施对齐。编译器在汇编代码中放人命令，指明全局数据所需的对齐。