Mailing-List: contact dev-help@harmony.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@harmony.apache.org
Received-SPF: pass (athena.apache.org: domain of sergey.kuksenko@gmail.com
 designates 72.14.220.156 as permitted sender)
DomainKey-Signature: a=rsa-sha1; c=nofws;
        d=gmail.com; s=beta;
        h=message-id:date:from:to:subject:in-reply-to:mime-version:content-type:references;
        b=b8YeyXeYkaY8aZ5gpa6bDd0EnKnY5BQ+pciUiajCD8BUZMU+VOE3lhRM/pPmqHgMSCDUCadtpJhhIGU5VcaDYbhmWWOmi8seeKT987YoUdLXvKhFaApFmGeMM3up0ZyAZg1fryrf/vZ7Uxj9ZvIPgPvTks7Ih/wQCTNUOR5n+3g=
Message-ID: <253b20230803190133t615e752jba137edcc1354924@mail.gmail.com>
Date: Wed, 19 Mar 2008 11:33:17 +0300
From: "Sergey Kuksenko" <sergey.kuksenko@gmail.com>
To: dev@harmony.apache.org
Subject: Re: [classlib][luni] TreeMap performance improvement on java6
In-Reply-To: <3b3f27c60803181756xa58e6a7u721c3ed2cc9acd2c@mail.gmail.com>
MIME-Version: 1.0
Content-Type: multipart/alternative;
	boundary="----=_Part_926_5257647.1205915597359"
References: <5c8e69f0801170235g78896f8cj4d12b285c787d144@mail.gmail.com>
	 <253b20230803180218r214fd5afw78e8f4c2206c9a44@mail.gmail.com>
	 <3b3f27c60803181717u2052f0c6idcee5834936b22@mail.gmail.com>
	 <c30d70960803181735i38d51817m82424e17d785739c@mail.gmail.com>
	 <3b3f27c60803181756xa58e6a7u721c3ed2cc9acd2c@mail.gmail.com>

------=_Part_926_5257647.1205915597359
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

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.

------=_Part_926_5257647.1205915597359--