SI-9823 Collections perf: favor virtual call over instanceof

This avoids concurrent usages of collections in NUMA architectures
from falling of a performance cliff due to an implementation detail
of interface instanceof checks in HotSpot JVM.

The VM contains a one element cache in the metadata of each class
to record the most recent successful test for a interface.

For example:

    classOf[Serializable].isAssignableFrom(classOf[Some[_]])

Would, in addition to returning `true`, set:

    classOf[Some[_]]._secondary_super_cache = classOf[Serializable]

This is done to hide the fact that interface tests are O(N),
where N is the number of inherited interfaces.

This scheme is discussed in "Fast Subtype Checking for the
HotSpot JVM" (Click, Rose) [1]

However, if this cache repeatedly misses, not only are we
exposed to the linear search of the secondary super type array,
but we are also required to write back to the cache. If other
cores are operating on the same cache line, this can lead to
a significant slowdown ("cache thrashing"). This effect will
by most (or only?) visible on multi socket machines.

The pathological case is:

    scala> Iterator.continually(List(classOf[Product], classOf[Serializable])).flatten.take(100).map(intf => intf.isAssignableFrom(classOf[Some[_]])).count(x => x)
    res19: Int = 100

Which, if run on a multi-socket machine, should be much slower
than:

    scala> (Iterator.continually(classOf[Product]).take(50) ++ Iterator.continually(classOf[Serializable]).take(50)).map(intf => intf.isAssignableFrom(classOf[Some[_]])).count(x => x)
    res20: Int = 100

This commit avoids a interface test in a hot path in the collections
by instead using virtual dispatch to differentiate between
IndexedSeqLike and other collections. HotSpot will still use some
shared bookkeeping ("inline cache" [2]) at the callsites of
this method, but these stabilize in the megamorphic usage and no
longer force expensive cache line synchronization.

[1] https://www.researchgate.net/publication/221552851_Fast_subtype_checking_in_the_HotSpot_JVM
[2] https://wiki.openjdk.java.net/display/HotSpot/PerformanceTechniques

3 files changed, 21 insertions, 10 deletions

diff --git a/src/library/scala/collection/GenTraversableOnce.scala b/src/library/scala/collection/GenTraversableOnce.scala
index 4af2ca23be..d3096a872c 100644
--- a/src/library/scala/collection/GenTraversableOnce.scala
+++ b/src/library/scala/collection/GenTraversableOnce.scala
@@ -96,6 +96,12 @@ trait GenTraversableOnce[+A] extends Any {
    */
   def size: Int
 
+   /** The size of this $coll if it is can be cheaply computed
+   *
+   *  @return    the number of elements in this $coll, or -1 if the size cannot be determined cheaply
+   */
+  protected[collection] def sizeHintIfCheap: Int = -1
+
   /** Tests whether the $coll is empty.
    *
    *  Note: Implementations in subclasses that are not repeatedly traversable must take
diff --git a/src/library/scala/collection/IndexedSeqLike.scala b/src/library/scala/collection/IndexedSeqLike.scala
index f4bf58ffe3..f0cede224d 100644
--- a/src/library/scala/collection/IndexedSeqLike.scala
+++ b/src/library/scala/collection/IndexedSeqLike.scala
@@ -92,4 +92,6 @@ trait IndexedSeqLike[+A, +Repr] extends Any with SeqLike[A, Repr] {
     copyToBuffer(result)
     result
   }
+
+  override protected[collection] def sizeHintIfCheap: Int = size
 }
diff --git a/src/library/scala/collection/mutable/Builder.scala b/src/library/scala/collection/mutable/Builder.scala
index 8d6a0ec69d..528f78bd98 100644
--- a/src/library/scala/collection/mutable/Builder.scala
+++ b/src/library/scala/collection/mutable/Builder.scala
@@ -65,18 +65,18 @@ trait Builder[-Elem, +To] extends Growable[Elem] {
   /** Gives a hint that one expects the `result` of this builder
    *  to have the same size as the given collection, plus some delta. This will
    *  provide a hint only if the collection is known to have a cheap
-   *  `size` method. Currently this is assumed to be the case if and only if
-   *  the collection is of type `IndexedSeqLike`.
-   *  Some builder classes
-   *  will optimize their representation based on the hint. However,
+   *  `size` method, which is determined by calling `sizeHint`.
+   *
+   *  Some builder classes will optimize their representation based on the hint. However,
    *  builder implementations are still required to work correctly even if the hint is
    *  wrong, i.e. a different number of elements is added.
    *
    *  @param coll  the collection which serves as a hint for the result's size.
    */
   def sizeHint(coll: TraversableLike[_, _]) {
-    if (coll.isInstanceOf[collection.IndexedSeqLike[_,_]]) {
-      sizeHint(coll.size)
+    coll.sizeHintIfCheap match {
+      case -1 =>
+      case n => sizeHint(n)
     }
   }
 
@@ -94,8 +94,9 @@ trait Builder[-Elem, +To] extends Growable[Elem] {
    *  @param delta a correction to add to the `coll.size` to produce the size hint.
    */
   def sizeHint(coll: TraversableLike[_, _], delta: Int) {
-    if (coll.isInstanceOf[collection.IndexedSeqLike[_,_]]) {
-      sizeHint(coll.size + delta)
+    coll.sizeHintIfCheap match {
+      case -1 =>
+      case n => sizeHint(n + delta)
     }
   }
 
@@ -112,8 +113,10 @@ trait Builder[-Elem, +To] extends Growable[Elem] {
    *                       than collection's size are reduced.
    */
   def sizeHintBounded(size: Int, boundingColl: TraversableLike[_, _]) {
-    if (boundingColl.isInstanceOf[collection.IndexedSeqLike[_,_]])
-      sizeHint(size min boundingColl.size)
+    boundingColl.sizeHintIfCheap match {
+      case -1 =>
+      case n => sizeHint(size min n)
+    }
   }
 
   /** Creates a new builder by applying a transformation function to