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 /test/benchmarks | |
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 'test/benchmarks')
-rw-r--r-- | test/benchmarks/src/scala/collection/mutable/hashtable-bench.scala | 61 |
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) + } +} |