Perform more comparative benchmarks of 2.12 and 2.13 collections

[retronym]

https://github.com/scala/scala/pull/6818 makes it relatively convenient to compare the results of a newly written benchmark between different Scala versions.

We should use this to seek out performance changes (regressions or progressions!).

I expect these changes to come from three sources:

• A new implementation of a collection (ChampHashMap, ArraySeq)
• Collections that are internally unchanged, but no longer inherit sufficiently performant implementations of a particular method after the hierarchy redesign.
• General patterns in the new collections design (e.g. the use of .iterator as the prime operation, rather than .foreach) hurt or help certain workloads. For instance, the cost of creating an iterator might be high for workloads that often call some method on an empty collection, meaning we should have fast paths based on the cheaply available collection size.

Comparing inheritance between 2.12 and 2.13

Given:

import scala.collection.immutable
import reflect.runtime.universe._

object OverrideChecker {
  def main(args: Array[String]): Unit = {
    def check(t: Type) {
      println("-" * 40)
      println(t.typeSymbol)
      val pattern = java.util.regex.Pattern.compile("^=>")
      for (t <- t.members.toList.sortBy(x => (x.name.toString, x.info.toString)) if !Set[Symbol](definitions.ObjectClass, definitions.AnyClass).contains(t.owner) && t.isMethod && t.isPublic) {

        println(s"${t.name}${pattern.matcher(t.info.toString).replaceAll(":")} from ${t.owner.fullName}")
      }
    }
    check(typeOf[::[_]])
    check(typeOf[Vector[_]])
  }
}

We can see where implementations are inherited from.

$ scalac-ref heads/2.13.x sandbox/test.scala && scala-ref heads/2.13.x OverrideChecker | tee /tmp/overrides-2.13.log

----------------------------------------
class ::
$colon$bslash[B](z: B)(op: (A, B) => B)B from scala.collection.IterableOnceOps
$colon$colon[B >: A](elem: B)List[B] from scala.collection.immutable.List
$colon$colon$colon[B >: A](prefix: List[B])List[B] from scala.collection.immutable.List
$colon$plus[B >: A](elem: B)CC[B] from scala.collection.SeqOps
$colon$plus$plus[B >: A](suffix: Iterable[B])CC[B] from scala.collection.SeqOps
$div$colon[B](z: B)(op: (B, A) => B)B from scala.collection.IterableOnceOps
$init$()Unit from scala.Product
$plus$colon[B >: A](elem: B)CC[B] from scala.collection.SeqOps
$plus$plus[B >: A](suffix: Iterable[B])CC[B] from scala.collection.IterableOps
$plus$plus$colon[B >: A](prefix: Iterable[B])CC[B] from scala.collection.SeqOps
<init>(head: A, next: List[A @scala.annotation.unchecked.uncheckedVariance])scala.collection.immutable.::[A] from scala.collection.immutable.$colon$colon
addString(b: StringBuilder)StringBuilder from scala.collection.IterableOnceOps
addString(b: StringBuilder, sep: String)StringBuilder from scala.collection.IterableOnceOps
addString(b: StringBuilder, start: String, sep: String, end: String)b.type from scala.collection.IterableOnceOps
andThen[C](k: B => C)PartialFunction[A,C] from scala.PartialFunction
appended[B >: A](elem: B)CC[B] from scala.collection.StrictOptimizedSeqOps
appendedAll[B >: A](suffix: Iterable[B])List[B] from scala.collection.immutable.List
...
exists(p: A => Boolean)Boolean from scala.collection.immutable.List
filter(p: A => Boolean)List[A] from scala.collection.immutable.List
filterNot(p: A => Boolean)List[A] from scala.collection.immutable.List

Any of these inherited from IterableOnceOps will require iterator collection. We can see that we've already overridden a few important methods (e.g List.exists) to avoid this cost.

For further insights, we can then use diff to compare this against 2.12:

$ scalac-ref heads/2.12.x sandbox/test.scala && scala-ref heads/2.12.x OverrideChecker | tee /tmp/overrides-2.12.log


$ diff /tmp/overrides-2.1{2,3}.log

Together, this could give a starting point for us to write some comparative benchmarks.

Writing a benchmark and comparing 2.12 and 2.13

• Add a benchmark to test/benchmarks/src/main/scala

$ for V in 2.12.6 ""; do \
  label=$V; [[ "$V" == "" ]] && label=2.13.x; \
  (set -x; sbt -Dbenchmark.scala.version="$V" 'bench/jmh:run scala.collection.mutable.HashMapBenchmark.* -psize=1000 -f1 -rf json -rff
/tmp/'$label'-result.json');\
 done

$ open http://jmh.morethan.io/

Load the two generated .json result files in http://jmh.morethan.io/ and look for outliers.

[retronym]

/cc @rorygraves