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: [email protected]
For additional commands, e-mail: [email protected]
