Summary

Reduce CPU and allocations when building RedBlackTree based structures (immutable.{TreeMap, TreeSet}) by using mutation in the builder. To make this work, the internal encoding of RedBlackTree is changed to use a single class, rather than encoding the colour into separate classes.

Mutability Handling

Mutable Trees are never contained in a TreeMap, or TreeSet, only ever in internal bulk operations of the builder. An immutable Tree cannot have a mutable Tree as a child, but a mutable Tree may have an immutable Tree as a child. This is to promote structural sharing

The major change the Tree is that the size, mutability, and colour are all determined by the _count field of the Tree. In the prior implementation the count ranged from 1 .. MaxInt, and the colour was based on the class. In the new implementation the colour is encoded in the top bit of _count and a value of 0 in the lower 31 bits indicated that the Tree is mutable. This way the range of count is maintained, and the other features are encoded within the same JVM footprint

Once a Tree has transitioned from mutable to immutable it can not become mutable again, so we use a copy-on-write to yield the mutable structure. Before the copy we always check that the values require a change, and if not return the structure unmodified to reduce garbage and promote structural sharing

All of the methods that can yield a mutable result have "mutable" on their name, and generally there is another method similarly named with doesn't. This is to aid safety and to reduce the cognitive load when reviewing changes. e.g.
upd with update an immutable Tree, producing an immutable Tree
mutableUpd will update a mutable or immutable Tree and may return a mutable or immutable Tree

When the series of mutable operations are complete, and the Tree needs to be exposed to the TreeMap/TreeSet the builder calls beforePublish which ensures that the returned Tree is immutable, and memory fences are enforced

Compatibliity:

The existing serialization form of these structures can be decoded. This is achieved keeping the RedBlackTree.{RedTree, BlackTree} classes in place with readResolve methods to generate instances of the new class, NewRedBlackTree.Tree. The new tests show that that the old format can be deserialized.

Conversely, the new structure has a writeReplace to convert to the old classes before serialization. This resulting serialized form is not byte-for-byte identical to before, because the type of leftTree/rightTree is now AnyRef, and Java serialization encodes this in the wire format, although it is not used in deserialization. The resulting format can be decoded on older version of 2.11.11 as follows:

➜ CL=/Users/jz/Library/Caches/Coursier/v1/https/repo1.maven.org/maven2/org/apache/commons/commons-lang3/3.11/commons-lang3-3.11.jar

➜ scala-launch 2.12.12 -nc -cp "$CL" -e 'java.nio.file.Files.write(java.nio.file.Paths.get("/tmp/ser.out"), org.apache.commons.lang3.SerializationUtils.serialize(scala.collection.mutable.TreeSet(1, 2, 3)))'

➜ scala-pr 8794 -nc -cp "$CL" -e 'println(org.apache.commons.lang3.SerializationUtils.deserialize(java.nio.file.Files.readAllBytes(java.nio.file.Paths.get("/tmp/ser.out"))))'
TreeSet(1, 2, 3)

➜ scala-pr 8794 -nc -cp "$CL" -e 'java.nio.file.Files.write(java.nio.file.Paths.get("/tmp/ser.out"), org.apache.commons.lang3.SerializationUtils.serialize(scala.collection.mutable.TreeSet(1, 2, 3)))'
➜ scala-launch 2.12.12 -nc -cp "$CL" -e 'println(org.apache.commons.lang3.SerializationUtils.deserialize(java.nio.file.Files.readAllBytes(java.nio.file.Paths.get("/tmp/ser.out"))))'
TreeSet(1, 2, 3)

The system properties scala.collection.immutable.TreeSet.newSerialisation and scala.collection.immutable.TreeMap.newSerialisation can be set to true if users don't require serialization compatiblity with older Scala 2.12 releases and want to opt-in to a more direct and compact serialization format, like the approach already in use in 2.13.x.

Irrespective of these setting the new reader will read old and new formats. The above setting apply to the format generated after this change. Prior code will not be able to read the new format

Performance.

The builder builds trees about 40-50% less CPU, and generally creates little or no garbage for ++= and +=.
When ++= is called with a compatible tree (i.e. with the same Ordering) the builder uses the existing union method, so there may be some garbage but the CPU usage is reduced further, and it promotes structural sharing, which seems a good trade-off

*** review notes

The first 3 commits are enablers ( backport of the RB tree, serialisation issues etc). The body of the mutability change is the later ones

*** current status
I am still looking a couple of places where the performance can be improved, but these will be small point fixes.

Detailed performance figures will be published in a separate comment