Uploaded image for project: 'FOP'
  1. FOP
  2. FOP-1888

O(n^2) algorithm for adding nodes

    Details

    • Type: Improvement
    • Status: Closed
    • Resolution: Fixed
    • Affects Version/s: trunk
    • Fix Version/s: None
    • Component/s: fo/unqualified
    • Labels:
      None
    • Environment:
      Operating System: All
      Platform: PC
    • External issue ID:
      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.

        Attachments

        1. add-node-speedup.patch
          3 kB
          Martin Koegler
        2. add-node-speedup.patch
          3 kB
          Martin Koegler

          Activity

            People

            • Assignee:
              fop-dev@xmlgraphics.apache.org fop-dev
              Reporter:
              e9925248 Martin Koegler
            • Votes:
              0 Vote for this issue
              Watchers:
              0 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved: