《深入理解计算机系统》读书笔记-05

条件分支的两种实现方法

1. 控制的条件转移（条件控制）

   通过直接改变控制流，来实现条件分支

2. 数据的条件转移（条件传送）

   通过对各分支无条件运算，根据条件选取结果，来实现条件分支

   更符合现代处理器的性能特性，充分利用了处理器时间，避免由于空等或分支预测错误的惩罚造成处理器性能的浪费。但使用条件受限，要慎重使用。只有当各分支没有其他副作用时，才可考虑选择条件传送。

现代处理器的分支预测

现代处理器使用分支预测逻辑来尝试预测每个分支可能的走向，这样就可以不用等待求出分支条件的具体结果，从而有效利用现代处理器的高性能。

预期的正确率是90%，但在复杂情况下，这一概率依旧很低。

一旦处理器做出预测，就会按照预测的走向继续往下执行指令，如果计算结果发现预测正确，就皆大欢喜；如果发现预测错误，则丢弃从分支入口处到当前时间点所做的全部与该分支有关的工作，从另一个分支入口重新开始计算。

这个丢弃行为所带来的时间损耗，即称为“分支预测错误的处罚”

while 循环的两种翻译

1. 调转到中间（jump to middle）

   通过一个无条件跳转，直接跳转到测试条件相应的语句块，将while循环转换为do-while循环。

2. guarded-do

   先测试条件，若不成立，直接跳过循环；若成立，则顺序往下执行，循环代码转换为do-while循环。

switch 语句使用跳转表

使用switch语句可以十分高效地实现跳转，在分支数目较多的情况下，能够节省大量对条件的计算时间，得到较高的运行效率。其中起到关键作用的就是被称为“跳转表（jump table）”的数据结构。

跳转表被实现为一个数组，数组中元素是代码段的地址。GCC 在 C 语言的基础上进行了扩展，可以通过结合使用两个取地址符&&和代码标号，直接获取代码段的地址。这一点需要知悉。

注意，switch 的开关变量n是整数。

过程

过程，即 C 语言中的函数（function），在其他语言中也称方法（method）、子例程（subroutine）、处理函数（handler）等。

过程具有三个属性或者说要素：

1. 传递控制
2. 传递数据
3. 分配和释放内存

其中“传递控制”主要是指的对程序运行位置，即程序计数器值的压栈和出栈。

必须要在内存中存放局部数据的常见情况

1. 局部数据较多，只用寄存器不足以存放
2. 对局部变量使用了取地址符&
3. 有的局部变量是数组或是结构体，要能够通过数组或结构的访问方式进行访问

其中第2、3两条说的其实是一个意思。二者都是因为必须要对局部变量产生一个“地址”，只有这样才能够符合 C 语言的语法标准；但是寄存器是不存在“地址”这个概念的，也不可能通过内存地址的方式进行索引，因此处理器必须要将这些存在“地址需求”的变量存储到内存中。

注意，栈指针%rsp所指为当前栈顶的低位字节，也就是说，在小端系统中，假如栈顶存储了一个 8 字节内容，则该内容的最低位字节（从右往左第0~7位）的内存地址就是%rsp的内容，而次低位字节（第8~15位）则存储在1(%rsp)，也就是%rsp+1的地址上，以此类推，最高位字节（第56~63位）才应保存在7(rsp)的地址上。而8(%rsp)所指的又是上一个入栈的元素的低位字节了。

寄存器中值的保存

寄存器组是唯一被所有过程共享的资源

被调用者保存的寄存器

16 个通用寄存器中，%rbx、%rbp、%r12、%r13、%r14、%r15共计 6 个寄存器，被划分为“被调用者保存”寄存器。所谓“被调用者保存”，指的是“被调用”地过程有责任维护好调用发生当时，这些中存在的值。

维护的方式有两种：

1. 不使用相应寄存器
2. 在使用相应寄存器之前，将其储存的值入栈

这两种方式只需择一即可，也就是说，只有需要用到的寄存器才被入栈，如果在整个过程中不需要使用某些寄存器，也就不需要将其入栈。

调用者保存的寄存器

除栈指针%rsp外，其他所有通用寄存器均为“调用者保存”寄存器。

此处暂时存疑，不知道是仅限于通用寄存器还是所有寄存器。按逻辑来说，应该是仅限于通用寄存器，但书上表述不太严谨。

这些寄存器包括：%rax、%rcx、%rdx、%rsi、%rdi、%r8、%r9、%r10、%r11，共计 9 个通用寄存器。对应用法见下表。

寄存器	用法
%rax	返回值
%rcx	第 4 个参数
%rdx	第 3 个参数
%rsi	第 2 个参数
%rdi	第 1 个参数
%r8	第 5 个参数
%r9	第 6 个参数
%r10	调用者保存
%r11	调用者保存

所谓“调用者保存”，也就是说被调用的过程对这些寄存器中的值不负任何责任，所有有用值的保存和恢复，即入栈和出栈操作，都是调用者（或者说主调函数）的责任，在调用其他过程之前，就必须自行保存好上述寄存器中的值，以免被所调用的过程覆盖重写。

递归

站在机器的视角来看，递归调用和一般的调用没有什么区别。每次调用都产生一个独立的存储空间，用来保存每次调用所需的各种状态信息。

递归在机器层面是一个很自然的过程。