Changed HashMap.getOrElseUpdate to only calculate the index once #5528

l0rinc · 2016-11-14T19:47:07Z

Fixes https://issues.scala-lang.org/browse/SI-10049

Since groupBy uses this method extensively and suffered a measurable slowdown in 2.12.0, this modification restores (and exceeds) its original speed.

included benchmarks:

(ns/op → smaller is better)

before (2.12.0):

Benchmark                                     (size)  Mode  Cnt      Score      Error  Units
s.c.immutable.VectorMapBenchmark.groupBy          10  avgt   20    865.693 ±    7.869  ns/op
s.c.immutable.VectorMapBenchmark.groupBy         100  avgt   20   3095.657 ±   56.438  ns/op
s.c.immutable.VectorMapBenchmark.groupBy        1000  avgt   20  28247.005 ±  470.513  ns/op
s.c.mutable.HashMapBenchmark.getOrElseUpdate      10  avgt   20    836.561 ±   20.085  ns/op
s.c.mutable.HashMapBenchmark.getOrElseUpdate     100  avgt   20   7891.368 ±   56.808  ns/op
s.c.mutable.HashMapBenchmark.getOrElseUpdate    1000  avgt   20  97478.629 ± 1782.497  ns/op

after:

Benchmark                                     (size)  Mode  Cnt      Score      Error  Units
s.c.immutable.VectorMapBenchmark.groupBy          10  avgt   20    627.007 ±    9.718  ns/op
s.c.immutable.VectorMapBenchmark.groupBy         100  avgt   20   2086.955 ±   19.042  ns/op
s.c.immutable.VectorMapBenchmark.groupBy        1000  avgt   20  19515.234 ±  173.647  ns/op
s.c.mutable.HashMapBenchmark.getOrElseUpdate      10  avgt   20    503.208 ±    2.643  ns/op
s.c.mutable.HashMapBenchmark.getOrElseUpdate     100  avgt   20   5526.483 ±   28.262  ns/op
s.c.mutable.HashMapBenchmark.getOrElseUpdate    1000  avgt   20  69265.900 ±  674.958  ns/op

i.e. for the given benchmark conditions ~40% faster groupBy and getOrElseUpdate

l0rinc · 2016-11-14T19:53:29Z

Signed the Scala CLA

l0rinc · 2016-11-14T19:56:44Z

src/library/scala/collection/mutable/HashMap.scala

@@ -72,6 +72,17 @@ extends AbstractMap[A, B]
    else Some(e.value)
  }

+  override def getOrElseUpdate(key: A, defaultValue: => B): B = {


In case the element was missing from the map, the hash code (with some added variance) was calculated first for verification, and again for the put operation.

I'm not sure this is a binary-compatible change. @retronym - is this? I would not intuitively have thought it would be with the new trait encoding, but I'm not sure of the new rules.

@Ichoran It should be binary compatible. A class gets a forwarder method that delegates to the static implementation method of the interface. Adding an override merely replaces the implementation of the class method without any changes to the signatures. I'll add a proper test case for this to MiMa.

l0rinc · 2016-11-14T19:58:16Z

src/library/scala/collection/mutable/HashTable.scala

@@ -131,7 +131,7 @@ trait HashTable[A, Entry >: Null <: HashEntry[A, Entry]] extends HashTable.HashU
  protected def findEntry(key: A): Entry =
    findEntry0(key, index(elemHashCode(key)))

-  private[this] def findEntry0(key: A, h: Int): Entry = {
+  protected[this] final def findEntry0(key: A, h: Int): Entry = {


These two parent methods needed to be accessed from HashMap to avoid calculation the hash code twice.
final was added to keep the semantics, changing only the visibility of the method.

I'm not 100% sure this change is forwards binary compatible. A custom subclass of 2.12.1 hashtable might rely on this newly exposed API and incur a linkage error if run with the 2.12.0 standard library. Our build is supposed to check for such violations, but it hasn't flagged this problem. I need to check out if there is a problem in our build, or in MiMa itself. This won't be a blocker for the change as we can always copy/paste these private methods into HashMap for the 2.12.x releases.

It would also be see whether performance of other methods in mutable.HashMap could be improved by using copy/pasted implementations of findEntry etc rather than those inherited from the HashTable trait. Obviously this isn't an ideal solution, but HashMap is so widely used, and these methods are so tiny that failure to JIT inline can have a real impact of observable performance, that I'd be open to this solution for 2.12.1.

My fix isn't about the inlining limit, that's a side-effect of collapsing the stack depth by calling the indexing methods earlier.

This fix would speed up 2.11 also.

Please advise on how you want me to change this PR.
I could start by adding a JMH benchmark for HashMap and verifying the performance of other methods also - and trying to optimize them on the way.
Are we sure we want to do the benchmarks from Scala and not Java?

@retronym, we would be forced to include more than these two methods, if we don't want to make it protected :/

If you inline findEntry0 and addEntry0 you'll end up with entirely protected methods, I think.

@retronym I agree about the binary compatibility. I'll check MiMa for a test case. I'd be surprised if this isn't covered or doesn't work. Could indeed be a problem of the Scala build.

adriaanm · 2016-11-14T20:22:55Z

Review by @Ichoran

retronym · 2016-11-15T00:53:00Z

The benchmark could be added to our (recently added) JMH suite, in the same place as OpenHashMapBenchmark.

We don't run these automatically, but it will at least provide a reference for someone studying this commit or making further changes to this area.

The benchmark itself could do with tests of workloads that exercise more code paths. For instance, using different key types will lead control through through more paths in BoxesRuntime.{equals*, hash*}, and different function arguments to produce the default to make the call to Function.apply within getOrElseUpdate megamorphic.

l0rinc · 2016-11-15T16:44:48Z

test/benchmarks/README.md

-The benchmarks require first building Scala into `../../build/pack` with `ant`.
-If you want to build with `sbt dist/mkPack` instead,
-you'll need to change `scalaHome` in this project.
+The benchmarks require first building Scala into `../../build/pack`.


sbt does it correctly also, no need for ant anmore

l0rinc · 2016-11-15T16:46:11Z

test/benchmarks/project/plugins.sbt

@@ -1,2 +1,2 @@
 addSbtPlugin("com.typesafe.sbteclipse" % "sbteclipse-plugin" % "4.0.0")
-addSbtPlugin("pl.project13.scala" % "sbt-jmh" % "0.2.16")
+addSbtPlugin("pl.project13.scala" % "sbt-jmh" % "0.2.17")


Sent a PR to update SBT-JMH, it was accepted and the new version containing the latest JMH was included here

l0rinc · 2016-11-15T16:49:04Z

test/benchmarks/src/main/scala/scala/collection/mutable/HashMapBenchmark.scala

+    }
+  }
+
+  @Benchmark def getOrElseUpdate_missing(bh: Blackhole): Unit = {


these two (found and not found in map) should probably be separated, as they have different speeds.
Otherwise the result would depend on their cardinality's ratio.

l0rinc · 2016-11-15T16:51:02Z

src/library/scala/collection/mutable/HashTable.scala

@@ -131,7 +131,7 @@ trait HashTable[A, Entry >: Null <: HashEntry[A, Entry]] extends HashTable.HashU
  protected def findEntry(key: A): Entry =
    findEntry0(key, index(elemHashCode(key)))

-  private[this] def findEntry0(key: A, h: Int): Entry = {
+  protected[this] final def findEntry0(key: A, h: Int): Entry = {


@retronym, we would be forced to include more than these two methods, if we don't want to make it protected :/

Ichoran · 2016-11-15T17:18:30Z

test/benchmarks/src/main/scala/scala/collection/immutable/VectorMapBenchmark.scala

+  @Setup(Level.Trial) def initKeys(): Unit = {
+    values = (0 to size).map(i => (i % 10) match {
+      case 0 => i.toString
+      case 1 => i.toByte


This seems excessive. Object and non-object are different paths, and maybe constant-box vs. newly allocated box (byte vs double) is good to check. Having to worry about so many seems excessive.

Ichoran · 2016-11-15T17:26:00Z

src/library/scala/collection/mutable/HashMap.scala

+      addEntry0(newEntry, i)
+      newEntry.value
+    }
+  }


This implementation looks fine, but what about using findOrAddEntry in HashTable? Does that still show the same speed improvement?

The idea is very good, but we don't have a value in HashTable's Entry, only key and next.

The other alternative would be to call findOrAddEntry directly, but then defaultValue would be evaluated twice, which should probably be avoided, right?

override def getOrElseUpdate(key: A, defaultValue: => B): B = { val e = findOrAddEntry(key, defaultValue) if (e ne null) e.value else defaultValue }

which should probably be avoided, right?

Correct. Also, we mustn't evaluate defaultValue if the key already exists.

Oops, didn't read the signatures correctly. It's not evaluating twice which is a problem; it's evaluating more than zero times when the entry exists. You're right; we can't do it this way.

Thanks!
In this particular case I think it cannot be evaluated once, only zero or two times (doesn't change the fact).

Ichoran · 2016-11-15T22:57:09Z

@paplorinc - As an aside: I'm not sure why using JMH from Scala rather than Java is "counter-intuitive" for you. A benchmark that depends on what language you use to embed it is almost by definition a bad benchmark because it means that the incidental stuff that you are not supposed to care about is not negligibly inexpensive compared to what you're actually interested in.
If there is a difference, I still wouldn't expect it to necessarily work out in favor of using Java for Scala (and vice-versa, I suppose): by removing the Scala code from a more normal context, you might make the microbenchmarking results even less relevant to normal usage than microbenchmarks usually are. For instance, if javac uses a pattern around the benchmark that is really easy for the JIT compiler to optimize away, but almost all use cases are from Scala with scalac's not-exactly-the-same pattern, you might fail to see an effect that is bothering everyone.
But really, the point is if it matters, it's already being done wrong. (The ops/s reported here are pretty well into the safe range where you could even call with interpreted Groovy and it'd be fine.)

Ichoran · 2016-11-15T23:06:25Z

I think the core question that I don't have an answer to is whether we're allowed to introduce an override to getOrElseUpdate and still stay binary compatible. If yes, then I think the other issues can be worked around by duplicating code (inlining it manually) until you end up with a set of calls to protected or public methods. If yes in both 2.12 and 2.11, maybe this patch could be backported! Faster hash maps benefit almost everyone.

retronym · 2016-11-16T01:05:31Z

I think the core question that I don't have an answer to is whether we're allowed to introduce an override to getOrElseUpdate and still stay binary compatible

This is okay because the class already inherits a method with and identical signature from AbstractMap. Client code of 2.12.1 may include invokevirtual HashMap.getOrElseUpdate, but this will not incur an IncompatibleClassChangeError if linked against the 2.12.0 class thanks to the override.

Here's an example of making this class change with Java code without linkage errors: https://gist.github.com/794c9f88771b210f5dab0b65793b4682

Here's the MiMa test case that shows that deleting an exact override is backwards compatible (meaning adding an exact override, like we do here, is forward compatible!)

Ichoran · 2016-11-16T01:19:26Z

@retronym - Okay, then I think we're clear once @paplorinc switches to use table and friends instead of addEntry0 etc.. Hopefully that will still show a speedup. The JIT compiler won't be able to take advantage of its efforts in already optimizing addEntry0, but hopefully it'll do just as well on the inlined version.

l0rinc · 2016-11-16T08:23:22Z

@Ichoran, to be sure I understand what you're requesting, do you want me to keep copy-pasting things from HashTable until everything compiles? That would result in duplicating even some fields:

override def getOrElseUpdate(key: A, defaultValue: => B): B = {
  val i = index(elemHashCode(key))
  val entry = findEntry0(key, i)
  if (entry != null)
    entry.value
  else {
    val newEntry = createNewEntry(key, defaultValue)
    addEntry0(newEntry, i)
    newEntry.value
  }
}
private[this] final def findEntry0(key: A, h: Int): Entry = {
  var e = table(h).asInstanceOf[Entry]
  while (e != null && !elemEquals(e.key, key)) e = e.next
  e
}
private[this] final def addEntry0(e: Entry, h: Int) {
  e.next = table(h).asInstanceOf[Entry]
  table(h) = e
  tableSize = tableSize + 1
  nnSizeMapAdd(h)
  if (tableSize > threshold)
    resize(2 * table.length)
}
private def resize(newSize: Int) {
  val oldTable = table
  table = new Array(newSize)
  nnSizeMapReset(table.length)
  var i = oldTable.length - 1
  while (i >= 0) {
    var e = oldTable(i)
    while (e != null) {
      val h = index(elemHashCode(e.key))
      val e1 = e.next
      e.next = table(h).asInstanceOf[Entry]
      table(h) = e
      e = e1
      nnSizeMapAdd(h)
    }
    i = i - 1
  }
  threshold = newThreshold(_loadFactor, newSize)
}
private[collection] final def newThreshold(_loadFactor: Int, size: Int) = ((size.toLong * _loadFactor) / loadFactorDenom).toInt
private[collection] final def loadFactorDenom = 1000

edit: about the Scala JMH tests (which I provided upon request), my concern is that (using a metaphor) you cannot trust a patient to self-diagnose an illness. i.e. you could use sbt-jmh for non-scala-core (i.e. when Scala is "healthy"), but for inside problems, you might be relying on the problem itself for diagnosing it (i.e if the compiler emits wrong bytecode, the benchmark itself will contain that error).

edit2: I could extract some logic to stateless methods in HashTable to DRY it, if you think that's better than exposing two stateful metohods :)

edit3: I could annotate the two exposed methods with @migration("exposed for internal optimizations, might change in the future", "2.12.1")

Ichoran · 2016-11-16T09:29:01Z

@paplorinc - Which fields do you need? You've got everything already there as protected, don't you?

It might be easier to intercept the size and just eat the extra lookup on an addEntry in the relatively rare case that the table needs to be enlarged.

I grant that it's ugly either way, but if we can avoid even a minor binary incompatibility, I think it's for the best. If we'd caught this before 2.12 was out, I'd have much preferred your patch as it was where you just change the visibility of some things.

Also, I understand your point in general regarding using a flawed system to detect its own flaws, but in this particular case, do you also understand my point?

retronym · 2016-11-16T10:45:51Z

The binary incompatibility wasn't reported because of a regression in the entry point into MiMa we use. Will be fixed tomorrow: lightbend-labs/mima#138

l0rinc · 2016-11-16T11:41:14Z

@Ichoran, thanks for the idea, I've tested it from the new Scala benchmarks and they maintained their speed advantage (except for the case when it actually needs growing, but that's ok), and the code is also still maintainable - great balance!

Please wait with the merge until I validate the results from Java also (I get some strange results that I need to investigate)

@retronym, thank you for your investigations!

retronym · 2016-11-16T11:49:55Z

Could you please add comments in both copies of each duplicated method to warn maintainers about the duplication? For bonus points/pints, you could submit a PR to the 2.13.x branch to make them protected and shared.

l0rinc · 2016-11-16T15:39:14Z

src/library/scala/collection/mutable/HashMap.scala

+      e = e.next
+    e
+  }
+  private[this] def notFound(key: A, e: Entry): Boolean = (e != null) && !elemEquals(e.key, key)


extracted to make findEntry inlinable (and the method more readable):
scala.collection.mutable.HashMap::findEntry (32 bytes) inline (hot)

l0rinc · 2016-11-16T15:39:34Z

src/library/scala/collection/mutable/HashMap.scala

+  private[this] def notFound(key: A, e: Entry): Boolean = (e != null) && !elemEquals(e.key, key)
+
+  /* inlined HashTable.addEntry0 to preserve its visibility */
+  private[this] def addEntry(e: Entry, h: Int): B = {


scala.collection.mutable.HashMap::addEntry (30 bytes) inline (hot)

l0rinc · 2016-11-16T15:40:27Z

src/library/scala/collection/mutable/HashMap.scala

@@ -72,6 +72,37 @@ extends AbstractMap[A, B]
    else Some(e.value)
  }

+  override def getOrElseUpdate(key: A, defaultValue: => B): B = {


scala.collection.mutable.HashMap::getOrElseUpdate (48 bytes) inline (hot)

l0rinc · 2016-11-16T15:41:15Z

src/library/scala/collection/mutable/HashTable.scala

@@ -365,9 +365,8 @@ trait HashTable[A, Entry >: Null <: HashEntry[A, Entry]] extends HashTable.HashU
  // this is of crucial importance when populating the table in parallel
  protected final def index(hcode: Int) = {


scala.collection.mutable.HashTable::index (33 bytes) inline (hot)

l0rinc · 2016-11-16T15:46:05Z

src/library/scala/collection/mutable/HashTable.scala

-    val improved = improve(hcode, seedvalue)
-    val shifted = (improved >> (32 - java.lang.Integer.bitCount(ones))) & ones
-    shifted
+    val exponent = Integer.numberOfLeadingZeros(ones)


since table.length is a power of two, table.length - 1 is composed of ones. The bitCount of that is the number of ones (= the exponent of the original power of 2), subtracted from 32 is the number of trailing zeroes.

The benchmark indicates that this is smaller and faster:

public static class Test { final int[] squares = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824}; @Benchmark public void bitCount(Blackhole bh) { for (int i = 0; i < squares.length; i++) { int leadingZeros = Integer.SIZE - Integer.bitCount(squares[i] - 1); bh.consume(leadingZeros); } } @Benchmark public void numberOfLeadingZeros(Blackhole bh) { for (int i = 0; i < squares.length; i++) { int leadingZeros = Integer.numberOfLeadingZeros(squares[i] - 1); bh.consume(leadingZeros); } } }

Benchmark Score Error Units Test.bitCount 8746665.311 ± 206703.549 ops/s Test.numberOfLeadingZeros 9255031.968 ± 114967.712 ops/s

(ops/s, greater is better)

Note: this affect all hashing operations!

Speed improvement or no, when the goal is to count the number of leading zeros it's better to clean up the method and say numberOfLeadingZeros unless there's a significant performance hit. It's nice that it's faster too, though!

l0rinc · 2016-11-16T15:47:16Z

src/library/scala/runtime/BoxesRunTime.java

-
-        return x.equals(y);
+    private static boolean equalsNotSame(Object x, Object y) {
+        return x != null && y != null && equalsNotSameOrNull(x, y);


if they're not the same (==), but one of them is null, they're certainly not equal
(scala.runtime.BoxesRunTime::equalsNotSame (22 bytes) inline (hot))

l0rinc · 2016-11-16T15:47:55Z

src/library/scala/runtime/BoxesRunTime.java

-            return equalsNumChar(xn, (java.lang.Character)y);
-        if (xn == null)
-            return y == null;
+    private static boolean equalsNotSameOrNull(Object x, Object y) {


scala.runtime.BoxesRunTime::equalsNotSameOrNull (38 bytes) inline (hot)

l0rinc · 2016-11-16T15:48:51Z

test/benchmarks/src/main/scala/scala/collection/mutable/HashMapBenchmark.scala

+  var keys: Vector[Any] = _
+
+  @Setup(Level.Trial) def initKeys(): Unit = {
+    keys = (0 to size).map(i => (i % 4) match {


@Ichoran, reduced the number of possibilities, hope it's ok now :)

This looks reasonable, thanks :)

…ethod As questioned in scala/scala#5528

retronym · 2016-11-17T05:57:03Z

src/library/scala/runtime/BoxesRunTime.java


-        return xn.equals(y);
+    static boolean equalsNumObject(java.lang.Number xn, Object y) {


We can't change signatures or accessibility of these methods. Even after the #5532, our binary compatibility checker didn't pick up this problem. I've patched the tool in lightbend-labs/mima#142 to report these errors.

Beyond the constraint that we can't change signatures, we also can't change semantics of of these "building blocks" of boxed equality, because the compiler emits direct calls to a variety of them, depending on how much static knowledge we have about the types and nullability of the arguments.

It is safe to introduce new private methods, and to refactor existing methods to use those private methods, so long at the semantics of existing non-private methods is unchanged.

I'd suggest to split out changes to BoxesRuntime into a separate commit and present benchmark results. We need to weigh up the performance wins against the risk of introducing regressions or subtle compatibility problems when mixing library from 2.12.1 with code compiled with 2.12.0 and vice versa.

My patched version of MiMa reports:

Found 5 binary incompatibilities ================================ * method equalsNumObject(java.lang.Number,java.lang.Object)Boolean in class scala.runtime.BoxesRunTime is inaccessible in current version, it must be public. * method equals2(java.lang.Object,java.lang.Object)Boolean in class scala.runtime.BoxesRunTime does not have a correspondent in current version * method equalsCharObject(java.lang.Character,java.lang.Object)Boolean in class scala.runtime.BoxesRunTime does not have a correspondent in current version * method equalsNumNum(java.lang.Number,java.lang.Number)Boolean in class scala.runtime.BoxesRunTime is inaccessible in current version, it must be public. * method equalsNumChar(java.lang.Number,java.lang.Character)Boolean in class scala.runtime.BoxesRunTime does not have a correspondent in current version

Thanks @retronym, will split it :)

l0rinc · 2016-11-17T15:31:43Z

test/benchmarks/README.md

@@ -18,8 +16,7 @@ Using this example, one would simply run

    jmh:runMain scala.collection.mutable.OpenHashMapRunner


not sure how to run only a single benchmark, sbt jmh:run runs everything, even if I provide a pattern after it :/

l0rinc · 2016-11-17T15:32:24Z

test/benchmarks/src/main/scala/scala/collection/mutable/HashMapBenchmark.scala

+    }
+  }
+
+  @Benchmark def get(bh: Blackhole): Unit = {


added get and put also, even though they weren't affected by this commit

l0rinc · 2016-11-17T15:32:49Z

test/benchmarks/src/main/scala/scala/collection/mutable/HashMapBenchmark.scala

+    var map = new mutable.HashMap[Any, Any]
+
+    var i = 0;
+    while (i < size) {


changed for comprehension to while for better SNR

Fixes https://issues.scala-lang.org/browse/SI-10049 Since `groupBy` uses this method extensively and suffered a measurable slowdown in `2.12.0`, this modification restores (and exceeds) its original speed. --- included benchmarks: (`ns/op` → smaller is better) `before (2.12.0):` ```java Benchmark (size) Mode Cnt Score Error Units s.c.immutable.VectorMapBenchmark.groupBy 10 avgt 20 865.693 ± 7.869 ns/op s.c.immutable.VectorMapBenchmark.groupBy 100 avgt 20 3095.657 ± 56.438 ns/op s.c.immutable.VectorMapBenchmark.groupBy 1000 avgt 20 28247.005 ± 470.513 ns/op s.c.mutable.HashMapBenchmark.get 10 avgt 20 679.448 ± 11.809 ns/op s.c.mutable.HashMapBenchmark.get 100 avgt 20 7240.178 ± 61.734 ns/op s.c.mutable.HashMapBenchmark.get 1000 avgt 20 95725.127 ± 2373.458 ns/op s.c.mutable.HashMapBenchmark.getOrElseUpdate 10 avgt 20 836.561 ± 20.085 ns/op s.c.mutable.HashMapBenchmark.getOrElseUpdate 100 avgt 20 7891.368 ± 56.808 ns/op s.c.mutable.HashMapBenchmark.getOrElseUpdate 1000 avgt 20 97478.629 ± 1782.497 ns/op s.c.mutable.HashMapBenchmark.put 10 avgt 20 243.422 ± 2.915 ns/op s.c.mutable.HashMapBenchmark.put 100 avgt 20 5810.927 ± 60.054 ns/op s.c.mutable.HashMapBenchmark.put 1000 avgt 20 82175.539 ± 1690.296 ns/op ``` `after:` ```java Benchmark (size) Mode Cnt Score Error Units s.c.immutable.VectorMapBenchmark.groupBy 10 avgt 20 627.007 ± 9.718 ns/op s.c.immutable.VectorMapBenchmark.groupBy 100 avgt 20 2086.955 ± 19.042 ns/op s.c.immutable.VectorMapBenchmark.groupBy 1000 avgt 20 19515.234 ± 173.647 ns/op s.c.mutable.HashMapBenchmark.get 10 avgt 20 683.977 ± 11.843 ns/op s.c.mutable.HashMapBenchmark.get 100 avgt 20 7345.675 ± 41.092 ns/op s.c.mutable.HashMapBenchmark.get 1000 avgt 20 95085.926 ± 1702.997 ns/op s.c.mutable.HashMapBenchmark.getOrElseUpdate 10 avgt 20 503.208 ± 2.643 ns/op s.c.mutable.HashMapBenchmark.getOrElseUpdate 100 avgt 20 5526.483 ± 28.262 ns/op s.c.mutable.HashMapBenchmark.getOrElseUpdate 1000 avgt 20 69265.900 ± 674.958 ns/op s.c.mutable.HashMapBenchmark.put 10 avgt 20 252.481 ± 7.597 ns/op s.c.mutable.HashMapBenchmark.put 100 avgt 20 5708.034 ± 110.360 ns/op s.c.mutable.HashMapBenchmark.put 1000 avgt 20 82051.378 ± 1432.009 ns/op ``` i.e. for the given benchmark conditions `~40%` faster `groupBy` and `getOrElseUpdate`

l0rinc · 2016-11-18T13:53:41Z

@Ichoran, not sure why the build is failing do I still have a MiMa violation?
library/mima failed: java.lang.RuntimeException: MiMa failed with exit code 1

szeiger · 2016-11-18T14:07:19Z

[info] Checking backward binary compatibility
[info] prev = /home/jenkins/.ivy2/cache/org.scala-lang/scala-library/jars/scala-library-2.12.0.jar, curr = /home/jenkins/workspace/scala-2.12.x-validate-test@2/build/pack/lib/scala-library.jar
Found 1 binary incompatibilities
================================
 * method getExitValue()scala.Tuple2 in class
   scala.sys.process.ProcessImpl#CompoundProcess does not have a correspondent
   in current version

Generated backward filter config definition
============================================

    filter {
        problems=[
            {
                matchName="scala.sys.process.ProcessImpl#CompoundProcess.getExitValue"
                problemName=DirectMissingMethodProblem
            }
        ]
    }


Generated forward filter config definition
===========================================

    filter {
        problems=[]
    }

szeiger · 2016-11-18T14:09:13Z

This looks like an unrelated failure due to MiMa having been accidentally disabled for a while.

l0rinc · 2016-11-18T16:12:57Z

@szeiger, what should I do to fix it (tried rebasing and retriggering the build)?

szeiger · 2016-11-18T17:09:58Z

/nothingtoseehere

The failure is due to #5481, which was based on an older commit before #5532, so the problem was not detected. There is nothing to do here. Since the binary incompatibility is in a private implementation class I would argue that we should whitelist it. @retronym, do you agree?

The other failure in the new build is a spurious error that we've seen before.

Ichoran

LGTM

retronym · 2016-11-22T06:10:53Z

LGTM, too. This is a fantastic contribution, keep them coming!

l0rinc · 2016-11-22T09:32:06Z

Thanks for your help @Ichoran, @retronym and @szeiger!

scala-jenkins added this to the 2.12.2 milestone Nov 14, 2016

SethTisue modified the milestones: 2.12.1, 2.12.2 Nov 14, 2016

l0rinc commented Nov 14, 2016

View reviewed changes

l0rinc force-pushed the getOrElseUpdate branch from 7086725 to 47cffd3 Compare November 15, 2016 16:43

l0rinc commented Nov 15, 2016

View reviewed changes

Ichoran reviewed Nov 15, 2016

View reviewed changes

retronym mentioned this pull request Nov 15, 2016

Is MiMa really working for 2.12.1? scala/scala-dev#264

Closed

l0rinc force-pushed the getOrElseUpdate branch 3 times, most recently from 4dac2b0 to e37b62e Compare November 15, 2016 22:36

l0rinc force-pushed the getOrElseUpdate branch from e37b62e to df50ce7 Compare November 16, 2016 11:14

l0rinc force-pushed the getOrElseUpdate branch from df50ce7 to 8b383cf Compare November 16, 2016 15:28

l0rinc commented Nov 16, 2016

View reviewed changes

szeiger added a commit to szeiger/migration-manager that referenced this pull request Nov 16, 2016

Add test case class-method-concrete-override-of-concrete-supertrait-m…

e607d19

…ethod As questioned in scala/scala#5528

szeiger mentioned this pull request Nov 16, 2016

Add test case class-method-concrete-override-of-concrete-supertrait-method lightbend-labs/mima#139

Merged

l0rinc force-pushed the getOrElseUpdate branch from 8b383cf to ab02d44 Compare November 16, 2016 19:39

retronym mentioned this pull request Nov 17, 2016

Add support for Java-defined static members lightbend-labs/mima#142

Merged

retronym reviewed Nov 17, 2016

View reviewed changes

l0rinc force-pushed the getOrElseUpdate branch 3 times, most recently from 5cc7418 to b1c83ab Compare November 17, 2016 15:30

l0rinc commented Nov 17, 2016

View reviewed changes

l0rinc mentioned this pull request Nov 17, 2016

Optimized HashTable.index #5537

Merged

l0rinc added 3 commits November 18, 2016 12:48

Updated benchmark dependencies

e9303d9

Added benchmarks for Vector and HashMap

5c93cd2

l0rinc force-pushed the getOrElseUpdate branch from b1c83ab to b67ca7d Compare November 18, 2016 10:49

Ichoran approved these changes Nov 21, 2016

View reviewed changes

scala-jenkins added the reviewed label Nov 22, 2016

retronym merged commit 9c5d3f8 into scala:2.12.x Nov 22, 2016

l0rinc deleted the getOrElseUpdate branch November 22, 2016 09:31

This was referenced Apr 7, 2017

Substantial slowdown in groupBy (all collections) scala/bug#10049

Closed

Performance degradation in Akka with 2.12 scala/bug#10083

Closed

HashMap getOrElseUpdate changed behaviour in 2.12.1 if the callback modifies the map scala/bug#10187

Closed

retronym mentioned this pull request Sep 6, 2017

Use AnyRefMap in pickler, we don't actually need a linked map #6062

Merged

		@@ -365,9 +365,8 @@ trait HashTable[A, Entry >: Null <: HashEntry[A, Entry]] extends HashTable.HashU
		// this is of crucial importance when populating the table in parallel
		protected final def index(hcode: Int) = {


		return xn.equals(y);
		static boolean equalsNumObject(java.lang.Number xn, Object y) {

		@@ -18,8 +16,7 @@ Using this example, one would simply run

		jmh:runMain scala.collection.mutable.OpenHashMapRunner

Changed HashMap.getOrElseUpdate to only calculate the index once #5528

Changed HashMap.getOrElseUpdate to only calculate the index once #5528

Uh oh!

Conversation

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment