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 Tue, 18 Mar 2008 09:18:37 GMT
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
What we have it is TreeMap interface which completely satisfied to
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

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.

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