thread locals instead of locks for vars in Types.scala

This is one of the changes suggested by Roland in order to reduce contention
caused by reflection GIL.

Locks optimized away here are indirectly used for such fundamental operations
as subtyping tests, so the optimization looks quite important.

9 files changed, 148 insertions, 106 deletions

diff --git a/src/reflect/scala/reflect/internal/Types.scala b/src/reflect/scala/reflect/internal/Types.scala
index 63ea9d2f31..204a2e7088 100644
--- a/src/reflect/scala/reflect/internal/Types.scala
+++ b/src/reflect/scala/reflect/internal/Types.scala
@@ -115,14 +115,17 @@ trait Types
   /** The current skolemization level, needed for the algorithms
    *  in isSameType, isSubType that do constraint solving under a prefix.
    */
-  var skolemizationLevel = 0
+  private var _skolemizationLevel = 0
+  def skolemizationLevel = _skolemizationLevel
+  def skolemizationLevel_=(value: Int) = _skolemizationLevel = value
 
   /** A map from lists to compound types that have the given list as parents.
    *  This is used to avoid duplication in the computation of base type sequences and baseClasses.
    *  It makes use of the fact that these two operations depend only on the parents,
    *  not on the refinement.
    */
-  val intersectionWitness = perRunCaches.newWeakMap[List[Type], WeakReference[Type]]()
+  private val _intersectionWitness = perRunCaches.newWeakMap[List[Type], WeakReference[Type]]()
+  def intersectionWitness = _intersectionWitness
 
   /** A proxy for a type (identified by field `underlying`) that forwards most
    *  operations to it (for exceptions, see WrappingProxy, which forwards even more operations).
@@ -1974,8 +1977,12 @@ trait Types
     def apply(value: Constant) = unique(new UniqueConstantType(value))
   }
 
-  private var volatileRecursions: Int = 0
-  private val pendingVolatiles = new mutable.HashSet[Symbol]
+  private var _volatileRecursions: Int = 0
+  def volatileRecursions = _volatileRecursions
+  def volatileRecursions_=(value: Int) = _volatileRecursions = value
+
+  private val _pendingVolatiles = new mutable.HashSet[Symbol]
+  def pendingVolatiles = _pendingVolatiles
 
   class ArgsTypeRef(pre0: Type, sym0: Symbol, args0: List[Type]) extends TypeRef(pre0, sym0, args0) {
     require(args0.nonEmpty, this)
@@ -3943,9 +3950,12 @@ trait Types
    */
   final def hasLength(xs: List[_], len: Int) = xs.lengthCompare(len) == 0
 
-  private var basetypeRecursions: Int = 0
-  private val pendingBaseTypes = new mutable.HashSet[Type]
+  private var _basetypeRecursions: Int = 0
+  def basetypeRecursions = _basetypeRecursions
+  def basetypeRecursions_=(value: Int) = _basetypeRecursions = value
 
+  private val _pendingBaseTypes = new mutable.HashSet[Type]
+  def pendingBaseTypes = _pendingBaseTypes
 
   /** Does this type have a prefix that begins with a type variable,
    *  or is it a refinement type? For type prefixes that fulfil this condition,
@@ -4445,7 +4455,9 @@ trait Types
   }
 
   /** The current indentation string for traces */
-  protected[internal] var indent: String = ""
+  private var _indent: String = ""
+  protected def indent = _indent
+  protected def indent_=(value: String) = _indent = value
 
   /** Perform operation `p` on arguments `tp1`, `arg2` and print trace of computation. */
   protected def explain[T](op: String, p: (Type, T) => Boolean, tp1: Type, arg2: T): Boolean = {
diff --git a/src/reflect/scala/reflect/internal/tpe/GlbLubs.scala b/src/reflect/scala/reflect/internal/tpe/GlbLubs.scala
index 6fa536d84c..6b33aca025 100644
--- a/src/reflect/scala/reflect/internal/tpe/GlbLubs.scala
+++ b/src/reflect/scala/reflect/internal/tpe/GlbLubs.scala
@@ -251,8 +251,11 @@ private[internal] trait GlbLubs {
       else if (isNumericSubType(t2, t1)) t1
       else IntTpe)
 
-  private val lubResults = new mutable.HashMap[(Depth, List[Type]), Type]
-  private val glbResults = new mutable.HashMap[(Depth, List[Type]), Type]
+  private val _lubResults = new mutable.HashMap[(Depth, List[Type]), Type]
+  def lubResults = _lubResults
+
+  private val _glbResults = new mutable.HashMap[(Depth, List[Type]), Type]
+  def glbResults = _glbResults
 
   /** Given a list of types, finds all the base classes they have in
     *  common, then returns a list of type constructors derived directly
diff --git a/src/reflect/scala/reflect/internal/tpe/TypeComparers.scala b/src/reflect/scala/reflect/internal/tpe/TypeComparers.scala
index 6532bce9f0..b60fecd66e 100644
--- a/src/reflect/scala/reflect/internal/tpe/TypeComparers.scala
+++ b/src/reflect/scala/reflect/internal/tpe/TypeComparers.scala
@@ -14,7 +14,8 @@ trait TypeComparers {
 
   private final val LogPendingSubTypesThreshold = TypeConstants.DefaultLogThreshhold
 
-  private val pendingSubTypes = new mutable.HashSet[SubTypePair]
+  private val _pendingSubTypes = new mutable.HashSet[SubTypePair]
+  def pendingSubTypes = _pendingSubTypes
 
   class SubTypePair(val tp1: Type, val tp2: Type) {
     override def hashCode = tp1.hashCode * 41 + tp2.hashCode
@@ -33,7 +34,9 @@ trait TypeComparers {
     override def toString = tp1+" <:<? "+tp2
   }
 
-  private var subsametypeRecursions: Int = 0
+  private var _subsametypeRecursions: Int = 0
+  def subsametypeRecursions = _subsametypeRecursions
+  def subsametypeRecursions_=(value: Int) = _subsametypeRecursions = value
 
   private def isUnifiable(pre1: Type, pre2: Type) = (
        (isEligibleForPrefixUnification(pre1) || isEligibleForPrefixUnification(pre2))
@@ -100,17 +103,13 @@ trait TypeComparers {
     //      isSameType1(tp1, tp2)
     //    }
 
-    undoLog.lock()
+    val before = undoLog.log
+    var result = false
     try {
-      val before = undoLog.log
-      var result = false
-      try {
-        result = isSameType1(tp1, tp2)
-      }
-      finally if (!result) undoLog.undoTo(before)
-      result
+      result = isSameType1(tp1, tp2)
     }
-    finally undoLog.unlock()
+    finally if (!result) undoLog.undoTo(before)
+    result
   }
   finally {
     subsametypeRecursions -= 1
@@ -256,30 +255,27 @@ trait TypeComparers {
     //      }
     //    }
 
-    undoLog.lock()
-    try {
-      val before = undoLog.log
-      var result = false
-
-      try result = { // if subtype test fails, it should not affect constraints on typevars
-        if (subsametypeRecursions >= LogPendingSubTypesThreshold) {
-          val p = new SubTypePair(tp1, tp2)
-          if (pendingSubTypes(p))
-            false
-          else
-            try {
-              pendingSubTypes += p
-              isSubType1(tp1, tp2, depth)
-            } finally {
-              pendingSubTypes -= p
-            }
-        } else {
-          isSubType1(tp1, tp2, depth)
-        }
-      } finally if (!result) undoLog.undoTo(before)
+    val before = undoLog.log
+    var result = false
+
+    try result = { // if subtype test fails, it should not affect constraints on typevars
+      if (subsametypeRecursions >= LogPendingSubTypesThreshold) {
+        val p = new SubTypePair(tp1, tp2)
+        if (pendingSubTypes(p))
+          false
+        else
+          try {
+            pendingSubTypes += p
+            isSubType1(tp1, tp2, depth)
+          } finally {
+            pendingSubTypes -= p
+          }
+      } else {
+        isSubType1(tp1, tp2, depth)
+      }
+    } finally if (!result) undoLog.undoTo(before)
 
-      result
-    } finally undoLog.unlock()
+    result
   } finally {
     subsametypeRecursions -= 1
     // XXX AM TODO: figure out when it is safe and needed to clear the log -- the commented approach below is too eager (it breaks #3281, #3866)
diff --git a/src/reflect/scala/reflect/internal/tpe/TypeConstraints.scala b/src/reflect/scala/reflect/internal/tpe/TypeConstraints.scala
index fdfe376c18..e2159d30f5 100644
--- a/src/reflect/scala/reflect/internal/tpe/TypeConstraints.scala
+++ b/src/reflect/scala/reflect/internal/tpe/TypeConstraints.scala
@@ -13,34 +13,14 @@ private[internal] trait TypeConstraints {
   /** A log of type variable with their original constraints. Used in order
     *  to undo constraints in the case of isSubType/isSameType failure.
     */
-  lazy val undoLog = newUndoLog
-
-  protected def newUndoLog = new UndoLog
+  private lazy val _undoLog = new UndoLog
+  def undoLog = _undoLog
 
   class UndoLog extends Clearable {
     private type UndoPairs = List[(TypeVar, TypeConstraint)]
     //OPT this method is public so we can do `manual inlining`
     var log: UndoPairs = List()
 
-    /*
-     * These two methods provide explicit locking mechanism that is overridden in SynchronizedUndoLog.
-     *
-     * The idea behind explicit locking mechanism is that all public methods that access mutable state
-     * will have to obtain the lock for their entire execution so both reads and writes can be kept in
-     * right order. Originally, that was achieved by overriding those public methods in
-     * `SynchronizedUndoLog` which was fine but expensive. The reason is that those public methods take
-     * thunk as argument and if we keep them non-final there's no way to make them inlined so thunks
-     * can go away.
-     *
-     * By using explicit locking we can achieve inlining.
-     *
-     * NOTE: They are made public for now so we can apply 'manual inlining' (copy&pasting into hot
-     * places implementation of `undo` or `undoUnless`). This should be changed back to protected
-     * once inliner is fixed.
-     */
-    def lock(): Unit = ()
-    def unlock(): Unit = ()
-
     // register with the auto-clearing cache manager
     perRunCaches.recordCache(this)
 
@@ -64,23 +44,16 @@ private[internal] trait TypeConstraints {
     }
 
     def clear() {
-      lock()
-      try {
-        if (settings.debug)
-          self.log("Clearing " + log.size + " entries from the undoLog.")
-        log = Nil
-      } finally unlock()
+      if (settings.debug)
+        self.log("Clearing " + log.size + " entries from the undoLog.")
+      log = Nil
     }
 
     // `block` should not affect constraints on typevars
     def undo[T](block: => T): T = {
-      lock()
-      try {
-        val before = log
-
-        try block
-        finally undoTo(before)
-      } finally unlock()
+      val before = log
+      try block
+      finally undoTo(before)
     }
   }
 
diff --git a/src/reflect/scala/reflect/internal/tpe/TypeToStrings.scala b/src/reflect/scala/reflect/internal/tpe/TypeToStrings.scala
index 16929cca0f..ebc4394d25 100644
--- a/src/reflect/scala/reflect/internal/tpe/TypeToStrings.scala
+++ b/src/reflect/scala/reflect/internal/tpe/TypeToStrings.scala
@@ -10,7 +10,9 @@ private[internal] trait TypeToStrings {
     */
   final val maxTostringRecursions = 50
 
-  private var tostringRecursions = 0
+  private var _tostringRecursions = 0
+  def tostringRecursions = _tostringRecursions
+  def tostringRecursions_=(value: Int) = _tostringRecursions = value
 
   protected def typeToString(tpe: Type): String =
     if (tostringRecursions >= maxTostringRecursions) {
diff --git a/src/reflect/scala/reflect/runtime/JavaUniverseForce.scala b/src/reflect/scala/reflect/runtime/JavaUniverseForce.scala
index 70126e713a..5f004330c3 100644
--- a/src/reflect/scala/reflect/runtime/JavaUniverseForce.scala
+++ b/src/reflect/scala/reflect/runtime/JavaUniverseForce.scala
@@ -29,6 +29,19 @@ trait JavaUniverseForce { self: runtime.JavaUniverse  =>
     this.treeInfo
     this.gil
     // inaccessible: this.uniqueLock
+    // inaccessible: this._skolemizationLevel
+    // inaccessible: this._undoLog
+    // inaccessible: this._intersectionWitness
+    // inaccessible: this._volatileRecursions
+    // inaccessible: this._pendingVolatiles
+    // inaccessible: this._subsametypeRecursions
+    // inaccessible: this._pendingSubTypes
+    // inaccessible: this._basetypeRecursions
+    // inaccessible: this._pendingBaseTypes
+    // inaccessible: this._lubResults
+    // inaccessible: this._glbResults
+    // inaccessible: this._indent
+    // inaccessible: this._tostringRecursions
     // inaccessible: this.nextIdLock
     // inaccessible: this.freshExistentialNameLock
     // inaccessible: this.mirrors
@@ -166,7 +179,7 @@ trait JavaUniverseForce { self: runtime.JavaUniverse  =>
     this.unwrapToStableClass
     this.unwrapWrapperTypes
     this.RecoverableCyclicReference
-    this.undoLog
+    // inaccessible: this._undoLog
     // inaccessible: this.numericLoBound
     // inaccessible: this.numericHiBound
     this.TypeConstraint
diff --git a/src/reflect/scala/reflect/runtime/SymbolTable.scala b/src/reflect/scala/reflect/runtime/SymbolTable.scala
index 7630fffd16..ddbf3bd629 100644
--- a/src/reflect/scala/reflect/runtime/SymbolTable.scala
+++ b/src/reflect/scala/reflect/runtime/SymbolTable.scala
@@ -9,7 +9,7 @@ import scala.reflect.internal.Flags._
  *  It can be used either from a reflexive universe (class scala.reflect.runtime.JavaUniverse), or else from
  *  a runtime compiler that uses reflection to get a class information (class scala.tools.reflect.ReflectGlobal)
  */
-private[scala] trait SymbolTable extends internal.SymbolTable with JavaMirrors with SymbolLoaders with SynchronizedOps with Gil {
+private[scala] trait SymbolTable extends internal.SymbolTable with JavaMirrors with SymbolLoaders with SynchronizedOps with Gil with ThreadLocalStorage {
 
   def info(msg: => String) =
     if (settings.verbose) println("[reflect-compiler] "+msg)
diff --git a/src/reflect/scala/reflect/runtime/SynchronizedTypes.scala b/src/reflect/scala/reflect/runtime/SynchronizedTypes.scala
index 4ea2d703c4..de78e527a7 100644
--- a/src/reflect/scala/reflect/runtime/SynchronizedTypes.scala
+++ b/src/reflect/scala/reflect/runtime/SynchronizedTypes.scala
@@ -2,8 +2,9 @@ package scala
 package reflect
 package runtime
 
-import scala.collection.mutable.WeakHashMap
-import java.lang.ref.WeakReference
+import scala.collection.mutable
+import java.lang.ref.{WeakReference => jWeakRef}
+import scala.ref.{WeakReference => sWeakRef}
 import scala.reflect.internal.Depth
 
 /** This trait overrides methods in reflect.internal, bracketing
@@ -17,7 +18,7 @@ private[reflect] trait SynchronizedTypes extends internal.Types { self: SymbolTa
   // we can keep this lock fine-grained, because super.unique just updates the cache
   // and, in particular, doesn't call any reflection APIs which makes deadlocks impossible
   private lazy val uniqueLock = new Object
-  private val uniques = WeakHashMap[Type, WeakReference[Type]]()
+  private val uniques = mutable.WeakHashMap[Type, jWeakRef[Type]]()
   override def unique[T <: Type](tp: T): T = uniqueLock.synchronized {
     // we need to have weak uniques for runtime reflection
     // because unlike the normal compiler universe, reflective universe isn't organized in runs
@@ -31,7 +32,7 @@ private[reflect] trait SynchronizedTypes extends internal.Types { self: SymbolTa
       val result = if (inCache.isDefined) inCache.get.get else null
       if (result ne null) result.asInstanceOf[T]
       else {
-        uniques(tp) = new WeakReference(tp)
+        uniques(tp) = new jWeakRef(tp)
         tp
       }
     } else {
@@ -39,36 +40,50 @@ private[reflect] trait SynchronizedTypes extends internal.Types { self: SymbolTa
     }
   }
 
-  class SynchronizedUndoLog extends UndoLog {
-    final override def lock(): Unit = gil.lock()
-    final override def unlock(): Unit = gil.unlock()
-  }
+  private lazy val _skolemizationLevel = mkThreadLocalStorage(0)
+  override def skolemizationLevel = _skolemizationLevel.get
+  override def skolemizationLevel_=(value: Int) = _skolemizationLevel.set(value)
+
+  private lazy val _undoLog = mkThreadLocalStorage(new UndoLog)
+  override def undoLog = _undoLog.get
+
+  private lazy val _intersectionWitness = mkThreadLocalStorage(perRunCaches.newWeakMap[List[Type], sWeakRef[Type]]())
+  override def intersectionWitness = _intersectionWitness.get
+
+  private lazy val _volatileRecursions = mkThreadLocalStorage(0)
+  override def volatileRecursions = _volatileRecursions.get
+  override def volatileRecursions_=(value: Int) = _volatileRecursions.set(value)
 
-  override protected def newUndoLog = new SynchronizedUndoLog
+  private lazy val _pendingVolatiles = mkThreadLocalStorage(new mutable.HashSet[Symbol])
+  override def pendingVolatiles = _pendingVolatiles.get
 
-  override protected def baseTypeOfNonClassTypeRef(tpe: NonClassTypeRef, clazz: Symbol) =
-    gilSynchronized { super.baseTypeOfNonClassTypeRef(tpe, clazz) }
+  private lazy val _subsametypeRecursions = mkThreadLocalStorage(0)
+  override def subsametypeRecursions = _subsametypeRecursions.get
+  override def subsametypeRecursions_=(value: Int) = _subsametypeRecursions.set(value)
 
-  override def isSameType(tp1: Type, tp2: Type): Boolean =
-    gilSynchronized { super.isSameType(tp1, tp2) }
+  private lazy val _pendingSubTypes = mkThreadLocalStorage(new mutable.HashSet[SubTypePair])
+  override def pendingSubTypes = _pendingSubTypes.get
 
-  override def isDifferentType(tp1: Type, tp2: Type): Boolean =
-    gilSynchronized { super.isDifferentType(tp1, tp2) }
+  private lazy val _basetypeRecursions = mkThreadLocalStorage(0)
+  override def basetypeRecursions = _basetypeRecursions.get
+  override def basetypeRecursions_=(value: Int) = _basetypeRecursions.set(value)
 
-  override def isSubType(tp1: Type, tp2: Type, depth: Depth): Boolean =
-    gilSynchronized { super.isSubType(tp1, tp2, depth) }
+  private lazy val _pendingBaseTypes = mkThreadLocalStorage(new mutable.HashSet[Type])
+  override def pendingBaseTypes = _pendingBaseTypes.get
 
-  override def glb(ts: List[Type]): Type =
-    gilSynchronized { super.glb(ts) }
+  private lazy val _lubResults = mkThreadLocalStorage(new mutable.HashMap[(Depth, List[Type]), Type])
+  override def lubResults = _lubResults.get
 
-  override def lub(ts: List[Type]): Type =
-    gilSynchronized { super.lub(ts) }
+  private lazy val _glbResults = mkThreadLocalStorage(new mutable.HashMap[(Depth, List[Type]), Type])
+  override def glbResults = _glbResults.get
 
-  override protected def explain[T](op: String, p: (Type, T) => Boolean, tp1: Type, arg2: T): Boolean =
-    gilSynchronized { super.explain(op, p, tp1, arg2) }
+  private lazy val _indent = mkThreadLocalStorage("")
+  override def indent = _indent.get
+  override def indent_=(value: String) = _indent.set(value)
 
-  override protected def typeToString(tpe: Type): String =
-    gilSynchronized(super.typeToString(tpe))
+  private lazy val _tostringRecursions = mkThreadLocalStorage(0)
+  override def tostringRecursions = _tostringRecursions.get
+  override def tostringRecursions_=(value: Int) = _tostringRecursions.set(value)
 
   /* The idea of caches is as follows.
    * When in reflexive mode, a cache is either null, or one sentinal
diff --git a/src/reflect/scala/reflect/runtime/ThreadLocalStorage.scala b/src/reflect/scala/reflect/runtime/ThreadLocalStorage.scala
new file mode 100644
index 0000000000..5edc051461
--- /dev/null
+++ b/src/reflect/scala/reflect/runtime/ThreadLocalStorage.scala
@@ -0,0 +1,28 @@
+package scala.reflect
+package runtime
+
+import java.lang.Thread._
+
+private[reflect] trait ThreadLocalStorage {
+  self: SymbolTable =>
+
+  // see a discussion at scala-internals for more information:
+  // http://groups.google.com/group/scala-internals/browse_thread/thread/337ce68aa5e51f79
+  trait ThreadLocalStorage[T] { def get: T; def set(newValue: T): Unit }
+  private class MyThreadLocalStorage[T](initialValue: => T) extends ThreadLocalStorage[T] {
+    // TODO: how do we use org.cliffc.high_scale_lib.NonBlockingHashMap here?
+    val values = new java.util.concurrent.ConcurrentHashMap[Thread, T]()
+    def get: T = {
+      if (values containsKey currentThread) values.get(currentThread)
+      else {
+        val value = initialValue
+        values.putIfAbsent(currentThread, value)
+        value
+      }
+    }
+    def set(newValue: T): Unit = {
+      values.put(currentThread, newValue)
+    }
+  }
+  @inline final def mkThreadLocalStorage[T](x: => T): ThreadLocalStorage[T] = new MyThreadLocalStorage(x)
+}