Having been tortured by remorse ever since tiar...

Having been tortured by remorse ever since tiark told me that r23934 had
made the hashmap slower, I crushed my previous efforts under the heel of
my boot, threw all the types out the window, poured acid on them, and
turned all the dials to the far other extreme. Pity the man who will
sell his soul for a few CPU cycles. (I am that man.) Review by rompf.

1 files changed, 12 insertions, 33 deletions

diff --git a/src/library/scala/collection/immutable/HashMap.scala b/src/library/scala/collection/immutable/HashMap.scala
index e253cd6a05..bf65966e80 100644
--- a/src/library/scala/collection/immutable/HashMap.scala
+++ b/src/library/scala/collection/immutable/HashMap.scala
@@ -180,7 +180,9 @@ object HashMap extends ImmutableMapFactory[HashMap] with BitOperations.Int {
     }
   }
 
-  private[collection] class HashMapCollision1[A,+B](private[HashMap] var hash: Int, var kvs: ListMap[A,B @uV]) extends HashMap[A,B] {
+  private[collection] class HashMapCollision1[A, +B](private[HashMap] var hash: Int, var kvs: ListMap[A, B @uV])
+          extends HashMap[A, B @uV] {
+
     override def size = kvs.size
 
     override def get0(key: A, hash: Int, level: Int): Option[B] =
@@ -222,8 +224,12 @@ object HashMap extends ImmutableMapFactory[HashMap] with BitOperations.Int {
     }
   }
 
-  class HashTrieMap[A,+B](private[HashMap] var bitmap: Int, private[collection] var elems: Array[HashMap[A,B @uV]],
-      private[HashMap] var size0: Int) extends HashMap[A,B] {
+  class HashTrieMap[A, +B](
+    private[HashMap] var bitmap: Int,
+    private[collection] var elems: Array[HashMap[A, B @uV]],
+    private[HashMap] var size0: Int
+  ) extends HashMap[A, B @uV] {
+
 /*
     def this (level: Int, m1: HashMap1[A,B], m2: HashMap1[A,B]) = {
       this(((m1.hash >>> level) & 0x1f) | ((m2.hash >>> level) & 0x1f), {
@@ -308,7 +314,9 @@ object HashMap extends ImmutableMapFactory[HashMap] with BitOperations.Int {
       }
     }
 
-    override def iterator: Iterator[(A, B)] = new CovariantTrieIterator[A, B](elems)
+    override def iterator: Iterator[(A, B)] = new TrieIterator[(A, B)](elems.asInstanceOf[Array[Iterable[(A, B)]]]) {
+      final override def getElem(cc: AnyRef): (A, B) = cc.asInstanceOf[HashMap1[A, B]].ensurePair
+    }
 
 /*
 
@@ -452,35 +460,6 @@ time { mNew.iterator.foreach( p => ()) }
     }
   }
 
-  class CovariantTrieIterator[A, +B](elems: Array[HashMap[A, B]]) extends Iterator[(A, B)] {
-    private[this] val it = new TrieIterator[A, B](elems)
-    def next = it.next
-    def hasNext = it.hasNext
-  }
-
-  class TrieIterator[A, B](elems: Array[HashMap[A, B]]) extends TrieIteratorBase[(A, B), HashMap[A, B]](elems) {
-    import TrieIteratorBase._
-
-    type This = TrieIterator[A, B]
-    private[immutable] def recreateIterator() = new TrieIterator(elems)
-    private[immutable] type ContainerType = HashMap1[A, B]
-    private[immutable] type TrieType      = HashTrieMap[A, B]
-    private[immutable] type CollisionType = HashMapCollision1[A, B]
-
-    private[immutable] def determineType(x: HashMap[A, B]) = x match {
-      case _: HashMap1[_, _]          => CONTAINER_TYPE
-      case _: HashTrieMap[_, _]       => TRIE_TYPE
-      case _: HashMapCollision1[_, _] => COLLISION_TYPE
-    }
-
-    private[immutable] def getElem(cc: ContainerType)            = cc.ensurePair
-    private[immutable] def getElems(t: TrieType)                 = t.elems
-    private[immutable] def collisionToArray(c: CollisionType)    = c.kvs map (x => HashMap(x)) toArray
-    private[immutable] def newThisType(xs: Array[HashMap[A, B]]) = new TrieIterator(xs)
-    private[immutable] def newDeepArray(size: Int)               = new Array[Array[HashMap[A, B]]](size)
-    private[immutable] def newSingleArray(el: HashMap[A, B])     = Array(el)
-  }
-
   private def check[K](x: HashMap[K, _], y: HashMap[K, _], xy: HashMap[K, _]) = { // TODO remove this debugging helper
     var xs = Set[K]()
     for (elem <- x) xs += elem._1