Rope:理论与实践

为何以及何时使用 Ropes for Java 操纵字符串

Java™语言默认的 StringStringBuilder类很难支撑起操纵大量字符串的系统。rope 数据结构可能是更好的替代品。这篇文章介绍 Ropes for Java,这是针对 Java 平台的 rope 实现;本文还将研究性能问题,并提供一些有效使用 rope 库的指导。

Amin Ahmad (amin.ahmad@gmail.com), 独立顾问, 软通动力信息技术有限公司

Amin Ahmad 是独立顾问,是 Ahmadsoft, LLC 的总裁。他有 7 年以上的 Java 咨询经验,主要关注向客户提供高性能的企业级 Java 系统。



2008 年 3 月 11 日

rope 数据结构表示不能修改的字符序列,与 Java 的 String非常像。但是 ropes 效率奇高的字符串变换操作使得它与 String及其同一体系的可修改的 StringBufferStringBuilder大不相同,非常适合那些执行繁重字符串操纵的应用程序,尤其在多线程环境下更是如此。

简要概括过 rope 数据结构之后,本文将介绍 rope 在 Java 平台上的实现 —— Ropes for Java。然后将在 Java 平台上对 StringStringBuffer和 Ropes for Java Rope类进行测评;考察一些特殊的性能问题;并讨论什么时候应该以及什么时候不应该在应用程序中使用 rope。

Rope:概述

一个 rope代表一个不能修改的字符序列。rope 的 长度就是序列中字符的个数。多数字符串表示都将字符串连续地保存在内存中。rope 的关键特点就是它突破了这个限制,允许一个 rope 的各个片断离散地存放,并通过 连接节点(concatenation node)连接它们。这种设计使得 rope 节点的连接操作比 Java String的连接操作更快。String版本的连接操作要求将需要连接的两个字符串复制到新位置,这是一种 O(n)操作。rope 版本的连接操作则只是创建一个新的连接节点,这是个 O(1)操作。(如果不熟悉 “大 O” 符号,请参阅 参考资料获得相关说明的链接。)

图 1 演示了两种字符串的表示方法。在左侧的表示方法中,字符放在连续的内存位置内。Java 的字符串使用这种表示方式。在右侧的表示方式中,离散的字符串通过连接节点组合在一起。

图 1. 字符串的两种表示方式
字符串的两种表示方式

Rope 实现通常也将延迟对大型子串操作的求值,它的作法是引入 子串节点。使用子串节点能够将获取长度为 n的子串的时间从 O(n)降低到 O(log n),通常会减到 O(1)。需要指出的是,Java 的 String由于是不可修改的,所以子串操作的时间是恒定的,但 StringBuilder并不是这样。

扁平 rope(flat rope)—没有连接节点或子串节点 —的 深度(depth)为 1。有连接和子串的 rope 的深度比它们所拥有的最深节点的深度大 1。

Rope 有两项开销是使用连续字符的字符串表达方式所没有的。第一个开销就是必须遍历子串和连接节点的上层结构(superstructure)才能到达指定的字符。而且,这个树形上层结构必须尽可能保持均衡,以便将遍历的次数降到最少,这意味着 rope 需要偶而进行重新均衡的操作,以保持良好的读取性能。即使 rope 的均衡很好,获取指定位置的字符也是个 O(log n)操作,其中 n是 rope 包含的连接和子串节点的个数。(为了方便,可以用 rope 的长度代替 n,因为长度总是比 rope 中的子串和连接节点的个数大。)

幸运的是,rope 的重新均衡操作非常迅速,至于应该何时进行重新均衡的决策也能够自动制定,例如通过比较 rope 的长度和深度来决定。而且,在多数数据处理例程中,都需要对 rope 字符进行顺序访问,在这种情况下,rope 的迭代器能够提供分摊的 O(1) 访问速度。

表 1 比较了一些常见的字符串操作在 rope 和 Java String上预计的运行时间。

表 1. 常见字符串操作的预计运行时间
操作RopeJava String
连接O(1)O(n
子串O(1)O(1)
检索字符O(log nO(1)
顺序检索所有字符(每个字符的开销)O(1)O(1)

Ropes for Java 简介

内存问题

Java 代码中耗时恒定的子串实现会引起内存问题,因为子串引用会阻止初始字符串被进行垃圾搜集。RopeString都为此问题所困扰。

Ropes for Java 是 rope 数据结构在 java 平台上的高质量实现(请参阅 参考资料)。它进行了广泛的优化,有助于提供全面的优秀性能和内存使用。这一节将解释如何将 rope 集成进 Java 应用程序,并比较 rope 与 StringStringBuffer的性能。

Ropes for Java 实现只向客户机公开了一个类:RopeRope实例可以用 Rope.BUILDER工厂构建器从任意 CharSequence上创建。

清单 1 显示了如何创建 rope。

清单 1. 创建 rope
 Rope r = Rope.BUILDER.build("Hello World");

Rope公开了一组操作方法,包括执行以下操作的方法:

  • 附加另一个字符序列
  • 删除子序列
  • 将另一个字符序列插入 rope

请记住,同 String一样,上面的每种变换都返回一个新 rope;原来的 rope 保持不变。清单 2 演示了其中一些操作。

清单 2. Rope 变换
 Rope r = Rope.BUILDER.build("Hello World"); 
 r = r.append("!");  // r is now "Hello World!"
 r = r.delete(0,6);  // r is now "World!"

有效的 rope

rope 上的迭代需要稍加注意。在查看了清单 3 的两个代码块之后,可以看出哪块代码执行得更好。

清单 3. 在 rope 上迭代的两种技术
 //Technique 1 
 final Rope r=some initialization code; 
 for (int j=0; j<r.length(); ++j) 
    result+=r.charAt(j); 

 //Technique 2 
 final Rope r=some initialization code; 
 for (final char c: r) 
    result+=c;

返回 rope 内任意位置字符的操作是个 O(log n)操作。但是,由于每个字符上都使用 charAt,清单 3 中第一个代码块花了 n倍的 O(log n)查询时间。第二个代码块使用的是 Iterator,应该比第一块执行得快一些。表 2 归纳了使用这两种方法在长度为 10,690,488 的 rope 上迭代的性能。为了比较,表 2 还包含了 StringStringBuffer的时间。

表 2. 复杂 rope 迭代的性能
技术时间(单位:纳秒)
String69,809,420
StringBuffer251,652,393
Rope.charAt79,441,772,895
Rope.iterator1,910,836,551

用来得到表 2 中符合预期的结果的 rope,是通过对初始字符串执行一系列复杂的变换之后创建的。但是,如果直接从字符序列创建这个 rope 而不进行变换,那么性能数字会产生较大的变化。表 3 比较了两种方法的性能。这次是在一个包含 182,029 个字符的 rope 上迭代,这次的 rope 是直接用包含 Project Gutenberg 版查理斯·狄更斯 圣诞欢歌的字符数组初始化的。

表 3. Rope 迭代的性能
技术时间(单位:纳秒)
String602,162
StringBuffer2,259,917
Rope.charAt462,904
Rope.iterator3,466,047

如何用我前面的理论讨论解释这一性能逆转呢? rope 的构建是个关键因素:当直接使用底层的 CharacterSequence或字符数组构建 rope 时,它只有一个简单的结构,里面包含一个扁平 rope。因为这个 rope 不包含连接或子串节点,所以字符查询操作要么直接委托给底层序列的 charAt方法(在 CharacterSequence的情况下),要么包含进行数组查询(在数组的情况下)。扁平 rope 的 Rope.charAt性能与底层表示的 chatAt 性能匹配,通常是 O(1);所以性能是不同的。

聪明的读者可能想知道既然大家都提供 0(1)的访问时间,为什么 charAt会比迭代器快 7 倍。这个区别是因为在 Java 语言中,Iterator必须返回 Object。而 charAt实现直接返回 char原语,迭代器实现必须将每个 char装箱为一个 Character对象。自动装箱可能消除了原语装箱在语法上的麻烦,但是不能消除性能上的损失。

最后,非常明显的是:Rope.charAt的性能比 String.charAt的性能好。原因是 Rope使用专门的类来表示延迟子串(lazy substring),因此使普通 rope 的 charAt的实现保持简单。对比之下,Java SE 的 String实现使用同一个类表示常规字符串和延迟子串,因此多多少少将 charAt的逻辑弄得复杂起来,所以在迭代常规字符串期间增加了少量性能开支。

在讨论 rope 上的正则表达式搜索性能的优化时,还会提到 Rope 迭代。

用 Rope.write 对输出进行优化

在某种程度上,多数 rope 实例都必须写入到某些位置,通常写到一个流内。不幸的是,将对象写入流就要调用对象的 toString方法。这种序列化方式强行在写入一个字符之前在内存中建立整个对象的字符串表示,对于大型对象来说,这是个非常大的性能拖累。Ropes for Java 设计的时候就考虑了大型的字符串对象,所以它提供了更好的方式。

为了提高性能,Rope引入了一个 write 方法,接受一个 Writer和一个范围说明,然后将 rope 的指定范围的字符写到 writer。这样就节省了用 rope 构建 String的时间和内存开支,对于大型 rope 来说,这种开支是相当巨大的。清单 4 显示了 rope 输出的标准方式和增强方式。

清单 4. Rope输出的两种方式
 out.write(rope); 
 rope.write(out);

表 4 包含的测评结果是将一个长度为 10,690,488、深度为 65 的 rope 写入一个由内存缓冲区支持的流的结果。请注意,只显示了节省的时间,但是在临时分配的堆空间上的节省也非常巨大。

表 4. Rope 输出的性能
技术时间(单位:纳秒)
out.write75,136,884
rope.write13,591,023

变换性能测评

Rope 的变换从理论上要比使用连续字符的字符串表示方式快得多。但反过来,正如所看到的,rope 的迭代变慢了。在这一节,将看到 Ropes for Java 和 StringStringBuffer进行变换操作的性能测评比较。

全部测试都用 Project Gutenberg 版本的电子书 圣诞欢歌初始化(182,029 个字节),并对其连续应用一系列变换。在多数情况下,变换的数量在 20 到 480 的范围内变动,以便演示数据结构缩放的效果。(图 2、3、4 将变换的数量称为 计划长度(plan length)。)每个测试执行了七次,并使用中间结果。

插入性能测评

在插入测评中,从前一次迭代的输出中随机选择一个子串,然后插入到字符串的随机位置。图 2 显示了测评的结果。

图 2. 插入性能测评结果
插入性能测评结果

StringStringBuffer来说,完成测评所需要的时间随着计划长度的增加呈指数级增长。相比之下,Rope 则执行得极好。

附加字符串性能评测

这个测评的方法是,从输入字符串中选取随机范围的字符附加到它本身。这个测试的有趣之处在于:StringBuffer正是为了执行快速附加而优化的。图 3 显示了这个测评的结果。

图 3. 附加字符串性能测评结果
附加字符串性能测评结果

不幸的是,图 3 的视图显示 String的性能非常糟糕。但是,如预期所料,StringBuffer的性能非常好。

图 4 从比较中撤出 String的结果,调整了图表的比例,更清楚地显示了 RopeStringBuffer性能的对比。

图 4. 附加字符串性能对比结果,不包括 String
附加字符串性能对比结果

提示:Rope 是不可修改的

Rope类被设计成不可修改,这意味着 mutator 函数永远不会修改原来的 Rope实例,而是返回一个修改后的副本。不可修改有许多好处,第一条好处就是不用考虑多线程环境就能共享 Rope的实例,从而简化了程序的逻辑。

Ropes for Java 从底层字符序列构造 rope。因为 CharSequence只是个接口,所以在构造的时候就有很多灵活性:可以从各种来源构造 rope,包括磁盘文件、内存缓冲区、远程服务器上的文档。但是,与 String不同的是(String 的不可修改是得到保证的),CharSequence对于它的实现没有这类限制。所以要由应用程序开发人员自己负责确保用来构建 rope 的底层字符序列在 rope 实例的生命周期期间不被修改。

图 4 显示了图 3 中不太明显的 RopeStringBuffer之间的巨大区别。Rope很少能突破 x 轴。但是真正有趣的是 StringBuffer的图 —骤然上升后保持稳定上升,而不是平滑地上升。(作为练习,在阅读下一段之前请试着解释一下原因。)

原因与 StringBuffer的空间分配方式有关。它们在其内部数组的末尾分配额外的空间,以便有效地附加字符。但是在空间用尽之后,就必须分配全新的数组,并将所有数据复制到新数组。新数组一般根据当前长度调整大小。随着计划长度的增加,生成的 StringBuffer的长度也会增加。随着逐渐到达重新设置大小的阈值,花费的时间也随着额外的重新设置大小和复制而骤升。然后下几个计划长度的性能稳定期(即缓慢提升的时间)也逐渐升高。因为每个计划项增加的字符串长度总数大体相同,所以随后的稳定期比例可以作为重新设置底层数组大小的参考指标。根据这些结果,可以准确地估算出这个 StringBuffer实现大约在 1.5 左右。

结果小结

迄今为止,已经用图表展示了 RopeStringStringBuffer之间的性能差异。表 5 提供了所有字符变换测评的计时结果,使用了 480 項计划长度。

表 5. 480 项计划的变换时间中间值,以及删除结果
变换 / 数据结构时间(单位:纳秒)
插入 
String18,447,562,195
StringBuffer6,540,357,890
Rope31,571,989
在前部添加 
String22,730,410,698
StringBuffer6,251,045,63
Rope57,748,641
在后面添加 
String23,984,100,264
StringBuffer169,927,944
Rope1,532,799
删除(从初始文本中删除 230 个随机范围) 
String162,563,010
StringBuffer10,422,938
Rope865,154

关于测评程序的链接请参阅 参考资料。我建议您在自己的平台上运行测评程序以检验本文给出的结果。


正则表达式的性能优化

正则表达式在 JDK 1.4 版本中引入,是许多应用程序中广泛使用的一个功能。所以,正则表达式在 rope 中执行良好至关重要。在 Java 语言中,正则表达式用 Pattern表示。要将 PatternCharSequence的区域匹配,要使用模式实例构建 Matcher对象,将 CharSequence作为参数传递给 Matcher。

操纵 CharSequence可为 Java 的正则表达式库提供极佳的灵活性,但也带来了一个严重的缺陷。CharSequence只提供了一个方法来访问它的字符:charAt(x)。就像我在概述一节中提到过的,在拥有许多内部节点的 rope 上随机访问字符的时间大约为 O(log n),所以遍历时间为 O(nlog n)。为了演示这个缺陷带来的问题,我测评了在长度为 10,690,488 的字符串中寻找模式 “Crachit*” 的所有实例所花费的时间。所用的 rope 是使用插入测评的同一个变换序列构建的,深度为 65。表 6 显示了测评的结果。

表 6. 正则表达式搜索时间
技术时间(单位:纳秒)
String75,286,078
StringBuffer86,083,830
Rope12,507,367,218
重新均衡后的 Rope2,628,889,679

显然,Rope的匹配性能很差。(明确地讲,对有许多内部节点的 Rope是这样。对于扁平 rope,性能几乎与底层字符表示的性能相同。)即使在显式地均衡过 Rope之后,虽然匹配快了 3.5 倍,Rope的性能还是没有达到与 StringStringBuffer相同的水平。

为了改进这种情况,Matcher应该而且能够利用 Rope迭代器提供的更快的 O(1)访问时间。为了掌握这种方法,首先需要理解 Matcher到其 CharSequence的访问模式。

正则表达式匹配最常见的场景是从字符序列的某个点上开始,向前移动,直到找到所有匹配,并到达序列末尾为止。在这个场景中,匹配器主要是向前移动,一次通常移动不止一个字符。但在少数情况下,匹配器被迫向后移动。

很容易就能将 Rope迭代器改成一次向前移动不止一个字符。但是向后移动要复杂些,因为迭代器内部执行的是深度优先算法,预先排好了 Rope遍历的顺序,需要访问每个叶节点。遍历堆栈没有足够的信息能够前移到前一个叶节点,但是如果促使向后移动的信息量没有使迭代器离开当前叶节点,那么迭代器就有可能服务请求。为了说明这个作法,图 5 显示一个虚构的迭代器的状态,它能够向后移动一、二、三、四个位置,但不能移动更多位置,因为这要求访问前面访问的叶节点。

图 5. 迭代器状态示例
迭代器状态示例

为了支持这一新功能,可以修改 RopecharAt方法,这样在第一次调用的时候,就在指定位置上构建一个迭代器。后续的调用会将迭代器前后移动指定的距离。如果迭代器不能后移指定的距离,那么就执行默认的 charAt例程取得字符的值 —这种情况很少发生。

因为这种优化无法做到普遍适用,而且要求引入新的成员变量,所以最好不要直接将它添加到 Rope类。相反,可以根据需要用这个优化修饰 rope。为此,Ropes for Java 在 Rope类中包含了一个方法,能够为指定的模式生成优化的匹配器。清单 5 演示了这种方法:

清单 5. 优化的正则表达式匹配
 Pattern p = ... 
 Matcher m = rope.matcher(p);

清单 5 中第二行调用对 rope 进行修饰,优化正则表达式匹配。

表 7 提供了这种方法的测评结果,并包含了以前的结果(表 6)以便进行对照。

表 7. 使用 rope.matcher()的正则表达式搜索时间
技术时间(单位:纳秒)
String75,286,078
StringBuffer86,083,830
Rope12,507,367,218
重新均衡后的 Rope2,628,889,679
Rope.matcher246,633,828

优化的结果比起重新均衡后的 rope 明显提高了 10.6 倍,使 rope 的性能与 String性能的差距缩小到 3.2 倍之内。


应用程序

什么时候不应使用 rope

企业级 Java 应用程序经常包含类似下面的代码:

String x = "<input type='text' name='name' value='"
+ escapePcData(bean.getName()) + "'>";

x随后放在 HTML 内发送到客户机浏览器。用 rope 代替编译器默认生成的 StringBuilder来计算 x的值是否有意义?

回答是否,原因有几个。首先,这里要连接的数据的数量比较小,所以使用 rope 不会提高性能(虽然能够提高健壮性和伸缩性)。(请设想一下 getName出人意料地返回 50 MB 字符串时这两种解决方案会如何反应。)

但是出于讨论的目的,假设有许多块数据进行连接。由于 Rope的附加性能通常比 StringBuffer好,这时使用 rope 是否有意义呢?答案还是否。不论何时将输入的数据组合在一起形成格式化输出时,最漂亮最有效的方法是使用模板引擎(例如 StringTemplate 或 FreeMarker)。这种方法不仅能干净地将表示标记与代码分开,而且模板只进行一次编译(通常编译为 JVM 字节码),以后可以重用,从而使它们拥有极佳的性能特征。

使用模板的第二个好处暴露了对于类似以上代码中那些输出构建例程(包括用 rope 编写的例程)常见的基本缺陷。这个好处是:可以对模板进行逐步评估,而且输出一旦生成就可以写入 Writer,不必先在内存中累积。在 Java EE 应用程序中,Writer实际就是到客户机浏览器的缓冲的连接,这种输出方法呈现恒定的内存量 —— O(1),而其他解决方案的内存使用则是 O(n)。这对应用程序的可伸缩性和健壮性都是 巨大的改进,虽然对小的输出或较低的应用程序负载来说不是那么明显。(请参阅 参考资料中两篇关于流式架构的文章的链接,获得进一步解释和定量分析。)

现在对于 rope 的性能已经有了很好的理解,可以考虑 rope 的一些传统用法,以及在 Java EE 应用程序中吸引人但很可能 并不恰当的用法

虽然 rope 可以作为一种通用方法替代字符串的连续内存表示法,但是只有在大量修改大型字符串的应用程序中才能看到明显的性能提升。这可能并不让人惊讶,因为最早的 rope 应用程序就是用来在文本编辑器中表示文档。不仅在特大的文档中能够以几乎恒定的时间执行文本插入和删除,rope 的不可修改性还使得 “撤消堆栈(undo stack)” 的实现非常容易:只要在每次修改时保存对前一个 rope 的引用即可。

另一个更加神奇的 rope 应用是表示虚拟机的状态。例如,ICFP 2007 编程竞赛中有一个比赛就是实现一个虚拟机,要求每个周期都修改它的状态,并针对某些输入运行数百万个周期(请参阅 参考资料)。在一个 Java 实现中,虚拟机的速度提高了三个数量级,从 ~50 周期 / 秒提高到超过 50,000/ 秒,这是通过使用 Rope代替专门的 StringBuffer来表示状态而做到的。

未来的研究方向

虽然 Ropes for Java 是一种新库,但底层概念并不新鲜,该库看起来实现了 rope 的性能许诺。但是,该项目希望通过以下方面在未来的发行版中对库的某些方面进行改进:

  • 提供其他常见字符串操作的高性能实现。
  • 编写适配器,将 rope 无缝地集成到 Scala(请参阅 参考资料)和面向 Java 平台的其他高级语言。
  • 通过进一步的自动测试提高质量。Ropes for Java 既使用手工编写的 JUnit 自动测试进行了测试,也通过 JUnit 工厂自动生成的测试进行了测试。集成 ESC/Java 2(请参阅 参考资料)检验过的 Java 建模语言(JML)标注可能会进一步提高质量。

参考资料

学习

获得产品和技术

  • Ropes for Java:下载最新发行版。
  • PerformanceTest.java:本文中用来测试变换性能的性能评测代码。可以下载并运行这个程序,获得针对自身平台的结果。
  • 下载 IBM 产品评估版并开始使用来自 DB2®、Lotus®、Rational®、Tivoli®和 WebSphere®的应用程序开发工具和中间件产品。

讨论

条评论

developerWorks: 登录

标有星(*)号的字段是必填字段。


需要一个 IBM ID?
忘记 IBM ID?


忘记密码?
更改您的密码

单击提交则表示您同意developerWorks 的条款和条件。 查看条款和条件

 


在您首次登录 developerWorks 时,会为您创建一份个人概要。您的个人概要中的信息(您的姓名、国家/地区,以及公司名称)是公开显示的,而且会随着您发布的任何内容一起显示,除非您选择隐藏您的公司名称。您可以随时更新您的 IBM 帐户。

所有提交的信息确保安全。

选择您的昵称



当您初次登录到 developerWorks 时,将会为您创建一份概要信息,您需要指定一个昵称。您的昵称将和您在 developerWorks 发布的内容显示在一起。

昵称长度在 3 至 31 个字符之间。 您的昵称在 developerWorks 社区中必须是唯一的,并且出于隐私保护的原因,不能是您的电子邮件地址。

标有星(*)号的字段是必填字段。

(昵称长度在 3 至 31 个字符之间)

单击提交则表示您同意developerWorks 的条款和条件。 查看条款和条件.

 


所有提交的信息确保安全。


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=10
Zone=Java technology
ArticleID=294136
ArticleTitle=Rope:理论与实践
publish-date=03112008