From f7e79bfbdef1123273d5f872572a6a6d55a2cd81 Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Sun, 26 Jan 2014 12:23:21 +0100 Subject: Better caching of types Now, PolyTypes, BoundTypes and TypeVars are cached, too. This leads to the following changes: - unique types table 135K -> 310K - uncached types 923K -> 0.5K (these are types that are cachable, but contain an uncached part) - cached type allocs 3420K -> 4322K - runtime on dotc (24KLOC) 31sec -> 20sec So, it's a big net win, but we should watch the size of the uniue types table; possibly make it weak. --- src/dotty/tools/dotc/core/Types.scala | 49 +++++++++++++++++++++-------------- src/dotty/tools/dotc/util/Stats.scala | 2 +- 2 files changed, 31 insertions(+), 20 deletions(-) (limited to 'src/dotty/tools') diff --git a/src/dotty/tools/dotc/core/Types.scala b/src/dotty/tools/dotc/core/Types.scala index 197c1ec97..f0385c08e 100644 --- a/src/dotty/tools/dotc/core/Types.scala +++ b/src/dotty/tools/dotc/core/Types.scala @@ -892,10 +892,12 @@ object Types { protected def hashSeed = getClass.hashCode - private def finishHash(hashCode: Int, arity: Int): Int = { - val h = hashing.finalizeHash(hashCode, arity) - if (h == NotCached) NotCachedAlt else h - } + 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 @@ -956,14 +958,13 @@ object Types { trait CachedType extends Type def unique[T <: Type](tp: T)(implicit ctx: Context): T = { - if (tp.hash == NotCached) { - record("uncached-types") - tp - } - else { - record("cached-types") - ctx.uniques.findEntryOrUpdate(tp).asInstanceOf[T] - } + if (monitored) + if (tp.hash == NotCached) { + record("uncached-types") + record(s"uncached: ${tp.getClass}") + } else record("cached-types") + if (tp.hash == NotCached) tp + else ctx.uniques.findEntryOrUpdate(tp).asInstanceOf[T] } /* !!! DEBUG ensuring ( result => tp.toString == result.toString || { @@ -1021,11 +1022,19 @@ object Types { /** Instances of this class are uncached and are not proxies. */ abstract class UncachedGroundType extends Type { final def hash = NotCached + if (monitored) { + record(s"uncachable") + record(s"uncachable: $getClass") + } } /** Instances of this class are uncached and are proxies. */ abstract class UncachedProxyType extends TypeProxy { final def hash = NotCached + if (monitored) { + record(s"uncachable") + record(s"uncachable: $getClass") + } } /** A marker trait for types that apply only to type symbols */ @@ -1619,7 +1628,7 @@ object Types { } case class PolyType(paramNames: List[TypeName])(paramBoundsExp: PolyType => List[TypeBounds], resultTypeExp: PolyType => Type) - extends UncachedGroundType with BindingType with TermType with MethodOrPoly { + extends CachedGroundType with BindingType with TermType with MethodOrPoly { val paramBounds = paramBoundsExp(this) override val resultType = resultTypeExp(this) @@ -1643,8 +1652,8 @@ object Types { // need to override hashCode and equals to be object identity // because paramNames by itself is not discriminatory enough - override def hashCode = System.identityHashCode(this) override def equals(other: Any) = this eq other.asInstanceOf[AnyRef] + override def computeHash = identityHash override def toString = s"PolyType($paramNames, $paramBounds, $resultType)" } @@ -1663,7 +1672,7 @@ object Types { // ----- Bound types: MethodParam, PolyParam, RefiendThis -------------------------- - abstract class BoundType extends UncachedProxyType with ValueType { + abstract class BoundType extends CachedProxyType with ValueType { type BT <: BindingType def binder: BT // Dotty deviation: copyBoundType was copy, but @@ -1683,7 +1692,7 @@ object Types { def copyBoundType(bt: BT) = MethodParam(bt, paramNum) // need to customize hashCode and equals to prevent infinite recursion for dep meth types. - override def hashCode = System.identityHashCode(binder) + paramNum + override def computeHash = avoidNotCached(System.identityHashCode(binder) + paramNum) override def equals(that: Any) = that match { case that: MethodParam => (this.binder eq that.binder) && this.paramNum == that.paramNum @@ -1714,6 +1723,8 @@ object Types { override def underlying(implicit ctx: Context): Type = binder.paramBounds(paramNum) // no customized hashCode/equals needed because cycle is broken in PolyType override def toString = s"PolyParam(${binder.paramNames(paramNum)})" + + override def computeHash = doHash(paramNum, binder) } case class RefinedThis(binder: RefinedType) extends BoundType with SingletonType { @@ -1723,7 +1734,7 @@ object Types { // need to customize hashCode and equals to prevent infinite recursion for // refinements that refer to the refinement type via this - override def hashCode = System.identityHashCode(binder) + override def computeHash = identityHash override def equals(that: Any) = that match { case that: RefinedThis => this.binder eq that.binder case _ => false @@ -1746,7 +1757,7 @@ object Types { * @param owningTree The function part of the TypeApply tree tree that introduces * the type variable. */ - final class TypeVar(val origin: PolyParam, creatorState: TyperState, val owningTree: untpd.Tree) extends UncachedProxyType with ValueType { + final class TypeVar(val origin: PolyParam, creatorState: TyperState, val owningTree: untpd.Tree) extends CachedProxyType with ValueType { /** The permanent instance type of the the variable, or NoType is none is given yet */ private[core] var inst: Type = NoType @@ -1811,7 +1822,7 @@ object Types { if (inst.exists) inst else origin } - override def hashCode: Int = System.identityHashCode(this) + override def computeHash: Int = identityHash override def equals(that: Any) = this eq that.asInstanceOf[AnyRef] override def toString = { diff --git a/src/dotty/tools/dotc/util/Stats.scala b/src/dotty/tools/dotc/util/Stats.scala index efae6be34..95b50cf58 100644 --- a/src/dotty/tools/dotc/util/Stats.scala +++ b/src/dotty/tools/dotc/util/Stats.scala @@ -24,7 +24,7 @@ object Stats { } } - private var monitored = false + var monitored = false def track[T](fn: String)(op: => T) = if (monitored) { -- cgit v1.2.3