Fix and test case for #2512, plus lots of time ...

Fix and test case for #2512, plus lots of time expended tuning HashSet
starting sizes and growth rate, with almost nothing to show for it (but
I did determine that "shadowed" is constructed identically something
like 10,000 times, so there is probably a cache to be had there.)

8 files changed, 29 insertions, 16 deletions

diff --git a/src/compiler/scala/tools/nsc/ast/TreeInfo.scala b/src/compiler/scala/tools/nsc/ast/TreeInfo.scala
index 6a8f653ac4..e7b9ec9187 100644
--- a/src/compiler/scala/tools/nsc/ast/TreeInfo.scala
+++ b/src/compiler/scala/tools/nsc/ast/TreeInfo.scala
@@ -189,7 +189,7 @@ abstract class TreeInfo {
   def isLeftAssoc(operator: Name): Boolean =
     operator.length > 0 && operator(operator.length - 1) != ':'
 
-  private val reserved = new HashSet[Name]
+  private val reserved = new HashSet[Name]("reserved", 64)
   reserved addEntry nme.false_
   reserved addEntry nme.true_
   reserved addEntry nme.null_
diff --git a/src/compiler/scala/tools/nsc/ast/Trees.scala b/src/compiler/scala/tools/nsc/ast/Trees.scala
index d1a1542b9b..8ae59fb9e6 100644
--- a/src/compiler/scala/tools/nsc/ast/Trees.scala
+++ b/src/compiler/scala/tools/nsc/ast/Trees.scala
@@ -1813,7 +1813,7 @@ trait Trees {
    *  (bq:) This traverser has mutable state and should be discarded after use
    */
   class ResetAttrsTraverser(strict: Boolean) extends Traverser {
-    private val erasedSyms = new HashSet[Symbol](8)
+    private val erasedSyms = new HashSet[Symbol]("erasedSyms", 8)
     override def traverse(tree: Tree): Unit = tree match {
       case EmptyTree | TypeTree() =>
         ;
diff --git a/src/compiler/scala/tools/nsc/symtab/Types.scala b/src/compiler/scala/tools/nsc/symtab/Types.scala
index bfb3b5f487..d5e8f0d02c 100644
--- a/src/compiler/scala/tools/nsc/symtab/Types.scala
+++ b/src/compiler/scala/tools/nsc/symtab/Types.scala
@@ -2558,14 +2558,15 @@ A type's typeSymbol should never be inspected directly.
 
 // Hash consing --------------------------------------------------------------
 
-  var uniques: HashSet[AnyRef] = _
+  private val initialUniquesCapacity = 4096
+  private var uniques: HashSet[AnyRef] = _
   private var uniqueRunId = NoRunId
 
-  def uniqueTypeCount = uniques.size // for statistics
+  def uniqueTypeCount = if (uniques == null) 0 else uniques.size // for statistics
 
   private def unique[T <: AnyRef](tp: T): T = {
     if (uniqueRunId != currentRunId) {
-      uniques = new HashSet(20000)
+      uniques = new HashSet("uniques", initialUniquesCapacity)
       uniqueRunId = currentRunId
     }
     uniques.findEntry(tp) match {
diff --git a/src/compiler/scala/tools/nsc/transform/OverridingPairs.scala b/src/compiler/scala/tools/nsc/transform/OverridingPairs.scala
index af63b48d00..83ed2f1765 100644
--- a/src/compiler/scala/tools/nsc/transform/OverridingPairs.scala
+++ b/src/compiler/scala/tools/nsc/transform/OverridingPairs.scala
@@ -148,7 +148,7 @@ abstract class OverridingPairs {
      *  (maybe excluded because of hasCommonParentAsSubclass).
      *  These will not appear as overriding
      */
-    private val visited = new HashSet[ScopeEntry](256)
+    private val visited = new HashSet[ScopeEntry]("visited", 64)
 
     /** The current entry candidate for overriding
      */
diff --git a/src/compiler/scala/tools/nsc/typechecker/Implicits.scala b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala
index 54b24bf071..023c5c2920 100644
--- a/src/compiler/scala/tools/nsc/typechecker/Implicits.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala
@@ -12,9 +12,8 @@ package scala.tools.nsc
 package typechecker
 
 import scala.collection.mutable.{LinkedHashMap, ListBuffer}
-import scala.tools.nsc.util.{HashSet, Position, Set, NoPosition, SourceFile}
+import scala.tools.nsc.util.{ HashSet, Position, Set, NoPosition, SourceFile }
 import symtab.Flags._
-import util.HashSet
 
 /** This trait provides methods to find various kinds of implicits.
  *
@@ -497,7 +496,7 @@ self: Analyzer =>
                         invalidImplicits: ListBuffer[Symbol]): Map[ImplicitInfo, SearchResult] = {
 
       /** A set containing names that are shadowed by implicit infos */
-      val shadowed = new HashSet[Name](8)
+      lazy val shadowed = new HashSet[Name]("shadowed", 512)
 
       /** Try implicit `info` to see whether it is applicable for expected type `pt`.
        *  This is the case if all of the following holds:
diff --git a/src/compiler/scala/tools/nsc/typechecker/Typers.scala b/src/compiler/scala/tools/nsc/typechecker/Typers.scala
index 738c1252ab..15ac8cdf67 100644
--- a/src/compiler/scala/tools/nsc/typechecker/Typers.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Typers.scala
@@ -15,9 +15,8 @@ import scala.collection.mutable.{HashMap, ListBuffer}
 import scala.util.control.ControlException
 import scala.compat.Platform.currentTime
 import scala.tools.nsc.interactive.RangePositions
-import scala.tools.nsc.util.{HashSet, Position, Set, NoPosition, SourceFile}
+import scala.tools.nsc.util.{ Position, Set, NoPosition, SourceFile }
 import symtab.Flags._
-import util.HashSet
 
 // Suggestion check whether we can do without priming scopes with symbols of outer scopes,
 // like the IDE does.
diff --git a/src/compiler/scala/tools/nsc/util/HashSet.scala b/src/compiler/scala/tools/nsc/util/HashSet.scala
index d17850ebf5..ebc517266b 100644
--- a/src/compiler/scala/tools/nsc/util/HashSet.scala
+++ b/src/compiler/scala/tools/nsc/util/HashSet.scala
@@ -7,15 +7,22 @@
 package scala.tools.nsc
 package util
 
-class HashSet[T >: Null <: AnyRef](initialCapacity: Int) extends Set[T] {
-
+class HashSet[T >: Null <: AnyRef](val label: String, initialCapacity: Int) extends Set[T] {
+  def this(initialCapacity: Int) = this("No Label", initialCapacity)
+  def this(label: String) = this(label, 16)
   def this() = this(16)
 
   private var capacity = initialCapacity
   private var used = 0
   private var table = new Array[AnyRef](capacity)
+  // System.err.println("Created: " + this)
 
   def size: Int = used
+  def clear() {
+    capacity = initialCapacity
+    used = 0
+    table = new Array[AnyRef](capacity)
+  }
 
   private def index(x: Int): Int = Math.abs(x % capacity)
 
@@ -39,7 +46,7 @@ class HashSet[T >: Null <: AnyRef](initialCapacity: Int) extends Set[T] {
     }
     table(h) = x
     used += 1
-    if (used >= (capacity >> 2)) growTable()
+    if (used > (capacity >> 2)) growTable()
   }
 
   def iterator = new Iterator[T] {
@@ -55,13 +62,21 @@ class HashSet[T >: Null <: AnyRef](initialCapacity: Int) extends Set[T] {
 
   private def growTable() {
     val oldtable = table
-    capacity *= 2
+    val growthFactor =
+      if (capacity <= initialCapacity) 8
+      else if (capacity <= (initialCapacity * 8)) 4
+      else 2
+
+    capacity *= growthFactor
     table = new Array[AnyRef](capacity)
     var i = 0
+    used = 0
     while (i < oldtable.length) {
       val entry = oldtable(i)
       if (entry ne null) addEntry(entry.asInstanceOf[T])
       i += 1
     }
+    // System.err.println("Grown: " + this)
   }
+  override def toString() = "HashSet %s(%d / %d)".format(label, used, capacity)
 }
diff --git a/src/compiler/scala/tools/nsc/util/Statistics.scala b/src/compiler/scala/tools/nsc/util/Statistics.scala
index 0addb7638d..3f22669e6f 100644
--- a/src/compiler/scala/tools/nsc/util/Statistics.scala
+++ b/src/compiler/scala/tools/nsc/util/Statistics.scala
@@ -45,7 +45,6 @@ abstract class Statistics {
       inform("#subtype     : " + subtypeCount)
       inform("ns subtype   : " + subtypeNanos)
       inform("#sametype    : " + sametypeCount)
-      inform("#unique types: " + uniques.size)
       inform("ms type-flow-analysis: " + analysis.timer.millis)
       if (phase.name == "typer") {
         inform("time spent typechecking: "+showRelTyper(analyzer.typerTime))