为什么遍历扁平化迭代器很慢？

Question

Scala 2.11.8

我正在通过扁平化和非扁平化迭代器测量迭代。我写了以下基准：

@State(Scope.Benchmark)
class SerializeBenchmark
  var list = List(
    List("test", 12, 34, 56),
    List("test-test-test", 123, 444, 0),
    List("test-test-test-tes", 145, 443, 4333),
    List("testdsfg-test-test-tes", 3145, 435, 333),
    List("test-tessdfgsdt-tessdfgt-tes", 1455, 43, 333),
    List("tesewrt-test-tessdgdsft-tes", 13345, 4533, 3222333),
    List("ewrtes6yhgfrtyt-test-test-tes", 122245, 433444, 322233),
    List("tserfest-test-testtryfgd-tes", 143345, 43, 3122233),
    List("test-reteytest-test-tes", 1121145, 4343, 3331212),
    List("test-test-ertyeu6test-tes", 14115, 4343, 33433),
    List("test-lknlkkn;lkntest-ertyeu6test-tes", 98141115, 4343, 33433),
    List("tkknknest-test-ertyeu6test-tes", 914111215, 488343, 33433),
    List("test-test-ertyeu6test-tes", 1411125, 437743, 93433),
    List("test-test-ertyeu6testo;kn;lkn;lk-tes", 14111215, 5409343, 39823),
    List("telnlkkn;lnih98st-test-ertyeu6test-tes", 1557215, 498343, 3377433)
  )

  @Benchmark
  @OutputTimeUnit(TimeUnit.NANOSECONDS)
  @BenchmarkMode(Array(Mode.AverageTime))
  def flattenerd(bh: Blackhole): Any = {
    list.iterator.flatten.foreach(bh.consume)
  }

  @Benchmark
  @OutputTimeUnit(TimeUnit.NANOSECONDS)
  @BenchmarkMode(Array(Mode.AverageTime))
  def raw(bh: Blackhole): Any = {
    list.iterator.foreach(_.foreach(bh.consume))
  }
}

在运行这些基准测试之后，我得到了以下结果：

Benchmark                      Mode  Cnt      Score      Error  Units
SerializeBenchmark.flattenerd  avgt    5  10311,373 ± 1189,448  ns/op
SerializeBenchmark.raw         avgt    5   3463,902 ±  141,145  ns/op

性能相差近 3 倍。我使源 list 越大，性能差异就越大。为什么？

我预计会有一些性能差异，但不是 3 倍。

Answer 1

我在 hs_gc 配置文件下运行重新运行你的测试运行ning。

这些是结果：

[info] Benchmark                                                       Mode  Cnt        Score          Error  Units
[info] IteratorFlatten.flattenerd                                      avgt   50        0.708 â–’        0.120  us/op
[info] IteratorFlatten.flattenerd:â•–sun.gc.collector.0.invocations    avgt   50        8.840 â–’        2.259      ?
[info] IteratorFlatten.raw                                             avgt   50        0.367 â–’        0.014  us/op
[info] IteratorFlatten.raw:â•–sun.gc.collector.0.invocations           avgt   50        0                     ?

IteratorFlatten.flattenerd 在测试运行期间平均有 8 个 GC 周期，其中 raw 为 0。这意味着由于 [= 分配产生的噪音15=]（包装器 class 及其方法，特别是 hasNext，它为每个列表分配一个迭代器），这是在 [=18= 上提供 flatten 方法所需要的]，我们在运行宁时间受苦

如果我重新运行测试并给它最小堆大小 2G，结果会更接近：

[info] Benchmark                   Mode   Cnt        Score           Error  Units
[info] IteratorFlatten.flattenerd  avgt   50        0.615 â–’         0.041  us/op
[info] IteratorFlatten.raw         avgt   50        0.434 â–’         0.064  us/op

其要点是，分配的越多，GC 要做的工作就越多，暂停次数越多，执行速度越慢。

请注意，此类微基准测试非常脆弱，可能会产生不同的结果。确保您测量了足够的分配以使统计数据变得重要。

为什么遍历扁平化迭代器很慢？

Why is iterating through flattened iterator slow?

collections

performance

scala

jmh