Details
-
Improvement
-
Status: Closed
-
Resolution: Fixed
-
2.5
-
None
-
None
-
Operating System: All
Platform: PC
-
50626
Description
Adding a node as last child (something common in FOP) is implemented by traversing the whole list of child nodes.
So adding one node is O and therefore adding n Nodes is O(n^2).
Caching a pointer to last element speeds up this process to O(1), so adding n Nodes is only O.
While processing an document with thousands of page sequences, adding a node to the list tail with the O(n^2) algorithm accounts for a major percentage of the FOP runtime.
The attached patch eliminates this by caching the last node.