New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Too many RedBlack$BlackTree instances in mutable.TreeSet. No mutable.TreeMap. #6938
Comments
Imported From: https://issues.scala-lang.org/browse/SI-6938?orig=1 |
@JamesIry said: On the other hand, mutable.TreeSet currently uses an immutable RedBlackTree as its backing. Previously it used an immutable AVL tree which had the same memory issues as an immutable RedBlackTree. Having an immutable tree to back a mutable TreeSet is not really necessary. It could use an array of elements that are tree ordered plus a bitset indicating color. It would mean that clone would move from O(1) to O(n), but that's pretty much the usual expectation on mutable data structures. As it stands, mutable.TreeSet isn't a particularly good data structure - it has all the speed/memory disadvantages of an immutable data structure and the no-thread-safety disadvantages of mutable data structure. That's a terrible price to pay just to get a cheap clone operation. Besides, if that's the exact data structure you need then wrapping an immutable.TreeSet in a mutable object ref isn't hard. A mutable balanced tree ordered array, on the other hand, is a bigger value from the standard library. So, unless somebody else can think of a clever way to make the immutable tree variants use less memory, I'm retargeting this bug to be specific to mutable.TreeSet. Along the way it would be good to have a mutable.TreeMap as well so that users can make the decision on mutable/immutable. |
@gkossakowski said: |
@adriaanm said: |
@Ichoran said: |
@ruippeixotog said: @Ichoran, does this prevent such a change to be included in Scala 2.12? If not, I can do a pull request later. |
@SethTisue said: |
Size of RedBlack$BlackTree types are taking up unexpectedly large amounts of heap space. Users on platforms with limited resources can't use these collections so long as they create so many instances for each entry.
The text was updated successfully, but these errors were encountered: