diff options
5 files changed, 96 insertions, 38 deletions
diff --git a/src/library/scala/collection/MapLike.scala b/src/library/scala/collection/MapLike.scala index f8dd9c1c79..4ffcc111cc 100644 --- a/src/library/scala/collection/MapLike.scala +++ b/src/library/scala/collection/MapLike.scala @@ -165,7 +165,7 @@ self => def + (elem: A): Set[A] = (Set[A]() ++ this + elem).asInstanceOf[Set[A]] // !!! concrete overrides abstract problem def - (elem: A): Set[A] = (Set[A]() ++ this - elem).asInstanceOf[Set[A]] // !!! concrete overrides abstract problem override def size = self.size - override def foreach[C](f: A => C) = for ((k, v) <- self) f(k) + override def foreach[C](f: A => C) = self.keysIterator foreach f } /** Creates an iterator for all keys. @@ -197,7 +197,7 @@ self => protected class DefaultValuesIterable extends Iterable[B] { def iterator = valuesIterator override def size = self.size - override def foreach[C](f: B => C) = for ((k, v) <- self) f(v) + override def foreach[C](f: B => C) = self.valuesIterator foreach f } /** Creates an iterator for all values in this map. diff --git a/src/library/scala/collection/mutable/DefaultEntry.scala b/src/library/scala/collection/mutable/DefaultEntry.scala index 66ca375f13..95ac98efe7 100644 --- a/src/library/scala/collection/mutable/DefaultEntry.scala +++ b/src/library/scala/collection/mutable/DefaultEntry.scala @@ -6,13 +6,9 @@ ** |/ ** \* */ - - package scala.collection package mutable - - /** Class used internally for default map model. * @since 2.3 */ diff --git a/src/library/scala/collection/mutable/HashMap.scala b/src/library/scala/collection/mutable/HashMap.scala index b082fc2770..98ece514f7 100644 --- a/src/library/scala/collection/mutable/HashMap.scala +++ b/src/library/scala/collection/mutable/HashMap.scala @@ -6,18 +6,12 @@ ** |/ ** \* */ - - package scala.collection package mutable import generic._ - - import scala.collection.parallel.mutable.ParHashMap - - /** This class implements mutable maps using a hashtable. * * @since 1 @@ -112,16 +106,16 @@ extends Map[A, B] /* Override to avoid tuple allocation */ override def keysIterator: Iterator[A] = new Iterator[A] { - val iter = entriesIterator + val iter = entriesIterator def hasNext = iter.hasNext - def next() = iter.next.key + def next() = iter.next.key } /* Override to avoid tuple allocation */ override def valuesIterator: Iterator[B] = new Iterator[B] { - val iter = entriesIterator + val iter = entriesIterator def hasNext = iter.hasNext - def next() = iter.next.value + def next() = iter.next.value } /** Toggles whether a size map is used to track hash map statistics. diff --git a/src/library/scala/collection/mutable/HashTable.scala b/src/library/scala/collection/mutable/HashTable.scala index 0f6fde0260..004b112253 100644 --- a/src/library/scala/collection/mutable/HashTable.scala +++ b/src/library/scala/collection/mutable/HashTable.scala @@ -54,6 +54,14 @@ trait HashTable[A, Entry >: Null <: HashEntry[A, Entry]] extends HashTable.HashU protected def initialSize: Int = HashTable.initialSize + private def lastPopulatedIndex = { + var idx = table.length - 1 + while (table(idx) == null && idx > 0) + idx -= 1 + + idx + } + /** * Initializes the collection from the input stream. `f` will be called for each key/value pair * read from the input stream in the order determined by the stream. This is useful for @@ -156,38 +164,37 @@ trait HashTable[A, Entry >: Null <: HashEntry[A, Entry]] extends HashTable.HashU */ protected def entriesIterator: Iterator[Entry] = new Iterator[Entry] { val iterTable = table - var idx = table.length - 1 - var es = iterTable(idx).asInstanceOf[Entry] - scan() + var idx = lastPopulatedIndex + var es = iterTable(idx) + def hasNext = es != null def next() = { val res = es es = es.next - scan() - res - } - def scan() { while (es == null && idx > 0) { idx = idx - 1 - es = iterTable(idx).asInstanceOf[Entry] + es = iterTable(idx) } + res.asInstanceOf[Entry] } } - /* - * We should implement this as a primitive operation over the underlying array, but it can - * cause a behaviour change in edge cases where: - * - Someone modifies a map during iteration - * - The insertion point is close to the iteration point. - * - * The reason this happens is that the iterator prefetches the following element before - * returning from next (to simplify the implementation of hasNext) while the natural - * implementation of foreach does not. - * - * It should be mentioned that modifying a map during iteration leads to unpredictable - * results with either implementation. - */ - protected final def foreachEntry[C](f: Entry => C) { entriesIterator.foreach(f) } + /** Avoid iterator for a 2x faster traversal. */ + protected final def foreachEntry[C](f: Entry => C) { + val iterTable = table + var idx = lastPopulatedIndex + var es = iterTable(idx) + + while (es != null) { + f(es.asInstanceOf[Entry]) + es = es.next + + while (es == null && idx > 0) { + idx -= 1 + es = iterTable(idx) + } + } + } /** An iterator returning all entries */ @deprecated("use entriesIterator instead", "2.8.0") diff --git a/test/benchmarks/src/scala/collection/mutable/hashtable-bench.scala b/test/benchmarks/src/scala/collection/mutable/hashtable-bench.scala new file mode 100644 index 0000000000..bea1b1df46 --- /dev/null +++ b/test/benchmarks/src/scala/collection/mutable/hashtable-bench.scala @@ -0,0 +1,61 @@ +import scala.collection.mutable.HashMap + +object Test { + var dummy: Long = 0L + var _foreach: Long = 0L + var _iterator: Long = 0L + + def numbers: Seq[Int] = 1 to 1000000 + val map: HashMap[Int, Int] = HashMap(numbers zip numbers: _*) + + @inline final def timed(body: => Unit): Long = { + val start = System.nanoTime + body + System.nanoTime - start + } + + def go(xs: Iterable[Int], reps: Int) = { + _foreach = 0L + _iterator = 0L + + 0 until reps foreach { _ => + _foreach += timed(xs foreach (dummy += _)) + _iterator += timed(xs.iterator foreach (dummy += _)) + } + + " foreach avg " + (_foreach / reps) + "\n iterator avg " + (_iterator / reps) + "\n" + } + + def go2(xs: collection.Map[Int, Int], reps: Int) = { + _foreach = 0L + _iterator = 0L + + def incDummy(nums: (Int, Int)) = { + dummy += nums._1 + dummy -= nums._2 + } + + 0 until reps foreach { _ => + _foreach += timed(xs foreach incDummy) + _iterator += timed(xs.iterator foreach incDummy) + } + + " foreach avg " + (_foreach / reps) + "\n iterator avg " + (_iterator / reps) + "\n" + } + + def main(args: Array[String]): Unit = { + println("map.keys:") + go(map.keys, 10) // warm + println(go(map.keys, 10)) + + println("map.values:") + go(map.values, 10) // warm + println(go(map.values, 10)) + + println("map:") + go2(map, 10) // warm + println(go2(map, 10)) + + println("// pay me no mind ... " + dummy) + } +} |