From cdeafeafd252b20a0df5440e0420211af95e0cdc Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Mon, 24 Feb 2014 13:21:24 +0100 Subject: Resetting uniques and hashset reorg. Uniques are now cleared after each run. Also, HashSets get a more standard API, without a label, but with configurable load factor. --- src/dotty/tools/dotc/Compiler.scala | 6 +- src/dotty/tools/dotc/core/Contexts.scala | 15 ++-- src/dotty/tools/dotc/core/Uniques.scala | 6 +- src/dotty/tools/dotc/util/HashSet.scala | 113 +++++++++++++++++-------------- src/dotty/tools/dotc/util/Stats.scala | 2 +- 5 files changed, 83 insertions(+), 59 deletions(-) (limited to 'src/dotty/tools/dotc') diff --git a/src/dotty/tools/dotc/Compiler.scala b/src/dotty/tools/dotc/Compiler.scala index f6723ddf4..38e3c8fd8 100644 --- a/src/dotty/tools/dotc/Compiler.scala +++ b/src/dotty/tools/dotc/Compiler.scala @@ -30,6 +30,8 @@ class Compiler { (start.withRunInfo(new RunInfo(start)) /: defn.RootImports)(addImport) } - def newRun(implicit ctx: Context): Run = - new Run(this)(rootContext) + def newRun(implicit ctx: Context): Run = { + try new Run(this)(rootContext) + finally ctx.base.reset() + } } \ No newline at end of file diff --git a/src/dotty/tools/dotc/core/Contexts.scala b/src/dotty/tools/dotc/core/Contexts.scala index 859475cd5..cfaa3720f 100644 --- a/src/dotty/tools/dotc/core/Contexts.scala +++ b/src/dotty/tools/dotc/core/Contexts.scala @@ -422,7 +422,7 @@ object Contexts { // Types state /** A table for hash consing unique types */ - private[core] val uniques = new util.HashSet[Type]("uniques", initialUniquesCapacity) { + private[core] val uniques = new util.HashSet[Type](initialUniquesCapacity) { override def hash(x: Type): Int = x.hash } @@ -435,11 +435,14 @@ object Contexts { /** A table for hash consing unique type bounds */ private[core] val uniqueTypeBounds = new TypeBoundsUniques - private def uniqueMaps = List(uniques, uniqueRefinedTypes, uniqueNamedTypes, uniqueTypeBounds) + private def uniqueSets = Map( + "uniques" -> uniques, + "uniqueRefinedTypes" -> uniqueRefinedTypes, + "uniqueNamedTypes" -> uniqueNamedTypes, + "uniqueTypeBounds" -> 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 + def uniquesSizes: Map[String, Int] = uniqueSets.mapValues(_.size) /** The number of recursive invocation of underlying on a NamedType * during a controlled operation. @@ -465,6 +468,10 @@ object Contexts { /** Should warnings and errors containing non-sensical strings be suppressed? */ private[dotc] var suppressNonSensicalErrors = true + + def reset() = { + for ((_, set) <- uniqueSets) set.clear() + } } object Context { diff --git a/src/dotty/tools/dotc/core/Uniques.scala b/src/dotty/tools/dotc/core/Uniques.scala index 9ad736c9c..5e5b3e225 100644 --- a/src/dotty/tools/dotc/core/Uniques.scala +++ b/src/dotty/tools/dotc/core/Uniques.scala @@ -39,7 +39,7 @@ object Uniques { ) */ - final class NamedTypeUniques extends HashSet[NamedType]("uniqueNamedTypes", initialUniquesCapacity) with Hashable { + final class NamedTypeUniques extends HashSet[NamedType](initialUniquesCapacity) with Hashable { override def hash(x: NamedType): Int = x.hash private def findPrevious(h: Int, prefix: Type, name: Name): NamedType = { @@ -65,7 +65,7 @@ object Uniques { } } - final class TypeBoundsUniques extends HashSet[TypeBounds]("uniqueTypeBounds", initialUniquesCapacity) with Hashable { + final class TypeBoundsUniques extends HashSet[TypeBounds](initialUniquesCapacity) with Hashable { override def hash(x: TypeBounds): Int = x.hash private def findPrevious(h: Int, lo: Type, hi: Type, variance: Int): TypeBounds = { @@ -92,7 +92,7 @@ object Uniques { } } - final class RefinedUniques extends HashSet[RefinedType]("uniqueRefinedTypes", initialUniquesCapacity) with Hashable { + final class RefinedUniques extends HashSet[RefinedType](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 diff --git a/src/dotty/tools/dotc/util/HashSet.scala b/src/dotty/tools/dotc/util/HashSet.scala index 44646e2ba..3c8ffa251 100644 --- a/src/dotty/tools/dotc/util/HashSet.scala +++ b/src/dotty/tools/dotc/util/HashSet.scala @@ -1,51 +1,57 @@ -/* NSC -- new Scala compiler - * Copyright 2005-2012 LAMP/EPFL - * @author Martin Odersky - */ - package dotty.tools.dotc.util -object HashSet { - def apply[T >: Null <: AnyRef](): HashSet[T] = this(16) - def apply[T >: Null <: AnyRef](label: String): HashSet[T] = this(label, 16) - def apply[T >: Null <: AnyRef](initialCapacity: Int): HashSet[T] = this("No Label", initialCapacity) - def apply[T >: Null <: AnyRef](label: String, initialCapacity: Int): HashSet[T] = - new HashSet[T](label, initialCapacity) -} - -class HashSet[T >: Null <: AnyRef](val label: String, initialCapacity: Int) extends Set[T] with scala.collection.generic.Clearable { - private var used = 0 - private var table = new Array[AnyRef](initialCapacity) - private def index(x: Int): Int = math.abs(x % table.length) +/** A hash set that allows some priviliged protected access to its internals + */ +class HashSet[T >: Null <: AnyRef](initialCapacity: Int, loadFactor: Float = 0.25f) extends Set[T] with scala.collection.generic.Clearable { + private var used: Int = _ + private var limit: Int = _ + private var table: Array[AnyRef] = _ - def hash(x: T): Int = x.hashCode + clear() + /** The number of elements in the set */ def size: Int = used + + private def allocate(size: Int) = { + table = new Array[AnyRef](size) + limit = (size * loadFactor).toInt + } + + /** Remove all elements from this set and set back to initial configuration */ def clear(): Unit = { used = 0 - table = new Array[AnyRef](initialCapacity) + allocate(initialCapacity) } + /** Turn hashode `x` into a table index */ + private def index(x: Int): Int = math.abs(x % table.length) + + /** Hashcode, can be overridden */ + def hash(x: T): Int = x.hashCode + + /** Find entry such that `x equals entry`. If it exists, return it. + * If not, enter `x` in set and return `x`. + */ def findEntryOrUpdate(x: T): T = { var h = index(hash(x)) var entry = table(h) while (entry ne null) { - if (x equals entry) - return entry.asInstanceOf[T] - + if (x equals entry) return entry.asInstanceOf[T] h = index(h + 1) entry = table(h) } addEntryAt(h, x) } - private def addEntryAt(h: Int, x: T) = { - table(h) = x + /** Add entry at `x` at index `idx` */ + private def addEntryAt(idx: Int, x: T) = { + table(idx) = x used += 1 - if (used > (table.length >> 2)) growTable() + if (used > limit) growTable() x } + /** The entry in the set such that `x equals entry`, or else `null`. */ def findEntry(x: T): T = { var h = index(hash(x)) var entry = table(h) @@ -58,23 +64,7 @@ class HashSet[T >: Null <: AnyRef](val label: String, initialCapacity: Int) exte 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) - + /** Add entry `x` to set */ def addEntry(x: T): Unit = { var h = index(hash(x)) var entry = table(h) @@ -87,10 +77,13 @@ class HashSet[T >: Null <: AnyRef](val label: String, initialCapacity: Int) exte used += 1 if (used > (table.length >> 2)) growTable() } + + /** Add all entries in `xs` to set */ def addEntries(xs: TraversableOnce[T]): Unit = { xs foreach addEntry } + /** The iterator of all elements in the set */ def iterator = new Iterator[T] { private var i = 0 def hasNext: Boolean = { @@ -102,6 +95,32 @@ class HashSet[T >: Null <: AnyRef](val label: String, initialCapacity: Int) exte else null } + /** Privileged access: Find first entry with given hashcode */ + protected def findEntryByHash(hashCode: Int): T = { + rover = index(hashCode) + nextEntryByHash(hashCode) + } + + /** Privileged access: Find next entry with given hashcode. Needs to immediately + * follow a `findEntryByhash` or `nextEntryByHash` operation. + */ + 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 + } + + /** Privileged access: Add entry `x` at the last position where an unsuccsessful + * `findEntryByHash` or `nextEntryByhash` operation returned. Needs to immediately + * follow a `findEntryByhash` or `nextEntryByHash` operation that was unsucessful, + * i.e. that returned `null`. + */ + protected def addEntryAfterScan(x: T): T = addEntryAt(rover, x) + private def addOldEntry(x: T): Unit = { var h = index(hash(x)) var entry = table(h) @@ -114,12 +133,7 @@ class HashSet[T >: Null <: AnyRef](val label: String, initialCapacity: Int) exte private def growTable(): Unit = { val oldtable = table - val growthFactor = - if (table.length <= initialCapacity) 8 - else if (table.length <= (initialCapacity * 8)) 4 - else 2 - - table = new Array[AnyRef](table.length * growthFactor) + allocate(table.length * 2) var i = 0 while (i < oldtable.length) { val entry = oldtable(i) @@ -127,5 +141,6 @@ class HashSet[T >: Null <: AnyRef](val label: String, initialCapacity: Int) exte i += 1 } } - override def toString() = "HashSet %s(%d / %d)".format(label, used, table.length) + + override def toString() = "HashSet(%d / %d)".format(used, table.length) } diff --git a/src/dotty/tools/dotc/util/Stats.scala b/src/dotty/tools/dotc/util/Stats.scala index a535f203c..09dfd894d 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"sizes: ${ctx.base.uniquesSize}") + println(s"sizes: ${ctx.base.uniquesSizes}") } } else op } -- cgit v1.2.3