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