编写高效程序可以考虑两个方面：选择好的算法和数据结构；编写编译器能够有效优化以转换为高效可执行代码的源码。程序通常需要在实现简单性、运行速度之间做出权衡折中。
程序优化的第一步就是消除不必要的内容，让代码尽可能有效地执行它期望的工作。这包括消除不必要的函数调用、条件测试和内存引用。这些优化不依赖于目标机器的任何具体属性。研究程序的汇编代码表示，是理解编译器以及产生的代码如何运行的最有效的手段之一。仔细研究内循环的代码是一个很好的开端。
另一方面，可以挖掘处理器的潜能，利用指令级并行（instruction-level parallelism），来同时执行多条指令实现加速。
优化编译器的能力和局限性
对于GCC编译器场景，可以利用命令行选项（option）指定优化的等级。编译器优化程序的能力受到几个因素的制约：
- 要求决不能改变正确程序的行为
- 对程序的行为、使用的环境有所了解
- 需要很快地完成编译工作
阻碍优化的几个因素：
- 内存别名（memory aliasing）的使用，编译器必须假设不同的指针可能会指向存储器中的同一个位置
- 函数调用，函数可能会有副作用（改变全局程序状态的一部分）。一种优化方式为行内替换（inline substitution），将函数调用替换为函数体本身
表示程序性能
引入度量标准–每元素的时钟周期数(Cycles Per Element, CPE)作为一种表示性能并指导我们改进代码的方法。处理器执行是由时钟控制的，时钟提供了某个频率的规律信号，通常用千兆赫兹(GHz)，即十亿周期每秒来表示。CPE 越小越好。
消除循环的低效率
代码的低效率往往源于循环
优化前
优化后
以上的代码移动(code motion)是一种优化。这类优化包括识别要执行多次(例如在循环里)但是计算结果不会改变的计算。因而可以将计算移动到代码前面不会被多次求值的部分。
编程时一个常见的问题就是一个看上去无足轻重的代码片段有隐藏的渐进低效率(asymptotic inefficiency)
减少过程调用
过程调用会代码相当大的开销，而且妨碍大多数形式的程序优化。我们可以直接访问数组，而不是利用函数调用并加上边界检查
对于性能至关重要的程序来说，为了速度，可能需要损害一些对象的模块性和抽象性
消除不必要的内存引用
累加过程中其实没有必要每次都把结果写入到 dest 中，可以使用一个临时变量，消除不必要的内存引用。寄存器读写比内存读写快多了。
理解现代处理器
不依赖目标机器的优化，只能简单通过降低过程调用开销、以及消除一些重大的“妨碍优化因素”来实现。
要想获得充分提高的性能，代码的生成也要针对目标处理器进行调整。在实际的处理器中可以同时对多条指令求值，这个现象称为指令级并行。现代微处理器采用复杂的微处理器架构，使得多条指令可以并行地执行，同时又呈现顺序执行指令的表象。
两种下界描述了程序的最大性能。当一系列操作必须按照严格顺序执行时，就会遇到延迟界限(latency bound)，因为在下一条指令开始之前，这条指令必须结束。当代码中的数据相关性限制了处理器利用指令级并行的能力时，延迟界限能够限定程序性能。吞吐量界限(throughput bound)刻画了处理器功能单元（function units）的原始计算能力。这个界限是程序性能的终极限制。
整数操作
许多制造商生产的典型高端处理器，在工业界称为超标量(superscalar)，意思是可以在每个时钟周期执行多个操作，而且是乱序的(out-of-order)，指令执行的顺序不一定要与它们在机器级程序中的顺序一致。整个设计有两个主要部分：指令控制单元(Instruction Control Unit, ICU)和执行单元(Execution Unit, EU)。前者负责从存储器中读出指令序列，并根据这些指令序列生成一组针对程序数据的基本操作；而后执行这些操作。
ICU 从指令高速缓存(instruction cache)中读取指令。指令高速缓存是一个特殊的高速缓存存储器，它包含最近访问的指令。通常，ICU 会在很早之前取指，这样它才有足够的时间对指令译码，并把操作发送到 EU。不过，一个问题是程序遇到分支时，程序有两个可能的前进方向。一种可能会选择分支，控制被传递到分支目标。另一种可能是，不选择分支，控制被传递到指令序列的下一条指令。现代处理器采用了一种称为分支预测(branch prediction)的技术，处理器会预测是否会选择分支。使用投机执行(speculative execution)的技术，处理器会开始取出位于它预测的分支会跳到的地方的指令，并对指令译码，甚至在它确定分支预测是否正确之前就开始执行这些操作。如果过后确定分支预测错误，会将状态重新设置到分支点的状态，并开始取出和执行另一个方向上的指令。
功能单元的性能
每个运算都是由两个周期计数值来刻画的：一个是延迟(latency)，它表示完成运算所需要的总时间；另一个是发射时间(issue time)，它表示两个连续的同类型运算之间需要的最小时钟周期数。随着字长的增加，对于更复杂的数据类型，对于更复杂的运算，延迟也会增加。
处理器操作的抽象模型
我们会使用程序的数据流(data-flow)表示，作为分析在现代处理器上执行的机器级程序性能的一个工具，这是一种图形化的表示方法，展现了不同操作之间的数据相关是如何限制它们的执行顺序的。这种限制形成了图中的关键路径(critical path)，这是执行一组机器指令所需时钟周期数的一个下界。
循环展开（loop unrolling）
循环展开是一种程序变换，通过增加每次迭代计算的元素的数量，减少循环的迭代次数。其思想是在一次迭代中访问数组并做乘法，这样得到的程序需要更少的迭代，从而降低循环的开销。
循环展开能够从两个方面改善程序的性能。首先，它减少了不直接有助于程序结果的操作的数量，例如循环索引计算和条件分支。其次，它提供了一些方法，可以进一步变化代码，减少整个计算中关键路径上的操作数量。
提高并行性
多累加器（multiple accumulaters）
每个累加器负责计算一部分结果，最后对累加器数值进行汇总。利用多个累加器之间运算的并行性实现同一时钟周期内多个运算，从而加速。
重结合转换（reassociation transformation）
整数符合结合律，重新改变运算的结合方式可以减少关键路径上的计算数量，更有助于利用处理器多功能单元（function units）、流水线并行计算的能力，提升程序性能。
SIMD指令优化
SIMD（single instruction, multiple data）指令可以操作向量数据，利用它可以实现更大程度的并行能力。
优化的限制因素
寄存器溢出（register spilling）
循环并行性（loop unrolling）受描述计算的汇编代码的限制，如果并行数量超过了可用的寄存器数量，这种情况性能就会急剧下降。
作为一条通用原则，无论何时当一个编译了的程序显示出来在某个频繁使用的内循环中有寄存器溢出的迹象时，都会偏向于重写代码，使之需要较少的临时值。
分支预测与误判惩罚
预测的分支会预先执行，如果预测错误需要回退找到另一分支重新执行，容易低效。建议的做法是尽量采用条件移动的方式实现条件分支。
确定和消除性能瓶颈
Amdahl定律
当我们加快系统一部分的速度时，对系统整体性能的影响依赖于这个部分有多重要和速度提高了多少。
主要观点：想要大幅度提高整个系统的速度，我们必须提高系统很大一部分的速度。
小结
没有任何编译器能用一个好的算法或数据结构代替低效率的算法或数据结构，因此程序设计时的这些方面仍然应该是程序员主要关心的！
要优化程序性能：
- 确认优化指标
- 定位问题来源，可以采用代码运行分析工具，例如code profilers（Unix系统下有GPROF）
- 优化代码
优化代码的原则总结：
- （软件上）优秀的顶层设计，选择合适的算法和数据结构至关重要
- （编码上）去除多余的函数调用，避免循环重复调用同一个函数
- （编码上）去除多余的内存引用，推荐采用临时变量（一般用寄存器实现）记录中间结果，而非每次将中间结果更新到内存中（数组、全局变量往往存在内存中）
- （底层）展开循环、多累加器、重结合、条件移动代替条件分支
评论区