性能观察: Trove 集合类

更小、更普通、更易上手

打印本页

将此页作为电子邮件发送

级别： 初级

Jack Shirazi (jack@JavaPerformanceTuning.com), 董事, JavaPerformanceTuning.com
Kirk Pepperdine (kirk@JavaPerformanceTuning.com), CTO, JavaPerformanceTuning.com

2004 年 9 月 28 日

Trove 是一种开放源代码的 Java 集合包，提供了核心 Java 集合类的高效替代品，特别针对于实现其键或值是基本类型的集合。本期 性能观察文章中，性能优化专家 Jack Shirazi 和 Kirk Pepperdine 考察了 Trove 类与传统的 Java 集合的区别，以及何时使用 Trove 类。

几年前，也就是 2001 年后期，我们收到了 Eric Friedman 的电子邮件。他说他已经决定构造一组开放源代码的集合类，用于取代 java.util 类。而且这些类执行速度更快、更轻巧、更灵活。是的，Eric 要创建 Six Million Dollar集合！

事实上，当时我们对是否能够直接取代 Java 平台的集合类并不特别感兴趣。Joshua Bloch 的工作做得很好，创建的通用集合框架非常有用、快捷而且能够扩展。但是通用与高效常常是互斥的两个目标。创建 专门的 集合类来处理 int 或 boolean 这类基本类型，对于我们而言即使在 2001 年也不是多么不寻常的事。否则，在 Java 平台通用集合框架中存储基本类型的集合都需要通过 Integer 和 Boolean 之类的包装器类进行包装和解包，这样做不但非常麻烦，而且大量的包装和解包很容易成为性能瓶颈。

这样说有点离题了。

美梦还是恶梦？

Eric 建议创建不通过包装和解包就直接处理数据原型的集合类。这是性能优化人员的梦想，而且可以改进类型安全性，但却是架构师的恶梦。比方说 Map 吧，它包括键和值，每个键或者值都可以是 Object 或者 8 种基本数据类型之一： byte 、 short 、 char 、 int 、 long 、 float 、 double 和 boolean 。

这样就有 9 种键和 9 种值，组成 81 种不同类型的 Map ！更糟的是，只要其中一个存在缺陷，就意味着其他 80 种很可能也存在缺陷，而能够共用的代码很有限，因为为了有效地处理每种数据类型，需要分别实现算法，从而，维护的工作量太大了。我非常钦佩 Eric，但是并不期望这种集合能够很快出现，因为开发和调试需要大量的时间。

在 2001 年，我们为 Eric 提供的支持很少。在“Java Performance Tuning” 12 号时事通讯中（请参阅 参考资料），我们看到了 Eric 关于 Trove 项目的宣告。除了偶尔的 bug 修复外，Eric 都是一个人在所有这些不同的集合版本中埋头苦干。他做了一项了不起的工作，今天我们可以欣然享受他艰苦劳作的成果了。Trove 集合可以使用了，而且确实非常有用。

许许多多的集合

好了，上面是一段小插曲，您到底能够从 Trove 中得到什么呢？许许多多的高效集合。除了那 81 种不同的 HashMap 版本之外（比如 TIntIntHashMap 、 TIntObjectHashMap 等），还有 List 和 Set 类可以存储基本类型（如 TIntHashSet 、 TFloatArrayList 等）。这种体系结构甚至允许您插入自己的散列策略，以便选择对您的数据集而言可能更有效（或者更灵活）的算法。当然，支持灵活的散列算法也要付出性能代价 —— 如果散列映射成为瓶颈，很可能是因为大量地使用它，这意味着散列函数被反复不断地调用。因此，散列函数中每一点多余的开销都可能成为瓶颈。（顺便说一下，如果散列函数足够简单，JIT 编译器就可能将其编译成内联函数，这样在支持灵活的散列策略的同时又不会带来额外的开销 —— 真是免费的午餐！）

此外，Eric 还实现了 Smalltalk 范型，就是说集合能够对自己的元素执行过程。这种处理不同于 Java 平台中一般的集合元素遍历，需要稍微讨论一下。在 Java 编程中，如果需要处理集合中的所有元素，通常要有一个迭代器（Iterator）来访问和处理每个元素，如清单 1 所示：

  Iterator iterator = collection.iterator();                        while (iterator.hasNext())                        {                        Object o = iterator.next();                        ... //do something with 'o'                        }                        

Trove 也支持这种迭代模式，但是还支持向集合传递过程，然后集合在内部迭代每个元素，依次将该过程应用于每个元素。尽管这种技术不一定能提高效率 —— 如果迭代器对象不能像集合本身那样高效地遍历元素，则可以提高效率 —— 但是有助于提高清晰性和灵活性。清单 2 是上述例子改写后的版本：

Procedure procedure = new DoSomethingWithOProcedure();                        collection.forEach(procedure);                        

开放选址

Trove 映射是采用开放选址而不是链接来实现的。在 Java 核心集合类中，多数映射都是使用链接实现，就是说如果多个键映射到表中的同一索引位置，则索引位置保存一个链表，其中存放映射到该位置的所有元素。开放选址映射则假设表中邻近的位置存在没有使用的索引。如果目标位置已经被占用，映射实现就查看附近的几个位置找到一个没有使用的位置。这种方法不需要链表节点，因此 Trove 映射和相同的核心集合类相比占用的内存更少。使用开放选址必须保证有足够的空闲索引，否则可能影响性能。（Trove 保持装载因子小于 0.5。）否则的话，开放选址的效率与链接基本相当，但多数情况下要好于后者。

开放选址的另一个优点是实现中不需要链表节点对象，链表节点需要靠链接来实现。为什么特别强调这一点呢？基本上每个 JVM 版本都会改进对象创建和无用单元回收的性能，但是较多的对象总会带来更多的开销。对于任何特定的问题，Java 编程中能够减少对象数量的解决方案通常都有更好的效率，这是一个标准的性能权衡问题，每个有经验的性能优化人员都知道。开放选址使用更少的对象来维护映射结构，这意味着 Trove 映射在多数情况下比核心 Java 映射更有效，也更小。值得一提的是，最近越来越多的 Java 核心 Map 实现开始使用开放选址（比如 IdentityHashMap 类）。现有的其他核心 Java Map 实现最终也可能改为使用开放选址，虽然我们可能不那么关心，因为如果需要开放选址的实现，使用 Trove 就可以了。

Trove 本身提供了一个小的基准测试，用于跟核心 Java 集合进行性能比较。Dion Almaer 所进行的独立比较测试（请参阅 参考资料）说明了 Trove 在性能和大小上的优势。结果表明，Trove 执行 Map.put() 操作的速度要快三倍，而占用的内存只有核心 Map 所需要的一半。

自动装箱

Java 5.0 平台引入了泛化（generics）和自动装箱机制（Autoboxing）。这意味着您可以编写下面这样的代码：

  mymap.put("201",201);                        mymap.put("202",202);                        int sum = mymap.get("201") + mymap.get("202")                        mymap.put("sum",sum);                        

注意，通过使用泛化， mymap 甚至可以限制为仅保存 Integer 对象。但是也要注意在幕后仍然会进行自动装箱，清单 3 代码中的所有 int 都在运行时使用 Integer 对象包装（通常每次都使用新的对象），并使用存取方法来访问（虽然 JIT 编译器可能将访问编译成内联函数）。

需要强调指出：Java 5.0 平台中的自动装箱可能造成高效的假象。在代码层上看起来基本数据类型的使用效率很高，但是在运行时，基本数据包装器类型的使用效率则会变得很低。Heinz Kabutz 博士最近撰文表明，如果不小心在循环中使用自动装箱机制，有可能使性能降低一个数量级（请参阅 参考资料）。

自动装箱的效率比不上使用直接保存基本数据类型的集合，比如值为 int 、键为 Object 的 Trove TObjectIntHashMap 类型不需要包装和解包 int 值。对于其他基本数据类型和集合组合，Trove 都有等价的集合，如 TIntIntHashMap （ int 键和 int 值）、 TLongArrayList （保存 long 的列表）、 TIntSet （保存 int 的集合）等等。Dion Almaer 对 TIntIntHashMap 和 HashMap 的比较测试也表明 Trove 的速度要快一个数量级。

结束语

将 Trove 加到您的项目中吧。我们并不建议在每个需要集合的地方都使用 Trove，因为 Trove 毕竟还年轻，使用的还不多，所以很可能会出现一些 bug。但是 Trove 提供了一种选择，如果需要效率更高的类，就可以使用它，当您在调优应用程序时会遇到这种情况。