New treatment of uniques

To avoid to always create a type before checking its uniqueness we specialize on the three most common categories: RefinedTypes, TypeBounds and NamedTypes.

Each category gets its own uniques map. Hashing is disentangled from Types.

The new treatement seems to give some improvement (2-5%?) but not much.

10 files changed, 300 insertions, 145 deletions

diff --git a/src/dotty/tools/dotc/core/Contexts.scala b/src/dotty/tools/dotc/core/Contexts.scala
index 8c2e0fbb3..d9116d2b6 100644
--- a/src/dotty/tools/dotc/core/Contexts.scala
+++ b/src/dotty/tools/dotc/core/Contexts.scala
@@ -10,6 +10,7 @@ import Types._
 import Symbols._
 import Scopes._
 import NameOps._
+import Uniques._
 import SymDenotations._
 import util.Positions._
 import ast.Trees._
@@ -427,7 +428,20 @@ object Contexts {
       override def hash(x: Type): Int = x.hash
     }
 
-    private[dotc] def uniquesSize = uniques.size
+    /** A table for hash consing unique refined types */
+    private[core] val uniqueRefinedTypes = new RefinedUniques
+
+    /** A table for hash consing unique named types */
+    private[core] val uniqueNamedTypes = new NamedTypeUniques
+
+    /** A table for hash consing unique type bounds */
+    private[core] val uniqueTypeBounds = new TypeBoundsUniques
+
+    private def uniqueMaps = List(uniques, uniqueRefinedTypes, uniqueNamedTypes, uniqueTypeBounds)
+
+    /** A map that associates label and size of all uniques sets */
+    def uniquesSize: Map[String, Int] =
+      uniqueMaps.map(m => m.label -> m.size).toMap
 
     /** The number of recursive invocation of underlying on a NamedType
      *  during a controlled operation.
@@ -475,7 +489,7 @@ object Contexts {
   private final val InitialSuperIdsSize = 4096
 
   /** Initial capacity of uniques HashMap */
-  private[core] final val initialUniquesCapacity = 50000
+  private[core] final val initialUniquesCapacity = 40000
 
   /** How many recursive calls to NamedType#underlying are performed before
    *  logging starts.
diff --git a/src/dotty/tools/dotc/core/Hashable.scala b/src/dotty/tools/dotc/core/Hashable.scala
new file mode 100644
index 000000000..2f55ef70a
--- /dev/null
+++ b/src/dotty/tools/dotc/core/Hashable.scala
@@ -0,0 +1,92 @@
+package dotty.tools.dotc
+package core
+
+import Types._
+import scala.util.hashing.{ MurmurHash3 => hashing }
+
+object Hashable {
+
+  /** A hash value indicating that the underlying type is not
+   *  cached in uniques.
+   */
+  final val NotCached = 0
+
+  /** An alternative value returned from `hash` if the
+   *  computed hashCode would be `NotCached`.
+   */
+  private[core] final val NotCachedAlt = Int.MinValue
+
+  /** A value that indicates that the hash code is unknown
+   */
+  private[core] final val HashUnknown = 1234
+
+  /** An alternative value if computeHash would otherwise yield HashUnknown
+   */
+  private[core] final val HashUnknownAlt = 4321
+}
+
+trait Hashable {
+  import Hashable._
+
+  protected def hashSeed: Int = getClass.hashCode
+
+  private def finishHash(hashCode: Int, arity: Int): Int =
+    avoidNotCached(hashing.finalizeHash(hashCode, arity))
+
+  protected final def identityHash = avoidNotCached(System.identityHashCode(this))
+
+  protected final def avoidNotCached(h: Int) = if (h == NotCached) NotCachedAlt else h
+
+  private def finishHash(seed: Int, arity: Int, tp: Type): Int = {
+    val elemHash = tp.hash
+    if (elemHash == NotCached) return NotCached
+    finishHash(hashing.mix(seed, elemHash), arity + 1)
+  }
+
+  private def finishHash(seed: Int, arity: Int, tp1: Type, tp2: Type): Int = {
+    val elemHash = tp1.hash
+    if (elemHash == NotCached) return NotCached
+    finishHash(hashing.mix(seed, elemHash), arity + 1, tp2)
+  }
+
+  private def finishHash(seed: Int, arity: Int, tps: List[Type]): Int = {
+    var h = seed
+    var xs = tps
+    var len = arity
+    while (xs.nonEmpty) {
+      val elemHash = xs.head.hash
+      if (elemHash == NotCached) return NotCached
+      h = hashing.mix(h, elemHash)
+      xs = xs.tail
+      len += 1
+    }
+    finishHash(h, len)
+  }
+
+  private def finishHash(seed: Int, arity: Int, tp: Type, tps: List[Type]): Int = {
+    val elemHash = tp.hash
+    if (elemHash == NotCached) return NotCached
+    finishHash(hashing.mix(seed, elemHash), arity + 1, tps)
+  }
+
+  protected final def doHash(x: Any): Int =
+    finishHash(hashing.mix(hashSeed, x.hashCode), 1)
+
+  protected final def doHash(tp: Type): Int =
+    finishHash(hashSeed, 0, tp)
+
+  protected final def doHash(x1: Any, tp2: Type): Int =
+    finishHash(hashing.mix(hashSeed, x1.hashCode), 1, tp2)
+
+  protected final def doHash(tp1: Type, tp2: Type): Int =
+    finishHash(hashSeed, 0, tp1, tp2)
+
+  protected final def doHash(x1: Any, tp2: Type, tp3: Type): Int =
+    finishHash(hashing.mix(hashSeed, x1.hashCode), 1, tp2, tp3)
+
+  protected final def doHash(tp1: Type, tps2: List[Type]): Int =
+    finishHash(hashSeed, 0, tp1, tps2)
+
+  protected final def doHash(x1: Any, tp2: Type, tps3: List[Type]): Int =
+    finishHash(hashing.mix(hashSeed, x1.hashCode), 1, tp2, tps3)
+}
diff --git a/src/dotty/tools/dotc/core/SymDenotations.scala b/src/dotty/tools/dotc/core/SymDenotations.scala
index 886024325..5278a08d2 100644
--- a/src/dotty/tools/dotc/core/SymDenotations.scala
+++ b/src/dotty/tools/dotc/core/SymDenotations.scala
@@ -730,7 +730,7 @@ object SymDenotations {
 
     // ----- denotation fields and accessors ------------------------------
 
-    if (initFlags is (Module, butNot = Package)) assert(name.isModuleClassName, this)
+    if (initFlags is (Module, butNot = Package)) assert(name.isModuleClassName)
 
     /** The symbol asserted to have type ClassSymbol */
     def classSymbol: ClassSymbol = symbol.asInstanceOf[ClassSymbol]
diff --git a/src/dotty/tools/dotc/core/Symbols.scala b/src/dotty/tools/dotc/core/Symbols.scala
index b454add44..53cb38b48 100644
--- a/src/dotty/tools/dotc/core/Symbols.scala
+++ b/src/dotty/tools/dotc/core/Symbols.scala
@@ -338,8 +338,8 @@ object Symbols {
     final def isType(implicit ctx: Context): Boolean = denot.isType
     final def isClass: Boolean = isInstanceOf[ClassSymbol]
 
-    final def asTerm(implicit ctx: Context): TermSymbol = { assert(isTerm, this); asInstanceOf[TermSymbol] }
-    final def asType(implicit ctx: Context): TypeSymbol = { assert(isType, this); asInstanceOf[TypeSymbol] }
+    final def asTerm(implicit ctx: Context): TermSymbol = { assert(isTerm); asInstanceOf[TermSymbol] }
+    final def asType(implicit ctx: Context): TypeSymbol = { assert(isType); asInstanceOf[TypeSymbol] }
     final def asClass: ClassSymbol = asInstanceOf[ClassSymbol]
 
     /** A unique, densely packed integer tag for each class symbol, -1
@@ -350,7 +350,7 @@ object Symbols {
 
     /** This symbol entered into owner's scope (owner must be a class). */
     final def entered(implicit ctx: Context): this.type = {
-      assert(this.owner.isClass, this.owner.denot) // !!! DEBUG
+      assert(this.owner.isClass) // !!! DEBUG
       this.owner.asClass.enter(this)
       if (this is Module) this.owner.asClass.enter(this.moduleClass)
       this
diff --git a/src/dotty/tools/dotc/core/Types.scala b/src/dotty/tools/dotc/core/Types.scala
index 0cda02a6e..38ed09ebd 100644
--- a/src/dotty/tools/dotc/core/Types.scala
+++ b/src/dotty/tools/dotc/core/Types.scala
@@ -1,7 +1,6 @@
 package dotty.tools.dotc
 package core
 
-import util.HashSet
 import util.common._
 import Symbols._
 import Flags._
@@ -22,7 +21,8 @@ import ast.tpd._, printing.Texts._
 import ast.untpd
 import transform.Erasure
 import printing.Printer
-import scala.util.hashing.{ MurmurHash3 => hashing }
+import Hashable._
+import Uniques._
 import collection.{mutable, Seq, breakOut}
 import config.Config
 import config.Printers._
@@ -30,24 +30,6 @@ import language.implicitConversions
 
 object Types {
 
-  /** A hash value indicating that the underlying type is not
-   *  cached in uniques.
-   */
-  final val NotCached = 0
-
-  /** An alternative value returned from `hash` if the
-   *  computed hashCode would be `NotCached`.
-   */
-  private final val NotCachedAlt = Int.MinValue
-
-  /** A value that indicates that the hash code is unknown
-   */
-  private final val HashUnknown = 1234
-
-  /** An alternative value if computeHash would otherwise yield HashUnknown
-   */
-  private final val HashUnknownAlt = 4321
-
   /** The class of types.
    *  The principal subclasses and sub-objects are as follows:
    *
@@ -79,7 +61,7 @@ object Types {
    *                       +- ErrorType
    *                       +- WildcardType
    */
-  abstract class Type extends DotClass with printing.Showable {
+  abstract class Type extends DotClass with Hashable with printing.Showable {
 
 // ----- Tests -----------------------------------------------------
 
@@ -880,105 +862,20 @@ object Types {
         }
       }
       new Simplify().apply(this)
-  }
-
-// ----- hashing ------------------------------------------------------
+    }
 
     /** customized hash code of this type.
      *  NotCached for uncached types. Cached types
      *  compute hash and use it as the type's hashCode.
      */
     def hash: Int
-
-    protected def hashSeed = getClass.hashCode
-
-    private def finishHash(hashCode: Int, arity: Int): Int =
-      avoidNotCached(hashing.finalizeHash(hashCode, arity))
-
-    protected def identityHash = avoidNotCached(System.identityHashCode(this))
-
-    protected def avoidNotCached(h: Int) = if (h == NotCached) NotCachedAlt else h
-
-    private def finishHash(seed: Int, arity: Int, tp: Type): Int = {
-      val elemHash = tp.hash
-      if (elemHash == NotCached) return NotCached
-      finishHash(hashing.mix(seed, elemHash), arity + 1)
-    }
-
-    private def finishHash(seed: Int, arity: Int, tp1: Type, tp2: Type): Int = {
-      val elemHash = tp1.hash
-      if (elemHash == NotCached) return NotCached
-      finishHash(hashing.mix(seed, elemHash), arity + 1, tp2)
-    }
-
-    private def finishHash(seed: Int, arity: Int, tps: List[Type]): Int = {
-      var h = seed
-      var xs = tps
-      var len = arity
-      while (xs.nonEmpty) {
-        val elemHash = xs.head.hash
-        if (elemHash == NotCached) return NotCached
-        h = hashing.mix(h, elemHash)
-        xs = xs.tail
-        len += 1
-      }
-      finishHash(h, len)
-    }
-
-    private def finishHash(seed: Int, arity: Int, tp: Type, tps: List[Type]): Int = {
-      val elemHash = tp.hash
-      if (elemHash == NotCached) return NotCached
-      finishHash(hashing.mix(seed, elemHash), arity + 1, tps)
-    }
-
-    protected def doHash(x: Any): Int =
-      finishHash(hashing.mix(hashSeed, x.hashCode), 1)
-
-    protected def doHash(tp: Type): Int =
-      finishHash(hashSeed, 0, tp)
-
-    protected def doHash(x1: Any, tp2: Type): Int =
-      finishHash(hashing.mix(hashSeed, x1.hashCode), 1, tp2)
-
-    protected def doHash(tp1: Type, tp2: Type): Int =
-      finishHash(hashSeed, 0, tp1, tp2)
-
-    protected def doHash(x1: Any, tp2: Type, tp3: Type): Int =
-      finishHash(hashing.mix(hashSeed, x1.hashCode), 1, tp2, tp3)
-
-    protected def doHash(tp1: Type, tps2: List[Type]): Int =
-      finishHash(hashSeed, 0, tp1, tps2)
-
-    protected def doHash(x1: Any, tp2: Type, tps3: List[Type]): Int =
-      finishHash(hashing.mix(hashSeed, x1.hashCode), 1, tp2, tps3)
-
   } // end Type
 
+// ----- Type categories ----------------------------------------------
+
   /** A marker trait for cached types */
   trait CachedType extends Type
 
-  def unique[T <: Type](tp: T)(implicit ctx: Context): T = {
-    if (monitored)
-      if (tp.hash == NotCached) {
-        record("uncached-types")
-        record(s"uncached: ${tp.getClass}")
-      } else {
-        record("cached-types")
-        record(s"cached: ${tp.getClass}")
-      }
-    if (tp.hash == NotCached) tp
-    else ctx.uniques.findEntryOrUpdate(tp).asInstanceOf[T]
-  } /* !!! DEBUG
-  ensuring (
-    result => tp.toString == result.toString || {
-      println(s"cache mismatch; tp = $tp, cached = $result")
-      false
-    }
-  )
- */
-
-// ----- Type categories ----------------------------------------------
-
   /** A marker trait for type proxies.
    *  Each implementation is expected to redefine the `underlying` method.
    */
@@ -1009,7 +906,7 @@ object Types {
 
   /**  Instances of this class are cached and are proxies. */
   abstract class CachedProxyType extends TypeProxy with CachedType {
-    private[this] var myHash = HashUnknown
+    protected[this] var myHash = HashUnknown
     final def hash = {
       if (myHash == HashUnknown) {
         myHash = computeHash
@@ -1076,8 +973,7 @@ object Types {
     val prefix: Type
     val name: Name
 
-    assert(prefix.isValueType ||
-           (prefix eq NoPrefix), s"bad prefix in $prefix.$name")
+    assert(prefix.isValueType || (prefix eq NoPrefix))
 
     private[this] var lastDenotationOrSym: AnyRef = null
 
@@ -1194,7 +1090,6 @@ object Types {
       case _ =>
         false
     }
-    override def computeHash = doHash(name, prefix)
   }
 
   abstract case class TermRef(override val prefix: Type, name: TermName) extends NamedType with SingletonType {
@@ -1251,12 +1146,16 @@ object Types {
     override def computeHash = doHash(fixedSym)
   }
 
-  final class CachedTermRef(prefix: Type, name: TermName) extends TermRef(prefix, name) {
+  final class CachedTermRef(prefix: Type, name: TermName, hc: Int) extends TermRef(prefix, name) {
     assert(prefix ne NoPrefix)
+    myHash = hc
+    override def computeHash = unsupported("computeHash")
   }
 
-  final class CachedTypeRef(prefix: Type, name: TypeName) extends TypeRef(prefix, name) {
+  final class CachedTypeRef(prefix: Type, name: TypeName, hc: Int) extends TypeRef(prefix, name) {
     assert(prefix ne NoPrefix)
+    myHash = hc
+    override def computeHash = unsupported("computeHash")
   }
 
   final class NoPrefixTermRef(name: TermName, val fixedSym: TermSymbol) extends TermRef(NoPrefix, name) with WithNoPrefix
@@ -1273,7 +1172,7 @@ object Types {
 
   object TermRef {
     def apply(prefix: Type, name: TermName)(implicit ctx: Context): TermRef =
-      unique(new CachedTermRef(prefix, name))
+      ctx.uniqueNamedTypes.enterIfNew(prefix, name).asInstanceOf[TermRef]
     def apply(prefix: Type, sym: TermSymbol)(implicit ctx: Context): TermRef =
       if (prefix eq NoPrefix) unique(new NoPrefixTermRef(sym.name, sym))
       else apply(prefix, sym.name) withSym sym
@@ -1288,7 +1187,7 @@ object Types {
 
   object TypeRef {
     def apply(prefix: Type, name: TypeName)(implicit ctx: Context): TypeRef =
-      unique(new CachedTypeRef(prefix, name))
+      ctx.uniqueNamedTypes.enterIfNew(prefix, name).asInstanceOf[TypeRef]
     def apply(prefix: Type, sym: TypeSymbol)(implicit ctx: Context): TypeRef =
       if (prefix eq NoPrefix) unique(new NoPrefixTypeRef(sym.name, sym))
       else apply(prefix, sym.name) withSym sym
@@ -1400,19 +1299,22 @@ object Types {
     val refinedInfo = infoFn(this)
   }
 
-  class DirectRefinedType(parent: Type, refinedName: Name, override val refinedInfo: Type) extends RefinedType(parent, refinedName)
+  class PreHashedRefinedType(parent: Type, refinedName: Name, override val refinedInfo: Type, hc: Int)
+  extends RefinedType(parent, refinedName) {
+    myHash = hc
+    override def computeHash = unsupported("computeHash")
+  }
 
   object RefinedType {
     def make(parent: Type, names: List[Name], infoFns: List[RefinedType => Type])(implicit ctx: Context): Type =
       if (names.isEmpty) parent
       else make(RefinedType(parent, names.head, infoFns.head), names.tail, infoFns.tail)
 
-    def apply(parent: Type, name: Name, infoFn: RefinedType => Type)(implicit ctx: Context): RefinedType = {
-      unique(new CachedRefinedType(parent, name, infoFn))
-    }
+    def apply(parent: Type, name: Name, infoFn: RefinedType => Type)(implicit ctx: Context): RefinedType =
+      ctx.base.uniqueRefinedTypes.enterIfNew(new CachedRefinedType(parent, name, infoFn))
 
     def apply(parent: Type, name: Name, info: Type)(implicit ctx: Context): RefinedType = {
-      unique(new DirectRefinedType(parent, name, info))
+      ctx.base.uniqueRefinedTypes.enterIfNew(parent, name, info)
     }
   }
 
@@ -1444,7 +1346,7 @@ object Types {
 
   object AndType {
     def apply(tp1: Type, tp2: Type)(implicit ctx: Context) = {
-      assert(tp1.isInstanceOf[ValueType] && tp2.isInstanceOf[ValueType], s"$tp1 & $tp2")
+      assert(tp1.isInstanceOf[ValueType] && tp2.isInstanceOf[ValueType])
       unchecked(tp1, tp2)
     }
     def unchecked(tp1: Type, tp2: Type)(implicit ctx: Context) = {
@@ -1453,7 +1355,7 @@ object Types {
   }
 
   abstract case class OrType(tp1: Type, tp2: Type) extends CachedGroundType with AndOrType {
-    assert(tp1.isInstanceOf[ValueType] && tp2.isInstanceOf[ValueType], s"$tp1 | $tp2")
+    assert(tp1.isInstanceOf[ValueType] && tp2.isInstanceOf[ValueType])
 
     def isAnd = false
 
@@ -1509,7 +1411,7 @@ object Types {
     extends CachedGroundType with BindingType with TermType with MethodOrPoly { thisMethodType =>
 
     override val resultType = resultTypeExp(this)
-    assert(resultType != NoType, this)
+    assert(resultType != NoType)
     def isJava = false
     def isImplicit = false
 
@@ -1927,8 +1829,8 @@ object Types {
   /** Type bounds >: lo <: hi */
   abstract case class TypeBounds(lo: Type, hi: Type) extends CachedProxyType with TypeType {
 
-    assert(lo.isInstanceOf[TermType], lo+" "+lo.getClass)
-    assert(hi.isInstanceOf[TermType], hi+" "+hi.getClass)
+    assert(lo.isInstanceOf[TermType])
+    assert(hi.isInstanceOf[TermType])
 
     def variance: Int = 0
 
@@ -2000,29 +1902,27 @@ object Types {
       TypeBounds(substBoundSyms(lo)(hkBound), AndType(hkBound, substBoundSyms(hi)(hkBound)))
     }
 
-    override def computeHash = doHash(lo, hi)
-
     override def toString =
       if (lo eq hi) s"TypeAlias($lo)" else s"TypeBounds($lo, $hi)"
   }
 
-  final class CachedTypeBounds(lo: Type, hi: Type) extends TypeBounds(lo, hi)
-  final class CoTypeBounds(lo: Type, hi: Type) extends TypeBounds(lo, hi) {
+  class CachedTypeBounds(lo: Type, hi: Type, hc: Int) extends TypeBounds(lo, hi) {
+    myHash = hc
+    override def computeHash = unsupported("computeHash")
+  }
+
+  final class CoTypeBounds(lo: Type, hi: Type, hc: Int) extends CachedTypeBounds(lo, hi, hc) {
     override def variance = 1
     override def toString = "Co" + super.toString
   }
-  final class ContraTypeBounds(lo: Type, hi: Type) extends TypeBounds(lo, hi) {
+  final class ContraTypeBounds(lo: Type, hi: Type, hc: Int) extends CachedTypeBounds(lo, hi, hc) {
     override def variance = -1
     override def toString = "Contra" + super.toString
   }
 
   object TypeBounds {
     def apply(lo: Type, hi: Type, variance: Int = 0)(implicit ctx: Context): TypeBounds =
-      unique(
-        if (variance == 0) new CachedTypeBounds(lo, hi)
-        else if (variance == 1) new CoTypeBounds(lo, hi)
-        else new ContraTypeBounds(lo, hi)
-      )
+      ctx.uniqueTypeBounds.enterIfNew(lo, hi, variance)
     def empty(implicit ctx: Context) = apply(defn.NothingType, defn.AnyType)
     def upper(hi: Type, variance: Int = 0)(implicit ctx: Context) = apply(defn.NothingType, hi, variance)
     def lower(lo: Type, variance: Int = 0)(implicit ctx: Context) = apply(lo, defn.AnyType, variance)
diff --git a/src/dotty/tools/dotc/core/Uniques.scala b/src/dotty/tools/dotc/core/Uniques.scala
new file mode 100644
index 000000000..765b5d73f
--- /dev/null
+++ b/src/dotty/tools/dotc/core/Uniques.scala
@@ -0,0 +1,124 @@
+package dotty.tools.dotc
+package core
+
+import Types._, Contexts._, util.Stats._, Hashable._, Names._
+import util.HashSet
+
+/** Defines operation `unique` for hash-consing types.
+ *  Also defines specialized hash sets for hash consing uniques of a specific type.
+ *  All sets offer a `enterIfNew` method which checks whether a type
+ *  with the given parts exists already and creates a new one if not.
+ */
+object Uniques {
+
+  private def recordCaching(tp: Type): Unit = recordCaching(tp.hash, tp.getClass)
+  private def recordCaching(h: Int, clazz: Class[_]): Unit =
+    if (h == NotCached) {
+      record("uncached-types")
+      record(s"uncached: $clazz")
+    } else {
+      record("cached-types")
+      record(s"cached: $clazz")
+    }
+
+  def unique[T <: Type](tp: T)(implicit ctx: Context): T = {
+    if (monitored) recordCaching(tp)
+    if (tp.hash == NotCached) tp
+    else ctx.uniques.findEntryOrUpdate(tp).asInstanceOf[T]
+  } /* !!! DEBUG
+  ensuring (
+    result => tp.toString == result.toString || {
+      println(s"cache mismatch; tp = $tp, cached = $result")
+      false
+    }
+  )
+ */
+
+  final class NamedTypeUniques extends HashSet[NamedType]("uniqueNamedTypes", initialUniquesCapacity) with Hashable {
+    override def hash(x: NamedType): Int = x.hash
+
+    private def findPrevious(h: Int, prefix: Type, name: Name): NamedType = {
+      var e = findEntryByHash(h)
+      while (e != null) {
+        if ((e.prefix == prefix) && (e.name eq name)) return e
+        e = nextEntryByHash(h)
+      }
+      e
+    }
+
+    def enterIfNew(prefix: Type, name: Name): NamedType = {
+      val h = doHash(name, prefix)
+      if (monitored) recordCaching(h, classOf[CachedTermRef])
+      def newType =
+        if (name.isTypeName) new CachedTypeRef(prefix, name.asTypeName, h)
+        else new CachedTermRef(prefix, name.asTermName, h)
+      if (h == NotCached) newType
+      else {
+        val r = findPrevious(h, prefix, name)
+        if (r ne null) r else addEntryAfterScan(newType)
+      }
+    }
+  }
+
+  final class TypeBoundsUniques extends HashSet[TypeBounds]("uniqueTypeBounds", initialUniquesCapacity) with Hashable {
+    override def hash(x: TypeBounds): Int = x.hash
+
+    private def findPrevious(h: Int, lo: Type, hi: Type, variance: Int): TypeBounds = {
+      var e = findEntryByHash(h)
+      while (e != null) {
+        if ((e.lo == lo) && (e.hi == hi) && (e.variance == variance)) return e
+        e = nextEntryByHash(h)
+      }
+      e
+    }
+
+    def enterIfNew(lo: Type, hi: Type, variance: Int): TypeBounds = {
+      val h = doHash(variance, lo, hi)
+      if (monitored) recordCaching(h, classOf[TypeBounds])
+      def newBounds =
+        if (variance == 0) new CachedTypeBounds(lo, hi, h)
+        else if (variance == 1) new CoTypeBounds(lo, hi, h)
+        else new ContraTypeBounds(lo, hi, h)
+      if (h == NotCached) newBounds
+      else {
+        val r = findPrevious(h, lo, hi, variance)
+        if (r ne null) r else addEntryAfterScan(newBounds)
+      }
+    }
+  }
+
+  final class RefinedUniques extends HashSet[RefinedType]("uniqueRefinedTypes", initialUniquesCapacity) with Hashable {
+    override val hashSeed = classOf[CachedRefinedType].hashCode // some types start life as CachedRefinedTypes, need to have same hash seed
+    override def hash(x: RefinedType): Int = x.hash
+
+    private def findPrevious(h: Int, parent: Type, refinedName: Name, refinedInfo: Type): RefinedType = {
+      var e = findEntryByHash(h)
+      while (e != null) {
+        if ((e.parent == parent) && (e.refinedName eq refinedName) && (e.refinedInfo == refinedInfo))
+          return e
+        e = nextEntryByHash(h)
+      }
+      e
+    }
+
+    def enterIfNew(parent: Type, refinedName: Name, refinedInfo: Type): RefinedType = {
+      val h = doHash(refinedName, refinedInfo, parent)
+      def newType = new PreHashedRefinedType(parent, refinedName, refinedInfo, h)
+      if (monitored) recordCaching(h, classOf[PreHashedRefinedType])
+      if (h == NotCached) newType
+      else {
+        val r = findPrevious(h, parent, refinedName, refinedInfo)
+        if (r ne null) r else addEntryAfterScan(newType)
+      }
+    }
+
+    def enterIfNew(rt: RefinedType) = {
+      if (monitored) recordCaching(rt)
+      if (rt.hash == NotCached) rt
+      else {
+        val r = findPrevious(rt.hash, rt.parent, rt.refinedName, rt.refinedInfo)
+        if (r ne null) r else addEntryAfterScan(rt)
+      }
+    }
+  }
+}
\ No newline at end of file
diff --git a/src/dotty/tools/dotc/typer/Implicits.scala b/src/dotty/tools/dotc/typer/Implicits.scala
index 8a1b9f554..a8985cf36 100644
--- a/src/dotty/tools/dotc/typer/Implicits.scala
+++ b/src/dotty/tools/dotc/typer/Implicits.scala
@@ -23,6 +23,7 @@ import Constants._
 import Inferencing._
 import Applications._
 import ErrorReporting._
+import Hashable._
 import config.Config
 import config.Printers._
 import collection.mutable
diff --git a/src/dotty/tools/dotc/typer/Inferencing.scala b/src/dotty/tools/dotc/typer/Inferencing.scala
index 3ef9f42a6..4986d257e 100644
--- a/src/dotty/tools/dotc/typer/Inferencing.scala
+++ b/src/dotty/tools/dotc/typer/Inferencing.scala
@@ -73,7 +73,8 @@ object Inferencing {
    *       [ ].name: proto
    */
   class SelectionProto(val name: Name, proto: Type, compat: Compatibility)
-  extends DirectRefinedType(WildcardType, name, proto) with ProtoType {
+  extends RefinedType(WildcardType, name) with ProtoType {
+    override val refinedInfo = proto
     override def isMatchedBy(tp1: Type)(implicit ctx: Context) =
       name == nme.WILDCARD || {
         val mbr = tp1.member(name)
diff --git a/src/dotty/tools/dotc/util/HashSet.scala b/src/dotty/tools/dotc/util/HashSet.scala
index 8d809cdf4..32c3dbc3d 100644
--- a/src/dotty/tools/dotc/util/HashSet.scala
+++ b/src/dotty/tools/dotc/util/HashSet.scala
@@ -36,6 +36,10 @@ class HashSet[T >: Null <: AnyRef](val label: String, initialCapacity: Int) exte
       h = index(h + 1)
       entry = table(h)
     }
+    addEntryAt(h, x)
+  }
+
+  private def addEntryAt(h: Int, x: T) = {
     table(h) = x
     used += 1
     if (used > (table.length >> 2)) growTable()
@@ -52,6 +56,25 @@ class HashSet[T >: Null <: AnyRef](val label: String, initialCapacity: Int) exte
     entry.asInstanceOf[T]
   }
 
+  private var rover: Int = -1
+
+  protected def findEntryByHash(hashCode: Int): T = {
+    rover = index(hashCode)
+    nextEntryByHash(hashCode)
+  }
+
+  protected def nextEntryByHash(hashCode: Int): T = {
+    var entry = table(rover)
+    while (entry ne null) {
+      rover = index(rover + 1)
+      if (hash(entry.asInstanceOf[T]) == hashCode) return entry.asInstanceOf[T]
+      entry = table(rover)
+    }
+    null
+  }
+
+  protected def addEntryAfterScan(x: T): T = addEntryAt(rover, x)
+
   def addEntry(x: T): Unit = {
     var h = index(hash(x))
     var entry = table(h)
diff --git a/src/dotty/tools/dotc/util/Stats.scala b/src/dotty/tools/dotc/util/Stats.scala
index 95b50cf58..a535f203c 100644
--- a/src/dotty/tools/dotc/util/Stats.scala
+++ b/src/dotty/tools/dotc/util/Stats.scala
@@ -63,7 +63,7 @@ object Stats {
         hb.continue = false
         println()
         println(hits.toList.sortBy(_._2).map{ case (x, y) => s"$x -> $y" } mkString "\n")
-        println(s"unique types: ${ctx.base.uniquesSize}")
+        println(s"sizes: ${ctx.base.uniquesSize}")
       }
     } else op
   }