From e1b58ccafc598c06b8011e3e0f411f6e91b99353 Mon Sep 17 00:00:00 2001 From: Performant Data LLC Date: Wed, 23 Mar 2016 12:07:00 -0700 Subject: Add get() tests to OpenHashMap, reduce timing artifacts. In order to get a better exploration of the variance of tests in a limited time, I've reduced the number of measurement iterations and increased the number of forks. By sight, the measurement iterations seemed pretty consistent within a trial, whereas they would vary widely on occasional forks. I extended testing down to 50-entry maps, to explore the rise in service times that I was seeing at small scale. This is probably a timing artifact, from too-short invocations, since I'm using @Level.Invocation in the put() tests. To fix that, I enlarged the unit of testing, by creating multiple, sometimes thousands, of maps for the invocation to fill. This has also changed the test from filling a previously-filled map, to filling a new, but sufficiently sized map. The put()/remove() test now performs much worse (on a more realistic scenario). This also adds a couple tests for calling get() against a map that's been filled only with put()s, or with a mix of put() and remove(). --- .../collection/mutable/OpenHashMapBenchmark.scala | 179 +++++++++++++++++---- 1 file changed, 144 insertions(+), 35 deletions(-) (limited to 'test/benchmarks/src') 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 eeea8f6508..73ab5e40d0 100644 --- a/test/benchmarks/src/main/scala/scala/collection/mutable/OpenHashMapBenchmark.scala +++ b/test/benchmarks/src/main/scala/scala/collection/mutable/OpenHashMapBenchmark.scala @@ -2,46 +2,104 @@ 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 +/** Utilities for the [[OpenHashMapBenchmark]]. + * + * The method calls are tested by looping to the size desired for the map; + * 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. * - * Provides a thread-scoped map, so that allocation for the hash table will be done - * in the first warm-up iteration, not during measurement. + * Provides an array of adequately-sized, empty maps to each invocation, + * so that hash table allocation won't be done during measurement. * - * Performs a GC after every invocation, so that only the GCs caused by the invocation - * contribute to the measurement. + * Empties the map and performs a GC after every invocation, + * so that only the GCs caused by the invocation contribute to the measurement. */ @State(Scope.Thread) + @AuxCounters class BulkPutState { + /** A lower-bound estimate of the number of nanoseconds per `put()` call */ + private[this] val nanosPerPut: Double = 5 + + /** Minimum number of nanoseconds per invocation, so as to avoid timing artifacts. */ + private[this] val minNanosPerInvocation = 1000000 // one millisecond + + /** The minimum number of `put()` calls to make per invocation, so as to avoid timing artifacts. */ + private[this] val minPutsPerInvocation = minNanosPerInvocation / nanosPerPut + + /** Size of the maps created in this trial. */ + private[this] var size: Int = _ + + /** Number of maps created in each invocation; the size of `maps`. */ + private[this] var n: Int = _ + + /** Number of operations performed in the current invocation. */ + var operations: Int = _ + + var maps: Array[OpenHashMap[Int,Int]] = null + + @Setup + def threadSetup(params: BenchmarkParams) { + size = params.getParam("size").toInt + n = math.ceil(minPutsPerInvocation / size).toInt + maps = new Array(n) + } + + @Setup(Level.Iteration) + def iterationSetup { + operations = 0 + } + + @Setup(Level.Invocation) + def setup { + for (i <- 0 until n) maps(i) = new OpenHashMap[Int,Int](size) + operations += size * n + System.gc() // clean up after last invocation + } + } + + /** State container for the `get()` bulk calling tests. + * + * Provides a thread-scoped map of the expected size. + * Performs a GC after loading the map. + */ + @State(Scope.Thread) + class BulkGetState { val map = new OpenHashMap[Int,Int].empty - - @TearDown(Level.Invocation) - def teardown { map.clear(); System.gc() } + + /** 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) + System.gc() + } } -} -/** Benchmark for the library's [[OpenHashMap]]. - * - * The `put()` calls are tested by looping to the size desired for the map; - * instead of using the JMH harness, which iterates for a fixed length of time. - */ -@BenchmarkMode(Array(Mode.AverageTime)) -@Threads(1) -@Fork(1) -@Warmup(iterations = 20) -@Measurement(iterations = 20) -@OutputTimeUnit(TimeUnit.MICROSECONDS) -@State(Scope.Benchmark) -class OpenHashMapBenchmark { - import OpenHashMapBenchmark._ + /** 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. + */ + @State(Scope.Thread) + class BulkRemovedGetState { + val map = new OpenHashMap[Int,Int].empty - @Param(Array("100", "250", "1000", "2500", "10000", "25000", "100000", "250000", "1000000", "2500000", - "5000000", "7500000", "10000000", "25000000")) - var size: Int = _ + /** 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) + System.gc() + } + } /** Put elements into the given map. */ - private[this] def put_Int(map: OpenHashMap[Int,Int], from: Int, to: Int) { + private def put_Int(map: OpenHashMap[Int,Int], from: Int, to: Int) { var i = from while (i <= to) { // using a `for` expression instead adds significant overhead map.put(i, i) @@ -49,28 +107,79 @@ class OpenHashMapBenchmark { } } - /** Test putting elements to a map of `Int` to `Int`. */ - @Benchmark - def put_Int(state: BulkPutState) { put_Int(state.map, 1, size) } - - /** Test putting and removing elements to a growing map of `Int` to `Int`. */ - @Benchmark - def put_remove_Int(state: BulkPutState) { + /** Put elements into the given map, removing half of them as they're added. + * + * @param size number of entries to leave in the map on return + */ + 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 var base = 0 while (base < totalPuts) { - put_Int(state.map, base + 1, base + blockSize) + put_Int(map, base + 1, base + blockSize) // remove every other entry var i = base + 1 while (i <= base + blockSize) { - state.map.remove(i) + map.remove(i) i += 2 } base += blockSize } } + + /** 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)) + i += 1 + } + } +} + +/** Benchmark for the library's [[OpenHashMap]]. */ +@BenchmarkMode(Array(Mode.AverageTime)) +@Fork(10) +@Threads(1) +@Warmup(iterations = 20) +@Measurement(iterations = 6) +@OutputTimeUnit(TimeUnit.NANOSECONDS) +@State(Scope.Benchmark) +class OpenHashMapBenchmark { + import OpenHashMapBenchmark._ + + @Param(Array("50", "100", "250", "1000", "2500", "10000", "25000", "100000", "250000", "1000000", "2500000", + "5000000", "7500000", "10000000", "25000000")) + var size: Int = _ + + /** Test putting elements to a map of `Int` to `Int`. */ + @Benchmark + def put_Int(state: BulkPutState) { + var i = 0 + while (i < state.maps.length) { + OpenHashMapBenchmark.put_Int(state.maps(i), 1, size) + i += 1 + } + } + + /** Test putting and removing elements to a growing map of `Int` to `Int`. */ + @Benchmark + def put_remove_Int(state: BulkPutState) { + var i = 0 + while (i < state.maps.length) { + OpenHashMapBenchmark.put_remove_Int(state.maps(i), size) + 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) + + /** Test getting elements from a map of `Int` to `Int` from which elements have been removed. */ + @Benchmark + def put_remove_get_Int(state: BulkRemovedGetState, bh: Blackhole) = OpenHashMapBenchmark.get_Int(state.map, size, bh) } -- cgit v1.2.3