harmony-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Nathan Beyer" <nbe...@gmail.com>
Subject Re: [classlib][luni] TreeMap performance improvement on java6
Date Wed, 19 Mar 2008 00:17:03 GMT
On Tue, Mar 18, 2008 at 4:18 AM, Sergey Kuksenko
<sergey.kuksenko@gmail.com> wrote:
> Hi Jimmy,
>  I am really sorry for my long silence.
>  > Does this cause a little confliction with spec, which annouced the TreeMap
>  is Red-Black tree based?
>  How it can be checked? There are no way to check if three is RB tree
>  outside.
>  What we have it is TreeMap interface which completely satisfied to
>  specification.
>  RB-tree of not RB-tree can't be checked with public interface.

True, but in this case, TreeMap isn't conceptually an interface, it's
an implementation and users are going to expect performance and
behavior that's consistent with the javadoc [1] and RI. If that's in
question in anyway, then we should avoid it. Optimizations on
implementation classes that declare their algorithms shouldn't change
the underlying algorithms; they should stick to things like reducing
memory overhead, reducing class complexity, reducing stack depth and
the like.

In my opinion, a Map implementation that doesn't use an RB tree isn't
java.util.TreeMap and is the realm of projects like


[1] http://java.sun.com/javase/6/docs/api/java/util/TreeMap.html

>  > This algorithm works very well on small number of pairs (as we see, 4%-10%
>  improvement ), but will it pause huge regression if the number of pairs
>  grows to a great number?
>  I've based my implementation on the following steps:
>  1. small array is always faster then tree on all operations.
>  2. If we create Tree of small arrays we will get benifits on tree sizes.
>  And the latest fact is proved by my measurements.
>  I am really want to collect all my data and share it here. But, please,
>  expect some delay in this.
>  > I have a simple idea here, is it possible to just to apply only binary
>  search array when total size of the tree is small (e.g, small than 64) and
>  change it to RB-tree aglorithm(rebuild a RB-Tree) when the size exceed the
>  bar?
>  If you check history of  TreeMap you can find that this first (initial) idea
>  was implemented (probably somewhere in August/September 2007 I don't
>  remember exactly when).
>  After that I was woking on expanding thiso idea to all tree sizes.
>  --
>  Best regards,
>  ---
>  Sergey Kuksenko.

View raw message