harmony-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Jimmy,Jing Lv" <firep...@gmail.com>
Subject Re: [classlib][luni] TreeMap performance improvement on java6
Date Wed, 19 Mar 2008 09:18:20 GMT

2008/3/18, Sergey Kuksenko <sergey.kuksenko@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

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

View raw message