harmony-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Alexei Fedotov" <alexei.fedo...@gmail.com>
Subject Re: [classlib][luni] TreeMap performance improvement on java6
Date Wed, 19 Mar 2008 00:35:08 GMT
Jimmy, Nathan, all,
Do you know real applications which suffer from Sergey's
implementation? Are there any broken use cases or failed tests?

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