读CSAPP之优化的基础知识

今年是离开校园的第六年，这六年来我一直在从事应用软件的设计、开发工作，大部分时间是在与高级编程语言、设计模式、业务逻辑打交道。它们大多流于表面，久而久之，与技术底层疏远了，诸如计算机组成原理、汇编语言、编译原理、数据结构以及算法慢慢得生疏，时至今日，向上碰到天花板，向下触到花岗岩。五年是一个契机，趁着下一个五年开始之际，我计划用三个月至半年时想间，重新学习这些知识，以期达到巩固基础，厚积薄发的目的。

本篇是我阅读《Computer System: A Programmer’s Perspective》一书的笔记，该书和与之搭配的《Professional Assembly Language》是我当下阅读计划的一部分。

编写高效代码就是善待你的用户，每节省一个时钟周期、一字节网络流量，就是善事一桩，善小亦为之，日久功德无量。

首先，动手之前，选择出合适的算法和数据结构；其次，编写出的源代码应该让编译器能够有效优化，以生成成高效可执行代码；最后，针对处理运算量特别大的计算，要能将一个任务分成多个部分，这些部分可以在多核或多处理器的某种组合上并行地计算。

程序优化的第一步就是消除不必要的内容，让代码尽可能有效地执行它期望的工作，包括消除不必要的函数调用、条件测试和存储器引用。

第二步是利用处理器提供的指令级并行（instruction-level parallelism）能力，同时执行多条指令。

编译器必须很小心地对程序只使用安全的优化，也就是说对于程序可能遇到的所有可能的情况，在 C 语言标准提供的保证之下，优化后得到程序和未优化得到的版本有一样的行为。

妨碍编译器优化的第一个因素是存储器别名使用，两个指针指向同一个存储器中同一个位置，这种情况叫做存储器别名使用（memory aliasing）。如果编译器不能确定两个指针是否指向同一个位置，就必须假设什么情况都有可能发生，这限制了可能的优化策略。

妨碍编译器优化的第二个因素是函数调用的副作用，副作用是指函数执行过程修改了全局程序状态的一部分，改变调用它的次数也就改变了程序的行为。大多数编译器不会试图判断一个函数是否没有副作用，相反会假设最糟的情况，并保持所有的函数调用不变。

未经优化的代码是从 C 语言代码到机器代码的直接翻译，通常有明显的低效率。简单地使用命令行选项“-O1”，可以获得一些基本的优化。

消除循环的低效率的一个常见策略是代码移动（code motion），其包括识别要执行多次，但计算结果不会改变的运算，可以将计算移动到代码前面不会被多次求值的部分。但是，这个改善是不能依赖于编译器的，因为编译器不能判断这么个运算是否有副作用。

渐近低效率（asymptotic inefficiency）在小数据量时不宜暴露问题，在大数据量的情况下往往成为制约效率的因素。