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 nbeyer@gmail.com designates
 64.233.184.236 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:content-transfer-encoding:content-disposition:references;
        b=AzEyy4YNs+z9nlm2NrDYGLv1hNeJVrrNi6YFL5UaN2Y7F2Hl/JfQnnic1n2DStYczp3qj4Df9Js79jWS08ZlFJoN8vCU2XUsN3bsWXt9f9oN30HBVYyy2k9LNA0RAjuplr9N/PyaIImLQgISHjKJgtMezONzh+xDxFtapXAn2B4=
Message-ID: <3b3f27c60803191947l60ab8056h6c872508354deeb5@mail.gmail.com>
Date: Wed, 19 Mar 2008 21:47:13 -0500
From: "Nathan Beyer" <nbeyer@gmail.com>
To: dev@harmony.apache.org
Subject: Re: [classlib][luni] TreeMap performance improvement on java6
In-Reply-To: <c30d70960803190249l1fb8634l45b29e83acbaea5a@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
References: <5c8e69f0801170235g78896f8cj4d12b285c787d144@mail.gmail.com>
	 <253b20230803180218r214fd5afw78e8f4c2206c9a44@mail.gmail.com>
	 <3b3f27c60803181717u2052f0c6idcee5834936b22@mail.gmail.com>
	 <c30d70960803181735i38d51817m82424e17d785739c@mail.gmail.com>
	 <3b3f27c60803181756xa58e6a7u721c3ed2cc9acd2c@mail.gmail.com>
	 <c30d70960803190249l1fb8634l45b29e83acbaea5a@mail.gmail.com>

On Wed, Mar 19, 2008 at 4:49 AM, Alexei Fedotov
<alexei.fedotov@gmail.com> wrote:
> Nathan,
>  I see your argument.
>
>  My personal point is that if we get some failing TCK-like tests or
>  applications, it would be easier for Sergey to get convinced to
>  allocate time to make his implementation more compatible. While we all
>  agree that violating speciation is not generally a good thing, an
>  effort to fight this violation might still be questionable due to low
>  impact of this violation.

What are we talking about? I'm confused. Are we talking about code
that's already been committed to the repository? Is this code specific
to the java6 branch?

-Nathan

>
>  Thanks.
>
>
>
>  On Wed, Mar 19, 2008 at 3:56 AM, 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
>  >  >
>  >
>
>
>
>  --
>  With best regards,
>  Alexei
>