Scala中不可变集实现的性能

Question

我最近一直在潜入Scala,并且(可能是可以预见的)花了相当多的时间研究Scala标准库中的不可变集合API.

我正在编写一个应用程序,它必须在大型集合上执行许多+/-操作.出于这个原因,我想确保我选择的实现是一个所谓的"持久"数据结构,这样我就可以避免进行写时复制.我看到马丁奥德斯基的这个答案,但它并没有真正解决我的问题.

我编写了以下测试代码来比较ListSet和HashSet的性能以进行添加操作:

import scala.collection.immutable._

object TestListSet extends App {
  var set = new ListSet[Int]
  for(i <- 0 to 100000) {
    set += i
  }
}

object TestHashSet extends App {
  var set = new HashSet[Int]
  for(i <- 0 to 100000) {
    set += i
  }
}

这是HashSet的粗略运行时测量:

$ time scala TestHashSet

real    0m0.955s
user    0m1.192s
sys     0m0.147s

和ListSet:

$ time scala TestListSet

real    0m30.516s
user    0m30.612s
sys     0m0.168s

单链表上的缺点是恒定时间操作,但这种性能看起来线性或更差.这个性能是否与需要检查集合中的每个元素以确保对象相等以符合Set的无重复不变量有关？如果是这种情况,我意识到它与"持久性"无关.

至于官方文档,我所能找到的只是以下页面,但似乎不完整:Scala 2.8 Collections API - Performance Characteristics.由于ListSet最初似乎是其内存占用的一个很好的选择,因此可能应该在API文档中提供有关其性能的一些信息.

Answer 1

一个老问题,但也是在错误的基础上得出结论的一个很好的例子.

Connor,基本上你正在尝试做一个微基准测试.这是一般不建议和该死的努力做正确.

为什么？因为JVM除了执行示例中的代码之外还执行许多其他操作.它是加载类,进行垃圾收集,将字节码编译为本机代码等.所有这些都是动态地并且基于在运行时采样的不同度量.

所以你不能用上面的测试代码总结两个集合的性能.例如,你实际上可以测量可能是什么的编译时间+=的方法HashSet和垃圾收集的时间ListSet.所以这是苹果和梨之间的比较.

要正确地进行微观基准测试,您应该:

1. 预热JVM:加载所有类,确保运行基准测试中的所有代码路径并编译代码中的热点(例如+=方法).
2. 运行基准测试并确保在测试期间GC或编译器都不运行(使用JVM标志-XX:-PrintCompilation和-XX:-PrintGC).如果在测试期间运行,则丢弃结果.
3. 重复步骤2,样品10-15次测量.计算方差和标准差.
4. 评估:如果每个基准+/- 3标准的平均值不重叠,那么您可以得出哪个更快的结论.否则,这是一个模糊的结果(取决于重叠的数量).

我可以推荐阅读Oracle关于微基准测试的建议以及Brian Goetz 关于基准陷阱的精彩文章.

此外,如果您想使用一个好的工具,它可以为您完成上述所有工作,请尝试使用Caliper by Google.

Answer 2

来源的关键ListSet是(在子类内Node):

override def +(e: A): ListSet[A] = if (contains(e)) this else new Node(e)

您可以看到只有在尚未包含项目时才添加该项目.所以添加到集合是O(n).您通常可以假设XMap具有与XSet类似的性能特征,并且ListMap一直列为线性时间.这就是原因,它是一个集合应该如何表现的原因.

PS在TestHashSet案例中,您正在测量启动时间.它的速度提高了30多倍.

Answer 3

由于集合必须没有重复项,因此在添加元素之前,集合必须检查它是否已包含该元素.在无法保证元素位置的列表中搜索将是O(N)线性时间.同样的一般想法适用于其删除操作.

使用HashSet,该类定义了一个函数,该函数为O(1)中的任何元素选取一个位置,这使得contains(element)方法更快,代价是占用更多空间以减少元素位置冲突的可能性.