harmony-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Jimmy,Jing Lv" <firep...@gmail.com>
Subject [classlib][luni] TreeMap performance improvement on java6
Date Thu, 17 Jan 2008 10:35:19 GMT
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
    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

View raw message