《代码优化：有效使用内存（含光盘1张）》

作者：[美]Kris Kaspersky
译者：谭明金
定价：48.00
页码：330
开本：短16开
出版时间：2004-10-01
 
　　本书系统深入地介绍了各种代码优化编程技术。全书分为4章。第1章集中介绍如何确定程序中消耗CPU时钟最多的热点代码，即有关所谓程序剖分技术，以及典型剖分工具的实用知识。第2、3章分别全面介绍RAM子系统与高速缓存子系统的代码优化知识。第4章主要介绍机器代码优化技术。各章在讨论基本原理的同时，详细给出了典型的代码实例，并对优化性能进行了定量的分析。
　　该书特别适合于作为应用程序员及系统程序员的学习与开发之用。同时，本书对在硬件方面的专业人员与技术工作者有一定的参考价值。

目录
第1章　程序剖分 1
1.1　剖分的目标与目的 2
1.1.1　总执行时间 2
1.1.2　执行时间的类型 5
1.1.3　处罚信息 7
1.1.4　调用次数 10
1.1.5　覆盖层次 11
1.2　微剖分的基本问题 12
1.2.1　流水作业或者吞吐量与等待时间 12
1.2.2　测不准 13
1.2.3　硬件优化 17
1.2.4　低分辨率 17
1.3　宏剖分的基本问题 18
1.3.1　运行时间的不一致性 18
1.3.2　二度运行问题 21
1.3.3　负面效应 22
1.3.4　单台机器的代码优化问题 24
1.4　最新剖分软件概述 24
1.4.1　Intel VTune 25
1.4.2　AMD Code Analyst 26
1.4.3　Microsoft的profile.exe 27
1.5　开发自己的剖分软件 28
1.6　VTune实用剖分知识 28
1.6.1　第一步：删除printf函数 36
1.6.2　第二步：将strlen函数体移出循环 36
1.6.3　第三步：对齐数据 38
1.6.4　第四步：删除strlen函数 41
1.6.5　第五步：删除除法操作 42
1.6.6　第六步：删除性能监测代码 43
1.6.7　第七步：函数组合 43
1.6.8　第八步：减少内存访问操作的次数 44
1.6.9　第九步：把VTune当做私人教练 47
1.6.10　第十步：下结论 53
1.6.11　结果与预测 57
第2章　RAM子系统 59
2.1　RAM概述 59
2.2　RAM的层次结构 60
2.3　随机存取存储器 63
2.4　RAM的设计与工作原理 64
2.4.1　内核部分 64
2.4.2　传统DRAM（页面模式的DRAM） 66
2.4.3　DRAM的发展 68
2.4.4　快速页面模式的DRAM（FPM DRAM） 68
2.4.5　存储器时序 69
2.4.6　扩展数据输出DRAM（EDO DRAM） 70
2.4.7　突发式EDO DRAM（BEDO DRAM） 70
2.4.8　同步DRAM（SDRAM） 72
2.4.9　倍速SDRAM（DDR SDRAM）或者SDRAM II 73
2.4.10　直接Rambus DRAM（直接RDRAM） 73
2.4.11　不同存储器类型的比较 75
2.5　存储器与处理器之间的交互操作 76
2.5.1　计算全存取时间 81
2.6　DRAM物理地址到逻辑地址的映射 83
2.7　内存优化操作 84
2.7.1　建议 85
2.7.2　展开循环 86
2.7.3　 消除数据相关性 91
2.7.4　 数据并行处理 94
2.7.5　 优化引用数据结构 96
2.7.6　减小数据结构的尺寸 100
2.7.7　DRAM板块上的数据分布策略 109
2.7.8　规划数据流 115
2.7.9　按字节、双字与四字进行内存处理 121
2.7.10　数据对齐 123
2.7.11　内存访问与计算的组合 132
2.7.12　读写操作的组合 135
2.7.13　只在必要时才访问内存 136
2.7.14　内置C内存处理函数的优化 137
2.7.15　内存处理函数的优化质量 150
2.7.16　C字符串库函数的优化 152
2.7.17　字符串处理函数的质量优化 156
2.7.18　块处理算法的优化 157
2.7.19　大型数组排序的优化 160
2.8　RAM测试问题 165
第3章　高速缓存子系统 168
3.1　SRAM的工作原理 168
3.1.1　历史概况 169
3.1.2　内核 169
3.1.3　触发器的设计 169
3.1.4　逻辑非元件（取反器）的设计 170
3.1.5　SRAM阵列的设计 171
3.1.6　封装接口的设计 172
3.1.7　读写时序图 173
3.1.8　静态存储器的类型 175
3.2　高速缓存的工作原理 175
3.2.1　起源 176
3.2.2　高速缓存的目标与任务 176
3.2.3　高速缓存的组织 179
3.3　高速缓存与存储器存取的优化 196
3.3.1　处理数据的尺寸对性能的影响 196
3.3.2　可执行代码的尺寸对性能的影响 209
3.3.3　数据对齐效率 213
3.3.4　数据在高速缓存板块上的分布 220
3.3.5　使用有限联合数目的高速缓存 226
3.3.6　二维数组的处理 231
3.3.7　写缓冲机制的详细说明 234
3.3.8　新一代x86处理器的高速缓存管理 250
3.3.9　预取机制的实际应用 256
3.3.10　内存拷贝内幕或者Pentium III与Pentium 4的新命令 275
第4章　机器优化 292
4.1　C/C++编译器的比较分析 292
4.1.1　常量表达式 294
4.1.2　代数表达式 296
4.1.3　算术运算 300
4.1.4　分支语句 302
4.1.5　switch运算符 304
4.1.6　循环 307
4.1.7　函数调用 311
4.1.8　变量分布 312
4.1.9　字符串初始化 312
4.1.10　死码 312
4.1.11　常量条件 313
4.1.12　确定优胜者 313
4.2　汇编器与编译器的对决 313
4.2.1　历史回顾——汇编语言使春天永驻 314
4.2.2　评价机器优化质量的指标 315
4.2.3　评价机器优化质量的方法 316
4.2.4　对主要编译器进行比较分析 317
4.2.5　测试结果的讨论 318
4.2.6　机器优化质量的示例 321
4.2.7　用汇编语言创建保护代码 325
4.2.8　用汇编语言编程是一种创造性活动 326
4.2.9　结束语 326
4.2.10　源代码 327

前言
优化概述
0.1　优化的好处
　　现在还值得在优化问题上花时间吗？集中精力学习MFC或者.NET技术不是更好吗？现代计算机的性能不是如此强大甚至连最新操作系统，如Windows XP都不能使它慢下来吗？
　　新一代程序员一直对优化心存疑虑。不过，从一个极端走到另一个极端，并非明智之举。即使最先进的处理器也没有强大到足以应付所有的任务。如果将它们难以完成的任务罗列出来，得到的仍然是一个长长的列表：现实世界中各种各样的物理过程建模、多媒体信息处理、文字识别，等等。哪怕是开发一个高效的数据压缩程序也会面临很多挑战。
　　处理器的性能的确在快速地提升，然而，PC用户对处理器性能的需求增长，也是并驾齐驱的。与早些时候人们情愿启动程序后等待它的运行这种数据处理情形不同的是，现在，大多数用户希望所有的操作能够立即完成或者在几分钟内完成，并且数据处理量也大大增加了。目前，文件的大小动不动就超过了几百兆字节。曾记否，整个硬盘容量尚不及现在硬盘容量的十分之一的那个时代？
　　有什么样的目标就有什么样的手段去达到目标。这种理念决定了本书叙述的方向。因此，读者应将如下的一些建议用于后面的所有优化算法当中去：
1．优化应该尽可能保持与硬件无关，并且对于其他操作系统，是可移植的，而不需要另外的付出或者导致效率的大幅度降低。换句话说，在程序中使用内联汇编语言函数基本上是不可以接受的。最好避免使用那些只有特定编译器才具备的非标准或者扩展语言能力。
2．优化不应该使开发过程（包括测试在内）的劳动强度增加15%以上。比较理想的情况是，所有关键算法都应该以独立库的形式来实现，因为独立库是不需要予以另外处理的。
3．优化算法应该使程序性能的提高不少于20%。本书很少去考虑那些使程序性能提高不足20%的优化方法。全书关注的焦点集中在不需要程序员额外付出就可以使程序性能至少加倍的算法上。尽管似乎显得有点不可信，但这样的算法确实存在！
4．优化应该使代码修改起来毫不费力。许多优化技巧可能会“杀死”程序，因为即使一个细微的修改都可能使优化丧失效能。所有变量都可以在寄存器之间进行仔细的分配，微代码可以实现并行化，任何能够发挥作用的特性都可以使用。但这些措施并不能弥补代码在灵活性方面出现的损失。这类程序的执行速度甚至连一个时钟周期都不能提高，代码的尺寸也不能哪怕减少一个字节。因此，本书将仅仅讨论那些对更改程序结构所引入的变化并不敏感的优化方法。
　　这里要试图证实的关键概念是：普遍认定的购买更新与性能更强的处理器比在优化方面花费时间与精力要好的看法是不对的。此外，优化并不像大多数人想像的那样费劲。例如，本书提供的许多通用方法就不需要对每个任务进行单独调整。书中力图描述一些在系统层次具有可移植性的优化技术，从而避免在没有特殊需要的情况下使用汇编语言。当然，绝对不使用汇编语言也是不可能做什么事情的，特别是在讨论剖分（profiling）技术及机器优化算法的章节中更是这样。不过，作者希望贯穿代码的全部注释会使有汇编语言的地方更容易理解，即使对于没有汇编语言编程经验的读者来说也是如此。
0.2　读者对象
　　本书描述了计算机的各组件之间的交互组织、体系与机制。本书着重从机器代码与数据结构的层次上，讲述了如何进行高效编程，以及各种代码优化技术。
　　该书是为在C/C++语言编程方面具有一定经验的应用程序开发者写的，同时也是为具有一些汇编语言知识的系统程序开发人员写的。不过，书中描述的优化方法并不局限于任何一种高级编程语言。因此，具备C语言知识仅仅对于理解书中给出的源代码是必要的。
　　当然，作者也希望本书能够为计算机硬件开发的专业人员与技术工作者带来一些帮助。本书尽可能详细地描述硬件的操作原理，并且讨论在最常用的计算机组件中存在的瓶颈。
　　书中提供的绝大多数素材都是以作者的经验为基础的。所有信息都经过了仔细的测试与验证。尽管如此，仍然不能保证书中没有错误。（毕竟，“漏洞总是竞相出现的”。）
　　本书的素材主要适用于AMD Athlon以及Intel Pentium II、Pentium III与 Pentium 4微处理器。较早的处理器只是在必要的时候才提到并加以考虑。
0.3　优化基础
　　程序员（即使是训练有素的程序员）都免不了经常不假思索地去与有问题的汇编语言函数较劲。这不是正确的因应之道！正如第4章将要展示的那样，在大多数情况下，机器优化与手工优化之间的差异是可以忽略不计的。除了修饰部分以外，程序通常并没有什么可以优化与提高的。在通常情况下，编译器会给出一个较为理想的结果，因而只做出一点努力并不能使程序的性能提高几个百分点。如果仅仅是在改写一个或者多个汇编语言函数之后，程序的性能才稍有改善的话，那将是非常不幸的事情。时间与精力都浪费掉了，而得到的只是一个遗憾。
　　因此，在进行手工优化之前，有必要确定编译器生成的代码是否真的没有经过优化，以及能够进行何种程度的优化。同样，对现有的潜在性能进行评估也很有好处。不过，走另一个极端而认定编译器总是生成优化代码也是不明智的。所有一切取决于实现的处理算法与高级编程语言上下文环境之间的对应关系如何。有些要用一系列C或者Pascal语言操作符才能实现的任务可以通过单条机器指令来完成。认为编译器会用适当的机器命令取代这组指令，未免显得天真。（与此不同，编译器把每条指令编译成一条或者多条机器指令。）
　　可见，对代码进行优化处理时，需要考虑一些基本的优化规则。
规则一
　　在进行代码优化之前，先要有一个同一代码的可靠的、非优化的版本。这意味着，在开始优化代码之前，一定要确保程序能够正确地运行。
　　在软件开发过程中是不可能生成优化代码的，这样做会实实在在地影响指令的设计。即使仅仅在算法中引入一点点变化，也几乎总会导致对代码进行彻底的修改。因此，在确信用高级编程语言实现的算法能够正确运行之前，切不可启动代码优化过程。并且，如果发现软件的某个地方存在漏洞，那么第一个要怀疑的部分就是经过优化的代码片断。（经过优化的代码基本上不具备可读性，并且不可理解，而调试这样的代码会是一个繁复冗长的过程。）一个没有优化但经过了仔细调试的代码版本会很有帮助：如果用非优化代码取代优化代码而没有产生新的错误，那么意味着软件bug存在于优化代码之中。假如这样做之后，错误依然存在，则需要在其他地方去寻找bug。
规则二
　　应利用算法优化措施，而不是通过提升系统特性来获取最大限度的性能提升。没有什么优化措施可以极大地提高诸如冒泡排序或者线性搜索之类的算法的效率。正确的指令规划及其他的程序设计技巧最多能将程序的性能提高几个百分点。与此不同，实现一个快速排序和折半查找算法会至少将程序的速度提高10 倍，而不管源代码写得粗糙与否。因此，如果程序运行速度显得太慢，应该尽量使用更加高效的算法，而不是去优化一个效率低下的算法。
规则三
　　不要将代码优化与汇编语言实现混为一谈。如果在剖分阶段检测到了程序中的热点（hotspot），并不要急于将它们用汇编语言进行重写。首先要做的是尽量在高级程序设计语言中采取各种可能的步骤：删除消耗资源的算术运算（特别是除法与余数计算）；最大限度地减少分支的数目；用数目更小的迭代操作（译者注：循环语言结构中重复执行的循环体部分称为迭代操作，这部分代码执行一次成为一次迭代）替换循环，等等。在极端情况下，试着换用别的编译器。（不同编译器的代码编译质量往往存在很大的差异。）
规则四
　　在试图用汇编语言重写程序之前，先查看一下编译器生成的汇编代码并估算它的效率。也许，程序性能差不是编译器的责任，可能是由处理器或者内存子系统引起的。对于要进行大量计算的科技应用程序和需要海量内存的图形软件来说，情况尤其如此。简单地将程序转换为汇编语言，并不能提高内存子系统的吞吐量或者使处理器的运算执行得更快。首先，通过编译器生成代码的汇编语言列表（例如，对于Microsoft Visual C++编译器来说，使用/FA命令行选项就可以达到目的）。然后，扫描列表，找出其中诸如MOV EAX,[EBX] \MOV [EBX], EAX之类的严重错误。原则上，改善由编译器生成的代码的性能将比从零开始用汇编语言实现要容易得多。因为前者需要的时间要少得多，而得到的结果却可能相差无几。
规则五
　　如果编译器生成的汇编语言列表虽然显得很不错，但是程序运行起来仍然很慢，就可以考虑将它加载到一个反汇编工具之中去。在这里可能发现很多东西，比如，编译器对跳转指令的存放位置的定位是不准确的，从而可能没有合适地定位跳转指令。通过其倍数为16的地址来对齐跳转指令可以得到最好的性能。将整个循环体放在一个高速缓存行（cache line）（也就是32个字节）中，甚至可以得到更好的结果。不过，这说得太远了点。机器代码优化手段是另外一个不同的主题。我能够给出的最好建议是，不妨去仔细研究一下由顶尖处理器制造商（Intel与AMD）发布的文档资料。
规则六
　　如果可用的处理器指令能够实现比较高效的算法，那么就用不着去管编译器而可以着手去实现汇编语言代码。不过，这种情况是很少见的。再说，我们不是生活在荒岛之上。经过了仔细调试并且性能很好的可用高度优化代码库文件，不下几吨重。如果能够买到一个库文件，那么自己为什么还要去重新开发呢？
规则七
　　在开发汇编语言代码时，不管存在什么样的干扰，都应该给出一个精巧而高效的方案。是的，确实存在一些没有公布的性能、不寻常的样式及其他的诀窍。然而，这些方法的任何一种都不是可移植的、与处理问题无关的或者每个人都清楚的。（老实说，谁能够轻而易举地弄明白自己十年前编写的源代码呢？）我曾经不止一次因为使用自己以往用过的诀窍而搬起石头砸自己的脚。其中，最令人痛苦的事情是，用到的这些诀窍通常并不是必需的；使用它们纯粹是因为要“露一手”。可见，不要忽视对程序进行注释，并且应该将所有的汇编函数存放在一个单独的模块之中。在程序代码中要避免使用内联汇编函数：这些函数很少是可移植的，并且在移植到其他平台或者编译器以后经常会带来负面效果。
　　汇编语言技巧仅仅用在软件版权保护方面才是合理的。不过，这又是另外一个显得非常不同的讨论话题。
0.4　常见的谬误
　　关于优化方面的错误说法为数不少。虽然专业人员大多会对此一笑了之，但是这些说法会对新手造成不利的影响。本节将揭示其中的几个讹传。
讹传1
　　编译器会替用户完成所有的优化任务。
　　认为编译器具有超凡脱俗的能力是毫无根据的。即使是一个具有强大的优化能力的编译器，也仅仅能够对设计良好的代码进行高效的转化。如果源代码残缺不全，没有什么编译器可以更正它的错误。可见，不应该将所有与性能和效率有关的任务都交给编译器去做！一个比较好的做法是协助编译器去完成这些任务。达到此种目的的具体方法需要单独加以讨论，这方面的内容可以在第4章中找到。
讹传2
　　最大限度的效率只有在单纯使用汇编语言编程时才可以得到，用高级语言编程是不可能得到这样的结果的。
　　将程序代码改为汇编指令，很少可以提高程序的性能。用手工优化方式转化高质量的源代码所得到的结果，在性能上只比由优化编译器给出的结果好10%~20%。这个差异虽然是很大的，但是它并没有大到足以消除单纯使用汇编语言进行程序设计所带来的困难与工作强度。
　　第4章提供了这个方面的详细内容，其中包括机器优化与手工优化质量的比较。
讹传3
　　与优化编译器不同，人不可能利用处理器体系方面的所有性能。
　　仅仅只有Intel开发的编译器才能够生成处理器微体系结构认为具有优化性质的代码。第1章（见“VTune实用剖分知识”一节）将给出这方面的实际例子。
　　尽管如此，最新的处理器其实能够优化被传递过来要它进行处理的代码。进行手工优化的企图容易遭到失败：没有什么代码对于现有的处理器体系结构来说是优化的，诸如PII、P4、AMD-K6与Athlon之类的处理器所具有的特性相互之间存在迥然的不同。
　　这方面的例外情形体现在对性能具有苛刻要求的小范围内的特定任务（诸如破译口令字）上。在这些例外当中，手工优化被证明是行之有效的，由此得到的结果比任何编译器都好。
讹传4
　　x86处理器不值得使用，要理解什么是真正的性能就必须使用PowerPC。
　　每种处理器体系结构都有自己的优点与不足。我虽然没有优化过要在PowerPC上运行的任何代码，但我有几个熟人在从事用于PowerPC的优化编译器的开发，他们对其中的一些“特性”感到很失望。
　　x86处理器系列同样具有许多限制与问题。不过，这不能成为程序员编写粗糙的代码而不去改进它的借口。
　　到目前为止，该处理器系列拥有最为复杂的指令系统之一，它为系统程序员提供了几乎不受限制的编程能力。应用程序员甚至想像不出编译器从他们那里剽窃到了哪些经验！

序
译者序
　　时间就是金钱，效率就是生命。这句名言对于程序，尤其是性能至关重要的程序来说，同样一点都不显过分。如何获取良好的程序运行性能，就是代码优化的研究内容。
　　代码优化对于许多程序员而言显得有点神秘，这是由于它涉及软件算法与硬件体系结构等方面的深层知识。对于希望掌握代码优化技术的计算机从业人员来说，要揭开代码优化技术神秘面纱的一条捷径是：阅读一本介绍代码优化技术的好书。Kris Kaspersky撰写的《代码优化：有效使用内存》一书就是这样一本好书。我无意在此为该书做免费的广告（尽管向读者推荐高质量的书籍也是作者或者译者应尽的责任和义务），说它好是由书的内容决定的（当然，是否真好最终要由读者来评判，但我相信读者在仔细阅读并理解了书中的内容之后，定会认为吾言不虚）。
　　本书系统地介绍了各种代码优化编程知识，其内容涵盖关于如何确定程序中消耗CPU时钟最多的热点代码的所谓程序剖分技术与典型剖分工具的实用知识，RAM子系统与高速缓存子系统的工作原理与代码优化知识，以及机器代码优化技术等。该书在透彻介绍各种优化技术原理时，详细给出了典型的代码实例，对性能进行了定量分析。特别是，全书针对各种优化方式的有利与不利之处进行了细致入微的对比分析，使读者可以轻松地选用满足自己应用需要的优化机制。实用、深入、系统与有效是本书在写作上的一大特色。
　　当然，本书的质量是由作者在该领域很高的学术造诣、丰富的开发经验及长期的写作经历等多方面的因素来保证的。Kris Kaspersky是一位技术撰稿人，其文章涉及黑客、反汇编与代码优化技术的各个方面，同时他还是《黑客反汇编揭秘》一书的作者。长期以来，他一直致力于研究与安全和系统程序开发有关的许多课题，这包括编译器开发、优化技术、安全机制研究、实时操作系统内核的创建与反病毒程序的生成等。
　　本书的翻译得到王璐、沈鑫剡、胡勇强、伍红兵、龙瑞、魏涛、汪东、张斌、李炎新等同志的大力协作与帮助，在此一并致谢。
　　由于代码优化涉及的内容十分丰富，相关知识的层次比较深，加之译者水平有限，译文中必定存在疏漏和不当之处，请读者不吝赐教。

译者

出处：蓝色理想
责任编辑：donger