Fop
  1. Fop
  2. FOP-1888

O(n^2) algorithm for adding nodes

    Details

    • Type: Improvement 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.

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

        Activity

          People

          • Assignee:
            fop-dev
            Reporter:
            Martin Koegler
          • Votes:
            0 Vote for this issue
            Watchers:
            0 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development