2.12 performance regression from ArrayOps allocations on vectors/seqs

[twenovales]

tl;dr: allocation of ArrayOps (.ofInt, et al.) for some common operations like .count, .isEmpty, etc. result in performance regressions in Scala 2.12 vs. 2.11. This seems to affect performance of Vectors (and, by proxy, the default Seq).

https://github.com/twenovales/scala-collections-benchmark is a test case for this.

2.12.8:

[info] Benchmark                                                                     Mode  Cnt      Score      Error   Units
[info] CollectionsBenchmark.existsEmptinessAfter                                    thrpt   25  94329.046 ± 1874.541   ops/s
[info] CollectionsBenchmark.existsEmptinessAfter:·gc.alloc.rate                     thrpt   25   1379.420 ±   27.431  MB/sec
[info] CollectionsBenchmark.existsEmptinessAfter:·gc.alloc.rate.norm                thrpt   25  16104.000 ±    0.001    B/op
[info] CollectionsBenchmark.existsEmptinessAfter:·gc.churn.PS_Eden_Space            thrpt   25   1379.108 ±   27.570  MB/sec
[info] CollectionsBenchmark.existsEmptinessAfter:·gc.churn.PS_Eden_Space.norm       thrpt   25  16100.461 ±   54.457    B/op
[info] CollectionsBenchmark.existsEmptinessAfter:·gc.churn.PS_Survivor_Space        thrpt   25      0.044 ±    0.009  MB/sec
[info] CollectionsBenchmark.existsEmptinessAfter:·gc.churn.PS_Survivor_Space.norm   thrpt   25      0.517 ±    0.099    B/op
[info] CollectionsBenchmark.existsEmptinessAfter:·gc.count                          thrpt   25   3179.000             counts
[info] CollectionsBenchmark.existsEmptinessAfter:·gc.time                           thrpt   25   2173.000                 ms
[info] CollectionsBenchmark.existsEmptinessBefore                                   thrpt   25  50941.865 ± 1343.292   ops/s
[info] CollectionsBenchmark.existsEmptinessBefore:·gc.alloc.rate                    thrpt   25    513.863 ±   17.343  MB/sec
[info] CollectionsBenchmark.existsEmptinessBefore:·gc.alloc.rate.norm               thrpt   25  11105.601 ±   98.347    B/op
[info] CollectionsBenchmark.existsEmptinessBefore:·gc.churn.PS_Eden_Space           thrpt   25    514.373 ±   17.452  MB/sec
[info] CollectionsBenchmark.existsEmptinessBefore:·gc.churn.PS_Eden_Space.norm      thrpt   25  11116.552 ±  101.305    B/op
[info] CollectionsBenchmark.existsEmptinessBefore:·gc.churn.PS_Survivor_Space       thrpt   25      0.035 ±    0.007  MB/sec
[info] CollectionsBenchmark.existsEmptinessBefore:·gc.churn.PS_Survivor_Space.norm  thrpt   25      0.764 ±    0.160    B/op
[info] CollectionsBenchmark.existsEmptinessBefore:·gc.count                         thrpt   25   3137.000             counts
[info] CollectionsBenchmark.existsEmptinessBefore:·gc.time                          thrpt   25   2104.000                 ms

2.11.11

[info] Benchmark                                                                 Mode  Cnt       Score      Error   Units
[info] CollectionsBenchmark.existsEmptinessAfter                                thrpt   25  181176.834 ± 4285.124   ops/s
[info] CollectionsBenchmark.existsEmptinessAfter:·gc.alloc.rate                 thrpt   25      15.793 ±    0.373  MB/sec
[info] CollectionsBenchmark.existsEmptinessAfter:·gc.alloc.rate.norm            thrpt   25      96.000 ±    0.001    B/op
[info] CollectionsBenchmark.existsEmptinessAfter:·gc.churn.PS_Eden_Space        thrpt   25      16.364 ±   25.165  MB/sec
[info] CollectionsBenchmark.existsEmptinessAfter:·gc.churn.PS_Eden_Space.norm   thrpt   25      99.492 ±  152.775    B/op
[info] CollectionsBenchmark.existsEmptinessAfter:·gc.count                      thrpt   25       5.000             counts
[info] CollectionsBenchmark.existsEmptinessAfter:·gc.time                       thrpt   25       4.000                 ms
[info] CollectionsBenchmark.existsEmptinessBefore                               thrpt   25  180176.343 ± 6345.755   ops/s
[info] CollectionsBenchmark.existsEmptinessBefore:·gc.alloc.rate                thrpt   25      15.706 ±    0.552  MB/sec
[info] CollectionsBenchmark.existsEmptinessBefore:·gc.alloc.rate.norm           thrpt   25      96.000 ±    0.001    B/op
[info] CollectionsBenchmark.existsEmptinessBefore:·gc.churn.PS_Eden_Space       thrpt   25      14.658 ±   30.346  MB/sec
[info] CollectionsBenchmark.existsEmptinessBefore:·gc.churn.PS_Eden_Space.norm  thrpt   25      90.158 ±  186.701    B/op
[info] CollectionsBenchmark.existsEmptinessBefore:·gc.count                     thrpt   25       3.000             counts
[info] CollectionsBenchmark.existsEmptinessBefore:·gc.time                      thrpt   25       2.000                 ms

Note the difference in gc.alloc.rate.norm. A heap dump indicated that these were instances of ArrayOps.ofInt, but I believe this will apply to any instance.

(There are some additional commented-out benchmarks in the example, which, from some earlier testing, all showed regressions. These benchmarks show no performance regression from 2.11 to 2.12 when written with types like List.)

[Jasper-M]

This seems to affect performance of Vectors (and, by proxy, the default Seq).

Not really important, but Vector is not the default Seq. But for some strange reason Scalacheck picks up Predef.fallbackStringCanBuildFrom for building Seqs.

[Jasper-M]

It's a bit ironic that the ArrayOps.ofInt conversion was optimized for 2.12. And the irony bonus is that those ArrayOps valueclasses still box anyway because all of their methods are inherited instead of defined in their own body.

[twenovales]

Ok. This regression occurs if the declared generated container types are Seq, Vector, IndexedSeq, or Iterable. (easier to generate if you remove one level of nesting in the collections) It doesn't occur for List or Array (i.e. if you generate an Array[Array[Int]] as the code is currently written).

[SethTisue]

It would be good to know whether this changed again in 2.13.

[twenovales]

@SethTisue 2.13.0-M5 is better on existsEmptinessBefore than 2.12.8, but still much slower than 2.11.11 overall.

[info] Benchmark                                                                     Mode  Cnt      Score      Error   Units
[info] CollectionsBenchmark.existsEmptinessAfter                                    thrpt   25  96018.283 ± 1504.860   ops/s
[info] CollectionsBenchmark.existsEmptinessAfter:·gc.alloc.rate                     thrpt   25     ≈ 10⁻⁴             MB/sec
[info] CollectionsBenchmark.existsEmptinessAfter:·gc.alloc.rate.norm                thrpt   25     ≈ 10⁻³               B/op
[info] CollectionsBenchmark.existsEmptinessAfter:·gc.count                          thrpt   25        ≈ 0             counts
[info] CollectionsBenchmark.existsEmptinessBefore                                   thrpt   25  79932.398 ± 1324.065   ops/s
[info] CollectionsBenchmark.existsEmptinessBefore:·gc.alloc.rate                    thrpt   25    812.047 ±   19.846  MB/sec
[info] CollectionsBenchmark.existsEmptinessBefore:·gc.alloc.rate.norm               thrpt   25  11187.201 ±  161.060    B/op
[info] CollectionsBenchmark.existsEmptinessBefore:·gc.churn.PS_Eden_Space           thrpt   25    811.790 ±   20.415  MB/sec
[info] CollectionsBenchmark.existsEmptinessBefore:·gc.churn.PS_Eden_Space.norm      thrpt   25  11183.317 ±  160.768    B/op
[info] CollectionsBenchmark.existsEmptinessBefore:·gc.churn.PS_Survivor_Space       thrpt   25      0.024 ±    0.006  MB/sec
[info] CollectionsBenchmark.existsEmptinessBefore:·gc.churn.PS_Survivor_Space.norm  thrpt   25      0.335 ±    0.089    B/op
[info] CollectionsBenchmark.existsEmptinessBefore:·gc.count                         thrpt   25   3389.000             counts
[info] CollectionsBenchmark.existsEmptinessBefore:·gc.time                          thrpt   25   2220.000                 ms

(I only ran these two, I haven't checked any other benchmarks on 2.13.0-M5.)