[jira] Commented: (XMLBEANS-438) O(n^2) operation in xmlbeans would like to make O(n log n) or better

["David Fisher (JIRA)" <xm...@xml.apache.org>]

    [ https://issues.apache.org/jira/browse/XMLBEANS-438?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12920613#action_12920613 ] 

David Fisher commented on XMLBEANS-438:
---------------------------------------

This is a problem for Apache POI. We would really like to have a solution.

Any comments on array setters and making these efficient?

> 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
>         Attachments: Main.java, PoiTest.jar, ResponseTimeVsRowCount.png
>
>
> 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