diff options
author | Paul Phillips <paulp@improving.org> | 2011-08-01 22:44:52 +0000 |
---|---|---|
committer | Paul Phillips <paulp@improving.org> | 2011-08-01 22:44:52 +0000 |
commit | 257b6c91a52dc805dfb413b323a70e52f6499c2e (patch) | |
tree | 3beafcf862fd0a544338ca0f166ade244cc670a4 /src/library | |
parent | daa26379ceae60b441f49dab49f367ebea027529 (diff) | |
download | scala-257b6c91a52dc805dfb413b323a70e52f6499c2e.tar.gz scala-257b6c91a52dc805dfb413b323a70e52f6499c2e.tar.bz2 scala-257b6c91a52dc805dfb413b323a70e52f6499c2e.zip |
Sped up traversal over mutable maps by a factor...
Sped up traversal over mutable maps by a factor of two.
There was this comment in HashTable explaining why foreach was
implemented in terms of iterator. /*
* 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.
*/
Item 1: foreach and iterator didn't behave the same if the map was
mutated in the midst of the traversal anyway. Item 2: protecting some
particular undefinition of inherently undefined behavior is a pretty
unconvincing reason to impose a 2x penalty on foreach.
Here are the before/after times for traversing the keys with foreach
vs. with iterator. Same impact on values and on the map itself. The
benchmark code is included in this commit.
before: foreach 143700900 iterator 143848900
after: foreach 67024400 iterator 144890300
Respecting the fact that this might be causing some behavior somewhere
to change, even though it would be pretty sick to be relying upon it,
** ATTENTION! POSSIBLE BEHAVIOR CHANGE! **
Review by dragos.
Diffstat (limited to 'src/library')
4 files changed, 35 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") |