scala/scala — pull request #3911 by alextg-github (2014-08-04 01:36:33+00:00)
Title: SI-8774 - set HashMap/HashSet node's link fields to null when removed

Several collection types have var link fields in their nodes. Examples
include HashMap, LinkedHashMap, LinkedHashSet, and ParHashMap. 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.

The PR includes 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. The test not included in this changeset because it needs to be
run in a way that can quantify the number of full GCs that occur during
the third phase.

When run on the existing code base, the test shows frequent repeated
full GCs after phase three starts. The fix is relatively straightforward:
add code in the remove operations to null out the link fields. With the
fix, there are only young GCs during that final phase.

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.

testing: "test/partest --all" passes all tests