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.

1 files changed, 29 insertions, 22 deletions

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")