Details
-
Improvement
-
Status: Open
-
Minor
-
Resolution: Unresolved
-
2.9.1
-
None
-
None
Description
Since Xerces stores children as a linked list, indexed access using NodeList.item(index) has an execution time of O
.
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.
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.