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

1 files changed, 2 insertions, 0 deletions

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
 }