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

        Hide
        Martin Koegler added a comment -

        Attachment add-node-speedup.patch has been added with description: Speedup of adding nodes to the list end

        Show
        Martin Koegler added a comment - Attachment add-node-speedup.patch has been added with description: Speedup of adding nodes to the list end
        Hide
        Jeremias Maerki added a comment -

        Thank you for the patch! I guess that optimization makes sense. However, I have to reject the patch in its current state. It introduces regressions in our test suite, namely with tests around markers. Please run "ant" (not just "ant package") so run the full test suite.

        You can render the subset of unit tests in your IDE by running org.apache.fop.layoutengine.LayoutEngineTestSuite with the system property "-Dfop.layoutengine.starts-with=marker".

        Furthermore, please change your Java editor's settings so that no tabs are generated. Tabs are evil.

        Show
        Jeremias Maerki added a comment - Thank you for the patch! I guess that optimization makes sense. However, I have to reject the patch in its current state. It introduces regressions in our test suite, namely with tests around markers. Please run "ant" (not just "ant package") so run the full test suite. You can render the subset of unit tests in your IDE by running org.apache.fop.layoutengine.LayoutEngineTestSuite with the system property "-Dfop.layoutengine.starts-with=marker". Furthermore, please change your Java editor's settings so that no tabs are generated. Tabs are evil.
        Hide
        Martin Koegler added a comment -

        Attachment add-node-speedup.patch has been added with description: New version

        Show
        Martin Koegler added a comment - Attachment add-node-speedup.patch has been added with description: New version
        Hide
        Martin Koegler added a comment -

        Here is a new version:

        It fixes an NullPointerException, when removing from an nearly empty child list.
        Additionally, this time only spaces.

        I hope, that I have caught all regressions:

        The ant output is clobered with known failures, so its difficult to see regressions there (eg. compared to the GCC testsuite).

        Maybe there is a better method to find regression, but I only found:
        $ diff -urN <previous test-result-directory> <new test-result-directory>

        The test infrastructure includes variable data in its output (time, when the test was run, run time in ms and so on), so that this means check over 15.000 lines for important changes. I hope, that I have not missed anything.

        Show
        Martin Koegler added a comment - Here is a new version: It fixes an NullPointerException, when removing from an nearly empty child list. Additionally, this time only spaces. I hope, that I have caught all regressions: The ant output is clobered with known failures, so its difficult to see regressions there (eg. compared to the GCC testsuite). Maybe there is a better method to find regression, but I only found: $ diff -urN <previous test-result-directory> <new test-result-directory> The test infrastructure includes variable data in its output (time, when the test was run, run time in ms and so on), so that this means check over 15.000 lines for important changes. I hope, that I have not missed anything.
        Hide
        Andreas L. Delmelle added a comment -

        (In reply to comment #3)
        > Here is a new version:
        >
        > It fixes an NullPointerException, when removing from an nearly empty child
        > list. Additionally, this time only spaces.

        Looks OK now, so is applied in r1062225 (http://svn.apache.org/viewvc?rev=1062225&view=rev) with a very minor style change (= we use braces around conditionals even if it's only a single statement)

        Thanks for reporting, and again, for the patch!

        Show
        Andreas L. Delmelle added a comment - (In reply to comment #3) > Here is a new version: > > It fixes an NullPointerException, when removing from an nearly empty child > list. Additionally, this time only spaces. Looks OK now, so is applied in r1062225 ( http://svn.apache.org/viewvc?rev=1062225&view=rev ) with a very minor style change (= we use braces around conditionals even if it's only a single statement) Thanks for reporting, and again, for the patch!
        Hide
        Glenn Adams added a comment -

        batch transition to closed; if someone wishes to restore one of these to resolved in order to perform a verification step, then feel free to do so

        Show
        Glenn Adams added a comment - batch transition to closed; if someone wishes to restore one of these to resolved in order to perform a verification step, then feel free to do so

          People

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

            Dates

            • Created:
              Updated:
              Resolved:

              Development