You are viewing a plain text version of this content. The canonical link for it is here.
Posted to j-dev@xerces.apache.org by "Ludger Bünger (JIRA)" <xe...@xml.apache.org> on 2009/12/02 16:22:20 UTC
[jira] Created: (XERCESJ-1409) Optimization for random indexed
access upon NodeList
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
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: j-dev-unsubscribe@xerces.apache.org
For additional commands, e-mail: j-dev-help@xerces.apache.org
[jira] Updated: (XERCESJ-1409) Optimization for random indexed
access upon NodeList
Posted by "Ludger Bünger (JIRA)" <xe...@xml.apache.org>.
[ 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: j-dev-unsubscribe@xerces.apache.org
For additional commands, e-mail: j-dev-help@xerces.apache.org