Uploaded image for project: 'XMLBeans'
  1. XMLBeans
  2. XMLBEANS-438

O(n^2) operation in xmlbeans would like to make O(n log n) or better

    XMLWordPrintableJSON

    Details

    • Type: Improvement
    • Status: Open
    • Priority: Major
    • Resolution: Unresolved
    • Affects Version/s: Version 2.4
    • Fix Version/s: None
    • Component/s: None
    • Environment:
      Using XMLbeans inside of POI when saving spreadsheets in the XLSX file format.

      Description

      Using POI to save a spread sheet in XLSX format causes an O(n^2) operation to occur.
      Specifically:

      Just a Quick overview
      it seems like XmlComplexContentImpl.arraySetterHelper iterates over all elements in the spread sheet.
      then in side of that iteration, the Xobj.find_element_user(Qname,int) is an Order n operation.

      Just making Xobj.find_element_user a O(log n) would completely solve the problem.

      ANALYSIS: O(n^2) in XML Beans: (Around Line 1153 or so pf XmlComplexContentImpl.java method arraySetterHelper)
      -----------------------------------------------------------
      // Order N (this is invoked 1 time for each element in sources (~120,000 records in my case)

      for ( i+, j; i < sources.length; i, j+)
      {
      long t1 = System.currentTimeMillis();
      XmlCursor c = sources[i].isImmutable() ? null : sources[i].newCursor();
      getCursorTime += (System.currentTimeMillis()-t1);
      long t2=System.currentTimeMillis();
      if (c != null && c.toParent() && c.getObject() == this)
      {
      ifCheckTime += (System.currentTimeMillis()-t2);
      long t3 = System.currentTimeMillis();
      c.dispose();
      long t4 = System.currentTimeMillis();

      // THIS CAUSES O(n^2) SEE CODE BELOW, but this on O for each record.
      // THIS IS THE INEFFICIENCY in XMLBeans...

      current = store.find_element_user( elemName, j );

      findUserElement += (System.currentTimeMillis() - t4);
      if (current == sources[i])
      ; // advance
      else

      { // Fall back to the general case break; }

      insideIfTime += (System.currentTimeMillis()-t3);
      }
      else

      { ifCheckTime += (System.currentTimeMillis()-t2); c.dispose(); // Insert before the current element TypeStoreUser user = store.insert_element_user( elemName, j ); ((XmlObjectBase) user).set( sources[i] ); }

      }

      ---------------- Method from store.find_element_user(QName,int i)---------

      // THIS METHOD IS 0
      // but this is called n times by XmlComplexContentImpl.java around line 1153....
      public TypeStoreUser find_element_user ( QName name, int i )

      { for ( Xobj x = _firstChild ; x != null ; x = x._nextSibling ) if (x.isElem() && x._name.equals( name ) && --i < 0) return x.getUser(); return null; }

      I will add a sample code showing exactly how to reproduce this issue.

        Attachments

        1. Main.java
          2 kB
          Bryce Alcock
        2. PoiTest.jar
          5 kB
          Bryce Alcock
        3. ResponseTimeVsRowCount.png
          29 kB
          Bryce Alcock

          Activity

            People

            • Assignee:
              Unassigned
              Reporter:
              u912boilermaker Bryce Alcock
            • Votes:
              0 Vote for this issue
              Watchers:
              2 Start watching this issue

              Dates

              • Created:
                Updated: