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

Created an attachment (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:
------- You are receiving this mail because: -------
You are the assignee for the bug.

Reply via email to