[prev in list] [next in list] [prev in thread] [next in thread] 

List:       xmlbeans-dev
Subject:    [jira] Created: (XMLBEANS-438) O(n^2) operation in xmlbeans would
From:       "Bryce Alcock (JIRA)" <xmlbeans-dev () xml ! apache ! org>
Date:       2010-05-10 18:42:37
Message-ID: 10425410.681273516957046.JavaMail.jira () thor
[Download RAW message or body]

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

                 Key: XMLBEANS-438
                 URL: https://issues.apache.org/jira/browse/XMLBEANS-438
             Project: XMLBeans
          Issue Type: Improvement
    Affects Versions: Version 2.4 
         Environment: Using XMLbeans inside of POI when saving spreadsheets in the \
XLSX file format.  Reporter: Bryce Alcock


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(n) 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(n)
 //  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.




-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@xmlbeans.apache.org
For additional commands, e-mail: dev-help@xmlbeans.apache.org


[prev in list] [next in list] [prev in thread] [next in thread]