科技行者

行者学院 转型私董会 科技行者专题报道 网红大战科技行者

知识库

知识库 安全导航

至顶网软件频道基础软件Java列表对象的性能分析和测试(3)

Java列表对象的性能分析和测试(3)

  • 扫一扫
    分享文章到微信

  • 扫一扫
    关注官方公众号
    至顶头条

SDK提供了有序集合接口java.util.List的几种实现,其中三种最为人们熟知的是Vector、ArrayList和LinkedList。有关这些List类的性能差别是一个经常被问及的问题。在这篇文章中,作者要探讨的就是LinkedList和Vector/ArrayList之间的性能差异。

作者:东波\\\'S BLOG 来源:东波’S BLOG 2007年9月1日

关键字:

  • 评论
  • 分享微博
  • 分享邮件
三、性能测试



这些类有许多不同的功能可以进行测试。LinkedList应用比较频繁,因为人们认为它在随机插入和删除操作时具有较好的性能。所以,下面我分析的重点将是插入操作的性能,即,构造集合。我测试并比较了LinkedList和ArrayList,因为这两者都是非同步的。

插入操作的速度主要由集合的大小和元素插入的位置决定。当插入点的位置在集合的两端和中间时,最差的插入性能和最好的插入性能都有机会出现。因此,我选择了三个插入位置(集合的开头、末尾和中间),三种典型的集合大小:中等(100个元素),大型(10,000个元素),超大型(1,000,000个元素)。

在本文的测试中,我使用的是JAVA SDK 1.2.0和1.3.0系列的SUN JVM。此外,我还用HOTSPOT JVM 2.0进行了测试,这个版本可以在1.3.0 SDK找到。在下面的表格中,各个测量得到的时间都以其中一次SDK 1.2 VM上的测试时间(表格中显示为100%的单元)为基准显示。测试期间使用了默认的JVM配置,即启用了JIT编译,因此对于所有JVM,堆空间都必须进行扩展,以避免内存溢出错误。表格中记录的时间是多次测试的平均时间。为了避免垃圾收集的影响,在各次测试之间我强制进行了完全的内存清理(参见测试源代码了解详情)。磁盘监测确保磁盘分页不会在测试过程中出现(任何测试,如果它显示出严重的磁盘分页操作,则被丢弃)。所有显示出数秒应答时间的速度太慢的测试都重复进行,直至记录到一个明显合理的时间。

表1:构造一个中等大小的集合(100个元素)。括号中的数字针对预先确定大小的集合。

 

1.2 JVM

1.3 JVM

HotSpot 2.0 JVM

总是插入到ArrayList的开头

100% (48.0%)

184.9% (152.0%)

108.0% (66.7%)

总是插入到LinkedList的开头

135.5%

109.1%

85.3%

总是插入到ArrayList的中间

130.0% (40.6%)

187.4% (158.0%)

84.7% (46.0%)

总是插入到LinkedList的中间

174.0%

135.0%

102.3%

总是插入到ArrayList的末尾

63.3% (20.7%)

65.9% (25.0%)

60.3% (29.3%)

总是插入到LinkedList的末尾

106.7%

86.3%

80.3%

对于规模较小的集合,ArrayList和LinkedList的性能很接近。当元素插入到集合的末尾时,即追加元素时,ArrayList的性能出现了突变。然而,追加元素是ArrayList特别为其优化的一个操作:如果你只想要一个固定大小的静态集合,Java数组(例如Object[])比任何集合对象都具有更好的性能。除了追加操作,测量得到的时间数据差别不是很大,它们反映了各个JVM的优化程度,而不是其他什么东西。

例如,对于把元素插入到集合的开始位置来说(表1的前两行),HotSpot 2.0 JVM加LinkedList具有最好的性能(85.3%),处于第二位的是 1.2 JVM加ArrayList(100%)。这两个结果显示出,1.2中简单的JIT编译器在执行迭代和复制数组等简单的操作时具有很高的效率。在HotSpot中复杂的JVM加上优化的编译器能够改进复杂操作的性能,比如对象创建(创建LinkedList节点),并能够利用代码内嵌(code-inlining)的优势。1.3 JVM的结果似乎显示出,在简单操作方面它的性能有着很大的不足,这一点很可能在以后的JVM版本中得到改进。

在这里我特别进行测试的是ArrayList相对于LinkedList的另一个优点,即预先确定集合大小的能力。具体地说,创建ArrayList的时候允许指定一个具体的大小(例如,在测试中ArrayList可以创建为拥有100个元素的容量),从而避免所有随着元素增多而增加集合规模的开销。表1括号中的数字显示了预先确定集合大小时性能的提高程度。LinkedList(直到 SDK 1.3)不能预先确定大小。

此外,ArrayList只生成少量的需要进行垃圾收集的对象,即,用来保存元素的内部数组对象,以及每次ArrayList容量不足需要进行扩展时创建的附加内部数组对象。LinkedList不管可能出现的任何删除操作,都为每一个插入操作生成一个节点对象。因此,LinkedList会给垃圾收集器带来相当多的工作。考虑到这些因素,对于任何中小规模的集合,我会选择使用ArrayList而不是LinkedList。

表2:构造一个大型集合(10,000个元素)

 

1.2 JVM

1.3 JVM

HotSpot 2.0 JVM

总是插入到ArrayList的开头

7773%

7537%

7500%

总是插入到LinkedList的开头

100%

90.34%

65.6%

总是插入到ArrayList的中间

3318%

3412%

3121%

总是插入到LinkedList的中间

26264%

14315%

14209%

总是插入到ArrayList的末尾

41.4%

41.2%

37.5%

总是插入到LinkedList的末尾

66.4%

73.9%

61.7%

表2显示了大规模集合的测试结果。可以看到,在出现大规模插入操作的时候,我们开始遭遇严厉的性能惩罚。正如我们前面分析类的实现所得到的结果,对于LinkedList来说最差的情形出现在把元素插入到集合中间时。另外我们还可以看到,与使用ArrayList时把元素插入到集合开头的最差性能相比,使用LinkedList时把元素插入到集合中间的性能更差一些。和这两种性能最差的情况相比,把元素插入到ArrayList中间的性能显然要好得多。

总地看来,ArrayList再一次在大多数情形下表现出更好的性能,包括根据索引把元素插入到随机位置的情形。如果你总是要把元素插入到集合中靠前的位置,LinkedList具有更好的性能;然而,此时你可以利用一个反向的ArrayList得到更好的性能,即,使用一个专用的实现,或者通过[size -index]映射翻转索引在集合中的位置。

表3:构造一个超大集合(1,000,000个元素)

 

1.2 JVM

1.3 JVM

HotSpot 2.0 JVM

总是插入到ArrayList的开头

太长

太长

太长

总是插入到LinkedList的开头

100%

179.5%

144.1%

总是插入到ArrayList的中间

太长

太长

太长

总是插入到LinkedList的中间

太长

太长

太长

总是插入到ArrayList的末尾

38.3%

47.7%

42.9%

总是插入到LinkedList的末尾

65.1%

161.5%

139.9%

表3显示了超大集合的测试结果,从该表可以得出的结论与表2非常相似。然而,表3强调的是,超大集合要求数据、集合类型、数据处理算法之间的恰到好处的配合;否则,你将得到事实上不可接受的性能表现。至于性能优化,你可以构造一个针对该问题的专用集合类。对于超大集合来说,为了获得可接受的性能,构造专用集合类往往是很有必要的。

    • 评论
    • 分享微博
    • 分享邮件
    邮件订阅

    如果您非常迫切的想了解IT领域最新产品与技术信息,那么订阅至顶网技术邮件将是您的最佳途径之一。

    重磅专题
    往期文章
    最新文章