harmony-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Alexey Petrenko" <alexey.a.petre...@gmail.com>
Subject Re: [classlib][luni] TreeMap woes (was: Re: [jira] Commented: (HARMONY-5265) [classlib][luni] TreeMap bug fixing and further performance improvements)
Date Fri, 07 Dec 2007 18:12:44 GMT
This patch gives us significant boost.
So it's better to investigate, fix and keep it in M4 then revert.

We still have some time before testing cycle and Sergey is investigating.

Be patient :)

SY, Alexey

2007/12/7, Tim Ellison <t.p.ellison@gmail.com>:
> This change to TreeMap seems to have introduced an instability, and I
> would say it is a candidate for reverting in M4.
>
> WDYT?
>
> Regards,
> Tim
>
> 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
trees.
> >> "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).
> >
>

Mime
View raw message