harmony-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Tim Ellison <t.p.elli...@gmail.com>
Subject [classlib][luni] TreeMap woes (was: Re: [jira] Commented: (HARMONY-5265) [classlib][luni] TreeMap bug fixing and further performance improvements)
Date Fri, 07 Dec 2007 14:02:54 GMT
This change to TreeMap seems to have introduced an instability, and I
would say it is a candidate for reverting in M4.



Ilya Berezhniuk (JIRA) wrote:
>     [ https://issues.apache.org/jira/browse/HARMONY-5265?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#action_12549389
> Ilya Berezhniuk commented on HARMONY-5265:
> ------------------------------------------
> I've checked 2 times with debug build, crash does not appear.
> But 3 unexpected failures are still here.
>> [classlib][luni] TreeMap bug fixing and further performance improvements
>> ------------------------------------------------------------------------
>>                 Key: HARMONY-5265
>>                 URL: https://issues.apache.org/jira/browse/HARMONY-5265
>>             Project: Harmony
>>          Issue Type: Bug
>>          Components: Classlib
>>    Affects Versions: 5.0M4
>>            Reporter: Sergey Kuksenko
>>            Assignee: Alexey Petrenko
>>             Fix For: 5.0M4
>>         Attachments: TreeMap64Rv7.patch
>> Attached patch is further development of idea shown in HARMONY-5232.
>> As it was obtained using sorted arrays for small trees gives a boost over classical
>> "In case of small SortedMap storing data in sorted array leads to significant increasing
of cache hits. Practical measurements shows that operation get() became 10-30% faster and
operation put is 3-10% faster. Even additional overhead for moving data for put() operation
is smaller then obtained benefit and as result we got speedup."
>> HARMONY-5232 splitted internal tree representation into two parts: sorted array for
small tree and classical tree for all other cases.
>> The attached patch implements the idea that we can store the origival tree structure,
but instead of storing one key in the tree node (classical tree) each tree node contains small
sorted array of keys. As result we:
>> - utilize performance benefits from "small sorted array" not only for small trees
(as it was done in HARMONY-5232), but for all trees.
>> - avoid internal dynamic switching between two kinds of internal tree representation
and makes code simple.
>> The latest fact has a big advantage for bug fixing, so fixing bugs described in HARMONY-5248
is much easier.
>> The current patch fixes all problems with EUT (HARMONY-5248).

View raw message