diff options
author | Jason Zaugg <jzaugg@gmail.com> | 2016-08-19 13:17:24 +1000 |
---|---|---|
committer | Jason Zaugg <jzaugg@gmail.com> | 2016-08-30 08:45:35 +1000 |
commit | 42ae254d3ca398e884bba4e587a63362b173a75e (patch) | |
tree | aa891016be7e18fe3862fcfd1c800918b70dafa1 /test/files/presentation/scope-completion-2 | |
parent | 6b82c72a0fac6e4284b270af0b17c6cacb48b291 (diff) | |
download | scala-42ae254d3ca398e884bba4e587a63362b173a75e.tar.gz scala-42ae254d3ca398e884bba4e587a63362b173a75e.tar.bz2 scala-42ae254d3ca398e884bba4e587a63362b173a75e.zip |
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
Diffstat (limited to 'test/files/presentation/scope-completion-2')
0 files changed, 0 insertions, 0 deletions