mutable LinkedHashMap/LinkedHashSet nodes' link fields should be nulled out when removed #8774
Description
Several collection types have var link fields in their nodes. Examples are LinkedHashMap, and LinkedHashSet. As implemented, removal of a value from one of these structures unlinks the node from the collection but leaves that node's link fields unchanged. This can lead to a form of nepotism causing unnecessary promotion of objects in generational garbage collection and can lead to sequences of frequent full garbage collections.
How does this happen? These fields allow older (previously allocated objects) to point to younger objects in the heap. If a removed node happens to be in an older generation, the fact that it refers to younger objects causes these objects to be promoted even if they are otherwise unreachable. This then causes an instance of one of these collections (especially if used as a queue) to repeatedly promote objects that should have been collected in the young generation. The problem is not a semantic one, but instead, a limitation of incremental tracing garbage collection in which it collects part of the heap while treating another part, conservatively, as if it were reachable.
Below is a simple benchmark (LinkedHashMapTest.scala) that shows the issue. The benchmark has three phases. In the first phase, a LinkedHashMap[Int, Int] is populated. In the second phase, that collection instance (and all its nodes) is promoted by invoking System.gc(). In the final phase, nodes are repeatedly added and removed as if the data structure were a queue.
In my tests, I ran the benchmark on a build of the top-of-tree for the scala-lang repo on OpenJDK 1.7. For options, I had:
export JAVA_OPTS="-verbose:gc -XX:+PrintGCDetails -XX:+UseParallelGC"
The command to run it was:
test/partest ~/tests/linkedhashmap/LinkedHashMapTest.scala
With an unmodified tree, one gets behavior like what is reported in the following attached logs:
run-bad.log: output from partest, itself
LinkedHashMapTest-linkedhashmap.log-bad: the log in the test directory generated by partest
One can see that in phase 3, the test does repeated full GCs as the nodes of the LinkedHashMap are all promoted.
The fix is relatively straightforward: add code in the remove operations to null out the link fields. My diffs for the top-of-tree can be seen in the attached file, gif-diffs.txt. With a tree modified with these diffs, one gets behavior like what is reported in these attached logs when running the same above test:
run-good.log: output from par test
LinkedHashMapTest-linkedhashmap.log-good: the log in the test directory generated by partest
As can be seen, there are now only young GCs when the test is run with the modified tree.
Separately, I have run the full test suite that comes with the repo and all tests pass.
Aside: This all came out of the observation of occasional/unpredictable spikes in GC activity in some of our services. We also found and fixed these issues with the Java LinkedHashMap class and fixed our 1.7 JDK to also null out these link fields. We've verified that this fixes the pathologies we saw. We also found that, independently, the OpenJDK 1.8 class files for these collection classes have also been modified (by Oracle) to null out these link fields. We'd now like to do the same for the Scala types.