Optimize immutable.{TreeSet, TreeMap} by backporting the 2.13.x RedBlackTree improvements#8749
Conversation
|
As discussed, we can probably retain forwards and backwards serialization compatibility here by
|
|
benchmark for simple backport of RedBlackTree, without TreeSet/TreeMap |
|
Do we need the added complexity of the serialization proxies? I don't see any incompatible changes in the classes that make up the tree. Some methods have changes, which would affect the computed version, but the fields are the same. Wouldn't it be enough to add the right serialVersionUID to the new implementation? |
a22c426 to
ad0414a
Compare
|
Oh right, we just need to restore The first commit passes the serialization tests with that small change. In this review branch, I've then dropped the serialization proxy changes. They do have some benefits (more compact serialized form), but that could be discussed in a separate PR. I cherry picked the last commit. I added MiMa exceptions, but there are some changes we can't make compatibly: They need to be pulled up into a type-case the overriden method in the 2.12.x. |
This is due to the change in return type from
This one is package-private and can be ignored. |
|
see retronym#86 and retronym#85 |
ad0414a to
5b8bb6b
Compare
|
@mkeskells I've pushed our collective changes to make this binary compatible. I have also removed the serialization proxy. |
5b8bb6b to
2bd6186
Compare
| with MapLike[A, B, TreeMap[A, B]] | ||
| with Serializable | ||
| with HasForeachEntry[A, B] { | ||
| private[immutable] val tree: RB.Tree[A, B] = _tree |
There was a problem hiding this comment.
Is this different from making it a val directly in the parameter list?
There was a problem hiding this comment.
The has changed since you commented to private def tree0: RB.Tree[A, B] = tree.
The problem we have is that class C(x: A) and class C(private val x: A); object C { (_:C).x } are not serialization compatible because the reference from object C caused the compiler to emit the backing field for that val with a mangled name.
|
Hum ... I can't help but wonder: is this PR worth it? What is the benefit? Does it deserve to be backported to 2.12 so late in its cycle? |
| private def sameCBF(bf: CanBuildFrom[_,_,_]): Boolean = { | ||
| bf match { | ||
| case tsb: TreeSet.TreeSetBuilder[_] if tsb.ordering == ordering => true | ||
| case _ => false | ||
| } | ||
| } |
There was a problem hiding this comment.
You may want to take WrappedCanBuildFrom (created by breakOut) into account:
private def sameCBF(bf: CanBuildFrom[_,_,_]): Boolean = {
bf match {
case tsb: TreeSet.TreeSetBuilder[_] if tsb.ordering == ordering => true
case w: WrappedCanBuildFrom[_,_,_] =>
sameCBF(w.unwrapped)
case _ => false
}
}
There was a problem hiding this comment.
added when I rebased to avoid conflicts. This was the only change other than the conflicts
We are participating in this effort because the improvements in RB-Trees are relevant to a customer of ours. The changes are subject to the ordinary compatiblity constraints, and will benefit all 2.12 users. We're happy to discuss any particular concerns of course! |
2bd6186 to
9495588
Compare
- Backports the new internal `RedBlackTree`.
- In 2.12.x `Tree` must still extend `Serializable` as we don't
use proxy based serialization for `TreeMap` / `TreeSet`.
- Take advantage of the new implementation when the operand to
`++`, `filter`, etc is the same collection type with the same
`Ordering`. Many of these changes require us to modify the
inherited implementation to add a type-case to be binary
compatibile.
9495588 to
b87dd51
Compare
The performance comparisons at #7284 (comment) are eye-popping. |
|
Thanks for your efforts and patience with this one, @mkeskells ! |
NP |
It hasn't been necessary since 2.13.2, because our fix was merged upstream in that version. This commit is an update of 36ea85c which had already removed the override for 2.13.x. This change is necessary now because 2.12.12+ has a completely different implementation, backported from 2.13.x in the upstream pull requests scala/scala#8749, which is not compatible with the classes that use `RedBlackTree`.
It hasn't been necessary since 2.12.2, because our fix was merged upstream in that version. This commit is an update of 36ea85c which had already removed the override for 2.13.x. This change is necessary now because 2.12.12+ has a completely different implementation, backported from 2.13.x in the upstream pull requests scala/scala#8749, which is not compatible with the classes that use `RedBlackTree`.
immutable.{TreeSet, TreeMap} by backporting the 2.13.x RedBlackTree improvements
immutable.{TreeSet, TreeMap} by backporting the 2.13.x RedBlackTree improvements…kport backport 2.13 immutable RedBlackTree to 2.12
…kport backport 2.13 immutable RedBlackTree to 2.12
Backport #7284 and related changes from 2.13.x to make
immutable.{TreeMap,TreeSet}more efficient.Adapt what is needed for the API changes. This means that 2.12 improvements can be more easily forward ported, as the APIs are more aligned