读《深入理解计算机系统》

最近花了十天的时间（加上春节前看的一点）终于将这部大部头的书看完了，整个过程很兴奋，感觉原本模糊的世界一下子变得清晰了，很久没有这样的感觉了。这里记下自己的收获。


汇编

第三章讲的是汇编语言，我对汇编一直感到十分畏惧，曾经也捡过一部大部头的书来看，名字已经忘记了，貌似还是一部很经典的书，当时那个痛苦，完全感受不到编程的乐趣。好在这本书不是讲用汇编编写程序，只是要借助汇编理解计算机如何工作，这正是我想学习汇编的目的，或许正因为我和作者的目的完全一致，读起来十分轻松，当然作者写得非常好。除了汇编指令之外，还讲了：如何将if/switch/for/while等控制结构翻译成汇编语言，这些我之前也大致知道一些，但再复习一遍也相当不错；过程调用栈的变化，哪些寄存器由调用者保存，哪些寄存器由被调用者保存；缓冲区溢出攻击以及应对方法；64位系统的变化，多了8个寄存器，这样大多数函数调用都不再需要使用栈。总的说来，第三章是非常重要的，是学习其它概念的基础。

流水线

流水线设计对提高处理器的性能可谓意义深远，思想其实很简单。类似工厂流水线，它不是等待一个指令运行完毕再接着运行下一条指令，而是将指令分成一个五个阶段(实际的处理器可能不一样)：取指、译码、执行、访存、写回，每个阶段由相应的硬件来实现，通过流水线可以让五个硬件同时工作，这样可以将运行效率提升大约五倍。见下图（图片来自网络），我第一次看到流水线在处理器上的应用时感觉是相当的震憾。



流水线也会有问题，由于前一条指令还没有完成时下一条指令就开始运行了，当这两条指令没有依赖时这种方式可以工作得很好（工厂的流水线一般都满足这种要求)，但是当下一条指令依赖于上一条指令的结果时问题就出来了。例如：

movl $3, %eax
addl %edx, %eax

在流水线中mov指令还没有将结果写入到%eax中，add指令就开始执行，结果取出来的是%eax之前的值，这显然是有问题的，这种情况称为数据冒险。一种解决方法是在mov和add之间插入nop指令，nop指令除了将PC(程序计数器)加1以外什么事情也不做，nop指令由处理器自动插入，这个相当于将流水线串行化，带来的结果就运行效率降低。另外一种方法就是使用转发技术，它可以将上一条指令的结果直接传给下一条指令，不需要等待，大部分数据冒险可以通过转发解除。

流水线保持指令按顺序执行的，前一条指令必须在后一条指令之前执行。例如：

movl 3%(eax), %ebx
addl %eax, 4(%edx)

虽然add指令和mov指针完全不相关，但在前述的流水器设计之中，add指令必须在mov指令之前执行。现代处理器更复杂，它可以将每个指令拆分多个微操作，例如上面mov指令可以分成三个操作：加法操作（计算3+eax的值），加载操作（从3+eax处加载数据），写回操作（写回%ebx)。同样的add指令也可以将add指令拆分三个操作。然后处理器会全局分析这些操作，哪些操作可以同时执行而不会产生冲突，结果是实际执行顺序可能跟代码中指定的顺序不同，这就是所谓的乱序(out-of-order)。

乱序可以最大化指令的并行，从而充分利用处理器的资源。不幸的是，在多线程编程中它是混乱之源。在单线程程序中，我们不需要关心乱序，因为处理器会保证其执行结果与顺序执行结果一样，但在多线程程序中就不同了，单线程下的顺序模型遭到破坏。假设初始条件x=y=0，线程1：

x = 1;
y = 2;

那么在线程2是不能通过:

if (x == 1) {
	// cannot assume y == 2
}

来假设y已经变成2，这是因为乱序，处理器可能先执行y=2（实际上编译器也可能导致乱序，这里先忽略）。如果要保持单线程下的严格顺序模型，将会导致性能低下，而如果我们要是假设随时都可能发生乱序，多线程编程就变得十分困难。于是Java定义了一个内存模型(实际上是Sequential Consistency)，使得既能够保持程序的高性能，同时程序员也无需过多关注乱序。这个模型要比单线程模型复杂很多，并且必须依赖同步，这里就不多讲了。


性能调优

第五章讲性能优化，要优化程序首先得了解编译器的局限性。尽管编译器越来越强大，能够执行大量优化，但是有些看起来很显然的优化编译器却无能为力。比如说书中提到的：

void twiddle(int *xp, int *yp) {
	*xp += *yp;
	*xp += *yp;
}

但是它并不能优化成：

void twiddle(int *xp, int *yp) {
	*xp += 2* *yp;
}

因为必须考虑xp和yp指针相等（即指针别名或引用别名）的情况，这种情况下，两个程序的结果并不一样。这就引出了C99的restrict关键字，当用在指针上时表示没有其它指针会指向同一个对象，这样编译器可以进行最大程度的优化。书中还有一个例子：

int f();

int func1() { return f() + f() + f() + f(); }
int func2() { return 4*f(); }

编译器也不能将func1优化成func2，因为必须考虑到f()可能会有副作用（比如增加某个全局变量的值），这使人想到函数式编程，它强调函数必须没有副作用，但是C语言没有关键字来指定一个函数有没有副作用。

常用的优化包括消除循环低效率(例如将循环次数计算提到循环外面)、减少过程调用、循环展开。更高级的优化必须利用处理器的特性：并行性（流水线及乱序）以及高速缓存。提高并行性的思想主要是去掉循环中操作依赖，有两种方法，分别是用多个累积变量和重新结合变换，这部分相当有趣，因为优化后需要进行的操作数并没有减少，只是利用了处理器的并行性，我们就可以将程序的性能提高一倍，书中使用一种叫做数据流图的东西来描述并行性。要利用高速缓存，就得考虑空间局部性，第6.6.2节讲的一个例子，没有利用局部性和利用局部性的程序性能差距可达20倍。第六章讲的高速缓存结构也很有意思，尤其要看它缓存是如何命中的。

条件传送指令（对应于C语言中的?:操作符）可以提高流水线执行的效率，书中有个例子（5.11.2节），下面代码交换数组a和b中元素，使得a中元素小于b中元素。通常的实现如下：

void minmax1(int a[], int b[], int n) {
	int i;
	for (i = 0; i < n; i++) {
		if (a[i] > b[i]) {
			int t = a[i];
			a[i] = b[i];
			b[i] = t;
		}
	}
}

而利用条件传送指令的实现如下：

void minmax2(int a[], int b[], int n) {
	int i;
	for (i = 0; i < n; i++) {
		int min = a[i] < b[i] ? a[i] : b[i];
		int max = a[i] < b[i] ? b[i] : a[i];
		a[i] = min;
		b[i] = max;
	}
}

初看起来minmax2的效率应当比minmax1的效率要低，因为它每次循环都得计算min,max。问题在于条件判断对于流水线操作并不友好，处理器会对跳转分支进行预测，如果分支预测错误，会有很高的性能惩罚。在上面的例子中，数组a和b的元素是随机的，这种情况下处理器再聪明它的预测准确率也只有50％左右。当使用条件传送指令时就完成免去了分支预测，也就不会有错误惩罚，这就是为什么minmax2的性能要比minmax1的性能要高得原因。这也给我们一个启示，看一个程序的性能并不能只看它执行的操作数的多少。需要注意的是，对于可预测的分支，条件判断很少会对性能有影响。对于Java，C#这样的高级语言，它会每次数组访问进行边界检查，但是由于在大多数情况下（超过99％）访问都不会越界，处理器也能够很好地预测到这一点并采取正确的路径，因而只会有微小的性能损失。

虽然本书讲优化讲得非常精彩，了解一些也是很有必要的，但它到底能够多大程度用在实际程序中，我是保持怀疑的，几乎所有的优化都会导致程序更难懂，也更难维护，某某牛人也说了，过早优化是万恶之源（已经被引用无数次了）。


虚拟存储器

这主要是第九章的内容。虚拟存储器给我们一个假象，每个进程都有4G的连续空间（对32位系统），尽管你的物理内存可能不到4G。但实际存储加载时需要访问物理存储器，这要依靠页表来将虚拟地址翻译成物理地址，每个进程都有一个页表，常驻于物理内存中，首地址放在页表寄存器(PTE)中，当给定一个虚拟地址时，首先要利用页表去获得相应的物理地址，如果当页不在物理内存时，会触发缺页异常（或者称为中断），然后从磁盘（位于交换分区）中加载相应页，然后继续。处理器采用了很多手段来优化虚拟地址到物理地址的翻译，书中讲得非常详细。

可以将虚拟存储器区域与磁盘上的文件关联起来，这样可以将文件当作一个巨大的数组来看待，这比直接从磁盘访问性能要高，这就是存储器映射(memory mapping)。著名的非关系型数据库MongoDB利用的就是存储器映射来访问数据库。linux内核如何实现fork系统调用的机制非常有趣，当使用fork()来创建子进程时并没有完全复制父进程的虚拟存储空间中的所有内容，它只是复制了父进程的mm_struct、区域结构和页表的原样拷贝，同时将两个进程的每个页面都标记为只读，父子进程对任意页面第一次写入时会创建它的私有写拷贝，父子进程就不会互相影响，这就是Copy-on-write技术。这种方法极大的避免了创建进程的开销。我第一次碰到copy-on-write是在多线程编程中，没想到linux内核中也可以使用，看来思想真的是相通的！

第九章末尾实现了一个简单的基于链式的动态存储器分配，我不是很感兴趣，因为类似的实现《C程序设计语言》也有讲过。令我感兴趣的是它还提到另一种分配方式，称为分离存储(segregated storage)，我所以会对这种方式感兴趣，是因为Memcache使用的就是这种分配方式，当时觉得这种方式实在是太高明了，当然现在仍然觉得很高明。


其它

其实我每一章都有很大的收获，第3章到第9章收获尤其大，我只是懒得写了，太费劲了，我读后的体会是，如果只让我推荐一本书，我就推荐这本，太经典了，真后悔没有早点看。

评论

5 楼 fobdddf 2015-11-28  

fobdddf 写道

朋友你好，我试了一下数组的那个例子，反汇编后发现似乎并没有使用条件传送指令，我使用的编译器是Code::Blocks，请问这是为什么呢？

看网上说，在GCC的x86平台上要优化到O2才会使用条件传送指令（g++ -S -O2 -m32 a.cpp），试了一下，然而发现优化到O2的汇编代码已经看不懂了。。

4 楼 fobdddf 2015-11-27  

朋友你好，我试了一下数组的那个例子，反汇编后发现似乎并没有使用条件传送指令，我使用的编译器是Code::Blocks，请问这是为什么呢？

3 楼 young7 2013-07-28  

我10天都没读完2章，然后很多家庭作业不会做，哥们你是牛人啊，

2 楼 marlonyao 2011-05-26  

AlwenS 写道

十天就看完了？ 跳读吧。。?

没有跳读，除了前两章以前看过，那段时间基本没有干别的（除了上班），就在看书，写得太好了。

1 楼 AlwenS 2011-05-26  

十天就看完了？ 跳读吧。。?