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 Wed, 19 Mar 2008 19:41:56 GMT
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
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)
>  change it to RB-tree aglorithm(rebuild a RB-Tree) when the size exceed
>  bar?
> If you check history of  TreeMap you can find that this first (initial)
>  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.

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