Skip to content
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

Closed
scabug opened this issue Jan 7, 2013 · 9 comments
Closed
Assignees
Milestone

Comments

@scabug
Copy link

scabug commented Jan 7, 2013

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.

@scabug
Copy link
Author

scabug commented Jan 7, 2013

Imported From: https://issues.scala-lang.org/browse/SI-6938?orig=1
Reporter: @JamesIry
Affected Versions: 2.9.2

@scabug
Copy link
Author

scabug commented Jan 7, 2013

@JamesIry said:
Extracted from #6825

@scabug
Copy link
Author

scabug commented Feb 20, 2013

@JamesIry said:
I've given this some thought and I don't think that we can really do much better on immutable.TreeSet and immutable.TreeMap and still get O(log N) inserts. It might be possible to do slightly better by "chunking" the leaves, but it wouldn't be a huge improvement and the code would be massively more complex.

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.

@scabug
Copy link
Author

scabug commented Oct 15, 2013

@gkossakowski said:
Unassigning and rescheduling to M7 as previous deadline was missed.

@scabug
Copy link
Author

scabug commented Dec 11, 2013

@adriaanm said:
Not scheduling, but assigning for your consideration.

@scabug
Copy link
Author

scabug commented Feb 9, 2014

@Ichoran said:
Will try to get to this for 2.12. Not practical for 2.11 at this point.

@scabug
Copy link
Author

scabug commented May 30, 2015

@Ichoran said:
We should consider this fixed by #4147 once it's in.

@scabug
Copy link
Author

scabug commented Jun 27, 2015

@ruippeixotog said:
I have just tried to change mutable.TreeSet so that it uses a mutable red-black tree (added in scala/scala#4504) as its underlying data structure. Everything worked well, ant test yields no issues and the changes seem to be source-compatible. However, as its underlying data changed, it may happen that users that serialized a mutable.TreeSet with a previous version of Scala will find out that its binary representation is no longer valid after such a modification (the current serialization stability tests do not include mutable.TreeMap).

@Ichoran, does this prevent such a change to be included in Scala 2.12? If not, I can do a pull request later.

@scabug
Copy link
Author

scabug commented Aug 6, 2015

@SethTisue said:
scala/scala#4608

@scabug scabug closed this as completed Aug 6, 2015
@scabug scabug added this to the 2.12.0-M3 milestone Apr 7, 2017
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants