harmony-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Sergey Kuksenko" <sergey.kukse...@gmail.com>
Subject Re: [classlib][luni] TreeMap performance improvement on java6
Date Wed, 19 Mar 2008 08:33:17 GMT
Hi Nathan,

I don't consider this implemenetation as something different.
Really, there is well know tree-optimization as clustering.
Clustering can be done for each kind of binary tree, and clustering saves
all properties of underlined tree.
If we make clustering on AVL-tree or on RB-tree all complexity properties
will be saved.
Moreover, how will you check that this Tree is contradict with requirement
to be RB-tree.
Looking into source is a slippery way.
Having some test for it? I am absolutetly sure that this tree will pass such
kind of test.


On 3/19/08, Nathan Beyer <nbeyer@gmail.com> wrote:
>
> 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
> >
>



-- 
Best regards,
---
Sergey Kuksenko.
Intel Enterprise Solutions Software Division.

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message