维普资讯 http://www.cqvip.com 第５卷第５期 实验科学与技术 ・４９・ 程序优化的基本思路’ 陈谊 ”，唐乐理 （成都纺织高等专科学校ａ．电气系；ｂ．电教中心，成都６１００４１） 摘要：从改善性能的前提出发，对程序优化的一些基本思路作了归纳。讨论了分析代码结构的几种常用的方法，比较了三 种底层策略，并提供了相应的范例代码。 关键词：程序优化；Ａｉｒ＂编；流水线 中图分类号：ＴＰ３１１．１１ 文献标识码：Ｂ 文章编号：１６７２－４５５０（２００７）０５—００４９—０４ Ｂａｓｉｃ Ｐｒｉｎｃｉｐｌｅｓ ａｎｄ Ｒｕｌｅｓ ｉｎ Ｐｒｏｇｒａｍ Ｏｐｔｉｍｉｚａｔｉｏｎ ＣＨＥＮ Ｙｉ，ＴＡＮＧ Ｌｅ—ｌｉ （ａ．Ｄｅｐｔ．ｏｆ Ｅｌｅｃｔｒｉｃａｌ Ｅｎｓｉｎｅｃｒｉｎｇ；ｂ．Ｅｌｃｅｔｒｉｃ Ｔｅａｃｈｉｎｇ Ｃｅｎｔｅｒ，Ｃｈｅｎｇｄｕ Ｔｅ￣ｉｌｅ Ｃｏｌｌｅｇｅ，Ｃｈｅｎｇｄｕ ６１００４１，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｉｓ ｐａｐｅｒ ｔｒｉｅｓ ｔｏ ｄｅｓｃｒｉｂｅ ｂａｓｉｃ ｐｒｉｎｃｉｐｌｅｓ ａｎｄ ｒｕｌｅｓ ｉｎ ｐｒｏｇｒａｍ ｏｐｔｉｍｉｚａｔｉｏｎ．Ｔｈｅ ａｒｔｉｃｌｅ ｄｉｓｃｕｓｓｅｓ ｓｅｖｅｒａｌ ｃｏｍｍｏｎ ｍｅｔｈ－ ｏｄｓ ｉｎ ｎａａｌｙｚｉｎｇ ｃｏｄｅ ａｒｃｈｉｔｅｃｔｕｒｅ ｎａｄ ｉｌｌｕｓｔｒａｔｅｓ ｔｈｒｅｅ ｌｏｗ ｌｅｖｅｌ ｓｔｒａｔｅｇｉｅｓ ｗｉｔｈ ｄｅｔａｉｌｅｄ ｅｘａｍｐｌｅｓ． Ｋｅｙ ｗｏｒｄｓ：ｐｒｏｇｒａｍ ｏｐｔｉｍｉｚａｔｉｏｎ；ｄｉｓａｓｓｅｍｂｌｉｎｇ；ｐｉｐｅｌｉｎｅ １ 引 言 法的设计？ ２。２理解技术上的表现 ・ 优化，是软件工程期待达到的许多目标之一， 即便在算法的最高层，开发人员也需要了解算 它常常会与软件工程的其他目标，比如稳定性、可 法的哪些部分能够快速运行，哪些部分不能快速运 维护性以及可移植性等发生冲突。在保证程序的稳 行，以及为什么不能快速运行。一般可以从以下几 定性、可维护性和可移植性等性能的前提下，开发 个方面来考虑。 人员应该对程序进行优化，但程序优化手法的多样 ２．２．１ ＰＣ机上设备的数据带宽 性与复杂性（内联汇编、预编译／自修改代码、循 ＰＣ机上设备的数据带宽可以按照如下的顺序 环体展开、超标量体系结构和向量处理机等等）又 排序：用户输人设备、磁带机、网络、光盘驱动 使得这一工作对时间的开销是巨大的。针对这种情 器、硬盘、映射到内存的局部总线设备（显存）、 况，本文提出了一些解决问题的思路和方法。 未缓存的主存、使用外部缓存的主存、局￣／ＣＰＵ ２代码结构 缓存的主存、本地变量（寄存器）。 通常改进数据带宽性能的办法是使用更快的设 一般说来，程序结构设计上的改变会比“微调 备来缓存低速设备的数据，例如，要获知鼠标的当 代码”更多地影响程序的性能。所以，除非已经用 前移动方向，鼠标接口会去查询存储在内存中的一 尽更高级的手法，否则单纯地追求代码本身的性能 对坐标值，而不是每次去直接查询鼠标设备。 是不可取的。我们主要从以下几个方面来考虑代码 ２．２．２ ＰＣ机上算术操作的性能 的结构。 Ｐｃ机上算术操作的性能依照以下次序排序： ２．１简单的数学分析 超越函数、开平方根、取模、除法、乘法、以２为 在计算运行算法所需时间的时候，把所有的瓶 幂的加／减／除／取模运算等。 颈考虑进去后，通过一些简单的数学运算方法评估 几乎所有的程序都必须要做一些各种各样的基 这个时间是否是最优化的，是否还能继续加以改 本运算。简化程序中的公式，使用比较简单的算术 进，是否还能根据理论计算所得知的问题来调整算 运算来完成操作，是一种很常见的优化方法。很多 。收稿日期：２００７—０４—１９；修改日期：２００７一ｏ６—０４ ＋作者简介：陈谊（１９７９一），女，助教，工学学士，研究方向：计算机软件开发与教学。 维普资讯 http://www.cqvip.com ・５０・ 实验科学与技术 ２００７年ｌ０月 开发人员所熟知的整数与浮点数的运算性能的差 别，实际上与平台有相当密切的关系，在现代处理 器中，两者的运算性能相差甚微。同时，了解数据 带宽与计算性能之间的相互关系同样也是非常重要 的。例如，使用数据表来回避那些特定的重复计算 通常也是很好的方法，但前提是，你必须仔细比较 数据带宽和重复计算之间的性能开销代价，太大的 数据表通常是不会被缓存的，而且有时候反倒比 ＣＰＵ重新运算来得还要慢。 ２．２．３控制流程的速度 控制流程的速度大体排序如下：间接函数调 用，ｓｗｉｔｃｈ（）语句，直接函数调用、ｉｆ（）语句、 ｗｈｉｌｅ（）语句。 但要考虑到的另外一个主要问题是在带有流水 线技术的现代处理器的控制传输中的“可预测性”。 现代处理器会依据控制传输的方向来猜测，如果遇 到错误，就会停止操作并丢弃那些已经完成的错误 操作。错误预报的系统开销是非常高昂的，所以， 在执行条件运算时，必须非常小心对待其中那些等 价算术运算。 ２．３并行处理 尽管典型的计算模型是单线程的，但有时候， 程序算法所使用的数据位宽大大小于处理器允许的 数据类型的宽度。更具体地说，如果某个算法使用 Ｂｙｔｅ，那么可以通过基于Ｗｏｒｄ的指令来连续使用 ２、４或者８个Ｂｙｔｅ进行操作。此外，在程序设计 的过程中，可以考虑使用现有系统上的多个处理单 元。例如，如果计算机装备有图形处理器（显示 卡），那么程序可以在ＣＰＵ做运算的时候，并行地 进行绘制图形的操作。 ２．４全局地看问题 程序开发人员应该对算法流程有一个整体的认 识，并意识到所采用算法的优劣之处。例如，应该 避免使用一些通用结构来处理一个可以被特定结构 更快处理的问题，在对程序的结构进行设计时应该 考虑到对其进行快速性能分析的可能性。 通常很难确切地知道一个程序是不是已经足够 优化，但是从数据类型的观点出发，应该考查数据 的访问是否频繁，程序是否使用Ｃａｃｈｅ，是否已经 对算法使用了一些标准的优化方法。 如果程序使用模块化的方法编写，那就意味着 每个模块都会有一些与其他模块交流的ＡＰＩ，对于 ＡＰＩ的修改通常会大大改进与其他模块交流的性 能。 常用的一个很有用的算法性能优化技巧，是把 嵌套循环中的内部循环操作提出到外部循环中来操 作。这样的操作对于性能的优化作用很明显，开发 人员通常不会注意到：复杂的外部循环有助于加速 内部循环的操作速度。关于这个技巧的最有名的一 个例子大概是在人工智能领域中有名的香农最小一 最大算法（计算树值）被一个叫做Ａｌｐｈａ—Ｂｅｔａ修枝 的方法大大优化。尽管修改前后，两种算法都有同 样的内容和同样的叶运算，但算法性能的提升是指 数级的。 下面举例说明全局地看问题的重要性。假设某 公司想要在ＰＣ上写一个动作类的游戏，而这个公 司在此前已经从网上或者游戏公司那里听说过优化 算法是很重要的工作，但如果没有经过全局的仔细 思考，就可能会进入误区，最典型的错误是你相信 你必须用汇编代码重写程序才能完全利用到ＣＰＵ 的性能。 动作视频游戏属于多媒体应用程序。它们需要 图像、声音，可能还有网络连接与用户输入。对于 ＰＣ来说，支持这些特性的硬件设备对于ＣＰＵ来 讲，都是完全的外部设备。实际上，像人工智能、 冲突检测、保持记录、保持时间这些操作对于一个 快速的ＣＰＵ（例如奔腾）来讲，都是开销很低的操 作。理解这些多媒体设备远比知道如何去优化 ＣＰＵ的每一次运算更重要。这就很自然地会导出 使用高级语言编译器和使用动态设备库的问题。 如何设计与硬件设备的交互，对于游戏来讲， 是非常重要的一环，甚至比速度为重要。游戏使用 者的计算机系统配置可能千变万化，这是个非常复 杂的问题。但是，使用其他的ＡＰＩ也是要考虑的重 要的问题。例如，使用可能的硬件并行／加速图形 填充功能就比使用ＣＰＵ做软件像素填充要好。如 果声卡硬件支持使用大缓存的声音采样，那就比使 用基于ＣＰＵ的小缓存音频要好。使用状态机来管 理输入比查询特定状态要好。同样，因为相对 ＣＰＵ来讲，网络运行速度太慢，所以单独开出一 个线程来管理它会比较好，再者，基于状态机的网 络管理也比基于状态查询的性能更好。 下面是一个范例项目中的一些参考程序，原作 者在过去的优化过程中犯了一些原则性的错误，原 作者的代码如图１所示。 如果把Ｄｏ—ＸＸＸ（ｉ）函数当作一个黑盒子，假 定对它的修改不会带来任何性能上的改进，那么， 根据前面提到的理论，对这段代码进行优化的方法 是把” 语句提到循环外面来，如图２所示。 维普资讯 http://www.cqvip.com
第５卷第５期 Ｅｘｐｅｒｉｍｅｎｔ Ｓｃｉｅｎｃｅ＆Ｔｅｃｈｎｏｌｏｇｙ ・５ １・ ／ 根据变量值设置状态位 ／ ＬｉｎｅＰｒｌｎｔｅｒＤｒｉｖｅｒ一＞ＣＡＰＳ Ｉ＝Ｚ： ／ 重要的内部循环 ／ Ｆｏｒ（ｉ＝０；ｉ＜ｎ；ｉ＋＋）｛ Ｉｆ（（ＬｉｎｅＰｒｉｎｔｅｒＤｒｉｖｅｒ一＞Ｃａｐｓ）＆Ｐｒｉｎｔｉｎｇ） ｛Ｄｏ—Ｆｉｒｓｔ（ｉ）； ｝ Ｅｌｓｅ ｉｆ（（ＬｉｎｅＰｒｉｎｔｅｒＤｒｉｖｅｒ一＞Ｃａｐｓ）＆Ｓｔｏｐｐｅｄ） ｛ Ｄｏ—Ｓｅｃｏｎｄ（ｉ）； ｝ Ｅｌｓｅ｛ Ｄ０—Ｔｈｉｒｄ（ｉ）； ｝ ｝ 图１原作者的代码 ／ 根据变量值设置状态位 ／ ＬｉｎｅＰｒｉｎｔｅｒＤｒｉｖｅｒ一＞ＣＡＰＳ Ｉ＝Ｚ： ／ 重要的内部循环 ／ Ｉｆ（（ＬｉｎｅＰｒｉｎｔｅｒＤｒｉｖｅｒ一＞Ｃａｐｓ）＆Ｐｒｉｎｔｉｎｇ） ｛ Ｆｏｒ（ｉ＝０；ｉ＜ｎ；ｉ＋＋）｛ Ｄｏ—Ｆｉｒｓｔ（ｉ）； ｝ ｝ Ｅｌｓｅｉｆ（（ＬｉｎｅＰｒｉｎｔｅｒＤｒｉｖｅｒ一＞Ｃａｐｓ）＆Ｓｔｏｐｐｅｄ）｛ Ｆｏｒ（ｉ－－Ｏ；ｉ＜ｎ；ｉ＋＋）｛ Ｄｏ—Ｓｅｃｏｎｄ（ｉ）； ｝ ｝ Ｅｌｓｅ ｛ Ｆｏｒ（ｉ＝０；ｉ＜ｎ；ｉ＋＋）｛ Ｄｏ＿Ｔｈｉｒｄ（ｉ）； ｝ ｝ 图２优化后的代码 现在可以根据前后两段代码来计算，ｉｆ语句会 带来多少性能开销？在第１个循环中，它是所有ｊｆ —ｅｌｓｅ逻辑的Ⅳ倍，在第２个循环中，它只是所有 ｉｆ—ｅｌｓｅ逻辑的一倍，所以在当ｎ＜１时，第１个程 序性能会很好，但当ｎ＞１时，第２个程序的性能 则远远胜出。 ３底层策略 当所有的算法优化方法都已经用尽，而算法距 离预期的性能指标还相差甚远的时候，就需要尽可 能地在最低的层次上来继续分析问题。 ３．１框架 不管使用什么方法，在设计算法时都必须知道 算法的性能瓶颈何在。优秀的编译器会提供全面的 工具来帮助简化性能分析。但即便是有最优秀的工 具，当算法变得复杂的时候，还是需要特别的小 心。例如，大多数ＵＮＩＸ系统内核都会把大约７０ 的处理器周期消耗在“空转”上，显然，无论怎样 对“空转”进行优化都是无济于事的，对性能不会 有任何改进。 ３．２反编译 当使用高级语言编码时，源程序的任何微小改 动都会给汇编代码带来巨大的不同。在这个方面， 经验很重要。在对目标代码做一次反汇编操作之 后，一般来说会看见：移位操作可能比乘法更有效 率，复杂的“ｆｏｒ”循环会产生到条件评估的额外跳 转。而“ｄｏ…ｗｈｉｌｅ”循环和它等效，却不会产生额 外的跳转指令。 ３．３使用ＣＰＵ／平台的特殊功能 很显然，如何去处理这个问题取决于程序所使 用的ＣＰＵ，但是，仍然有一些值得开发人员关注 的事情：脉冲写入，存储器访问约束，分支预测， 流水线，多重执行单元等。运用灵活的优化编译 器，这许多的功能都可以通过对程序的高层代码做 细微修正来做到。理论上讲，可以在程序的任意位 置插入内联汇编代码来改进速度，但对于现代优化 编译器来说，这种说法不一定总是正确。 一般来讲，对于代码的调整都会涉及以上提到 的几个方面，框 反编译这两个步骤通常会消耗 大量的时间，但带来的改善程度有限。 使用平台的特殊功能通常意味着要动手写一些 汇编代码，但结果会很好。这方面的一个例子是 Ｑｕａｋｅ游戏的纯软件渲染引擎。Ｍｉｃｈａｅｌ Ａｂｒａｓｈ组 织了Ｑｕａｋｅ中的代码，他利用了奔腾处理器上的整 数和浮点流水线的同时执行来加速信息传递，这样 做的好处已经在游戏中显现出来了。 在决定花费相当时间执行底层优化之前，需要 认真考虑，因为无论如何，对于架构的了解都比随 意去砍掉一些代码更重要。比如说，在一个视频游 戏中，如果能解决图形存储器的瓶颈问题，会比单 纯去优化ＣＰＵ执行周期更有效、更直接。 关于特定ＣＰＵ的优化，在Ｘ８６平台上有一个关 于浮点数的例子，其中—个问题是关于“ｉｆ”语句的。 Ｆｌｏａｔ ｚ［ｃｏｕｎｔ］； ｝ 在包含分支跳转的条件语句中，执行浮点数到 维普资讯 http://www.cqvip.com
・５２・ 实验科学与技术 ２００７年１Ｏ月 整形数的转换速度相当缓慢。对这个问题的解决办 改进相比，我们可以忽略掉这个缺陷。 法是：无论是浮点数还是整数访问存储器的速度都 很快，又由于ｚ是在内存中的变量，开发人员需 ４结束语 要做的是把每一个ｚ［ｉ］与０做比较，而ＩＥＥＥ的规 本文所提到的一些方法与技巧大都基于Ｉｎｔｅｌ 范里面提到０和一０都是允许的，只是在运算时做 Ｘ８６架构，这是为了避免引入一些额外的话题而使 同一数处理。 问题复杂化，读者可以结合本文所提出的思路与实 根据这个理论，我们可以这样修改算法： 际工作中的经验，在相应的硬件平台上实现程序算 Ｆｌｏａｔ Ｚ［ｃｏｕｎｔ］； 法的优化。 Ｌｏｎｇ Ｔ； 参考文献 Ｔ＝ （（１ｏｎｇ ）＆（Ｚ［ｉ］））； ［１］Ｂｒｕｃｅ ＥｃｋｅＬ《ｃ＋＋编程思想》［Ｍ］．郑宗田，邢大 Ｉｆ（Ｔ＋Ｔ） ｛ 红，孙慧杰，等，译．北京：机械工业出版社， ２ｏｏＯ． ［２］ 夏宏，李占才．浮点加法器电路设计算法的研究 ｝ ［Ｊ］．计算机工程与应用，２００１，３７（１３）：１Ｏ一１２． 这段代码的问题在于不能移植，只是一种属于 ［３］都志辉，程旭．一种ＨＰＦ程序的监测与分析工具 ３２位ＩＥＥＥ规范的技巧，但与它所带来的性能上的 ［Ｊ］．软件学报，１９９９，１０（１０）：１０９１～１０９５． （上接第３８页） 或苹果表面粘匀酵母液，放人已配制好的培养基 果，喜欢营养物质丰实的生存环境。我校遗传工程 上，再将此瓶放在２５℃培养箱中。待一两天后酵 实验室以１５０ ｍＬ水为单位玉米面粉培养基进行配 母菌大量繁殖，创造了果蝇营养物质丰富的生存环 制，所需原料成分及数量如表１所示。 境，将果蝇接进瓶内繁殖，２～３ ｄ待雌蝇产下大 表１培养基的组成成分 量的卵后，取出。取出后的培养瓶放人温度１６～ １８℃的培养箱中继续培养。延长幼虫生长周期，时 间大约１２ ｄ左右，使其充分地生长发育和吸取营 养物质，达到育肥的目的。 方法２：将果蝇放人培养瓶中（半磅牛奶瓶放 １Ｏ对左右）在１６～１８￣Ｃ的稍低温度条件下培养。接 种１２～１８ ｈ后，将成虫移出，控制成虫的排卵持 续时间，以免产生过多的卵（要求每ｃｍ 培养基表 面有２Ｏ～４ｏ只幼虫）。一龄幼虫出现后，每天在培 养基表面滴加２％～４．５％的酵母液或鲜酵母。２～ ３龄幼虫应滴加１Ｏ 左右的酵母液，滴加的量以覆 配制时，先将水分成两份，其中一份用于煮溶 琼脂和蔗糖，另一份煮溶玉米粉，待两份分别溶解 盖在培养基表面薄薄一层为宜。使其在生长过程中 充分地发育和吸取营养物质，达到育肥的目的，时 煮好后再合到一起煮沸，去火后再加酵母粉和丙 间大约１４ ｄ左右。 酸。然后，将黏稠的培养基搅拌后再分装在５０ ｍＬ 这样的三龄幼虫易解剖出唾腺，可以获得染色 三角培养瓶中，厚度２ ｃｍ左右，加盖棉塞，在 体分散良好的制片。 ０．１ １ ｍＰ、１２１℃下灭菌５～８ ｍｉｎ，待培养基冷却 后，即可分装果蝇。 ４唾腺材料的特点 ３ 唾腺材料的培养方法 用以上两种方法培养出的三龄幼虫与普通培养 基相比有明显的优势，表现在： 发育充足、肥大的三龄幼虫，其唾腺和唾腺细 （１）个体肥大，身体强壮，生命力旺盛等。 胞发育良好。利用这样的唾腺细胞才能制备出理想 （２）剖离出的唾液腺发达，在显微镜１０×物 的染色体玻片标本。因此要求培养基营养丰富，含 镜下观察，细胞轮廓非常清晰，每个腺体上大约有 水量较高，发酵良好。 １００多个大型细胞，细胞核也大。 方法１：取洁净消毒的烧杯一个，取无菌水２Ｏ （３）染色后，染色体着色速度快，经过大约 ｍＬ，加酵母粉１～１．５ ｇ融化成均匀新鲜酵母液。 １０ ｍｉｎ左右可以清晰看到细胞核是由染色体卷缩在 用７５％酒精将双手消毒，然后，将切成小块的梨 一起形成的。