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:56:42 GMT
On Tue, Mar 18, 2008 at 7:35 PM, Alexei Fedotov
<alexei.fedotov@gmail.com> wrote:
> Jimmy, Nathan, all,
>  Do you know real applications which suffer from Sergey's
>  implementation? Are there any broken use cases or failed tests?
>

I don't think that's relevant to my argument, so I'm willing to make
the assumption that the code is functional and fine. In the case of
TreeMap and other implementation classes (HashMap, etc), I don't think
 that being functional according to the interfaces that are
implemented is enough. In other words; it's not TreeMap because it
correctly implements SortedMap, NavigableMap, Map, Cloneable and
Serizable, it's TreeMap because it implements all of those and does it
with a red-black tree.

I think the real question is can TreeMap still say it's implemented
using a red-black tree and all of the other comments mentioned in the
javadoc?

-Nathan

>  Thanks.
>
>
>
>  On Wed, Mar 19, 2008 at 3:17 AM, Nathan Beyer <nbeyer@gmail.com> wrote:
>  > 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
>  >  commons-collections.
>  >
>  >  -Nathan
>  >
>  >  [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.
>  >  >
>  >
>
>
>
>  --
>  With best regards,
>  Alexei
>

Mime
View raw message