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.

1 files changed, 92 insertions, 0 deletions

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)
+}