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, 61 insertions, 0 deletions

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)
+  }
+}