附录C Java编程规则

本附录包含了大量有用的建议，帮助大家进行低级程序设计，并提供了代码编写的一般性指导：

(1) 类名首字母应该大写。字段、方法以及对象（句柄）的首字母应小写。对于所有标识符，其中包含的所有单词都应紧靠在一起，而且大写中间单词的首字母。例如：

ThisIsAClassName

thisIsMethodOrFieldName

若在定义中出现了常数初始化字符，则大写static final基本类型标识符中的所有字母。这样便可标志出它们属于编译期的常数。

Java包（Package）属于一种特殊情况：它们全都是小写字母，即便中间的单词亦是如此。对于域名扩展名称，如com，org，net或者edu等，全部都应小写（这也是Java 1.1和Java 1.2的区别之一）。

(2) 为了常规用途而创建一个类时，请采取“经典形式”，并包含对下述元素的定义：

equals()

hashCode()

toString()

clone()（implement Cloneable）

implement Serializable

(3) 对于自己创建的每一个类，都考虑置入一个main()，其中包含了用于测试那个类的代码。为使用一个项目中的类，我们没必要删除测试代码。若进行了任何形式的改动，可方便地返回测试。这些代码也可作为如何使用类的一个示例使用。

(4) 应将方法设计成简要的、功能性单元，用它描述和实现一个不连续的类接口部分。理想情况下，方法应简明扼要。若长度很大，可考虑通过某种方式将其分割成较短的几个方法。这样做也便于类内代码的重复使用（有些时候，方法必须非常大，但它们仍应只做同样的一件事情）。

(5) 设计一个类时，请设身处地为客户程序员考虑一下（类的使用方法应该是非常明确的）。然后，再设身处地为管理代码的人考虑一下（预计有可能进行哪些形式的修改，想想用什么方法可把它们变得更简单）。

(6) 使类尽可能短小精悍，而且只解决一个特定的问题。下面是对类设计的一些建议：

■一个复杂的开关语句：考虑采用“多形”机制

■数量众多的方法涉及到类型差别极大的操作：考虑用几个类来分别实现

■许多成员变量在特征上有很大的差别：考虑使用几个类

(7) 让一切东西都尽可能地“私有”——private。可使库的某一部分“公共化”（一个方法、类或者一个字段等等），就永远不能把它拿出。若强行拿出，就可能破坏其他人现有的代码，使他们不得不重新编写和设计。若只公布自己必须公布的，就可放心大胆地改变其他任何东西。在多线程环境中，隐私是特别重要的一个因素——只有private字段才能在非同步使用的情况下受到保护。

(8) 谨惕“巨大对象综合症”。对一些习惯于顺序编程思维、且初涉OOP领域的新手，往往喜欢先写一个顺序执行的程序，再把它嵌入一个或两个巨大的对象里。根据编程原理，对象表达的应该是应用程序的概念，而非应用程序本身。

(9) 若不得已进行一些不太雅观的编程，至少应该把那些代码置于一个类的内部。

(10) 任何时候只要发现类与类之间结合得非常紧密，就需要考虑是否采用内部类，从而改善编码及维护工作（参见第14章14.1.2小节的“用内部类改进代码”）。

(11) 尽可能细致地加上注释，并用javadoc注释文档语法生成自己的程序文档。

(12) 避免使用“魔术数字”，这些数字很难与代码很好地配合。如以后需要修改它，无疑会成为一场噩梦，因为根本不知道“100”到底是指“数组大小”还是“其他全然不同的东西”。所以，我们应创建一个常数，并为其使用具有说服力的描述性名称，并在整个程序中都采用常数标识符。这样可使程序更易理解以及更易维护。

(13) 涉及构建器和异常的时候，通常希望重新丢弃在构建器中捕获的任何异常——如果它造成了那个对象的创建失败。这样一来，调用者就不会以为那个对象已正确地创建，从而盲目地继续。

(14) 当客户程序员用完对象以后，若你的类要求进行任何清除工作，可考虑将清除代码置于一个良好定义的方法里，采用类似于cleanup()这样的名字，明确表明自己的用途。除此以外，可在类内放置一个boolean（布尔）标记，指出对象是否已被清除。在类的finalize()方法里，请确定对象已被清除，并已丢弃了从RuntimeException继承的一个类（如果还没有的话），从而指出一个编程错误。在采取象这样的方案之前，请确定finalize()能够在自己的系统中工作（可能需要调用System.runFinalizersOnExit(true)，从而确保这一行为）。

(15) 在一个特定的作用域内，若一个对象必须清除（非由垃圾收集机制处理），请采用下述方法：初始化对象；若成功，则立即进入一个含有finally从句的try块，开始清除工作。

(16) 若在初始化过程中需要覆盖（取消）finalize()，请记住调用super.finalize()（若Object属于我们的直接超类，则无此必要）。在对finalize()进行覆盖的过程中，对super.finalize()的调用应属于最后一个行动，而不应是第一个行动，这样可确保在需要基础类组件的时候它们依然有效。

(17) 创建大小固定的对象集合时，请将它们传输至一个数组（若准备从一个方法里返回这个集合，更应如此操作）。这样一来，我们就可享受到数组在编译期进行类型检查的好处。此外，为使用它们，数组的接收者也许并不需要将对象“造型”到数组里。

(18) 尽量使用interfaces，不要使用abstract类。若已知某样东西准备成为一个基础类，那么第一个选择应是将其变成一个interface（接口）。只有在不得不使用方法定义或者成员变量的时候，才需要将其变成一个abstract（抽象）类。接口主要描述了客户希望做什么事情，而一个类则致力于（或允许）具体的实施细节。

(19) 在构建器内部，只进行那些将对象设为正确状态所需的工作。尽可能地避免调用其他方法，因为那些方法可能被其他人覆盖或取消，从而在构建过程中产生不可预知的结果（参见第7章的详细说明）。

(20) 对象不应只是简单地容纳一些数据；它们的行为也应得到良好的定义。

(21) 在现成类的基础上创建新类时，请首先选择“新建”或“创作”。只有自己的设计要求必须继承时，才应考虑这方面的问题。若在本来允许新建的场合使用了继承，则整个设计会变得没有必要地复杂。

(22) 用继承及方法覆盖来表示行为间的差异，而用字段表示状态间的区别。一个非常极端的例子是通过对不同类的继承来表示颜色，这是绝对应该避免的：应直接使用一个“颜色”字段。

(23) 为避免编程时遇到麻烦，请保证在自己类路径指到的任何地方，每个名字都仅对应一个类。否则，编译器可能先找到同名的另一个类，并报告出错消息。若怀疑自己碰到了类路径问题，请试试在类路径的每一个起点，搜索一下同名的.class文件。

(24) 在Java 1.1 AWT中使用事件“适配器”时，特别容易碰到一个陷阱。若覆盖了某个适配器方法，同时拼写方法没有特别讲究，最后的结果就是新添加一个方法，而不是覆盖现成方法。然而，由于这样做是完全合法的，所以不会从编译器或运行期系统获得任何出错提示——只不过代码的工作就变得不正常了。

(25) 用合理的设计方案消除“伪功能”。也就是说，假若只需要创建类的一个对象，就不要提前限制自己使用应用程序，并加上一条“只生成其中一个”注释。请考虑将其封装成一个“独生子”的形式。若在主程序里有大量散乱的代码，用于创建自己的对象，请考虑采纳一种创造性的方案，将些代码封装起来。

(26) 警惕“分析瘫痪”。请记住，无论如何都要提前了解整个项目的状况，再去考察其中的细节。由于把握了全局，可快速认识自己未知的一些因素，防止在考察细节的时候陷入“死逻辑”中。

(27) 警惕“过早优化”。首先让它运行起来，再考虑变得更快——但只有在自己必须这样做、而且经证实在某部分代码中的确存在一个性能瓶颈的时候，才应进行优化。除非用专门的工具分析瓶颈，否则很有可能是在浪费自己的时间。性能提升的隐含代价是自己的代码变得难于理解，而且难于维护。

(28) 请记住，阅读代码的时间比写代码的时间多得多。思路清晰的设计可获得易于理解的程序，但注释、细致的解释以及一些示例往往具有不可估量的价值。无论对你自己，还是对后来的人，它们都是相当重要的。如对此仍有怀疑，那么请试想自己试图从联机Java文档里找出有用信息时碰到的挫折，这样或许能将你说服。

(29) 如认为自己已进行了良好的分析、设计或者实施，那么请稍微更换一下思维角度。试试邀请一些外来人士——并不一定是专家，但可以是来自本公司其他部门的人。请他们用完全新鲜的眼光考察你的工作，看看是否能找出你一度熟视无睹的问题。采取这种方式，往往能在最适合修改的阶段找出一些关键性的问题，避免产品发行后再解决问题而造成的金钱及精力方面的损失。

(30) 良好的设计能带来最大的回报。简言之，对于一个特定的问题，通常会花较长的时间才能找到一种最恰当的解决方案。但一旦找到了正确的方法，以后的工作就轻松多了，再也不用经历数小时、数天或者数月的痛苦挣扎。我们的努力工作会带来最大的回报（甚至无可估量）。而且由于自己倾注了大量心血，最终获得一个出色的设计方案，成功的快感也是令人心动的。坚持抵制草草完工的诱惑——那样做往往得不偿失。

(31) 可在Web上找到大量的编程参考资源，甚至包括大量新闻组、讨论组、邮寄列表等。下面这个地方提供了大量有益的链接：

http://www.ulb.ac.be/esp/ip-Links/Java/joodcs/mm-WebBiblio.html

附录D 性能

“本附录由Joe Sharp投稿，并获得他的同意在这儿转载。请联系SharpJoe@aol.com”

Java语言特别强调准确性，但可靠的行为要以性能作为代价。这一特点反映在自动收集垃圾、严格的运行期检查、完整的字节码检查以及保守的运行期同步等等方面。对一个解释型的虚拟机来说，由于目前有大量平台可供挑选，所以进一步阻碍了性能的发挥。

“先做完它，再逐步完善。幸好需要改进的地方通常不会太多。”（Steve McConnell的《About performance》[16]）

本附录的宗旨就是指导大家寻找和优化“需要完善的那一部分”。

D.1 基本方法

只有正确和完整地检测了程序后，再可着手解决性能方面的问题：

(1) 在现实环境中检测程序的性能。若符合要求，则目标达到。若不符合，则转到下一步。

(2) 寻找最致命的性能瓶颈。这也许要求一定的技巧，但所有努力都不会白费。如简单地猜测瓶颈所在，并试图进行优化，那么可能是白花时间。

(3) 运用本附录介绍的提速技术，然后返回步骤1。

为使努力不至白费，瓶颈的定位是至关重要的一环。Donald Knuth[9]曾改进过一个程序，那个程序把50％的时间都花在约4％的代码量上。在仅一个工作小时里，他修改了几行代码，使程序的执行速度倍增。此时，若将时间继续投入到剩余代码的修改上，那么只会得不偿失。Knuth在编程界有一句名言：“过早的优化是一切麻烦的根源”（Premature optimization is the root of all evil）。最明智的做法是抑制过早优化的冲动，因为那样做可能遗漏多种有用的编程技术，造成代码更难理解和操控，并需更大的精力进行维护。

D.2 寻找瓶颈

为找出最影响程序性能的瓶颈，可采取下述几种方法：

D.2.1 安插自己的测试代码

插入下述“显式”计时代码，对程序进行评测：

long start = System.currentTimeMillis();

// 要计时的运算代码放在这儿

long time = System.currentTimeMillis() - start;

利用System.out.println()，让一种不常用到的方法将累积时间打印到控制台窗口。由于一旦出错，编译器会将其忽略，所以可用一个“静态最终布尔值”（Static final boolean）打开或关闭计时，使代码能放心留在最终发行的程序里，这样任何时候都可以拿来应急。尽管还可以选用更复杂的评测手段，但若仅仅为了量度一个特定任务的执行时间，这无疑是最简便的方法。

System.currentTimeMillis()返回的时间以千分之一秒（1毫秒）为单位。然而，有些系统的时间精度低于1毫秒（如Windows PC），所以需要重复n次，再将总时间除以n，获得准确的时间。

D.2.2 JDK性能评测[2]

JDK配套提供了一个内建的评测程序，能跟踪花在每个例程上的时间，并将评测结果写入一个文件。不幸的是，JDK评测器并不稳定。它在JDK 1.1.1中能正常工作，但在后续版本中却非常不稳定。

为运行评测程序，请在调用Java解释器的未优化版本时加上-prof选项。例如：

java_g -prof myClass

或加上一个程序片（Applet）：

java_g -prof sun.applet.AppletViewer applet.html

理解评测程序的输出信息并不容易。事实上，在JDK 1.0中，它居然将方法名称截短为30字符。所以可能无法区分出某些方法。然而，若您用的平台确实能支持-prof选项，那么可试试Vladimir Bulatov的“HyperPorf”[3]或者Greg White的“ProfileViewer”来解释一下结果。

D.2.3 特殊工具

如果想随时跟上性能优化工具的潮流，最好的方法就是作一些Web站点的常客。比如由Jonathan Hardwick制作的“Tools for Optimizing Java”（Java优化工具）网站：

http://www.cs.cmu.edu/~jch/java/tools.html

D.2.4 性能评测的技巧

■由于评测时要用到系统时钟，所以当时不要运行其他任何进程或应用程序，以免影响测试结果。

■如对自己的程序进行了修改，并试图（至少在开发平台上）改善它的性能，那么在修改前后应分别测试一下代码的执行时间。

■尽量在完全一致的环境中进行每一次时间测试。

■如果可能，应设计一个不依赖任何用户输入的测试，避免用户的不同反应导致结果出现误差。

D.3 提速方法

现在，关键的性能瓶颈应已隔离出来。接下来，可对其应用两种类型的优化：常规手段以及依赖Java语言。

D.3.1 常规手段

通常，一个有效的提速方法是用更现实的方式重新定义程序。例如，在《Programming Pearls》（编程拾贝）一书中[14]，Bentley利用了一段小说数据描写，它可以生成速度非常快、而且非常精简的拼写检查器，从而介绍了Doug McIlroy对英语语言的表述。除此以外，与其他方法相比，更好的算法也许能带来更大的性能提升——特别是在数据集的尺寸越来越大的时候。欲了解这些常规手段的详情，请参考本附录末尾的“一般书籍”清单。

D.3.2 依赖语言的方法

为进行客观的分析，最好明确掌握各种运算的执行时间。这样一来，得到的结果可独立于当前使用的计算机——通过除以花在本地赋值上的时间，最后得到的就是“标准时间”。

运算 示例 标准时间

本地赋值 i=n; 1.0

实例赋值 this.i=n; 1.2

int增值 i++; 1.5

byte增值 b++; 2.0

short增值 s++; 2.0

float增值 f++; 2.0

double增值 d++; 2.0

空循环 while(true) n++; 2.0

三元表达式 (x<0) ?-x : x 2.2

算术调用 Math.abs(x); 2.5

数组赋值 a[0] = n; 2.7

long增值 l++; 3.5

方法调用 funct(); 5.9

throw或catch异常 try{ throw e; }或catch(e){} 320

同步方法调用 synchMehod(); 570

新建对象 new Object(); 980

新建数组 new int[10]; 3100

通过自己的系统（如我的Pentium 200 Pro，Netscape 3及JDK 1.1.5），这些相对时间向大家揭示出：新建对象和数组会造成最沉重的开销，同步会造成比较沉重的开销，而一次不同步的方法调用会造成适度的开销。参考资源[5]和[6]为大家总结了测量用程序片的Web地址，可到自己的机器上运行它们。

1. 常规修改

下面是加快Java程序关键部分执行速度的一些常规操作建议（注意对比修改前后的测试结果）。

将... 修改成... 理由

接口 抽象类（只需一个父时） 接口的多个继承会妨碍性能的优化

非本地或数组循环变量 本地循环变量 根据前表的耗时比较，一次实例整数赋值的时间是本地整数赋值时间的1.2倍，但数组赋值的时间是本地整数赋值的2.7倍

链接列表（固定尺寸） 保存丢弃的链接项目，或将列表替换成一个循环数组（大致知道尺寸） 每新建一个对象，都相当于本地赋值980次。参考“重复利用对象”（下一节）、Van Wyk[12] p.87以及Bentley[15] p.81

x/2（或2的任意次幂） X>>2（或2的任意次幂） 使用更快的硬件指令

D.3.3 特殊情况

■字串的开销：字串连接运算符+看似简单，但实际需要消耗大量系统资源。编译器可高效地连接字串，但变量字串却要求可观的处理器时间。例如，假设s和t是字串变量：

System.out.println("heading" + s + "trailer" + t);

上述语句要求新建一个StringBuffer（字串缓冲），追加自变量，然后用toString()将结果转换回一个字串。因此，无论磁盘空间还是处理器时间，都会受到严重消耗。若准备追加多个字串，则可考虑直接使用一个字串缓冲——特别是能在一个循环里重复利用它的时候。通过在每次循环里禁止新建一个字串缓冲，可节省980单位的对象创建时间（如前所述）。利用substring()以及其他字串方法，可进一步地改善性能。如果可行，字符数组的速度甚至能够更快。也要注意由于同步的关系，所以StringTokenizer会造成较大的开销。

■同步：在JDK解释器中，调用同步方法通常会比调用不同步方法慢10倍。经JIT编译器处理后，这一性能上的差距提升到50到100倍（注意前表总结的时间显示出要慢97倍）。所以要尽可能避免使用同步方法——若不能避免，方法的同步也要比代码块的同步稍快一些。

■重复利用对象：要花很长的时间来新建一个对象（根据前表总结的时间，对象的新建时间是赋值时间的980倍，而新建一个小数组的时间是赋值时间的3100倍）。因此，最明智的做法是保存和更新老对象的字段，而不是创建一个新对象。例如，不要在自己的paint()方法中新建一个Font对象。相反，应将其声明成实例对象，再初始化一次。在这以后，可在paint()里需要的时候随时进行更新。参见Bentley编著的《编程拾贝》，p.81[15]。

■异常：只有在不正常的情况下，才应放弃异常处理模块。什么才叫“不正常”呢？这通常是指程序遇到了问题，而这一般是不愿见到的，所以性能不再成为优先考虑的目标。进行优化时，将小的“try-catch”块合并到一起。由于这些块将代码分割成小的、各自独立的片断，所以会妨碍编译器进行优化。另一方面，若过份热衷于删除异常处理模块，也可能造成代码健壮程度的下降。

■散列处理：首先，Java 1.0和1.1的标准“散列表”（Hashtable）类需要造型以及特别消耗系统资源的同步处理（570单位的赋值时间）。其次，早期的JDK库不能自动决定最佳的表格尺寸。最后，散列函数应针对实际使用项（Key）的特征设计。考虑到所有这些原因，我们可特别设计一个散列类，令其与特定的应用程序配合，从而改善常规散列表的性能。注意Java 1.2集合库的散列映射（HashMap）具有更大的灵活性，而且不会自动同步。

■方法内嵌：只有在方法属于final（最终）、private（专用）或static（静态）的情况下，Java编译器才能内嵌这个方法。而且某些情况下，还要求它绝对不可以有局部变量。若代码花大量时间调用一个不含上述任何属性的方法，那么请考虑为其编写一个“final”版本。

■I/O：应尽可能使用缓冲。否则，最终也许就是一次仅输入／输出一个字节的恶果。注意JDK 1.0的I/O类采用了大量同步措施，所以若使用象readFully()这样的一个“大批量”调用，然后由自己解释数据，就可获得更佳的性能。也要注意Java 1.1的“reader”和“writer”类已针对性能进行了优化。

■造型和实例：造型会耗去2到200个单位的赋值时间。开销更大的甚至要求上溯继承（遗传）结构。其他高代价的操作会损失和恢复更低层结构的能力。

■图形：利用剪切技术，减少在repaint()中的工作量；倍增缓冲区，提高接收速度；同时利用图形压缩技术，缩短下载时间。来自JavaWorld的“Java Applets”以及来自Sun的“Performing Animation”是两个很好的教程。请记着使用最贴切的命令。例如，为根据一系列点画一个多边形，和drawLine()相比，drawPolygon()的速度要快得多。如必须画一条单像素粗细的直线，drawLine(x,y,x,y)的速度比fillRect(x,y,1,1)快。

■使用API类：尽量使用来自Java API的类，因为它们本身已针对机器的性能进行了优化。这是用Java难于达到的。比如在复制任意长度的一个数组时，arraryCopy()比使用循环的速度快得多。

■替换API类：有些时候，API类提供了比我们希望更多的功能，相应的执行时间也会增加。因此，可定做特别的版本，让它做更少的事情，但可更快地运行。例如，假定一个应用程序需要一个容器来保存大量数组。为加快执行速度，可将原来的Vector（矢量）替换成更快的动态对象数组。

1. 其他建议

■将重复的常数计算移至关键循环之外——比如计算固定长度缓冲区的buffer.length。

■static final（静态最终）常数有助于编译器优化程序。

■实现固定长度的循环。

■使用javac的优化选项：-O。它通过内嵌static，final以及private方法，从而优化编译过的代码。注意类的长度可能会增加（只对JDK 1.1而言——更早的版本也许不能执行字节查证）。新型的“Just-in-time”（JIT）编译器会动态加速代码。

■尽可能地将计数减至0——这使用了一个特殊的JVM字节码。

D.4 参考资源

D.4.1 性能工具

[1] 运行于Pentium Pro 200，Netscape 3.0，JDK 1.1.4的MicroBenchmark（参见下面的参考资源[5]）

[2] Sun的Java文档页——JDK Java解释器主题：

http://java.sun.com/products/JDK/tools/win32/java.html

[3] Vladimir Bulatov的HyperProf

http://www.physics.orst.edu/~bulatov/HyperProf

[4] Greg White的ProfileViewer

http://www.inetmi.com/~gwhi/ProfileViewer/ProfileViewer.html

D.4.2 Web站点

[5] 对于Java代码的优化主题，最出色的在线参考资源是Jonathan Hardwick的“Java Optimization”网站：

http://www.cs.cmu.edu/~jch/java/optimization.html

“Java优化工具”主页：

http://www.cs.cmu.edu/~jch/java/tools.html

以及“Java Microbenchmarks”（有一个45秒钟的评测过程）：

http://www.cs.cmu.edu/~jch/java/benchmarks.html

D.4.3 文章

[6] “Make Java fast:Optimize! How to get the greatest performanceout of your code through low-level optimizations in Java”（让Java更快：优化！如何通过在Java中的低级优化，使代码发挥最出色的性能）。作者：Doug Bell。网址：

http://www.javaworld.com/javaworld/jw-04-1997/jw-04-optimize.html

（含一个全面的性能评测程序片，有详尽注释）

[7] “Java Optimization Resources”（Java优化资源）

http://www.cs.cmu.edu/~jch/java/resources.html

[8] “Optimizing Java for Speed”（优化Java，提高速度）：

http://www.cs.cmu.edu/~jch/java/speed.html

[9] “An Empirical Study of FORTRAN Programs”（FORTRAN程序实战解析）。作者：Donald Knuth。1971年出版。第1卷，p.105-33，“软件——实践和练习”。

[10] “Building High-Performance Applications and Servers in Java:An Experiential Study”。作者:Jimmy Nguyen，Michael Fraenkel，RichardRedpath，Binh Q. Nguyen以及Sandeep K. Singhal。IBM T.J. Watson ResearchCenter,IBM Software Solutions。

http://www.ibm.com/java/education/javahipr.html

D.4.4 Java专业书籍

[11] 《Advanced Java，Idioms，Pitfalls，Styles, and Programming Tips》。作者：Chris Laffra。Prentice Hall 1997年出版（Java 1.0）。第11章第20小节。

D.4.5 一般书籍

[12] 《Data Structures and C Programs》（数据结构和C程序）。作者：J.Van Wyk。Addison-Wesly 1998年出版。

[13] 《Writing Efficient Programs》（编写有效的程序）。作者：Jon Bentley。Prentice Hall 1982年出版。特别参考p.110和p.145-151。

[14] 《More Programming Pearls》（编程拾贝第二版）。作者：JonBentley。“Association for Computing Machinery”，1998年2月。

[15] 《Programming Pearls》（编程拾贝）。作者：Jone Bentley。Addison-Wesley 1989年出版。第2部分强调了常规的性能改善问题。 [16] 《Code Complete:A Practical Handbook of Software Construction》（完整代码索引：实用软件开发手册）。作者：Steve McConnell。Microsoft出版社1993年出版，第9章。

[17] 《Object-Oriented System Development》（面向对象系统的开发）。作者：Champeaux，Lea和Faure。第25章。

[18] 《The Art of Programming》（编程艺术）。作者：Donald Knuth。第1卷“基本算法第3版”；第3卷“排序和搜索第2版”。Addison-Wesley出版。这是有关程序算法的一本百科全书。

[19] 《Algorithms in C:Fundammentals,Data Structures, Sorting,Searching》（C算法：基础、数据结构、排序、搜索）第3版。作者：RobertSedgewick。Addison-Wesley 1997年出版。作者是Knuth的学生。这是专门讨论几种语言的七个版本之一。对算法进行了深入浅出的解释。

附录E 关于垃圾收集的一些话

“很难相信Java居然能和C++一样快，甚至还能更快一些。”

据我自己的实践，这种说法确实成立。然而，我也发现许多关于速度的怀疑都来自一些早期的实现方式。由于这些方式并非特别有效，所以没有一个模型可供参考，不能解释Java速度快的原因。

我之所以想到速度，部分原因是由于C++模型。C++将自己的主要精力放在编译期间“静态”发生的所有事情上，所以程序的运行期版本非常短小和快速。C++也直接建立在C模型的基础上（主要为了向后兼容），但有时仅仅由于它在C中能按特定的方式工作，所以也是C++中最方便的一种方法。最重要的一种情况是C和C++对内存的管理方式，它是某些人觉得Java速度肯定慢的重要依据：在Java中，所有对象都必须在内存“堆”里创建。

而在C++中，对象是在堆栈中创建的。这样可达到更快的速度，因为当我们进入一个特定的作用域时，堆栈指针会向下移动一个单位，为那个作用域内创建的、以堆栈为基础的所有对象分配存储空间。而当我们离开作用域的时候（调用完毕所有局部构建器后），堆栈指针会向上移动一个单位。然而，在C++里创建“内存堆”（Heap）对象通常会慢得多，因为它建立在C的内存堆基础上。这种内存堆实际是一个大的内存池，要求必须进行再循环（再生）。在C++里调用delete以后，释放的内存会在堆里留下一个洞，所以再调用new的时候，存储分配机制必须进行某种形式的搜索，使对象的存储与堆内任何现成的洞相配，否则就会很快用光堆的存储空间。之所以内存堆的分配会在C++里对性能造成如此重大的性能影响，对可用内存的搜索正是一个重要的原因。所以创建基于堆栈的对象要快得多。

同样地，由于C++如此多的工作都在编译期间进行，所以必须考虑这方面的因素。但在Java的某些地方，事情的发生却要显得“动态”得多，它会改变模型。创建对象的时候，垃圾收集器的使用对于提高对象创建的速度产生了显著的影响。从表面上看，这种说法似乎有些奇怪——存储空间的释放会对存储空间的分配造成影响，但它正是JVM采取的重要手段之一，这意味着在Java中为堆对象分配存储空间几乎能达到与C++中在堆栈里创建存储空间一样快的速度。

可将C++的堆（以及更慢的Java堆）想象成一个庭院，每个对象都拥有自己的一块地皮。在以后的某个时间，这种“不动产”会被抛弃，而且必须再生。但在某些JVM里，Java堆的工作方式却是颇有不同的。它更象一条传送带：每次分配了一个新对象后，都会朝前移动。这意味着对象存储空间的分配可以达到非常快的速度。“堆指针”简单地向前移至处女地，所以它与C++的堆栈分配方式几乎是完全相同的（当然，在数据记录上会多花一些开销，但要比搜索存储空间快多了）。

现在，大家可能注意到了堆事实并非一条传送带。如按那种方式对待它，最终就要求进行大量的页交换（这对性能的发挥会产生巨大干扰），这样终究会用光内存，出现内存分页错误。所以这儿必须采取一个技巧，那就是著名的“垃圾收集器”。它在收集“垃圾”的同时，也负责压缩堆里的所有对象，将“堆指针”移至尽可能靠近传送带开头的地方，远离发生（内存）分页错误的地点。垃圾收集器会重新安排所有东西，使其成为一个高速、无限自由的堆模型，同时游刃有余地分配存储空间。

为真正掌握它的工作原理，我们首先需要理解不同垃圾收集器（GC）采取的工作方案。一种简单、但速度较慢的GC技术是引用计数。这意味着每个对象都包含了一个引用计数器。每当一个句柄同一个对象连接起来时，引用计数器就会增值。每当一个句柄超出自己的作用域，或者设为null时，引用计数就会减值。这样一来，只要程序处于运行状态，就需要连续进行引用计数管理——尽管这种管理本身的开销比较少。垃圾收集器会在整个对象列表中移动巡视，一旦它发现其中一个引用计数成为0，就释放它占据的存储空间。但这样做也有一个缺点：若对象相互之间进行循环引用，那么即使引用计数不是0，仍有可能属于应收掉的“垃圾”。为了找出这种自引用的组，要求垃圾收集器进行大量额外的工作。引用计数属于垃圾收集的一种类型，但它看起来并不适合在所有JVM方案中采用。

在速度更快的方案里，垃圾收集并不建立在引用计数的基础上。相反，它们基于这样一个原理：所有非死锁的对象最终都肯定能回溯至一个句柄，该句柄要么存在于堆栈中，要么存在于静态存储空间。这个回溯链可能经历了几层对象。所以，如果从堆栈和静态存储区域开始，并经历所有句柄，就能找出所有活动的对象。对于自己找到的每个句柄，都必须跟踪到它指向的那个对象，然后跟随那个对象中的所有句柄，“跟踪追击”到它们指向的对象……等等，直到遍历了从堆栈或静态存储区域中的句柄发起的整个链接网路为止。中途移经的每个对象都必须仍处于活动状态。注意对于那些特殊的自引用组，并不会出现前述的问题。由于它们根本找不到，所以会自动当作垃圾处理。

在这里阐述的方法中，JVM采用一种“自适应”的垃圾收集方案。对于它找到的那些活动对象，具体采取的操作取决于当前正在使用的是什么变体。其中一个变体是“停止和复制”。这意味着由于一些不久之后就会非常明显的原因，程序首先会停止运行（并非一种后台收集方案）。随后，已找到的每个活动对象都会从一个内存堆复制到另一个，留下所有的垃圾。除此以外，随着对象复制到新堆，它们会一个接一个地聚焦在一起。这样可使新堆显得更加紧凑（并使新的存储区域可以简单地抽离末尾，就象前面讲述的那样）。

当然，将一个对象从一处挪到另一处时，指向那个对象的所有句柄（引用）都必须改变。对于那些通过跟踪内存堆的对象而获得的句柄，以及那些静态存储区域，都可以立即改变。但在“遍历”过程中，还有可能遇到指向这个对象的其他句柄。一旦发现这个问题，就当即进行修正（可想象一个散列表将老地址映射成新地址）。

有两方面的问题使复制收集器显得效率低下。第一个问题是我们拥有两个堆，所有内存都在这两个独立的堆内来回移动，要求付出的管理量是实际需要的两倍。为解决这个问题，有些JVM根据需要分配内存堆，并将一个堆简单地复制到另一个。

第二个问题是复制。随着程序变得越来越“健壮”，它几乎不产生或产生很少的垃圾。尽管如此，一个副本收集器仍会将所有内存从一处复制到另一处，这显得非常浪费。为避免这个问题，有些JVM能侦测是否没有产生新的垃圾，并随即改换另一种方案（这便是“自适应”的缘由）。另一种方案叫作“标记和清除”，Sun公司的JVM一直采用的都是这种方案。对于常规性的应用，标记和清除显得非常慢，但一旦知道自己不产生垃圾，或者只产生很少的垃圾，它的速度就会非常快。

标记和清除采用相同的逻辑：从堆栈和静态存储区域开始，并跟踪所有句柄，寻找活动对象。然而，每次发现一个活动对象的时候，就会设置一个标记，为那个对象作上“记号”。但此时尚不收集那个对象。只有在标记过程结束，清除过程才正式开始。在清除过程中，死锁的对象会被释放然而，不会进行任何形式的复制，所以假若收集器决定压缩一个断续的内存堆，它通过移动周围的对象来实现。

“停止和复制”向我们表明这种类型的垃圾收集并不是在后台进行的；相反，一旦发生垃圾收集，程序就会停止运行。在Sun公司的文档库中，可发现许多地方都将垃圾收集定义成一种低优先级的后台进程，但它只是一种理论上的实验，实际根本不能工作。在实际应用中，Sun的垃圾收集器会在内存减少时运行。除此以外，“标记和清除”也要求程序停止运行。

正如早先指出的那样，在这里介绍的JVM中，内存是按大块分配的。若分配一个大块头对象，它会获得自己的内存块。严格的“停止和复制”要求在释放旧堆之前，将每个活动的对象从源堆复制到一个新堆，此时会涉及大量的内存转换工作。通过内存块，垃圾收集器通常可利用死块复制对象，就象它进行收集时那样。每个块都有一个生成计数，用于跟踪它是否依然“存活”。通常，只有自上次垃圾收集以来创建的块才会得到压缩；对于其他所有块，如果已从其他某些地方进行了引用，那么生成计数都会溢出。这是许多短期的、临时的对象经常遇到的情况。会周期性地进行一次完整清除工作——大块头的对象仍未复制（只是让它们的生成计数溢出），而那些包含了小对象的块会进行复制和压缩。JVM会监视垃圾收集器的效率，如果由于所有对象都属于长期对象，造成垃圾收集成为浪费时间的一个过程，就会切换到“标记和清除”方案。类似地，JVM会跟踪监视成功的“标记与清除”工作，若内存堆变得越来越“散乱”，就会换回“停止和复制”方案。“自定义”的说法就是从这种行为来的，我们将其最后总结为：“根据情况，自动转换停止和复制／标记和清除这两种模式”。

JVM还采用了其他许多加速方案。其中一个特别重要的涉及装载器以及JIT编译器。若必须装载一个类（通常是我们首次想创建那个类的一个对象时），会找到.class文件，并将那个类的字节码送入内存。此时，一个方法是用JIT编译所有代码，但这样做有两方面的缺点：它会花更多的时间，若与程序的运行时间综合考虑，编译时间还有可能更长；而且它增大了执行文件的长度（字节码比扩展过的JIT代码精简得多），这有可能造成内存页交换，从而显著放慢一个程序的执行速度。另一种替代办法是：除非确有必要，否则不经JIT编译。这样一来，那些根本不会执行的代码就可能永远得不到JIT的编译。

由于JVM对浏览器来说是外置的，大家可能希望在使用浏览器的时候从一些JVM的速度提高中获得好处。但非常不幸，JVM目前不能与不同的浏览器进行沟通。为发挥一种特定JVM的潜力，要么使用内建了那种JVM的浏览器，要么只有运行独立的Java应用程序。