[
https://issues.apache.org/jira/browse/XERCESJ-1409?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Ludger Bünger updated XERCESJ-1409:
-----------------------------------
Attachment: NodeListItemAccessPatch.txt
This patch additionally does some trivial index out of bounds checks.
> Optimization for random indexed access upon NodeList
> ----------------------------------------------------
>
> Key: XERCESJ-1409
> URL: https://issues.apache.org/jira/browse/XERCESJ-1409
> Project: Xerces2-J
> Issue Type: Improvement
> Components: DOM (Level 3 Core)
> Affects Versions: 2.9.1
> Reporter: Ludger Bünger
> Priority: Minor
> Attachments: NodeListItemAccessPatch.txt
>
>
> Since Xerces stores children as a linked list, indexed access using
> NodeList.item(index) has an execution time of O(n).
> That said, there are a few tweaks we still can do to keep absolute acces time
> low even though we won't change it from O(n).
> Current Xerces imlementation already provides a simple optimization:
> Currently, the last retrieved child node and it's index is cached.
> Subsequent calls to ParentNode.nodeListItem start iterating the linked list
> of children from this position.
> Assuming that quite a lot of random accesses are somewhat local to the last
> access point, this is a reasonable optimization.
> However it improves nothing (but also does no harm) when accessing large
> child lists in a random pattern.
> I suggest an additional tweak to be applied:
> The idea is to add a simple calculation to determine whether it might require
> less iterations when iterating from the start or the end of the linked list
> instead of the last accessed ChildNode.
> While this imposes a (relatively small) constant overhead per call of item (a
> comparison, an addition and a bitshift) this optimization should reduce the
> average number of linked list iterations required for a true random access by
> a factor of two while ensuring that the number of iterations will never
> exceed the number of iterations done by the current implementation.
> Please review attached Patch.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
