diff options
5 files changed, 257 insertions, 94 deletions
diff --git a/src/library/scala/collection/mutable/OpenHashMap.scala b/src/library/scala/collection/mutable/OpenHashMap.scala index 5f8f5b9a0a..c86357efad 100644 --- a/src/library/scala/collection/mutable/OpenHashMap.scala +++ b/src/library/scala/collection/mutable/OpenHashMap.scala @@ -108,16 +108,13 @@ extends AbstractMap[Key, Value] * @param hash hash value for `key` */ private[this] def findIndex(key: Key, hash: Int): Int = { - var j = hash - var index = hash & mask - var perturb = index + var j = 0 while(table(index) != null && !(table(index).hash == hash && table(index).key == key)){ - j = 5 * j + 1 + perturb - perturb >>= 5 - index = j & mask + j += 1 + index = (index + j) & mask } index } @@ -172,20 +169,17 @@ extends AbstractMap[Key, Value] def get(key : Key) : Option[Value] = { val hash = hashOf(key) - - var j = hash var index = hash & mask - var perturb = index var entry = table(index) + var j = 0 while(entry != null){ if (entry.hash == hash && entry.key == key){ return entry.value } - j = 5 * j + 1 + perturb - perturb >>= 5 - index = j & mask + j += 1 + index = (index + j) & mask entry = table(index) } None diff --git a/test/benchmarks/src/main/scala/benchmark/KeySeq.scala b/test/benchmarks/src/main/scala/benchmark/KeySeq.scala new file mode 100644 index 0000000000..126b92b3b6 --- /dev/null +++ b/test/benchmarks/src/main/scala/benchmark/KeySeq.scala @@ -0,0 +1,24 @@ +package benchmark + +/** A sequence of keys. + * + * Tests of maps and sets require a sequence of keys that can be used + * to add entries and possibly to find them again. + * This type provides such a sequence. + * + * Note that this needn't be a "sequence" in the full sense of [[collection.Seq]], + * particularly in that it needn't extend [[PartialFunction]]. + * + * @tparam K the type of the keys + */ +trait KeySeq[K] { + /** Selects a key by its index in the sequence. + * Repeated calls with the same index return the same key (by reference equality). + * + * @param idx The index to select. Should be non-negative and less than `size`. + */ + def apply(idx: Int): K + + /** The size of this sequence. */ + def size: Int +} diff --git a/test/benchmarks/src/main/scala/benchmark/KeySeqBuilder.scala b/test/benchmarks/src/main/scala/benchmark/KeySeqBuilder.scala new file mode 100644 index 0000000000..95f6c7afd7 --- /dev/null +++ b/test/benchmarks/src/main/scala/benchmark/KeySeqBuilder.scala @@ -0,0 +1,33 @@ +package benchmark + +/** Builder of a [[KeySeq]] + * + * @tparam K the type of the keys + */ +trait KeySeqBuilder[K] { + /** Return a [[KeySeq]] having at least the given size. */ + def build(size: Int): KeySeq[K] +} + +object KeySeqBuilder { + /** Builder of a sequence of `Int` keys. + * Simply maps the sequence index to itself. + */ + implicit object IntKeySeqBuilder extends KeySeqBuilder[Int] { + def build(_size: Int) = new KeySeq[Int] { + def apply(idx: Int) = idx + def size = _size + } + } + + /** Builder of a sequence of `AnyRef` keys. */ + implicit object AnyRefKeySeqBuilder extends KeySeqBuilder[AnyRef] { + def build(_size: Int) = new KeySeq[AnyRef] { + private[this] val arr = new Array[AnyRef](size) + for (i <- 0 until size) arr(i) = new AnyRef() + + def apply(idx: Int) = arr(idx) + def size = _size + } + } +} diff --git a/test/benchmarks/src/main/scala/scala/collection/mutable/OpenHashMapBenchmark.scala b/test/benchmarks/src/main/scala/scala/collection/mutable/OpenHashMapBenchmark.scala index 26e26b3065..64e2244499 100644 --- a/test/benchmarks/src/main/scala/scala/collection/mutable/OpenHashMapBenchmark.scala +++ b/test/benchmarks/src/main/scala/scala/collection/mutable/OpenHashMapBenchmark.scala @@ -1,14 +1,12 @@ package scala.collection.mutable; -import java.util.concurrent.TimeUnit import org.openjdk.jmh.annotations._ -import org.openjdk.jmh.infra.Blackhole -import org.openjdk.jmh.infra.BenchmarkParams -import org.openjdk.jol.info.GraphLayout -import org.openjdk.jol.info.GraphWalker -import org.openjdk.jol.info.GraphVisitor -import org.openjdk.jmh.infra.IterationParams +import org.openjdk.jmh.infra._ import org.openjdk.jmh.runner.IterationType +import org.openjdk.jol.info.GraphLayout + +import benchmark._ +import java.util.concurrent.TimeUnit /** Utilities for the [[OpenHashMapBenchmark]]. * @@ -16,7 +14,8 @@ import org.openjdk.jmh.runner.IterationType * instead of using the JMH harness, which iterates for a fixed length of time. */ private object OpenHashMapBenchmark { - /** State container for the `put()` bulk calling tests. + + /** Abstract state container for the `put()` bulk calling tests. * * Provides an array of adequately-sized, empty maps to each invocation, * so that hash table allocation won't be done during measurement. @@ -25,10 +24,11 @@ private object OpenHashMapBenchmark { * so that only the GCs caused by the invocation contribute to the measurement. * * Records the memory used by all the maps in the last invocation of each iteration. + * + * @tparam K type of the map keys to be used in the test */ @State(Scope.Thread) - @AuxCounters - class BulkPutState { + private[this] abstract class BulkPutState[K](implicit keyBuilder: KeySeqBuilder[K]) { /** A lower-bound estimate of the number of nanoseconds per `put()` call */ private[this] val nanosPerPut: Double = 5 @@ -39,35 +39,43 @@ private object OpenHashMapBenchmark { private[this] var size: Int = _ /** Total number of entries in all of the `maps` combined. */ - var mapEntries: Int = _ + private[this] var _mapEntries: Int = _ + protected def mapEntries = _mapEntries /** Number of operations performed in the current invocation. */ - var operations: Int = _ + private[this] var _operations: Int = _ + protected def operations = _operations /** Bytes of memory used in the object graphs of all the maps. */ - var memory: Long = _ + private[this] var _memory: Long = _ + protected def memory = _memory + + /** The sequence of keys to store into a map. */ + private[this] var _keys: KeySeq[K] = _ + def keys() = _keys - var maps: Array[OpenHashMap[Int,Int]] = null + var maps: Array[OpenHashMap[K,Int]] = null @Setup def threadSetup(params: BenchmarkParams) { size = params.getParam("size").toInt val n = math.ceil(minNanosPerInvocation / (nanosPerPut * size)).toInt - mapEntries = size * n + _mapEntries = size * n + _keys = keyBuilder.build(size) maps = new Array(n) } @Setup(Level.Iteration) def iterationSetup { - operations = 0 + _operations = 0 } @Setup(Level.Invocation) def setup(params: IterationParams) { - for (i <- 0 until maps.length) maps(i) = new OpenHashMap[Int,Int](size) + for (i <- 0 until maps.length) maps(i) = new OpenHashMap[K,Int](size) if (params.getType == IterationType.MEASUREMENT) { - operations += mapEntries + _operations += _mapEntries System.gc() // clean up after last invocation } } @@ -76,72 +84,124 @@ private object OpenHashMapBenchmark { def iterationTeardown(params: IterationParams) { if (params.getType == IterationType.MEASUREMENT) { // limit to smaller cases to avoid OOM - memory = if (mapEntries <= 1000000) GraphLayout.parseInstance(maps(0), maps.tail).totalSize else 0 + _memory = + if (_mapEntries <= 1000000) GraphLayout.parseInstance(maps(0), maps.tail).totalSize + else 0 } } } - /** State container for the `get()` bulk calling tests. + /** Abstract state container for the `get()` bulk calling tests. * * Provides a thread-scoped map of the expected size. * Performs a GC after loading the map. + * + * @tparam K type of the map keys to be used in the test */ @State(Scope.Thread) - class BulkGetState { - val map = new OpenHashMap[Int,Int].empty + private[this] abstract class BulkGetState[K](implicit keyBuilder: KeySeqBuilder[K]) { + /** The sequence of keys to store into a map. */ + private[this] var _keys: KeySeq[K] = _ + def keys() = _keys + + val map = new OpenHashMap[K,Int].empty /** Load the map with keys from `1` to `size`. */ @Setup def setup(params: BenchmarkParams) { val size = params.getParam("size").toInt - put_Int(map, 1, size) + _keys = keyBuilder.build(size) + put(map, keys, 0, size) System.gc() } } - /** State container for the `get()` bulk calling tests with deleted entries. + /** Abstract state container for the `get()` bulk calling tests with deleted entries. * * Provides a thread-scoped map of the expected size, from which entries have been removed. * Performs a GC after loading the map. + * + * @tparam K type of the map keys to be used in the test */ @State(Scope.Thread) - class BulkRemovedGetState { - val map = new OpenHashMap[Int,Int].empty + private[this] abstract class BulkRemovedGetState[K](implicit keyBuilder: KeySeqBuilder[K]) { + /** The sequence of keys to store into a map. */ + private[this] var _keys: KeySeq[K] = _ + def keys() = _keys + + val map = new OpenHashMap[K,Int].empty /** Load the map with keys from `1` to `size`, removing half of them. */ @Setup def setup(params: BenchmarkParams) { val size = params.getParam("size").toInt - put_remove_Int(map, size) + _keys = keyBuilder.build(size) + put_remove(map, keys) System.gc() } } - /** Put elements into the given map. */ - private def put_Int(map: OpenHashMap[Int,Int], from: Int, to: Int) { + /* In order to use `@AuxCounters` on a class hierarchy (as of JMH 1.11.3), + * it's necessary to place it on the injected (sub)class, and to make the + * counters visible as explicit public members of the that class. JMH doesn't + * scan the ancestor classes for counters. + */ + + @AuxCounters + private class IntBulkPutState extends BulkPutState[Int] { + override def mapEntries = super.mapEntries + override def operations = super.operations + override def memory = super.memory + } + private class IntBulkGetState extends BulkGetState[Int] + private class IntBulkRemovedGetState extends BulkRemovedGetState[Int] + + @AuxCounters + private class AnyRefBulkPutState extends BulkPutState[AnyRef] { + override def mapEntries = super.mapEntries + override def operations = super.operations + override def memory = super.memory + } + private class AnyRefBulkGetState extends BulkGetState[AnyRef] + private class AnyRefBulkRemovedGetState extends BulkRemovedGetState[AnyRef] + + + /** Put entries into the given map. + * Adds entries using a range of keys from the given list. + * + * @param from lowest index in the range of keys to add + * @param to highest index in the range of keys to add, plus one + */ + private[this] def put[K](map: OpenHashMap[K,Int], keys: KeySeq[K], from: Int, to: Int) { var i = from - while (i <= to) { // using a `for` expression instead adds significant overhead - map.put(i, i) + while (i < to) { // using a `for` expression instead adds significant overhead + map.put(keys(i), i) i += 1 } } - /** Put elements into the given map, removing half of them as they're added. + /** Put entries into the given map. + * Adds entries using all of the keys from the given list. + */ + private def put[K](map: OpenHashMap[K,Int], keys: KeySeq[K]): Unit = + put(map, keys, 0, keys.size) + + /** Put entries into the given map, removing half of them as they're added. * - * @param size number of entries to leave in the map on return + * @param keys list of keys to use */ - def put_remove_Int(map: OpenHashMap[Int,Int], size: Int) { - val blocks = 50 // should be a factor of `size` - val totalPuts = 2 * size // add twice as many, because we remove half of them - val blockSize: Int = totalPuts / blocks + private def put_remove[K](map: OpenHashMap[K,Int], keys: KeySeq[K]) { + val blocks = 25 // should be a non-trivial factor of `size` + val size = keys.size + val blockSize: Int = size / blocks var base = 0 - while (base < totalPuts) { - put_Int(map, base + 1, base + blockSize) + while (base < size) { + put(map, keys, base, base + blockSize) // remove every other entry - var i = base + 1 - while (i <= base + blockSize) { - map.remove(i) + var i = base + while (i < base + blockSize) { + map.remove(keys(i)) i += 2 } @@ -150,55 +210,99 @@ private object OpenHashMapBenchmark { } /** Get elements from the given map. */ - def get_Int(map: OpenHashMap[Int,Int], size: Int, bh: Blackhole) { - var i = 1 - while (i <= size) { - bh.consume(map.get(i).getOrElse(0)) + private def get[K](map: OpenHashMap[K,Int], keys: KeySeq[K]) = { + val size = keys.size + var i = 0 + var sum = 0 + while (i < size) { + sum += map.get(keys(i)).getOrElse(0) i += 1 } + sum } } /** Benchmark for the library's [[OpenHashMap]]. */ @BenchmarkMode(Array(Mode.AverageTime)) -@Fork(6) +@Fork(5) @Threads(1) @Warmup(iterations = 20) -@Measurement(iterations = 6) +@Measurement(iterations = 5) @OutputTimeUnit(TimeUnit.NANOSECONDS) @State(Scope.Benchmark) class OpenHashMapBenchmark { import OpenHashMapBenchmark._ - @Param(Array("25", "50", "100", "250", "1000", "2500", "10000", "25000", "100000", "250000", "1000000", "2500000", + @Param(Array("50", "100", "1000", "10000", "100000", "1000000", "2500000", "5000000", "7500000", "10000000", "25000000")) var size: Int = _ + // Tests with Int keys + /** Test putting elements to a map of `Int` to `Int`. */ @Benchmark - def put_Int(state: BulkPutState) { + def put_Int(state: IntBulkPutState) { var i = 0 while (i < state.maps.length) { - OpenHashMapBenchmark.put_Int(state.maps(i), 1, size) + put(state.maps(i), state.keys) i += 1 } } /** Test putting and removing elements to a growing map of `Int` to `Int`. */ @Benchmark - def put_remove_Int(state: BulkPutState) { + def put_remove_Int(state: IntBulkPutState) { var i = 0 while (i < state.maps.length) { - OpenHashMapBenchmark.put_remove_Int(state.maps(i), size) + put_remove(state.maps(i), state.keys) i += 1 } } /** Test getting elements from a map of `Int` to `Int`. */ @Benchmark - def put_get_Int(state: BulkGetState, bh: Blackhole) = OpenHashMapBenchmark.get_Int(state.map, size, bh) + def get_Int_after_put(state: IntBulkGetState) = + get(state.map, state.keys) + + /** Test getting elements from a map of `Int` to `Int` from which elements have been removed. + * Note that half of these queries will fail to find their keys, which have been removed. + */ + @Benchmark + def get_Int_after_put_remove(state: IntBulkRemovedGetState) = + get(state.map, state.keys) + + + // Tests with AnyRef keys + + /** Test putting elements to a map of `AnyRef` to `Int`. */ + @Benchmark + def put_AnyRef(state: AnyRefBulkPutState) { + var i = 0 + while (i < state.maps.length) { + put(state.maps(i), state.keys) + i += 1 + } + } + + /** Test putting and removing elements to a growing map of `AnyRef` to `Int`. */ + @Benchmark + def put_remove_AnyRef(state: AnyRefBulkPutState) { + var i = 0 + while (i < state.maps.length) { + put_remove(state.maps(i), state.keys) + i += 1 + } + } + + /** Test getting elements from a map of `AnyRef` to `Int`. */ + @Benchmark + def get_AnyRef_after_put(state: AnyRefBulkGetState) = + get(state.map, state.keys) - /** Test getting elements from a map of `Int` to `Int` from which elements have been removed. */ + /** Test getting elements from a map of `AnyRef` to `Int` from which elements have been removed. + * Note that half of these queries will fail to find their keys, which have been removed. + */ @Benchmark - def put_remove_get_Int(state: BulkRemovedGetState, bh: Blackhole) = OpenHashMapBenchmark.get_Int(state.map, size, bh) + def get_AnyRef_after_put_remove(state: AnyRefBulkRemovedGetState) = + get(state.map, state.keys) } diff --git a/test/benchmarks/src/main/scala/scala/collection/mutable/OpenHashMapRunner.scala b/test/benchmarks/src/main/scala/scala/collection/mutable/OpenHashMapRunner.scala index 1a58b18ee9..b14b733a81 100644 --- a/test/benchmarks/src/main/scala/scala/collection/mutable/OpenHashMapRunner.scala +++ b/test/benchmarks/src/main/scala/scala/collection/mutable/OpenHashMapRunner.scala @@ -1,20 +1,18 @@ package scala.collection.mutable -import java.io.BufferedWriter import java.io.File -import java.io.FileOutputStream -import java.io.OutputStreamWriter import java.io.PrintWriter -import scala.collection.JavaConversions + import scala.language.existentials + +import org.openjdk.jmh.results.Result import org.openjdk.jmh.results.RunResult import org.openjdk.jmh.runner.Runner import org.openjdk.jmh.runner.options.CommandLineOptions -import org.openjdk.jmh.runner.options.Options -import benchmark.JmhRunner import org.openjdk.jmh.runner.options.OptionsBuilder import org.openjdk.jmh.runner.options.VerboseMode -import org.openjdk.jmh.results.Result + +import benchmark.JmhRunner /** Replacement JMH application that runs the [[OpenHashMap]] benchmark. * @@ -27,6 +25,7 @@ object OpenHashMapRunner extends JmhRunner { /** Qualifier to add to the name of a memory usage data set. */ private[this] val memoryDatasetQualifier = "-memory" + /** Adapter to the JMH result class that simplifies our method calls. */ private[this] implicit class MyRunResult(r: RunResult) { /** Return the dataset label. */ def label = r.getPrimaryResult.getLabel @@ -34,13 +33,13 @@ object OpenHashMapRunner extends JmhRunner { /** Return the value of the JMH parameter for the number of map entries per invocation. */ def size: String = r.getParams.getParam("size") - /** Return the operation counts. */ + /** Return the operation counts. Not every test tracks this. */ def operations = Option(r.getSecondaryResults.get("operations")) /** Return the number of map entries. */ def entries = r.getSecondaryResults.get("mapEntries") - /** Return the memory usage. */ + /** Return the memory usage. Only defined if memory usage was measured. */ def memory = Option(r.getSecondaryResults.get("memory")) } @@ -50,7 +49,6 @@ object OpenHashMapRunner extends JmhRunner { def main(args: Array[String]) { import scala.collection.JavaConversions._ - import scala.language.existentials val opts = new CommandLineOptions(args: _*) var builder = new OptionsBuilder().parent(opts).jvmArgsPrepend("-Xmx6000m") @@ -58,7 +56,12 @@ object OpenHashMapRunner extends JmhRunner { val results = new Runner(builder.build).run() - // Sort the results + /* Sort the JMH results into "data sets", each representing a complete test of one feature. + * Some results only measure CPU performance; while others also measure memory usage, and + * thus are split into two data sets. A data set is distinguished by its label, which is + * the label of the JMH result, for CPU performance, or that with an added suffix, for memory + * usage. + */ /** Map from data set name to data set. */ val datasetByName = Map.empty[String, Set[RunResult]] @@ -83,23 +86,28 @@ object OpenHashMapRunner extends JmhRunner { val f = new PrintWriter(outputFile, "UTF-8") try { - datasetByName.foreach(_ match { case (label: String, dataset: Iterable[RunResult]) => { - f.println(s"# [$label]") - - val isMemoryUsageDataset = label.endsWith(memoryDatasetQualifier) - dataset.foreach { r => - f.println(r.size + " " + ( - if (isMemoryUsageDataset) - stats(r.entries) + " " + stats(r.memory.get) - else - stats(r.operations getOrElse r.getPrimaryResult) - )) - } - - f.println(); f.println() // data set separator - }}) + datasetByName.foreach(_ match { + case (label: String, dataset: Iterable[RunResult]) => + outputDataset(f, label, dataset) + }) } finally { f.close() } } + + private[this] def outputDataset(f: PrintWriter, label: String, dataset: Iterable[RunResult]) { + f.println(s"# [$label]") + + val isMemoryUsageDataset = label.endsWith(memoryDatasetQualifier) + dataset.foreach { r => + f.println(r.size + " " + ( + if (isMemoryUsageDataset && !r.memory.get.getScore.isInfinite) + stats(r.entries) + " " + stats(r.memory.get) + else + stats(r.operations getOrElse r.getPrimaryResult) + )) + } + + f.println(); f.println() // data set separator + } } |