国家集训队2009论文集论程序底层优化的一些.pdf

《国家集训队2009论文集论程序底层优化的一些.pdf》由会员分享，可在线阅读，更多相关《国家集训队2009论文集论程序底层优化的一些.pdf（37页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2009 年全国信息学奥林匹克冬令营论文 成都七中 骆可强 第 1 页 论程序底层优化的一些方法与技巧 成都七中 骆可强 摘要：本文以优化程序运行的时间效率为目地，从编译器、汇编代码、CPU 特性等较为底层的概念着眼，对程序优化进行了全方位的探讨，总结了在优化中实用的思想、原则、方法和技巧，并对它们在竞赛中的应用价值做出了一些尝试。关键字：优化 CPU 汇编语言 编译器 目录 序言 第页 引例 第页 CPU 指令的运行效率 第页 数值运算的优化 第页 除法 第页 乘法 第页 高精度运算 第页 CPU 优化特性 第页 高速缓存 第页 分支预测 第页 乱序执行 第页 位运算技巧 第页 高维数组使用

2、的注意事项 第页 应用举例 第页 总结 第页 参考文献 第页 特别感谢 第页 序言 信息学奥林匹克竞赛（Olympiad in Informatics）是研究怎样编写计算机程序来解决特定问题的竞赛。考察的关键点，在于怎样利用有限的系统资源（CPU 时间片与系统内存）来求解规模庞大的数学模型。在“正确”这一前提下，“效率”自然是考虑问题的第一要素。效率，分为时间效率与空间效率，如何对时间效率进行优化是本文将要研究的主题。算法算法是决定时间效率的关键是决定时间效率的关键 优化程序的时间效率，简单地讲，就是用尽一切手段，在保证正确的前提下让程序的运行时间更短。那么，有些什么手段呢？最重要的自然是：使

3、用尽可能高效的算法。算法（Algorithm），是一系列解决问题的机械步骤，它采用明确定义的语义，描述了求解特定数学模型的一般方法。算法的好坏，直接决定了程序的运行效率。采用低效的算法或高效的算法，其差别就好像选择走路或是坐飞机，完全不在一个数量级。时间复杂度时间复杂度的概念的概念及其局限性及其局限性 2009 年全国信息学奥林匹克冬令营论文 成都七中 骆可强 第 2 页 为了衡量一个算法时间效率上的优劣，计算机科学中引入了时间复杂度的概念。回忆我们习惯使用的大 O 表示法，我们说一个算法运行时间的界是 O(f(n)，所表示的意义是，假设这个算法的实际运行时间关于输入规模 n 的函数是 T(n

4、)，那么存在正常数 n0、c，使得对于 n n0，有 0T(n)cf(n)。有了这样一个上界，我们就能知道 T(n)的增长速度，从而能够大致判断对于给定的 n，我们的算法能不能在一个合理的时间内出解。然而另一方面不可否认的是，这样一个工具是极其粗略的。我们注意到刚才的定义式中存在一个常数 c，它在渐进意义上是无关紧要的，但回到现实世界中，它却不可忽视。同样是 O(n)阶的算法，有些可以快到只消耗 2n 个 CPU 时钟周期，而另一些甚至需要 1000n 个时钟周期还要多。就好像同样是乘坐飞机，也有快慢的极大差别。使用相同时间复杂度的算法，因为这个常数 c 的不同，实际运行所需要的时间，也可能有

5、天壤之别。算法并不是时间效率的全部算法并不是时间效率的全部 那么，这个常数受哪些因素的影响呢？无疑，它同样受制于算法：不同的算法，可能有着相同的复杂度，但是实际效果截然不同。相同的算法，可能有着不同的实现方式，一些逻辑上的简化也能大大降低运行所需花费的时间。那么，算法就是程序运行效率的全部了么？答案是否定的，有些东西是隐藏在逻辑层面之下的，它们同样显著地影响着程序的运行效率，而我们却很难看到。举例来说，你能想象当我们在 C 语言中书写 a/=7 这一语句时，实际上处理器并没有做缓慢的除法，而使用了乘法和位移取而代之么？因为这样，我喜欢把大 O 定义式中的常数 c 一分为二的来看待：cc1c2，

6、c1 代表逻辑层面（算法）的消耗，而 c2 表示每一句程序语句在底层运行的消耗，那么程序的实际运行时间，约为 c2c1f(n)，方括号中的部分 c1f(n)就完全由算法来决定，而 c2 则取决于程序的底层实现。前者固然重要，后者也同样不可忽视。本文将要研究的，就是怎样在程序运行的底层对细节做出优化，以提升程序的运行效率。为什么要学习底为什么要学习底层优化层优化 在 OI 竞赛中，算法是考察的重点。底层实现看起来并不重要，确实提升空间也相对较小，但当我们设计的算法有一些先天缺陷时，或许对底层做细致的优化能对我们有很大的帮助，在后文中会展示一些实际的例子。在竞赛之外，学习底层的东西，能让我们更深入

7、地认识眼前的机器，即使在使用高级语言书写程序时，脑海中也会自然投射出底层发生的事情，从而能够写出质量更高的代码。在这篇论文前期准备、实验研究、总结规律到最终成文的过程中，我学到了太多的东西，这些东西在我们平时为 OI 竞赛编程的过程中是很难看到的，而我也相信，这些东西在为大家所广泛认识之后，同样能够服务于竞赛，实际地提升成绩。说了这么多，或许是该展现一个实例的时候了。下面我们从一个极其简化的编程任务入手，来看看什么是底层优化，有些什么样的工具，能做到什么程度。2009 年全国信息学奥林匹克冬令营论文 成都七中 骆可强 第 3 页 引例 让我们先来看一个非常简单的例子：假设我们被要求编写这样一个

8、函数，接受一个指向 32 位正整数数组头部的指针，以及数组的长度，要求函数返回这些整数中的最大值。在 C 语言中，函数头应该是这样：朴素朴素的实现的实现 若要在算法层面研究这个问题几乎没有任何价值，进行一遍线性的扫描即可得到 O(n)级别的算法，另外由于数组中的每一个元素必须被访问到才能保证出解正确，所以算法的复杂度下界也是 O(n)。我们可以立即写出下面这个 C 语言程序：int get_max(int*a,int l);平台简介平台简介 条件所限，本文中的所有研究、编码、测量工作均在一台 Thinkpad X61 笔记本上进行，下面简要给出工作平台上硬件和软件与优化工作相关的规格参数：CP

9、U:Intel Core 2 Duo CPU T7100 1.80GHz Cache:L1-64KB L2-2MB 主存:SODIMM Synchronous 667 MHz 1GB 2 操作系统:Ubuntu 8.10-Intrepid Ibex 内核版本:Linux 2.6.27-8-generic 编译器版本:gcc 4.3.2 汇编器版本:GNU assembler 2.18.93.20081009 连接器版本:GNU ld 2.18.93.20081009 当然，一种优化方法的实际效果，和平台规格密切相关。如果只在一种平台（主要指 CPU）进行测试就妄下结论，是不负责任的。为此，我也

10、将文中所涉及的程序在不同的平台下进行了广泛的测试，跨越了不同的操作系统（windows 与 linux）和不同厂家生产的 CPU（intel 与 AMD）。测量结果的绝对值自然千差万别，但采取不同优化方式所取得的效果基本上是一致的，这得益于现代 CPU 都采用了一套相似的内部架构与优化引擎，为开发人员提供了方便。不过另一方面，也要求我们在学习 CPU 开发时应以把握大原则为重点，而不要钻牛角尖。如果沉溺于为某种特定的 CPU 内部特性做古怪的优化，会导致在不同的 CPU 上运行效果天差地别，这样的优化是没有价值的。遗憾的是，后文将提及的 SIMD 系列优化方法，在 AMD 生产的芯片上，虽然可

11、以兼容，但是优化效果并不突出，值得大家留意。/最初版程序 int get_max(int*a,int l)int mx=0,i;for(i=0;imx)mx=ai;return mx;2009 年全国信息学奥林匹克冬令营论文 成都七中 骆可强 第 4 页 这个程序显然能够正确地完成所要求的任务，而且，算法的复杂度也达到了理论下界。效率怎么样呢？效率怎么样呢？让我们来检验一下程序运行的速度。我在测试平台将此函数应用于一个存有 10000000个整数的数组，连续运行 100 次并求平均占用的时钟周期数。测量值为 75305510 个周期。处理一个数平均就占用了 78 个时钟周期，结果不令人满意。第

12、一次优化第一次优化 开始着手寻找程序可优化之处，首先发现ai被提及了两次，重复计算地址在这个小循环中的开销也是不可忽略的，那么第一版的优化我们尝试来进行普通的循环和寻址的优化：关于文中程序所使用的计时方法关于文中程序所使用的计时方法 为了测试程序的运行效率，需要一种测量时间的工具，有许多不同的库函数，操作系统 api，命令行工具可以进行时间测量，本文主要使用 IA32 处理器提供的 rdtsc 指令来获取程序运行消耗的时钟周期，此方法精确度较高，缺点在于无法排除掉程序运行过程中操作系统和后台运行程序所占用的时钟周期，结合 linux 系统命令 time 一起使用可以弥补这一缺憾.下面是本文所有

13、程序都会用到的计时函数的 C 代码：#define ull unsigned long long ull get_clock()ull ret;_asm_ _volatile_(rdtscnt:=A(ret):);return ret;编译说明编译说明 众所周知，现代编译器已经不再局限于简单地把一句句高级语言翻译为对应的汇编语言，而能够智能地完成许多以前只有人手工才能完成的优化，特别是各个编译器提供的高级优化选项，更是常常能够提供接近人类手工优化的效率。但是，在我们 OI 竞赛的评测中，这些优化选项是不会被开启的。所以，本文中所有程序的编译，都没有打开优化选项。诚然，打开这些优化选项，本文中介

14、绍的各种人工优化的效果可能会打些折扣，但我仍然觉得这样做是合理的，一来更贴近比赛中使用的评测环境，二来既然是在研究优化，我们自然应该亲自去探究其中的方法和原理，而不应该让别人的程序来代劳，否则可能永远也不会清楚其中的奥妙。为此，本文中所有的程序均使用竞赛时的编译选项进行编译并测量效果，对于 c语言程序，编译命令为:gcc a.c-o a 2009 年全国信息学奥林匹克冬令营论文 成都七中 骆可强 第 5 页 测试一下运行时间，平均占用时钟周期测量值为:66047005，处理一个数平均下降了一个时钟周期，比第一版程序在时间效率上优化了 12%。来回顾一下这次优化，他解决了在初版程序代码中出现的重

15、复寻址的问题，而获得了期望中效率的提升，从本质上说仍然属于逻辑层面的优化。这次优化是在 C 语言层面编写，也能够在 C 语言层面进行解释的。第二次优化第二次优化 继续前面的思路，很难再想出什么有效的优化了，这就是我们的终点吗？其实游戏才刚刚开始，下面给出第二个优化：这个程序使用了许多宏定义，可读性较差。不过思路非常简单：将原来单线的求最大值进程分为八路，最后再来汇总总的最大值。要说明一点的是，正如程序第一行的 assert所显示，这个函数只能在 l 是 8 的倍数的情况下工作，要让它可以对任何 l 工作很容易，不/第二次优化 int get_max(int*a,int l)assert(l%8

16、=0);#define D(x)mx#x=0 int D(0),D(1),D(2),D(3),D(4),D(5),D(6),D(7),*ed=a+l;#define CMP(x)if(*(a+x)mx#x)mx#x=*(a+x);while(a!=ed)CMP(0);CMP(1);CMP(2);CMP(3);CMP(4);CMP(5);CMP(6);CMP(7);a+=8;#define CC(x1,x2)if(mx#x1mx#x2)mx#x2=mx#x1;CC(1,0);CC(3,2);CC(5,4);CC(7,6);CC(2,0);CC(6,4);CC(4,0);return mx0;/第

17、一次优化 int get_max(int*a,int l)int mx=0,*ed=a+l;while(a!=ed)if(*amx)mx=*a;a+;return mx;2009 年全国信息学奥林匹克冬令营论文 成都七中 骆可强 第 6 页 过那不是我们关注的重点，为了让代码简短一些，略去不表。这个程序的效率怎样呢？同样平台下的测量值为：34818706，比最初版本优化了 54%。是什么让这个程序拥有了如此大的效率提升？难道是指针 a 的递增次数只有原来 1/8导致的？从 C 语言的层面来看，只有这一个解释。但这是说不通的，因为相比循环体里面的语句，这一个递增显得无足轻重，至少不会带来这么大的

18、效率改善。而除了这里，从 C 代码上看和第二个程序又没有本质上的区别。难道计算机程序的运行是完全不可预测和理解的吗？深入深入汇编语言汇编语言 让我们来回顾一下 C 语言编写的程序是怎样运行的吧，首先编译器(compiler)将 C 代码编译为汇编语言(assembly language)代码，再经过汇编，连接等一系列步骤转化为可执行文件。这里最关键的一部，自然在编译环节，因为一旦代码编译为机器指令后，在 CPU中执行它的方式就已经确定了。编译的质量，也直接决定了程序运行的效率。如果仅仅把目光集中在 C 代码的层次，而完全不在汇编语言层面进行思考，优化的过程就像被蒙住了眼睛。既不可能真正看清程序

19、运行效率的本质，也不能进一步进行更强的优化。对第二次优化的程序进行编译，得到相应的汇编代码，经过查看，发现除了循环变量的累加之外，其他语句对应的汇编代码的面目并无甚差别，仅仅是简单的重复并列起来。但确实获得了极大的效率提升，要完整的解释这个问题，会提及处理器中的各种优化机制：乱序执行、流水线机制、指令预取、分支预测、寄存器重命名、高速缓存，这些主题都将在后文中作研究。简单的讲，在最初两个程序中，每次计算新的 mx 都会依赖于上一步的计算结果，相关的计算指令也必须依次运行，而将求值过程分为多路处理，mx0,mx1 等变量的相关指令之间互相没有关联，让处理器有更大的机会将他们并发。过于底层的细节固

20、然不容易完全掌控，但是遵循一些基本的原则，总有机会使处理器为我们作出优化。第三次优化第三次优化 既然已经深入到了汇编语言的层次，那不如直接用汇编语言来编写这个函数。汇编语言的利与弊汇编语言的利与弊 在 CPU 中重要的概念如寄存器(register)、状态标志(status flag)、指令(instruction)等，在高级语言中全部被隐藏，取而代之的是，高级语言过于依赖内存变量这一概念，而读写内存，是处理器最低效的操作之一。而且高级语言过于丰富的语义也造成了翻译过程自然出现极大浪费。这一切，让我们在 C 语言层面作优化，就像带着脚镣跳舞，一旦使用起汇编语言，这一切就豁然开朗了，我们不再被内

21、存变量与高级语句所束缚，可以直接操纵最底层的部件，更有额外的丰富指令可供使用。可以说，使用汇编语言是获得极致效率的基础。汇编语言既然如此之好，那我们为什么不用汇编语言来编写所有的程序呢。这主要是因为汇编语言编码成本太高，要用来编写大型程序虽并非完全不可能，也是极其困难的，实际的程序中并非所有地方都需要如此极致的效率，而真正需要的是正确地设计代码架构并编写程序逻辑，要用汇编语言来做这些，就好像用小颗粒的颜料逐点绘制一副油画，是很难把握成品的全貌的。另一方面，汇编语言编写的程序会有较强的平台依赖性，可移植性很差，也使它被拒于应用程序开发的门外，而高级语言(如 C 语言)被发明出来较好地解决了这些缺

22、陷。那么汇编语言又一钱不值了吗？当然也不是，就算在现今的实际程序开发过程中，程序员们仍然使用汇编语言来编写程序中的效率瓶颈部分，而程序的主要部分使用高级语言来2009 年全国信息学奥林匹克冬令营论文 成都七中 骆可强 第 7 页 编写。要实现这一点，最简便的方法是使用编译器各自提供的内嵌汇编机制。使我们可以直接在 C 代码中书写汇编代码，并且可以通过 C 编译器的编译。这样做还有一个最直接的好处：在竞赛中，我们可以直接提交这样的程序并通过编译。使用内嵌汇编进行优化使用内嵌汇编进行优化 下面正式开始转向汇编语言进行优化，本文中的程序均使用 gcc 内嵌汇编，采用 AT&T格式的汇编语法，后面不再

23、做说明。首先，我们直接朴素地将原始意图使用汇编语言实现一遍，得到如下代码：这个程序的效率如何呢？测量结果为:平均 21322853 个时钟周期。处理一个数据平均只需要 2 个时钟周期了，相比最初的程序，优化了 72%，结果十分令人满意。打量一下这个程序，核心循环中，有 5 条指令，其中甚至有两条是条件分支指令，还有两条需要访问内存，而且使用了最复杂的 sib 寻址方式。感觉起来，平均 2 个时钟周期，是没有道理的，其实这主要得益于现代 CPU 各种强大的优化机制：高速数据 cache 使两次访问同一内存如同访问寄存器一般迅速，第一个条件跳转大部分时间不会成立，而相反第二个跳转总会成立，这让 C

24、PU 的分支预测发挥到极致。而强大的乱序执行引擎使得循环中的这些小指令得以以接近双倍的时间运行（以上提到的这些名词在后文都会有详细的介绍）。现代CPU 的优化如此强大，是否我们可以胡乱书写汇编代码了呢？绝对不是。优化中的一些小插曲优化中的一些小插曲 声明声明 本文并非以讲授汇编语言与计算机体系结构为目的，所以在这里假设读者对这两者有最基本的了解，否则阅读会有较大障碍。/第三次优化 int get_max(int*a,int l)int ret;_asm_ _volatile_(movl$0,%eaxnt .p2align 4,15n LP1:nt cmpl-4(%1,%2,4),%eaxnt

25、jge EDnt movl-4(%1,%2,4),%eaxn ED:nt /loop LP1nt decl%2nt jnz LP1nt movl%eax,%0nt :=m(ret):r(a),c(l):%eax);return ret;2009 年全国信息学奥林匹克冬令营论文 成都七中 骆可强 第 8 页 注意到在上面的程序中，有一行注释掉的 loop 指令，如果没有经验，或许会想，使用 loop 指令，指令码体积更小，而且使用复杂指令，一次性指示 CPU 完成更复杂的工作，应该具有更高的效率。那么我们使用 loop 指令取代递减与跳转指令试一试，结果令人大跌眼镜：平均耗费 56457348

26、个时钟周期，整整慢了一倍还多。RISCRISC 与与 CISCCISC 要解释这个问题，不得不提到 RISC 与 CISC 架构。CISC 全称为“Complex Instruction Set Computer”，即“复杂指令系统计算机”，它从计算机诞生之初一直沿用至今，他的指令集极其庞大，功能繁杂，导致制作工艺复杂，成本高昂，而且速度缓慢。看看我们现在使用的 intel pentium 处理器就知道了，虽然看似其中有很多一次性完成复杂工作的指令，事实上还是在 CPU 内部被翻译成多条微指令，才能真正在 cpu 上运行。这个过程本身造成的性能损耗可想而知，虽然处理器厂商采用了各种强大的办法来

27、试图优化这一过程，也不能弥补设计上先天的劣势。后来工程师们发现，事实上人们所使用的 80%的指令都处于 20%的指令集中，于是设计了理念完全不同的 RISC(精简指令集计算机)。通过采用一个较小但功能完备的指令集，大大简化处理器的设计。RISC 中不再需要微指令的概念，而直接硬件执行指令码，在一个时钟周期执行一条指令，性能极高且容易控制。到今天，只有 intel,AMD 等少数厂家还在生产 CISC 芯片。虽然 RISC 有如此多的优势，但不可回避的是，我们的普通桌面应用已经使用 CISC 架构许多年，对以前软件的兼容性不能放弃。为了兼顾性能与兼容性，处理器厂商使用了折中的方案：处理器的外层继

28、续兼容老式的 x86 指令集，而内核尽量向 RISC 靠拢：使用一套类似 RISC 的微指令集，内部采用 128 个物理寄存器，在外层通过微指令解码器，RAT(Register Alias Table)等把对外部指令映射到 RISC 核心上去。除此之外，处理器厂商继续大力优化指令集中类 RISC 的那一部分，使他们在流水线上能有最好的表现，而对于某些复杂指令，在很早以前就已经被处理器厂商放弃，cmps、cmov、lea 等复合指令不再具备速度优势，loop当然也是其中一员。所以，我们应该了解现今做汇编优化，应该尽量使用最基本的那一个指令子集，CPU 会帮助我们尽量高效地运行。当然也有例外，那就

29、是各 cpu 厂商都投入大量精力研发的 SMID 指令集，这在后面会提到。回到我们的程序，loop 指令低效的问题已经有了解答。同理，如果试图用 cmov 指令优化掉条件跳转，结果同样会令人失望。第四次优化第四次优化 完成了这个朴素的汇编优化，下一步又怎么做呢？容易想到：降低程序上下文依赖性！在前面的第二次优化中，这种方法起到了非常好的效果，那我们就在汇编语言中如法炮制一次：2009 年全国信息学奥林匹克冬令营论文 成都七中 骆可强 第 9 页 我们期待着它能起到第二个优化一般神奇的效果，运行程序，测量结果为 17447544个时钟周期。确实取得了优化，但效果不明显。立即想到，是不是应该展开更

30、多的次数呢？我试着进行 4 次展开，用上了全部的通用寄存器，结果再次令人大跌眼镜：速度竟然比没有展开时还要慢。其实仔细观察这个程序和前面第二次优化程序的汇编代码，不难发现第二次优化由于是编译器生成代码，冗余的小操作很多，乱序执行有非常大的优化空间。但是到了这个程序，代码已经十分精简，在每次循环体第一句 mov 指令 cache miss(后文会讲解)时，后面并没有指令可以提前来执行。所以优化的这点时间，本质上仅仅是循环展开所得。如果再进一步试图采用所有寄存器参与来进行 4 路求值，一来很不利于 RAT 工作，另一方面过多的条件跳转指令也让处理器吃不消。我们再一次看到，优化工作不是想当然的，如果

31、不充分了解处理器的特性，仅仅凭想象来做优化，不会取得什么效果，甚至适得其反。第五次优化第五次优化 已经做到了这个程度，考察程序各处似乎都无利可图了，优化再次陷入了僵局。要想再取得优化，必须再打开思维才行。这里要提到的，是所谓的单指令多数据(SIMD)的方法。/第四次优化 int get_max(int*a,int l)assert(l%2=0);int ret;_asm_ _volatile_(movl$0,%eaxnt movl$0,%edxnt .p2align 4,15n LP2:nt cmpl(%1),%eaxnt jge ED2nt movl(%1),%eaxn ED2:nt cmp

32、l 4(%1),%edxnt jge ED3nt movl 4(%1),%edxn ED3:nt addl$8,%1nt subl$2,%2nt jnz LP2nt cmpl%edx,%eaxnt cmovll%edx,%eaxnt movl%eax,%0nt :=m(ret):r(a),r(l):%eax,%edx);return ret;2009 年全国信息学奥林匹克冬令营论文 成都七中 骆可强 第 10 页 什么是什么是 S SIMDIMD？让我们回归程序优化的本原：优化，自然是为了让程序运行效率更高，而程序运行时，%90 的时间都在运行 10%的代码，这些代码自然就是循环。我们只用找出

33、程序的瓶颈部分，在最耗时的循环中取得微弱的优化，也胜过在外层决定性的巨大优化。而这些循环是在做什么呢，许多时候，他们是在遍历并处理大块的数据。处理器厂商发现了这一点，开发了SIMD 指令集来专门帮助更高效地处理大量数据。我们刚才有提到，不应该使用过于复杂的指令，用经过充分优化的更适应流水线的简单指令对程序运行效率更有益处，SIMD 的理念看上去不是和这个原则背道而驰么？其实不然，打个比方，我们有三条基本指令，洗苹果，削苹果，切苹果，为了更高效地完成任务，我们把他整合成一条复杂指令：处理苹果。这对更高效地完成任务有帮助吗？一点也没有，因为接受命令者首先要先回忆，处理苹果这一条指令意味着什么，然后

34、再按部就班地进行洗、削、切三个过程，不但执行任务的时间没有减少，反而还多出了分解复杂命令的过程，如果说这一个整合有帮助的话，那就在于创建了一条更简短的指令表达丰富的含义。使用那些“单指令多任务”的复杂语句，就好比上面一个过程，对时间效率优化毫无益处。但是，“单指令多数据”就不一样了，再设想一下，假如我们时常需要处理一大堆苹果，我们可以创建一个叫“一刀切两个苹果”的指令，那么在切的阶段，必然就能更高效地完成任务，为什么不创建“一刀切 100 个苹果”的指令呢？因为我们的刀，让我们一次切不了这么多。处理器就是我们的刀，数据就是苹果，创建一次处理多个数据的指令，可以减少发号施令所用的时间，而让处理器

35、专注于十分高效地完成数据处理任务。同样，处理器处理数据的能力也是有限的，一次能处理多少数据，受制于处理器内部寄存器的大小。intel 在 Pentium MMX 处理器中发布了 MMX 指令集，它借用 FPU 中的八个 80 位浮点寄存器，一次只能同时处理 8 字节数据。在 Pentium 2 又发布了 SSE 指令集，加入 8 个独立的 128 位寄存器，此后又发布了 SSE2,3,4，不断加入新的 SIMD 指令，使程序员可以极其高效地完成打包整数、浮点数的处理，在科学计算、信号处理、3D 游戏中都有着广泛的应用，而 AMD 也一直紧跟 intel 的脚步，现在新一代的 AMD 处理器均能

36、支持到 SSE3 指令集。下面我们就来尝试将 SIMD 用在这个程序的优化中：2009 年全国信息学奥林匹克冬令营论文 成都七中 骆可强 第 11 页 用 SSE 指令集来处理这个问题的方式有些间接，大体思路仍然是多路求值，不过这次的这四路局部最大值，打包保存在 xmm0 寄存器中。为了把内存中的四个连续值与 xmm0 取较大值，需要先使用 sse 比较指令获得一个掩码，再通过位运算进行结合，这也是 sse 处理数据的常见方式。值得注意的是，这里使用了整整 5 条 sse 指令，这么复杂的过程，真的能有优化的效果么？运行程序，这次的平均时钟周期为 15898751，还真有一定的优化效果。看来，

37、处理器厂商确实也在 simd 指令优化上下了大力气。到了这里，我们的程序仅仅需要最初版程序 1/5 的时间了，处理一个数据仅仅需要 1.5个时钟周期，效率是十分惊人的。第六次优化第六次优化 优化就到此为止了吗？当然没有，有句话说得好：程序的优化是无止境的。我相信一定还存在更加优秀的方式解决这个问题，只是我才疏学浅，暂时还无法企及。不过另一方面，cpu 厂商同时也在不断地努力，给我们提供更加强大的工具。就这个问题，在 intel 近年发/第五次优化 int get_max(int*a,int l)assert(l%4=0);assert(sse2);int ret,tmp4;_asm_ _vol

38、atile_(txorps%xmm0,%xmm0n LP3:n tmovdqa%xmm0,%xmm1n tpcmpgtd(%1),%xmm1n tandps%xmm1,%xmm0n tandnps(%1),%xmm1n torps%xmm1,%xmm0n taddl$16,%1n tsubl$4,%2n tjnz LP3n tmovdqu%xmm0,(%3)n tmovl(%3),%eaxn tcmpl 4(%3),%eaxn tcmovll 4(%3),%eaxn tcmpl 8(%3),%eaxn tcmovll 8(%3),%eaxn tcmpl 12(%3),%eaxn tcmovll

39、 12(%3),%eaxn tmovl%eax,%0n :=m(ret):r(a),r(l),r(tmp):%eax);return ret;2009 年全国信息学奥林匹克冬令营论文 成都七中 骆可强 第 12 页 布的 45 纳米 Penryn 处理器中，支持了 SSE4 指令集，其中有一条 pmaxsd 指令，可直接取代前面的位运算步骤，那么可以写出这样一个程序：这个程序在我的处理器上尚无法运行，故无法测量其优化效果，不过我估计，在未来支持 SSE4 的处理器上，这个程序可以跑到处理每个数据一个时钟周期的极致。这个程序的优化就做到这里了，确实，这个例子显得过于简单而没有实用性，但它所折射出

40、来的一些思想和方法是共通的，后文将分别具体讨论各种方法与技巧，它们将为我们的优化实战提供详细的参考。关于各 CPU 指令的运行效率 在后文的内容中我们时常要与 CPU 指令打交道，要做出有效的优化，对这些指令的效率有基本的了解是前提。因此在开始之前，我们先来研究一下这些指令运行的快慢。在 CISC 架构处理器上，一条特定的指令具体要占用多少个时钟周期是很难有一个确切的答案的。因为这条指令不是独立存在于此的，在实际的运行中，它的微指令可能会被打散并和其它指令并发执行，这样就不再具有一个完整且独立的运行周期。另一方面，指令本/第六次优化 int get_max(int*a,int l)assert

41、(l%4=0);assert(sse4);int ret,tmp4;_asm_ _volatile_(txorps%xmm0,%xmm0n LP4:n tpmaxsd(%1),%xmm0n taddl$16,%1n tsubl$4,%2n tjnz LP4n tmovdqu%xmm0,(%3)n tmovl(%3),%eaxn tcmpl 4(%3),%eaxn tcmovll 4(%3),%eaxn tcmpl 8(%3),%eaxn tcmovll 8(%3),%eaxn tcmpl 12(%3),%eaxn tcmovll 12(%3),%eaxn tmovl%eax,%0n :=m(r

42、et):r(a),r(l),r(tmp):%eax);return ret;2009 年全国信息学奥林匹克冬令营论文 成都七中 骆可强 第 13 页 身和指令所使用的数据是否 cache，是否对齐，对效率也有着致命的影响。总的来说，一条指令的运行效率，和代码中的上下文环境有着密不可分的联系。这当然不是说我们就不需要关心各种指令的快慢了，例如一条除法指令无论在什么情况下也是会比一条加法指令要慢的，对指令集中各条指令的效率有个大致的了解，是正确地书写汇编代码的基础，甚至对于编写高级语言代码也很有好处。诚然 intel 官方的开发手册上有提供各条指令平均占用时钟周期数的一个参考数值，不过我还是更喜欢

43、在自己的平台上进行实际测量，印象也会更深刻一些。我的测量方式是，将待测指令放在一个有意义的上下文环境中，在指令的两测各插入一条 cpuid 指令以将被测指令隔离开来，并循环 1000000 次，测量消耗的时钟周期，再将被测指令抽去，再次循环同样的次数并测量，两者相减并除以循环次数，就得到了一个近似的时钟周期数。当然，这样的测量有许多可能导致误差之处，不过没有关系，因为我们关注的重点并不是它实际需要占用时钟周期数的绝对数值，这个数值在不同的 cpu 上是有差异的，但了解一个大体的情况始终是有意义的。下面给出我所测量的一些结果，它们将会在后文的论证中被引用。指令名称指令名称 操作数类型操作数类型

44、平均时钟周期数平均时钟周期数 add r32/r32 1 shr imm8/r32 1 bsr r32/r32 1 mul r32 2 div r32 21 fadd r 3 fdiv r 35 fsqrt n/a 60 padd xmm/xmm 1 关于数值运算的优化 一除法 在现代 cpu 中，乘法指令的速度基本已经被优化到足够快了，但除法指令，由于其逻辑的过于复杂，一直以来都需要消耗庞大数目的时钟周期，比其它简单指令要慢上数十倍。从前文中所做的测量就可以看出，即使使用 20 条位移指令，如果能取代一条除法指令的话，也是十分值得的。可是只要稍加思考就会想到，假如存在一种通用的除法算法，其效

45、率能够比 CPU 内部硬件实现的除法指令还要高的话，CPU 厂商一定会使用这种算法来重写除法电路。也就是说，对于一次普遍性的除法任务，固然 div 指令较为缓慢，但是也没有什么可优化的余地。从逻辑上讲是这样，事实也就是这样。消除除法消除除法 当然，这并不意味着对于除法我们就束手无策了。在各种特殊的场合，时常有专门的方法可以进行一些针对性的优化。最简单有效的一个方法无疑就是：避免使用除法，这时常需要在逻辑上进行一些调整，例如最简单的一句条件判断语句:if(a/bc)，我们可以将其转换为 if(ab*c)，要注意这并不总是成立，要考虑到乘法可能溢出还有 b 为负数时不等式需要变号等问题。在实际的算

46、法设计中，有时也有机会进行一些类似的变换，不过需要非常小心。2009 年全国信息学奥林匹克冬令营论文 成都七中 骆可强 第 14 页 减少取模运算减少取模运算 在竞赛题目中，我们时常需要解决这样的问题：要求对某种对象进行计数，不过由于数目太大，仅仅需要我们给出最后答案 mod M 的值即可。在这类问题的算法设计中，滥用%M操作对效率的影响可能是致命的，而取模操作，在计算机底层和除法操作是同一条指令所完成，速度极其缓慢，应该尽可能消除。这个工作有时只是举手之劳，例如对于一个可能为负的整数 a 进行取模，惯常的写法是(a%M+M)%M，之所以有两次 mod，是为了解决底层除法指令规定余数的符号和被

47、除数相同的问题，但是第二次 mod 是相当浪费的，一个简单的 if 就可以解决这个问题：又比如说，在许多线性递推的模型中，将其抽象为矩阵乘积的形式可以高效地解决。在求矩阵乘积的内层循环中，频繁地调用除法指令会使程序运行效率不堪忍受。为了解决这个问题，可以在计算结果中某个元素的值时先不进行取模，仅仅简单地进行乘法和累加，在计算完后再来取模。实践表明，此方法可以极大的提高程序的运行效率。减少减少浮点除法浮点除法 如果把浮点数也加入进来考虑，那优化的方法就更加灵活多样。一方面浮点数的各种运算之间的速度差距更为悬殊，除法指令更是慢到难以忍受；而另一方面，浮点数模拟的是数学中实数的概念，运算规律为我们所

48、熟悉，不需要像对待整数运算一样去推导数论方面的结论。例如，在浮点数中，我们可以认为 ab 等价于 a(1b)，而在整数运算中是不行的。相比在整数领域，对于浮点我们可以更加不遗余力地将除法指令替换为多条更加快速的指令：最简单的例子是，如果需要多次进行除以 b 的操作，我们事先计算 b 的倒数再来进行乘法是很划算的。如果要计算 abcd，我们可以先通分变为(adcb)(bd)再进行计算，虽然多了 3 次乘法，但是消除了一次除法，仍然是值得的。对此我进行了实际的测量，用通分与不通分的方式分别计算 10000000 次，在我的机器上，通分的方法，整整快了一倍还要多。这种优化甚至可以扩展到不相关的代数式

49、上，例如我们需要计算：我们可以写为:在我的机器上，第二段代码占用的时间，仅仅是第一段的 1/3！至此我们已经能够看出，浮点数乘法指令在除法的面前，几乎是可以忽略不计的。其实不仅仅是乘除法，浮点指令集中不同指令的效率差距拉得很开，这给了我们的优化无限的可能。就曾经有人自己实现了一个非常高效的基于牛顿迭代的开根算法，比 FPU 内部硬件实现的还整整快了 6 倍。不过，这些技巧更像是某种智力游戏，就不再在这里展开讨论了，我们只需要对各种浮点指令的速度有一个大致的了解，在编码时再即兴发挥即可。不过凡事不能过度，如果需要使用过多的简单指令来取代复杂指令，不但效率是否能有优化值得商榷，还会显著地导致代码易

50、错，难t=1/(b*d*f);x=a*d*f*t;y=c*b*f*t;z=e*b*d*t;x=a/b;y=c/d;z=e/f;inline int mod(int a)a%=M;if(a27 a=(unsigned int)b/123;2009 年全国信息学奥林匹克冬令营论文 成都七中 骆可强 第 16 页 CPUCPU 的位扫描指令的位扫描指令 但是前面所说的这些方法，都不是我想讲的重点。换个角度思考，处理器能够在一个时钟周期内完成 add，mov 等指令，这些指令都需要访问全部的 32 个 bit，按理来说，处理器要想快速得到一个 1 的位置，是非常容易的，幸运地是，IA-32 处理器确实