diff options
author | Adriaan Moors <adriaan@lightbend.com> | 2017-02-07 17:29:45 -0800 |
---|---|---|
committer | GitHub <noreply@github.com> | 2017-02-07 17:29:45 -0800 |
commit | 8038924acb9326ee8378b8dd916e2d74e388878d (patch) | |
tree | fd5eb585fa7de31e6574943ce26a6fda0da343d1 | |
parent | 5f944cca7e43f5c9f52e2294781f56634feba2d8 (diff) | |
parent | 43e9c9053538230a2af41657c7108232d9be0216 (diff) | |
download | scala-8038924acb9326ee8378b8dd916e2d74e388878d.tar.gz scala-8038924acb9326ee8378b8dd916e2d74e388878d.tar.bz2 scala-8038924acb9326ee8378b8dd916e2d74e388878d.zip |
Merge pull request #5673 from retronym/topic/hashmap-contains
Optimizations in immutable.Map.{get, contains}
-rw-r--r-- | bincompat-backward.whitelist.conf | 16 | ||||
-rw-r--r-- | bincompat-forward.whitelist.conf | 16 | ||||
-rw-r--r-- | src/library/scala/collection/immutable/HashMap.scala | 50 | ||||
-rw-r--r-- | test/benchmarks/src/main/scala/scala/collection/immutable/HashMapBenchmark.scala | 56 |
4 files changed, 128 insertions, 10 deletions
diff --git a/bincompat-backward.whitelist.conf b/bincompat-backward.whitelist.conf index d4db9962e7..b88fa64584 100644 --- a/bincompat-backward.whitelist.conf +++ b/bincompat-backward.whitelist.conf @@ -32,6 +32,22 @@ filter { { matchName="scala.sys.process.ProcessImpl#CompoundProcess.getExitValue" problemName=DirectMissingMethodProblem + }, + { + matchName="scala.collection.immutable.HashMap.contains0" + problemName=DirectMissingMethodProblem + }, + { + matchName="scala.collection.immutable.HashMap#HashTrieMap.contains0" + problemName=DirectMissingMethodProblem + }, + { + matchName="scala.collection.immutable.HashMap#HashMap1.contains0" + problemName=DirectMissingMethodProblem + }, + { + matchName="scala.collection.immutable.HashMap#HashMapCollision1.contains0" + problemName=DirectMissingMethodProblem } ] } diff --git a/bincompat-forward.whitelist.conf b/bincompat-forward.whitelist.conf index 533f1b2467..bb9078c362 100644 --- a/bincompat-forward.whitelist.conf +++ b/bincompat-forward.whitelist.conf @@ -42,6 +42,22 @@ filter { { matchName="scala.util.hashing.MurmurHash3.wrappedArrayHash" problemName=DirectMissingMethodProblem + }, + { + matchName="scala.collection.immutable.HashMap.contains0" + problemName=DirectMissingMethodProblem + }, + { + matchName="scala.collection.immutable.HashMap#HashTrieMap.contains0" + problemName=DirectMissingMethodProblem + }, + { + matchName="scala.collection.immutable.HashMap#HashMap1.contains0" + problemName=DirectMissingMethodProblem + }, + { + matchName="scala.collection.immutable.HashMap#HashMapCollision1.contains0" + problemName=DirectMissingMethodProblem } ] } diff --git a/src/library/scala/collection/immutable/HashMap.scala b/src/library/scala/collection/immutable/HashMap.scala index 6b29b084aa..627f723cb0 100644 --- a/src/library/scala/collection/immutable/HashMap.scala +++ b/src/library/scala/collection/immutable/HashMap.scala @@ -52,6 +52,9 @@ sealed class HashMap[A, +B] extends AbstractMap[A, B] def get(key: A): Option[B] = get0(key, computeHash(key), 0) + override final def contains(key: A): Boolean = + contains0(key, computeHash(key), 0) + override def updated [B1 >: B] (key: A, value: B1): HashMap[A, B1] = updated0(key, computeHash(key), 0, value, null, null) @@ -92,7 +95,7 @@ sealed class HashMap[A, +B] extends AbstractMap[A, B] import HashMap.{Merger, MergeFunction, liftMerger} private[collection] def get0(key: A, hash: Int, level: Int): Option[B] = None - + protected def contains0(key: A, hash: Int, level: Int): Boolean = false private[collection] def updated0[B1 >: B](key: A, hash: Int, level: Int, value: B1, kv: (A, B1), merger: Merger[A, B1]): HashMap[A, B1] = new HashMap.HashMap1(key, hash, value, kv) @@ -185,6 +188,7 @@ object HashMap extends ImmutableMapFactory[HashMap] with BitOperations.Int { } } + @deprecatedInheritance("This class will be made final in a future release.", "2.12.2") class HashMap1[A,+B](private[collection] val key: A, private[collection] val hash: Int, private[collection] val value: (B @uV), private[collection] var kv: (A,B @uV)) extends HashMap[A,B] { override def size = 1 @@ -195,6 +199,8 @@ object HashMap extends ImmutableMapFactory[HashMap] with BitOperations.Int { override def get0(key: A, hash: Int, level: Int): Option[B] = if (hash == this.hash && key == this.key) Some(value) else None + override protected def contains0(key: A, hash: Int, level: Int): Boolean = + hash == this.hash && key == this.key private[collection] override def updated0[B1 >: B](key: A, hash: Int, level: Int, value: B1, kv: (A, B1), merger: Merger[A, B1]): HashMap[A, B1] = if (hash == this.hash && key == this.key ) { if (merger eq null) { @@ -239,6 +245,9 @@ object HashMap extends ImmutableMapFactory[HashMap] with BitOperations.Int { override def get0(key: A, hash: Int, level: Int): Option[B] = if (hash == this.hash) kvs.get(key) else None + override protected def contains0(key: A, hash: Int, level: Int): Boolean = + hash == this.hash && kvs.contains(key) + private[collection] override def updated0[B1 >: B](key: A, hash: Int, level: Int, value: B1, kv: (A, B1), merger: Merger[A, B1]): HashMap[A, B1] = if (hash == this.hash) { if ((merger eq null) || !kvs.contains(key)) new HashMapCollision1(hash, kvs.updated(key, value)) @@ -294,6 +303,7 @@ object HashMap extends ImmutableMapFactory[HashMap] with BitOperations.Int { } } + @deprecatedInheritance("This class will be made final in a future release.", "2.12.2") class HashTrieMap[A, +B]( private[collection] val bitmap: Int, private[collection] val elems: Array[HashMap[A, B @uV]], @@ -306,21 +316,41 @@ object HashMap extends ImmutableMapFactory[HashMap] with BitOperations.Int { override def size = size0 override def get0(key: A, hash: Int, level: Int): Option[B] = { + // Note: this code is duplicated with `contains0` + val index = (hash >>> level) & 0x1f + if (bitmap == - 1) { + elems(index).get0(key, hash, level + 5) + } else { + val mask = (1 << index) + if ((bitmap & mask) != 0) { + val offset = Integer.bitCount(bitmap & (mask - 1)) + elems(offset).get0(key, hash, level + 5) + } else { + None + } + } + } + + override protected def contains0(key: A, hash: Int, level: Int): Boolean = { + // Note: this code is duplicated from `get0` val index = (hash >>> level) & 0x1f - val mask = (1 << index) if (bitmap == - 1) { - elems(index & 0x1f).get0(key, hash, level + 5) - } else if ((bitmap & mask) != 0) { - val offset = Integer.bitCount(bitmap & (mask-1)) - elems(offset).get0(key, hash, level + 5) - } else - None + elems(index).contains0(key, hash, level + 5) + } else { + val mask = (1 << index) + if ((bitmap & mask) != 0) { + val offset = Integer.bitCount(bitmap & (mask - 1)) + elems(offset).contains0(key, hash, level + 5) + } else { + false + } + } } private[collection] override def updated0[B1 >: B](key: A, hash: Int, level: Int, value: B1, kv: (A, B1), merger: Merger[A, B1]): HashMap[A, B1] = { val index = (hash >>> level) & 0x1f val mask = (1 << index) - val offset = Integer.bitCount(bitmap & (mask-1)) + val offset = Integer.bitCount(bitmap & (mask - 1)) if ((bitmap & mask) != 0) { val sub = elems(offset) val subNew = sub.updated0(key, hash, level + 5, value, kv, merger) @@ -342,7 +372,7 @@ object HashMap extends ImmutableMapFactory[HashMap] with BitOperations.Int { override def removed0(key: A, hash: Int, level: Int): HashMap[A, B] = { val index = (hash >>> level) & 0x1f val mask = (1 << index) - val offset = Integer.bitCount(bitmap & (mask-1)) + val offset = Integer.bitCount(bitmap & (mask - 1)) if ((bitmap & mask) != 0) { val sub = elems(offset) val subNew = sub.removed0(key, hash, level + 5) diff --git a/test/benchmarks/src/main/scala/scala/collection/immutable/HashMapBenchmark.scala b/test/benchmarks/src/main/scala/scala/collection/immutable/HashMapBenchmark.scala new file mode 100644 index 0000000000..134cd6879b --- /dev/null +++ b/test/benchmarks/src/main/scala/scala/collection/immutable/HashMapBenchmark.scala @@ -0,0 +1,56 @@ +package scala.collection.immutable + +import org.openjdk.jmh.annotations._ +import org.openjdk.jmh.infra._ +import org.openjdk.jmh.runner.IterationType +import benchmark._ +import java.util.concurrent.TimeUnit + +@BenchmarkMode(Array(Mode.AverageTime)) +@Fork(2) +@Threads(1) +@Warmup(iterations = 10) +@Measurement(iterations = 10) +@OutputTimeUnit(TimeUnit.NANOSECONDS) +@State(Scope.Benchmark) +class HashMapBenchmark { + @Param(Array("10", "100", "1000")) + var size: Int = _ + + var existingKeys: Array[Any] = _ + var missingKeys: Array[Any] = _ + + @Setup(Level.Trial) def initKeys(): Unit = { + existingKeys = (0 to size).map(i => (i % 4) match { + case 0 => i.toString + case 1 => i.toChar + case 2 => i.toDouble + case 3 => i.toInt + }).toArray + missingKeys = (size to 2 * size).toArray + } + + var map: collection.immutable.HashMap[Any, Any] = null + + @Setup(Level.Trial) def initialize = { + map = collection.immutable.HashMap(existingKeys.map(x => (x, x)) : _*) + } + + @Benchmark def contains(bh: Blackhole): Unit = { + var i = 0; + while (i < size) { + bh.consume(map.contains(existingKeys(i))) + bh.consume(map.contains(missingKeys(i))) + i += 1 + } + } + + @Benchmark def get(bh: Blackhole): Unit = { + var i = 0; + while (i < size) { + bh.consume(map.get(existingKeys(i))) + bh.consume(map.get(missingKeys(i))) + i += 1 + } + } +} |