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:42:57 GMT
Soory, I did typo
"Generally it was lacky coincidence"
Should be read as
"Generally it was lucky coincidence"


On 3/19/08, Sergey Kuksenko <sergey.kuksenko@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.

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