harmony-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Alexei Fedotov" <alexei.fedo...@gmail.com>
Subject Re: [classlib][luni] TreeMap performance improvement on java6
Date Thu, 24 Jan 2008 12:36:57 GMT
Hello, Jimmy,

I believe we are within the specification as long as search time is O(log n).

Switching to another tree structure at some point might add to
algorithm complexity, but will keep the search estimate since the
search does not modify the tree.  When I was an algorithm scientist, I
wrote about techniques to replace these hardcoded boundaries such as
"64" in your case with adaptive ones and hence make transition from
one data structure to another smoother. While this sometimes works
nicely in practice, making complexity estimates for such adaptive
algorithms is a real challenge and we might have more chance to
violate complexity requirement in this way.


On Jan 17, 2008 1:35 PM, Jimmy,Jing Lv <firepure@gmail.com> wrote:
> Hi All,
>     I notice that currently TreeMap is stable for quite one month and
> I've got time to do update the improvement for java6. A few test on
> TreeMap with some famous benchmarks do show the performance is of
> 4%-10% imporvement (great work!). No eclipse-related bugs remains in
> the current version, right?
>     TreeMap has significant change between java5 and java6. It
> implements a new interface "NavigableMap" in new version, as a result,
> it has some new APIs and changes its inner manner in a deep degree.
> However, it may be still possible to update java6 TreeMap by applying
> Sergey's idea.
>     And I still have some questions about the algorithm itself.
> Currectly the fix on TreeMap uses an alternative Red-Black Tree whose
> leaves may contains no more than 64 pairs while classical R-B tree
> shall have only one (Does this cause a little confliction with spec,
> which annouced the TreeMap is Red-Black tree based? ). This algorithm
> works very well on small number of pairs (as we see, 4%-10%
> improvement ), but will it cause huge regression if the number of
> pairs grows to a great number? BTW, the algorithm is a bit complex
> here in put/remove/get algorism as it should deal with both RB tree
> and arrays with binary search algorism, which make the code full of
> if-statements.
>     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? As we know, RB-tree works well with huge
> mount of pairs while binary search array works well on smaller size.
> And in this way we can deal with one algorithm at a time and make
> put/get/remove method smaller and easy to read (currently put method
> is over 200 lines!).
>     I don't know if this idea may break cpu cache hit here? Any cpu
> guru knows? And what's your idea, Sergey? Thanks a lot!
> --
> Best Regards!
> Jimmy, Jing Lv
> China Software Development Lab, IBM

With best regards,
ESSD, Intel

View raw message