[FOP-1888] O(n^2) algorithm for adding nodes

• Type: Improvement
• Status: Closed
• Resolution: Fixed
• Affects Version/s: 2.5
• Component/s: fo/unqualified
• Environment: Operating System: All; Platform: PC
• External issue ID: 50626
• Assignee: fop-dev
• Reporter: Martin Koegler
• Created: 20/Jan/11 17:12
• Updated: 22/Jan/11 12:29
• Resolved: 01/Apr/12 06:19

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.