Registering an event of type DOMNodeInsertedIntoDocument and
DOMNodeRemovedFromDocument significantly slows down insertion or removal upon
any other DOM in the VM.
-------------------------------------------------------------------------------------------------------------------------------------------------------------------
Key: XERCESJ-1376
URL: https://issues.apache.org/jira/browse/XERCESJ-1376
Project: Xerces2-J
Issue Type: Improvement
Components: DOM (Level 2 Events)
Affects Versions: 2.9.1
Reporter: Ludger Bünger
DOMNodeInsertedIntoDocument and DOMNodeRemovedFromDocument events do dom
iterations over a whole subtree even if no event listeners are present in the
event distribution path.
Dispatching DOMNodeInsertedIntoDocument and DOMNodeRemovedFromDocument events
is quite time consuming since the respective events need to be thrown upon
*every child* of the node removed or inserted.
This aproximies to a disturbing O(n log n) runtime with n being the number of
nodes in the DOM *for each insertion or removal*.
Xerces2-J provides a very basic optimization for these events such that if
there is no event listener of the event type to be dispatched registered in the
global static event listener pool than we do not go into dispatching the event
upon the whole subtree.
Thus, as soon as such an event listener is registered upon a document every
insertion and removal significantly slows down.
What makes this thing really bad is issue
https://issues.apache.org/jira/browse/XERCESJ-1345:
Currently the event listener tracking data structure is static and used
globally by every document, thus this slowdown happens upon every document -
not only those that have the respective event listener registered.
I have a significant improvement coded for these event types that I'd like to
share which is already in productive use in our xerces2-j based application.
But this code is based upon my code i provided for issue #1345, thus the patch
requires also the patch for issue #1345 to be applied to the xerces repository.
The basic idea is to check and inhibit dispatching of an event upon every node
in the subtree if there is no event listener of the required type is registered
in the event path.
The checks have to be sufficiently fast to not slow down the whole operation if
no or only a few events need to be thrown.
These checks would be:
1) is there an event listener of the required type registered upon the document
at all?
If not: do not dispatch at all - we definitely do not need to dispatch any of
these "slow" events.
This check already exists already but only globally and is done in constant
O(1) time.
Thus my solution requires issue #1345 (to which I already provided a patch) to
be solved beforehand.
2) check whether there exists an event listener in the event path between the
node removed/inserted and the document root.
If yes: no optimization possible, we definitely need to dispatch the event upon
each node in the whole subtree of the node inserted/removed.
This check requires iterating from the node to its document root and thus takes
O(log n) time in average.
Since node insertion/removal also requires dispatching
DOMNodeInserted/DomNodeRemoved/DomSubtreeModified-events which themself require
O(log n) time in average, we do not have a degration in runtime complexity by
this check. However it has the potential to apply the optimization:
3) check whether any node in the subtree of the inserted/removed node has an
event listener of type DOMNodeInsertedIntoDocument or
DOMNodeRemovedFromDocument.
If not: do not dispatch at all - we definitely do not need to dispatch any of
these "slow" events.
Checking this can be done in constant O(1) time if we track the number of these
"slow event type" event listeners registered in the whole subtree represented
by a node.
Thus this requires an additional field in NodeImpl.
Updating this field takes time itself:
a) constant time during insertion or removal of every child and
b) O(log n) time upon registering/unregistering of event listeners of the
respective "slow event" types.
Having this additional field allows another significant optimization if
condition 2 does not apply (which we already checked earlier):
4) We need to dispatch the respective event only upon those nodes inside the
subtree of the inserted/removed node, that have such an event listener
registered.
These nodes can be easily found by recursively iterating over every child node
of the node inserted/removed while ommiting all those nodes that have no such
event listeners registered determined by the additional field required to check
condition 3) fast.
Ok, that's it.
I'd like to provide the code for solving this but my code depends upon issue
#1345, thus, I would be glad to see my patch attached to issue #1345 be applied
to the svn repository so I can provide my patch for this.
--
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]
