https://issues.apache.org/bugzilla/show_bug.cgi?id=50626
Summary: O(n^2) algorithm for adding nodes
Product: Fop
Version: 1.1dev
Platform: PC
OS/Version: All
Status: NEW
Severity: enhancement
Priority: P2
Component: fo tree
AssignedTo: fop-dev@xmlgraphics.apache.org
ReportedBy: mkoeg...@auto.tuwien.ac.at
Created an attachment (id=26526)
--> (https://issues.apache.org/bugzilla/attachment.cgi?id=26526)
Speedup of adding nodes to the list end
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(n) 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(n).
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.
--
Configure bugmail: https://issues.apache.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are the assignee for the bug.
