编写高效程序需要做到以下几点：首先，选择合适的算法和数据结构；其次编写出编译器可以进行优化并转换成高效代码的源代码，因为编译器的优化能力有限，所以需要人为地辅助；最后便是借助硬件，把任务拆分成小的模块，并发地执行。

进行优化代码的第一步，需要消除不必要的工作，让代码尽可能高效集中的执行任务；第二步便是利用处理器提供的指令级并行能力，降低计算之间的耦合度，增加并行能力。

经过实验可以发现，即使是使用低优先级编译一个好代码，也比使用最高优先级编译坏代码的性能高，可见编译器的局限性，以及代码设计的重要性。

而对于GCC来说，安全更为重要。借此，引出了优化问题，来看一下：

这两个函数看起来功能是一样的，后者性能更好。但是，假如指针xp和yp指向了同一个位置，后者就会出现计算错误。

两个指针指向同一个内存的情况称为内存别名使用。在只执行安全优化的编译，编译器必须假设所有的指针可能指向同一位置，就不能使用twiddle2的形式。因此可能存在内存别名引用会严重的限制编译器优化。所以程序员尽可能编写的代码，要么明确指出存在内存别名引用，要么直接不存在，而不是让编译器去判断。

第二个妨碍优化的因素是函数调用。对于可能修改全局变量的函数，这就是一个很大的优化限制因素。大多数编译器并不会试图判断一个函数的副作用，然后直接进行优化，就像把函数func1()优化成func2()一样。但是如果f()如果会修改全局变量，就会造成错误的优化。

对于函数，可以考虑使用内联函数，就是把被调用的目标函数的函数体直接写在调用者的函数体里。

为了更好地度量程序执行的性能，引入度量标准：每元素周期数CPE作为一种表示程序性能的方法。这个值越小，代表程序越好。

CPU的Ghz指的是时钟周期数，就是每秒时钟滴答数。

没

首先就是代码移动，就是把某个会经常执行但是结果不变的操作提取出来，比如for循环的str.length()就属于这样的，可以提前记录str.length()。虽然编译器会自己这么做，但是编译器一般比较保守，它不知道这么做会不会产生副作用，因此最好手动写好。

这说明了一个问题，就是一个看上去无足轻重的代码片段，可能隐藏着渐进低效率。

一个有经验的程序员的一部分工作就是避免这样的渐进低效率。

就像对于str.length()的调用一样，在一次次迭代中调用一个结果不变的函数，无疑是加剧了性能浪费，阻碍了编译器的优化。所以可以试着把过程调用的结果保存起来，然后在其他地方使用。

有时候，不好的代码会导致不停地向一个内存地址写数据，然后再读出来，那为何不提前定义一个变量来保存呢(此时聪明的编译器直到把这个变量存储在寄存器里，而寄存器足够快)？此时，便优化了程序。

要想更好地榨干处理器的性能，实现更好的效率，那么就必须了解处理器的结构，进而使用处理器微体系结构地优化。

现代处理器为了使程序性能最大化，使用了很多复杂的硬件和组织形式，进而使得处理器的实际操作与机器级程序的执行顺序大相径庭。

在实际的处理器中，是同时对多条指令进行求值，处理的，这称为指令级并行。然后采用一些精细的模型，保证指令的处理可以满足机器级程序要求的顺序语义模型的效果。

在这里，引入两种界限用来描述程序的最大性能：延迟界限，指明在下一条指令开始之前，这条指令必须结束；吞吐量界限，指明了处理器功能单元的运算能力，这个是无法突破的终极界限。

现代处理器使用了一种称为超标量的结构来使处理器可以一个周期内执行多条指令，并且是乱序的。整个设计中主要有两个部分，指令控制单元(ICU)，执行单元(EU)，一般来说，乱序处理器的硬件更大更复杂，但是它们可以更好地达到更高的指令级并行度。

取值控制单元告诉指令缓存，应该取哪些指令到指令译码单元中；指令译码单元会把取到的指令进一步分解成微操作，然后交给EU去执行。EU中的分支模块会告诉指令控制单元分支预测的结果。

一般来说，ICU会在当前正在执行的指令很早之前就把它取出来了，这样才有足够的时间进行译码，并把操作发送到EU。对于分支，ICU绘制用投机执行的技术确定分支预测的结果(可能不正确)，选择到底是跳转还是不跳转，并取出那里的指令，对指令译码，甚至在确定分支预测结果之前就开始执行这条指令。

• 取值控制单元包括分支预测，以完成确定取哪些指令的任务。
  
• 指令译码单元接收实际的程序指令，并把它们分解成一组基本的操作，比如加法，从内存中载入数据，向内存写数据等。分解的指令的好处就是，可以让不同的单元并行地执行一条指令的不同部分，提高吞吐量。
  
• EU接收来自取指单元的操作，一般来说一个时钟周期可以接收多个操作(是多个不是多次)。然后分配到对应的功能单元中(图示的深蓝色部分)。
  
• 读写内存由加载和存储单元实现，它们内部有一个加法器，用来实现计算内存地址。加载和存储单元都通过数据高速缓存来访问内存，这里存放着最近的操作数据(详见下述)。
  
• 使用投机技术对分支进行求值，然后得到的结果不会保存在寄存器或者内存中，直到分支正确，怎么知道分支预测结果呢？分支操作也会被发送到EU，如果预测错误，EU抛弃之前计算出来的结果，并发信号告诉取值控制单元，然后指出正确的地址。
  
• 由于不同操作之间的差异很大，所以算术运算单元被设计成能够执行各种不同的操作。
  
• 乘法和除法需要更多的专用资源，所以他们有自己的专属硬件。
  
• 在ICU中退役单元记录正在进行的处理，并确保它遵守机器级程序的顺序语义。指令译码时，关于指令的信息被放在一个先进先出的队列中，这些信息一直保存到操作完成或者指令预测错误。什么意思呢？具体来说就是，如果这条指令计算全部完成，且所有引起这条指令的分支点全部是正确的，那么这条指令就可以退役了；反之，如果引起该指令的某个分支点被证明是错误的，那么该指令就会被清空。
  
• 任何对于程序寄存器的更新，只有在指令退役时才会发生。
  
• 控制操作数在执行单元间传送的最常见的机制称为寄存器重命名。当某个指令更新寄存器r时，会对其进行标记，然后任何在它之后的需要寄存器r的指令，都会直接使用这个指令更新的结果，而不是等到这条指令写入寄存器，再读出来，这是一定程度上的数据转发。
  

评价功能单元有三个指标，一个是延迟，它表示完成运算所需要的总时间；另一个是发射时间，它表示两个连续的同类型的操作之间的最小时钟周期数；最后一个是容量，它表示能够执行该运算的功能单元的数量。

可以看到，加法和乘法的发射时间都是1，表示每个时钟周期都可以开始一个新的运算。这种很短的发射之间是通过流水线实现的。发射时间为1的功能单元被称为完全流水线化的。而对于除法，它的延迟和发射之间都很大，这导致除法是一个很大的开销。

另外，表达发射时间的另一个方法是吞吐量，定义为发射时间的倒数。

延迟界限给出了任何必须按照严格顺序完成合并运算的函数所需要的最小CPE值。根据功能单元产生结果的最大速率，吞吐量界限给出了CPE的最小界限。

为了更好地展现程序执行的性能，使用数据流图来表示，数据流图展示了不同操作之间的数据相关是如何限制它们的执行顺序的。这些限制形成了图中的关键路径，这是执行一组机器指令所需时钟周期数的一个下界。

为了进一步讨论这个问题，使用上述的combine4作为研究对象。

首先是double类型，乘法的情况。首先看看其汇编代码：

Inner loop of combine4. data_t=double, OP=* acc in %xmm0, data+i in %rdx, data+length in %rax
1 .L25:     loop:
2   vmulsd  (%rdx), %xmm0, %xmm0            Multiply acc by data[i]
3   addq    $8, %rdx                        Increment data+i
4   cmpq    %rax, %rdx                      Compare to data+length
5   jne     .L25                            If !=, goto loop

可以看到，最开始的乘法指令被扩展成一个load和mul操作。得到的操作如下：

对于形成循环的代码片段，把访问到的寄存器分为四类： - 只读：这种寄存器只会用做源值，可以作为数据，也可以作为内存地址，不过它们不会被修改。

• 只写：这种寄存器只用作数据传送操作的目的寄存器。
  
• 局部：这种寄存器只会在当前循环被修改，与上一次迭代和下一次迭代无关。
  
• 循环：这种寄存器存在于每一次迭代中，此次迭代的结果可能作为下一次迭代的源来使用。
  

进一步抽象得到数据流图：

在此，把那些与循环相关链无关的操作标记为白色。然后简单的重复图B中的模块n次，就能得到下面这张图：

假设乘法需要5个时钟周期，而加法需要1个，那么左边的链总计需要5n个，右边的链需要n个，性能制约在于左边的链。

关键路径所指明的只是程序运行需要的周期数的下界。所以不妨考虑提升指令的并行度，使唯一的限制变成吞吐量界限，得到接近于1.00的CPE。

循环展开是一种常见的方式，通过增加每次迭代计算的元素，来减少执行的次数。

循环展开能从两个方面改进程序的性能，第一，它减少了不直接有助于程序结果的操作的数量，比如循环索引计算和条件分支，第二，它提供了一些方法，可以减少整个计算中关键路径上的操作数量。

不过，并不是简单的在循环里计算多点就是提升性能了，来看一个反例：

这个代码虽然缩短了循环次数，但是本质上还是5n而不是2.5n。来看看它的数据流图：

所以不能单纯的增加计算，而要有设计的增加每次迭代的计算。

一般来说，编译器都会自动进行循环展开，不过最好编写代码时就进行此操作。

此时需要借助于硬件数量，来实现硬件级别的并行处理。

还有一种方式，对于可结合和可交换的运算来说。可以通过把一组运算拆分成多个部分，最后合并来实现。这样可以减少迭代次数，实现更加切实可行的优化。来看一个例子：

来看看实际的运行效率：

可以看到，在这里通过这种方式打破了由延迟界限设下的限制。

要理解这种性能产生的原因，就需要看看数据流图，因为在这个版本里，两个乘法操作被翻译成了对不同寄存器的读写，彼此独立，没有数据依赖，所以关联路径实现的/2的减少：

可以将多个累计变量变换归纳为将循环展开K次，以及并行累积K个值。当K足够大时，程序在所有情况下几乎都能达到吞吐量界限。

不过在执行K*K循环展开变换时，必须考虑是否保留原始函数的功能。因为补码运算是可交换和可结合的，甚至当溢出时也是如此。另一方面，浮点乘法和加法不是可结合的(IEEE表示法决定的)，所以不能这么处理。所以一般来说，编译器会自动对整数运算进行循环展开，但是对于浮点数却保留原本的形式(暗示写代码时主动地引导编译器进行变换)。

来看一个新的计算方法：

此方法和combine5的区别在于：

combine5:

acc=(acc OP data[i]) OP data[i];

combine7:

acc=acc OP (data[i]OP data[i]);

再来看看它们的数据流图：

可以看到combine7和combine5的区别在于：前者是加载一次值，计算，再加载，再计算；后者是加载，加载，计算，计算。所以速度逼近2*2的展开，在这里，称combine7为2*1a展开。经过测试，对于k*1a的循环展开，性能接近于k*k的循环展开——都接近吞吐量界限。

一般来说，循环展开和累积地并行计算是提高性能的好方法。

关键路径指出了该程序执行所需时间的一个基本下界；而功能单元的吞吐量界限也是程序执行时间的一个下界。不过还存在一些其他的因素。

这个很好理解，如果程序迭代时，并行计算使用的寄存器数量超过了提供的寄存器数量，那么就会使用栈空间来提供，这样反而会降低运行速度。

对于分支指令，处理器为了保持流水线的满载，会进行分支预测，一般是称为投机执行的技术。如果预测正确，程序继续执行，投机技术把执行结果提交到程序寄存器或内存；如果预测错误，那么必须清空所有投机执行的结果，然后重新填充流水线，保证流水线的尽可能满载。

GCC会编译出使用条件传送的指令，而不是更传统的基于控制的条件转移的实现。

对于预测错误，不需要很恐慌，正常对待即可，因为： - 现代处理器中的分支预测逻辑非常善于辨别不同的分支指令的有规律的模式和长期的趋势。所以不要过分关心分支预测 - 分支预测只对于有规律的模式可行，因此尽可能书写适合条件传送的代码，因为这可以让GCC自己识别并把代码转换成条件传送。

现代处理器有专门的功能单元来执行对于内存的加载和存储操作。

一个包含加载操作的程序的性能即依赖于流水线的能力，也依赖于加载单元的延迟。一般来说加载操作要比功能单元更耗时。

这个操作与加载操作互斥，它们之间存在一些很细微的差别。

加载操作不会影响任何寄存器，所以一系列的存储操作之间并不存在数据相关(但是存储操作与其他操作不好说)。只有加载操作才会受到存储操作的影响，因为只有它才可以从那里读回值。

一般来说，存储单元包含一个存储缓冲区。它包含被发送到存储单元但是还没完成存储操作的数据和地址，这里的完成包含更新数据高速缓存。有了这样的机制，就可以保证每个存储操作都可以立刻放入数据并返回，不需要等待其他的存储操作更新高速缓存。如果一个加载操作被调用，会首先检查存储缓冲区，看看有没有匹配的地址，有的话就直接使用，不需要访问数据高速缓存，提高了速度。

来看一个例子：

.L3:    loop:
 movq   %rax, (%rsi)        Write val to dst
 movq   (%rdi), %rax        t=*src
 addq   $1, %rax            val=t+1
 subq   $1, %rdx            cnt--
 jne    .L3                 If !=0, goto loop

注意，两个计算是独立执行的，这就可以保证他们使用不同的功能单元进行这些操作。

注意看，图中的s_data和load操作之间有虚弧线，表明这个数据相关是有条件的：如果地址相同，那么load必须等待s_data把它的结果放在存储缓冲区才能继续，否则它们就可以独立地进行。

这个图更加清晰地展示了各个操作之间的关系。

对于示例A，由于加载存储之间使用的是不同的地址，所以关键路径只有cnt一个；而对于示例B，由于地址相同的，存储和加载存在数据相关，所以关键路径更多了。

从这两个例子看得出，对于内存操作有一些细微之处。对于寄存器操作，在指令被译码成微操作时，处理器就可以确定哪些指令会影响其他哪些指令；而对于内存操作而言，只有到计算出加载和存储的地址后，处理器才能确定哪些指令会影响其他的哪些。