From b924c4142de1ca6525a3d5e57ecfb7a345dd9f89 Mon Sep 17 00:00:00 2001 From: Paul Phillips Date: Thu, 23 Jun 2011 06:13:55 +0000 Subject: Overrode contains and apply in mutable.HashMap ... Overrode contains and apply in mutable.HashMap to avoid allocating an unnecessary Some on every call to either of them. Fruit looks a little better defended in immutable.HashMap, so I deleted a bunch of old debugging code instead. Closes #4469, no review. --- .../backend/icode/analysis/TypeFlowAnalysis.scala | 2 +- src/library/scala/collection/MapLike.scala | 5 +- .../scala/collection/immutable/HashMap.scala | 74 +++++----------------- src/library/scala/collection/mutable/HashMap.scala | 8 +++ test/files/neg/bug876.check | 2 +- 5 files changed, 27 insertions(+), 64 deletions(-) diff --git a/src/compiler/scala/tools/nsc/backend/icode/analysis/TypeFlowAnalysis.scala b/src/compiler/scala/tools/nsc/backend/icode/analysis/TypeFlowAnalysis.scala index 0826a7676f..9ec8364db7 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/analysis/TypeFlowAnalysis.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/TypeFlowAnalysis.scala @@ -57,7 +57,7 @@ abstract class TypeFlowAnalysis { /** A map which returns the bottom type for unfound elements */ class VarBinding extends mutable.HashMap[icodes.Local, icodes.TypeKind] { - override def get(l: icodes.Local) = super.get(l) orElse Some(typeLattice.bottom) + override def default(l: icodes.Local) = typeLattice.bottom def this(o: VarBinding) = { this() diff --git a/src/library/scala/collection/MapLike.scala b/src/library/scala/collection/MapLike.scala index f6a5c57ddf..4850898ce8 100644 --- a/src/library/scala/collection/MapLike.scala +++ b/src/library/scala/collection/MapLike.scala @@ -141,10 +141,7 @@ self => * @param key the key * @return `true` if there is a binding for `key` in this map, `false` otherwise. */ - def contains(key: A): Boolean = get(key) match { - case None => false - case Some(_) => true - } + def contains(key: A): Boolean = get(key).isDefined /** Tests whether this map contains a binding for a key. This method, * which implements an abstract method of trait `PartialFunction`, diff --git a/src/library/scala/collection/immutable/HashMap.scala b/src/library/scala/collection/immutable/HashMap.scala index bf65966e80..f4e9c91733 100644 --- a/src/library/scala/collection/immutable/HashMap.scala +++ b/src/library/scala/collection/immutable/HashMap.scala @@ -6,8 +6,6 @@ ** |/ ** \* */ - - package scala.collection package immutable @@ -33,8 +31,11 @@ import parallel.immutable.ParHashMap * @define willNotTerminateInf */ @SerialVersionUID(2L) -class HashMap[A, +B] extends Map[A,B] with MapLike[A, B, HashMap[A, B]] with Serializable with CustomParallelizable[(A, B), ParHashMap[A, B]] { - +class HashMap[A, +B] extends Map[A,B] + with MapLike[A, B, HashMap[A, B]] + with Serializable + with CustomParallelizable[(A, B), ParHashMap[A, B]] +{ override def size: Int = 0 override def empty = HashMap.empty[A, B] @@ -103,9 +104,7 @@ object HashMap extends ImmutableMapFactory[HashMap] with BitOperations.Int { implicit def canBuildFrom[A, B]: CanBuildFrom[Coll, (A, B), HashMap[A, B]] = new MapCanBuildFrom[A, B] def empty[A, B]: HashMap[A, B] = EmptyHashMap.asInstanceOf[HashMap[A, B]] - private object EmptyHashMap extends HashMap[Any,Nothing] { - - } + private object EmptyHashMap extends HashMap[Any, Nothing] { } // TODO: add HashMap2, HashMap3, ... @@ -319,7 +318,6 @@ object HashMap extends ImmutableMapFactory[HashMap] with BitOperations.Int { } /* - def time(block: =>Unit) = { val t0 = System.nanoTime; block; println("elapsed: " + (System.nanoTime - t0)/1000000.0) } var mOld = OldHashMap.empty[Int,Int] var mNew = HashMap.empty[Int,Int] @@ -335,10 +333,8 @@ time { mOld.iterator.foreach( p => ()) } time { mNew.iterator.foreach( p => ()) } time { mNew.iterator.foreach( p => ()) } time { mNew.iterator.foreach( p => ()) } - */ - override def foreach[U](f: ((A, B)) => U): Unit = { var i = 0; while (i < elems.length) { @@ -347,18 +343,14 @@ time { mNew.iterator.foreach( p => ()) } } } - private def printBitmap(bm: Int) { - println(bitString(bm, " ")) - } - private def posOf(n: Int, bm: Int) = { var left = n var i = -1 var b = bm while (left >= 0) { - i += 1 - if ((b & 1) != 0) left -= 1 - b = b >>> 1 + i += 1 + if ((b & 1) != 0) left -= 1 + b = b >>> 1 } i } @@ -366,20 +358,12 @@ time { mNew.iterator.foreach( p => ()) } override def split: Seq[HashMap[A, B]] = if (size == 1) Seq(this) else { val nodesize = Integer.bitCount(bitmap) if (nodesize > 1) { - // printBitmap(bitmap) - // println(elems.toList) - - // println("subtrees: " + nodesize) - // println("will split at: " + (nodesize / 2)) val splitpoint = nodesize / 2 val bitsplitpoint = posOf(nodesize / 2, bitmap) val bm1 = bitmap & (-1 << bitsplitpoint) val bm2 = bitmap & (-1 >>> (32 - bitsplitpoint)) - // printBitmap(bm1) - // printBitmap(bm2) + val (e1, e2) = elems.splitAt(splitpoint) - // println(e1.toList) - // println(e2.toList) val hm1 = new HashTrieMap(bm1, e1, e1.foldLeft(0)(_ + _.size)) val hm2 = new HashTrieMap(bm2, e2, e2.foldLeft(0)(_ + _.size)) @@ -389,10 +373,8 @@ time { mNew.iterator.foreach( p => ()) } protected override def merge0[B1 >: B](that: HashMap[A, B1], level: Int, merger: Merger[B1]): HashMap[A, B1] = that match { case hm: HashMap1[_, _] => - // onetrie += 1 this.updated0(hm.key, hm.hash, level, hm.value.asInstanceOf[B1], hm.kv, merger) case hm: HashTrieMap[_, _] => - // bothtries += 1 val that = hm.asInstanceOf[HashTrieMap[A, B1]] val thiselems = this.elems val thatelems = that.elems @@ -400,12 +382,12 @@ time { mNew.iterator.foreach( p => ()) } var thatbm = that.bitmap // determine the necessary size for the array - val subcount = Integer.bitCount(thisbm | thatbm) + val subcount = Integer.bitCount(thisbm | thatbm) // construct a new array of appropriate size val merged = new Array[HashMap[A, B1]](subcount) - // run through both bitmaps and add elements to it + // run through both bitmaps and add elements to it var i = 0 var thisi = 0 var thati = 0 @@ -413,13 +395,9 @@ time { mNew.iterator.foreach( p => ()) } while (i < subcount) { val thislsb = thisbm ^ (thisbm & (thisbm - 1)) val thatlsb = thatbm ^ (thatbm & (thatbm - 1)) - // if (this.bitmap == -1660585213) { TODO remove - // printBitmap(thislsb) - // printBitmap(thatlsb) - // println("------------------") - // } + + // collision if (thislsb == thatlsb) { - // println("a collision") val m = thiselems(thisi).merge0(thatelems(thati), level + 5, merger) totalelems += m.size merged(i) = m @@ -435,14 +413,13 @@ time { mNew.iterator.foreach( p => ()) } val b = thatlsb - 1 if (unsignedCompare(thislsb - 1, thatlsb - 1)) { - // println("an element from this trie") val m = thiselems(thisi) totalelems += m.size merged(i) = m thisbm = thisbm & ~thislsb thisi += 1 - } else { - // println("an element from that trie") + } + else { val m = thatelems(thati) totalelems += m.size merged(i) = m @@ -460,25 +437,6 @@ time { mNew.iterator.foreach( p => ()) } } } - 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 - var ys = Set[K]() - for (elem <- y) ys += elem._1 - var union = Set[K]() - for (elem <- xy) union += elem._1 - if ((xs ++ ys) != union) { - println("Error.") - println(x.getClass) - println(y.getClass) - println(xs) - println(ys) - println(xs ++ ys) - println(union) - false - } else true - } - @SerialVersionUID(2L) private class SerializationProxy[A,B](@transient private var orig: HashMap[A, B]) extends Serializable { private def writeObject(out: java.io.ObjectOutputStream) { diff --git a/src/library/scala/collection/mutable/HashMap.scala b/src/library/scala/collection/mutable/HashMap.scala index 19ad53faf5..b082fc2770 100644 --- a/src/library/scala/collection/mutable/HashMap.scala +++ b/src/library/scala/collection/mutable/HashMap.scala @@ -59,6 +59,14 @@ extends Map[A, B] override def par = new ParHashMap[A, B](hashTableContents) + // contains and apply overridden to avoid option allocations. + override def contains(key: A) = findEntry(key) != null + override def apply(key: A): B = { + val result = findEntry(key) + if (result == null) default(key) + else result.value + } + def get(key: A): Option[B] = { val e = findEntry(key) if (e == null) None diff --git a/test/files/neg/bug876.check b/test/files/neg/bug876.check index 85522423a8..f72cc969c2 100644 --- a/test/files/neg/bug876.check +++ b/test/files/neg/bug876.check @@ -1,4 +1,4 @@ -bug876.scala:25: error: too many arguments for method apply: (key: AssertionError.A)manager.B in trait MapLike +bug876.scala:25: error: too many arguments for method apply: (key: AssertionError.A)manager.B in class HashMap assert(manager.map(A2) == List(manager.map(A2, A1))) ^ one error found -- cgit v1.2.3