Performance of immutable TreeMap/TreeSet implementations

On Wed, Dec 21, 2011 at 10:43 AM, Erik Rozendaal <erik@deler.org> wrote:

(please let me know if this is not the right list for discussing this)

Library issues in general should probably go somewhere else, but we'll let it slide this time, because those are awful things you found.  I have to look more closely at the patches, but assuming there's nothing too horrifying they can definitely be in 2.10.  For 2.9 I have to wait-and-see.  (I wonder if we should have a 2.9.x-binary-incompatible series, because otherwise the binary compatibility mandate scoops up a lot of baby as the patch bathwater goes by.) Can you please open a ticket if you haven't already.

On Wed, Dec 21, 2011 at 16:43, Erik Rozendaal wrote:

> 2. The range related operations (range, from, to, until) construct a new tree by splitting the existing tree. Unfortunately, the size of the new tree is calculated by calling RedBlack#Tree.count. This is an O(n) operation (also see SI-4026).

I decided to take a look at this, and the curious thing is that this
count is used in *only one place*. It is used only when removing an
element to see if an empty tree should be returned or not. All other
uses are simply to feed this parameter again, or could be replaced
with isEmpty.

So, since you are feeling all pro-active about this (which I commend!
:), I suggest trying to remove this accursed parameter might, perhaps,
not be hard to do. One can always provide an alternate constructor
that takes and discards this parameter for compatibility reasons.

Using size to check != 0 or > 0 or >= 1 should be punished by a slap on the wrist.

On Wed, Dec 21, 2011 at 8:53 PM, Daniel Sobral <dcsobral@gmail.com> wrote:

On Wed, Dec 21, 2011 at 16:43, Erik Rozendaal <erik@deler.org> wrote:

> 2. The range related operations (range, from, to, until) construct a new tree by splitting the existing tree. Unfortunately, the size of the new tree is calculated by calling RedBlack#Tree.count. This is an O(n) operation (also see SI-4026).

I decided to take a look at this, and the curious thing is that this
count is used in *only one place*. It is used only when removing an
element to see if an empty tree should be returned or not. All other
uses are simply to feed this parameter again, or could be replaced
with isEmpty.

So, since you are feeling all pro-active about this (which I commend!
:), I suggest trying to remove this accursed parameter might, perhaps,
not be hard to do. One can always provide an alternate constructor
that takes and discards this parameter for compatibility reasons.

--
Daniel C. Sobral

I travel to the future all the time.

--
Viktor Klang

Akka Tech LeadTypesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

2011/12/21 √iktor Ҡlang :
> Using size to check != 0 or > 0 or >= 1 should be punished by a slap on the
> wrist.

Here's a simple grep:

dcs@ayanami:~/github/scala/src/library/scala/collection/immutable
(subrange)$ grep size TreeSet.scala
class TreeSet[A](override val size: Int, t: RedBlack[A]#Tree[Unit])
protected val tree: RedBlack[A]#Tree[Unit] = if (size == 0) Empty else t
val newsize = if (tree.lookup(elem).isEmpty) size + 1 else size
newSet(newsize, tree.update(elem, ()))
newSet(size + 1, tree.update(elem, ()))
else newSet(size - 1, tree delete elem)

dcs@ayanami:~/github/scala/src/library/scala/collection/immutable
(subrange)$ grep size TreeMap.scala
class TreeMap[A, +B](override val size: Int, t:
RedBlack[A]#Tree[B])(implicit val ordering: Ordering[A])
protected val tree: RedBlack[A]#Tree[B] = if (size == 0) Empty else t
val newsize = if (tree.lookup(key).isEmpty) size + 1 else size
TreeMap.make(newsize, tree.update(key, value))
TreeMap.make(size + 1, tree.update(key, value))
else if (size == 1) empty
else TreeMap.make(size - 1, tree.delete(key))

There's one size == 0, and one size == 1. All others are just
record-keeping. Now, this gives TreeSet and TreeMap an O(1)
size/length method, but turns range and all methods derived from it
into O(n). Removing size from constructor turns it into O(n), and
makes range O(log n). Putting a count on the immutable RedBlack
increases its size, keeps size/length O(1) and turns range into O(log
n).

As for size increase, this is what a Red tree looks like:

private final java.lang.Object key;
private final java.lang.Object value;
private final scala.collection.immutable.RedBlack$Tree left;
private final scala.collection.immutable.RedBlack$Tree right;

So, given the 4-bytes used by every Object and the 8-bytes increment
of atual size allocated, there would not be any increment memory
consumption if size was added to RedBlack.

Which doesn't make that size == 0 any less punishable. :-)

Ticket SI-5331 was just opened. SI-4026 is related. 
The most horrifying part is probably abusing type-erasure to ensure we need only one instance to represent an Empty RedBlack tree, without making the first type-parameter covariant (impossible due to the use of Ordering which has an invariant type parameter): https://github.com/erikrozendaal/scala/blob/trees-redblack/src/library/scala/collection/immutable/RedBlack.scala#L264
Besides that there are still some things that could be fixed:- make the RedBlack implementation private to the Scala library (so we can keep improving the implementation), make sure it doesn't leak into the TreeMap/TreeSet API (why is this https://github.com/erikrozendaal/scala/blob/trees-redblack/src/library/scala/collection/immutable/TreeMap.scala#L64 protected instead of private?)- Like Daniel mentioned, remove the need for the size field in TreeMap/TreeSet and the unnecessary tests, now that RedBlack.Tree contains a count.- Efficiency optimizations and see if we can match/beat java.util.TreeMap/TreeSet :)
Regards,Erik
On 21 dec. 2011, at 20:06, Paul Phillips wrote:

On Wed, Dec 21, 2011 at 10:43 AM, Erik Rozendaal <erik@deler.org> wrote:

(please let me know if this is not the right list for discussing this)

Library issues in general should probably go somewhere else, but we'll let it slide this time, because those are awful things you found.  I have to look more closely at the patches, but assuming there's nothing too horrifying they can definitely be in 2.10.  For 2.9 I have to wait-and-see.  (I wonder if we should have a 2.9.x-binary-incompatible series, because otherwise the binary compatibility mandate scoops up a lot of baby as the patch bathwater goes by.) Can you please open a ticket if you haven't already.

I hit most of these issues a while back - there should be a thread about it on -users. I started tryingto put together patches, but the inheritance/mixin hierarchy is so tangled that it's really hard to follow what code is *actually* invoked without stepping through with a debugger, which is very time-consuming. Sorry, I probably should have persevered.
Have we got any closer to having a benchmarking harness for common collection operations, ideally with graphs/histograms and regression lines for estimating the observed complexity? Most of the performance issues I found where things like finding the lowest element of an ordered set not being constant time, and some code-paths being stupidly slow because they chain into size() that was O(n). The other thing that put me off making patches was the lack of any obvious test harness for collections that I could use to make sure that I hadn't obviously broken anything in the process, or inadvertently turned an O(log(n)) into an O(n^2) because the better version chains into some other badly behaved code.
Sorry if this sounds like a laundry list of griping, but perception of the quality of a language often stands or falls on the efficiency of the default collections library. While the scala one is good, having an O(n) lowest op on a sorted set is not a Good Thing.
Matthew

On 21 December 2011 20:59, Erik Rozendaal <erik@deler.org> wrote:

Ticket SI-5331 was just opened. SI-4026 is related. 
The most horrifying part is probably abusing type-erasure to ensure we need only one instance to represent an Empty RedBlack tree, without making the first type-parameter covariant (impossible due to the use of Ordering which has an invariant type parameter): https://github.com/erikrozendaal/scala/blob/trees-redblack/src/library/scala/collection/immutable/RedBlack.scala#L264
Besides that there are still some things that could be fixed:- make the RedBlack implementation private to the Scala library (so we can keep improving the implementation), make sure it doesn't leak into the TreeMap/TreeSet API (why is this https://github.com/erikrozendaal/scala/blob/trees-redblack/src/library/scala/collection/immutable/TreeMap.scala#L64 protected instead of private?) - Like Daniel mentioned, remove the need for the size field in TreeMap/TreeSet and the unnecessary tests, now that RedBlack.Tree contains a count.- Efficiency optimizations and see if we can match/beat java.util.TreeMap/TreeSet :)
Regards,Erik
On 21 dec. 2011, at 20:06, Paul Phillips wrote:

On Wed, Dec 21, 2011 at 10:43 AM, Erik Rozendaal <erik@deler.org> wrote:

(please let me know if this is not the right list for discussing this)

Library issues in general should probably go somewhere else, but we'll let it slide this time, because those are awful things you found.  I have to look more closely at the patches, but assuming there's nothing too horrifying they can definitely be in 2.10.  For 2.9 I have to wait-and-see.  (I wonder if we should have a 2.9.x-binary-incompatible series, because otherwise the binary compatibility mandate scoops up a lot of baby as the patch bathwater goes by.) Can you please open a ticket if you haven't already.

--
Dr Matthew PocockIntegrative Bioinformatics Group, School of Computing Science, Newcastle University mailto: turingatemyhamster@gmail.comgchat: turingatemyhamster@gmail.com msn: matthew_pocock@yahoo.co.ukirc.freenode.net: drdozerskype: matthew.pocock tel: (0191) 2566550mob: +447535664143

On Thu, Dec 22, 2011 at 6:01 AM, Matthew Pocock <turingatemyhamster@gmail.com> wrote:

Have we got any closer to having a benchmarking harness for common collection operations, ideally with graphs/histograms and regression lines for estimating the observed complexity? Most of the performance issues I found where things like finding the lowest element of an ordered set not being constant time, and some code-paths being stupidly slow because they chain into size() that was O(n). The other thing that put me off making patches was the lack of any obvious test harness for collections that I could use to make sure that I hadn't obviously broken anything in the process, or inadvertently turned an O(log(n)) into an O(n^2) because the better version chains into some other badly behaved code.
Sorry if this sounds like a laundry list of griping, but perception of the quality of a language often stands or falls on the efficiency of the default collections library. While the scala one is good, having an O(n) lowest op on a sorted set is not a Good Thing.

I can only observe that it would be hard to dream up anything which would be easier for some individual to implement independently.  When I hear someone talking about it being difficult to contribute to scala (I hear that somewhat less lately, but anyway) I can't help but think that the interest in doing so isn't actually all that high, because we still haven't managed to eke this one out.
Nobody will contest the desirability of what you describe, but in addition to the fact that I can't do everything, I intentionally resist doing this one precisely because it would be so easy (easy in terms of low coordination requirements and the absence of high-inertia decisions, not necessarily in terms of time or effort) for someone who isn't me to do it, and I'm not in any danger of running out of important matters which lack that attribute.