You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@harmony.apache.org by Sergey Kuksenko <se...@gmail.com> on 2008/03/18 10:18:37 UTC
Re: [classlib][luni] TreeMap performance improvement on java6
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.
> 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.
Re: [classlib][luni] TreeMap performance improvement on java6
Posted by Sergey Kuksenko <se...@gmail.com>.
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 <nb...@gmail.com> wrote:
>
> On Tue, Mar 18, 2008 at 7:35 PM, Alexei Fedotov
> <al...@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 <nb...@gmail.com> wrote:
> > > On Tue, Mar 18, 2008 at 4:18 AM, Sergey Kuksenko
> > > <se...@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.
Re: [classlib][luni] TreeMap performance improvement on java6
Posted by Nathan Beyer <nb...@gmail.com>.
On Wed, Mar 19, 2008 at 4:49 AM, Alexei Fedotov
<al...@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 <nb...@gmail.com> wrote:
> > On Tue, Mar 18, 2008 at 7:35 PM, Alexei Fedotov
> > <al...@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 <nb...@gmail.com> wrote:
> > > > On Tue, Mar 18, 2008 at 4:18 AM, Sergey Kuksenko
> > > > <se...@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
>
Re: [classlib][luni] TreeMap performance improvement on java6
Posted by Alexei Fedotov <al...@gmail.com>.
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.
Thanks.
On Wed, Mar 19, 2008 at 3:56 AM, Nathan Beyer <nb...@gmail.com> wrote:
> On Tue, Mar 18, 2008 at 7:35 PM, Alexei Fedotov
> <al...@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 <nb...@gmail.com> wrote:
> > > On Tue, Mar 18, 2008 at 4:18 AM, Sergey Kuksenko
> > > <se...@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
Re: [classlib][luni] TreeMap performance improvement on java6
Posted by Nathan Beyer <nb...@gmail.com>.
On Tue, Mar 18, 2008 at 7:35 PM, Alexei Fedotov
<al...@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 <nb...@gmail.com> wrote:
> > On Tue, Mar 18, 2008 at 4:18 AM, Sergey Kuksenko
> > <se...@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
>
Re: [classlib][luni] TreeMap performance improvement on java6
Posted by Alexei Fedotov <al...@gmail.com>.
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 <nb...@gmail.com> wrote:
> On Tue, Mar 18, 2008 at 4:18 AM, Sergey Kuksenko
> <se...@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
Re: [classlib][luni] TreeMap performance improvement on java6
Posted by Nathan Beyer <nb...@gmail.com>.
On Tue, Mar 18, 2008 at 4:18 AM, Sergey Kuksenko
<se...@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.
>
Re: [classlib][luni] TreeMap performance improvement on java6
Posted by Sergey Kuksenko <se...@gmail.com>.
Soory, I did typo
"Generally it was lacky coincidence"
Should be read as
"Generally it was lucky coincidence"
On 3/19/08, Sergey Kuksenko <se...@gmail.com> wrote:
>
> Hi Jimmy,
>
> > My main concern is performance, as it appear so good on SPECjbb, will
> it turn a bit slower in some other programs or benchmarks than the
> typical RB-tree?
>
> Generally it was lacky coincidence that it gave some small benefit on
> SPECjbb.
> In general, I've realized in set of experiments that small array is better
> then small tree.
> After that I've created a RB-tree of small arrays and realized that such
> representation is faster then simple tree on operations not only like get,
> but including such operations like put and delete.
> I have a set of practical measurements which show that such is faster even
> for really big trees.
> The question is that I am going to write article about that, that is why I
> didn't put my results here yet.
>
> > Typical RB-tree algorithm has proved its own
> benefits on some fields. And I believe java programmers may choose
> TreeMap instead of Arrays for their own propose of performance, in
> some fields that only typical RB-tree is best?
> I really have no idea or data about this, but as you say "small array
> is ALWAYS faster than tree on all operations", I think it is OK then
> (if we find some other problem, let's restart this thread) :)
>
> >
> > > 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.
> >
>
>
> --
>
> Best Regards!
>
> Jimmy, Jing Lv
> China Software Development Lab, IBM
>
>
>
>
> --
> Best regards,
> ---
> Sergey Kuksenko.
> Intel Enterprise Solutions Software Division.
>
--
Best regards,
---
Sergey Kuksenko.
Intel Enterprise Solutions Software Division.
Re: [classlib][luni] TreeMap performance improvement on java6
Posted by Sergey Kuksenko <se...@gmail.com>.
Hi Jimmy,
> My main concern is performance, as it appear so good on SPECjbb, will
it turn a bit slower in some other programs or benchmarks than the
typical RB-tree?
Generally it was lacky coincidence that it gave some small benefit on
SPECjbb.
In general, I've realized in set of experiments that small array is better
then small tree.
After that I've created a RB-tree of small arrays and realized that such
representation is faster then simple tree on operations not only like get,
but including such operations like put and delete.
I have a set of practical measurements which show that such is faster even
for really big trees.
The question is that I am going to write article about that, that is why I
didn't put my results here yet.
> Typical RB-tree algorithm has proved its own
benefits on some fields. And I believe java programmers may choose
TreeMap instead of Arrays for their own propose of performance, in
some fields that only typical RB-tree is best?
I really have no idea or data about this, but as you say "small array
is ALWAYS faster than tree on all operations", I think it is OK then
(if we find some other problem, let's restart this thread) :)
>
> > 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.
>
--
Best Regards!
Jimmy, Jing Lv
China Software Development Lab, IBM
--
Best regards,
---
Sergey Kuksenko.
Intel Enterprise Solutions Software Division.
Re: [classlib][luni] TreeMap performance improvement on java6
Posted by "Jimmy,Jing Lv" <fi...@gmail.com>.
Hi,
2008/3/18, Sergey Kuksenko <se...@gmail.com>:
> 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.
>
>
> > 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.
>
>
Yes, I believe so, it may be hard to test if the TreeMap is based on a
typical R-B Tree.
I just doubt it may break the spec if we use another mechanism instead
former RB Tree. However current code is based on RB tree and small
array, I have no idea if we can call it as an alternative-RB-tree
algorithm?
My main concern is performance, as it appear so good on SPECjbb, will
it turn a bit slower in some other programs or benchmarks than the
typical RB-tree? Typical RB-tree algorithm has proved its own
benefits on some fields. And I believe java programmers may choose
TreeMap instead of Arrays for their own propose of performance, in
some fields that only typical RB-tree is best?
I really have no idea or data about this, but as you say "small array
is ALWAYS faster than tree on all operations", I think it is OK then
(if we find some other problem, let's restart this thread) :)
>
> > 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.
>
--
Best Regards!
Jimmy, Jing Lv
China Software Development Lab, IBM