This is an automated email from the ASF dual-hosted git repository.

pjfanning pushed a commit to branch trunk
in repository https://gitbox.apache.org/repos/asf/poi.git


The following commit(s) were added to refs/heads/trunk by this push:
     new 4dbced3e78 Avoid quadratic XmlBeans element access on hot paths (#1242)
4dbced3e78 is described below

commit 4dbced3e78fdafa68d8c463cd2a5befbc119f987
Author: PJ Fanning <[email protected]>
AuthorDate: Thu Sep 3 19:48:40 2026 +0100

    Avoid quadratic XmlBeans element access on hot paths (#1242)
    
    XmlBeans indexed accessors walk the child list from the start, so
    getXxxArray(i) is O(i) and iterating the lazy getXxxList() is O(n^2)
    - a full pass over 16000 children measured 6062ms via getXxxList()
    against 1.4ms for a single getXxxArray() walk. Three places paid that
    cost:
    
    XSSFRow.fixupCTCells, which runs on save for any row whose cells were
    created out of column order, deep-copied every CTCell and reordered
    them with indexed setCArray(i, ...)/getCArray(i), making it O(cells^2)
    per row. It now reorders the existing beans with XmlCursor.moveXml(),
    which is linear, and re-attaches each XSSFCell from a single
    getCArray() call. Note that a single setCArray(CTCell[]) is not a fix
    here: arraySetterHelper keeps the common prefix and then rebuilds the
    tail, so a divergence at index 0 makes it markedly slower than the
    existing code.
    
    The XDDFDataSourcesFactory data sources implemented getPointAt(index)
    as getPtArray(index), so reading every point of a series was O(n^2).
    Each anonymous source already holds a private deep copy taken at
    construction and nothing mutates it, so the point array is now
    materialised once and indexed directly.
    
    ColumnHelper iterated getColList() in four read-only loops, including
    cleanColumns() which runs when every sheet is loaded. These now
    iterate getColArray() instead, turning each into a single walk.
    
    Co-authored-by: Claude Fable 5 <[email protected]>
---
 .../usermodel/chart/XDDFDataSourcesFactory.java    | 36 ++++++++++---
 .../org/apache/poi/xssf/usermodel/XSSFRow.java     | 63 +++++++++++++++++-----
 .../poi/xssf/usermodel/helpers/ColumnHelper.java   | 11 ++--
 3 files changed, 84 insertions(+), 26 deletions(-)

diff --git 
a/poi-ooxml/src/main/java/org/apache/poi/xddf/usermodel/chart/XDDFDataSourcesFactory.java
 
b/poi-ooxml/src/main/java/org/apache/poi/xddf/usermodel/chart/XDDFDataSourcesFactory.java
index c57c7c453a..4864612a74 100644
--- 
a/poi-ooxml/src/main/java/org/apache/poi/xddf/usermodel/chart/XDDFDataSourcesFactory.java
+++ 
b/poi-ooxml/src/main/java/org/apache/poi/xddf/usermodel/chart/XDDFDataSourcesFactory.java
@@ -29,7 +29,9 @@ import org.apache.poi.xssf.usermodel.XSSFSheet;
 import org.openxmlformats.schemas.drawingml.x2006.chart.CTAxDataSource;
 import org.openxmlformats.schemas.drawingml.x2006.chart.CTNumData;
 import org.openxmlformats.schemas.drawingml.x2006.chart.CTNumDataSource;
+import org.openxmlformats.schemas.drawingml.x2006.chart.CTNumVal;
 import org.openxmlformats.schemas.drawingml.x2006.chart.CTStrData;
+import org.openxmlformats.schemas.drawingml.x2006.chart.CTStrVal;
 
 /**
  * Class {@code XDDFDataSourcesFactory} is a factory for {@link XDDFDataSource}
@@ -48,6 +50,9 @@ public class XDDFDataSourcesFactory {
         if (categoryDS.getNumRef() != null && 
categoryDS.getNumRef().getNumCache() != null) {
             return new XDDFCategoryDataSource() {
                 private final CTNumData category = (CTNumData) 
categoryDS.getNumRef().getNumCache().copy();
+                // the points are read once, as the indexed accessor of 
XmlBeans walks
+                // the list of elements from the start on every call
+                private final CTNumVal[] points = category.getPtArray();
                 private final String formatCode = category.isSetFormatCode() ? 
category.getFormatCode() : null;
 
                 @Override
@@ -72,11 +77,11 @@ public class XDDFDataSourcesFactory {
 
                 @Override
                 public String getPointAt(int index) {
-                    if (category.sizeOfPtArray() <= index) {
+                    if (points.length <= index) {
                         throw new IllegalArgumentException("Cannot access 
0-based index " + index +
-                                " in point-array with " + 
category.sizeOfPtArray() + " items");
+                                " in point-array with " + points.length + " 
items");
                     }
-                    return category.getPtArray(index).getV();
+                    return points[index].getV();
                 }
 
                 @Override
@@ -85,6 +90,9 @@ public class XDDFDataSourcesFactory {
         } else if (categoryDS.getStrRef() != null && 
categoryDS.getStrRef().getStrCache() != null) {
             return new XDDFCategoryDataSource() {
                 private final CTStrData category = (CTStrData) 
categoryDS.getStrRef().getStrCache().copy();
+                // the points are read once, as the indexed accessor of 
XmlBeans walks
+                // the list of elements from the start on every call
+                private final CTStrVal[] points = category.getPtArray();
 
                 @Override
                 public boolean isCellRange() {
@@ -103,7 +111,7 @@ public class XDDFDataSourcesFactory {
 
                 @Override
                 public String getPointAt(int index) {
-                    return category.getPtArray(index).getV();
+                    return points[index].getV();
                 }
 
                 @Override
@@ -112,6 +120,9 @@ public class XDDFDataSourcesFactory {
         } else if (categoryDS.getNumLit() != null) {
             return new XDDFCategoryDataSource() {
                 private final CTNumData category = (CTNumData) 
categoryDS.getNumLit().copy();
+                // the points are read once, as the indexed accessor of 
XmlBeans walks
+                // the list of elements from the start on every call
+                private final CTNumVal[] points = category.getPtArray();
                 private final String formatCode = category.isSetFormatCode() ? 
category.getFormatCode() : null;
 
                 @Override
@@ -146,7 +157,7 @@ public class XDDFDataSourcesFactory {
 
                 @Override
                 public String getPointAt(int index) {
-                    return category.getPtArray(index).getV();
+                    return points[index].getV();
                 }
 
                 @Override
@@ -155,6 +166,9 @@ public class XDDFDataSourcesFactory {
         } else if (categoryDS.getStrLit() != null) {
             return new XDDFCategoryDataSource() {
                 private final CTStrData category = (CTStrData) 
categoryDS.getStrLit().copy();
+                // the points are read once, as the indexed accessor of 
XmlBeans walks
+                // the list of elements from the start on every call
+                private final CTStrVal[] points = category.getPtArray();
 
                 @Override
                 public boolean isCellRange() {
@@ -183,7 +197,7 @@ public class XDDFDataSourcesFactory {
 
                 @Override
                 public String getPointAt(int index) {
-                    return category.getPtArray(index).getV();
+                    return points[index].getV();
                 }
 
                 @Override
@@ -201,6 +215,9 @@ public class XDDFDataSourcesFactory {
         if (valuesDS.getNumRef() != null && valuesDS.getNumRef().getNumCache() 
!= null) {
             return new XDDFNumericalDataSource<Double>() {
                 private final CTNumData values = (CTNumData) 
valuesDS.getNumRef().getNumCache().copy();
+                // the points are read once, as the indexed accessor of 
XmlBeans walks
+                // the list of elements from the start on every call
+                private final CTNumVal[] points = values.getPtArray();
                 private String formatCode = values.isSetFormatCode() ? 
values.getFormatCode() : null;
 
                 @Override
@@ -235,7 +252,7 @@ public class XDDFDataSourcesFactory {
 
                 @Override
                 public Double getPointAt(int index) {
-                    return Double.valueOf(values.getPtArray(index).getV());
+                    return Double.valueOf(points[index].getV());
                 }
 
                 @Override
@@ -251,6 +268,9 @@ public class XDDFDataSourcesFactory {
         } else if (valuesDS.getNumLit() != null) {
             return new XDDFNumericalDataSource<Double>() {
                 private final CTNumData values = (CTNumData) 
valuesDS.getNumLit().copy();
+                // the points are read once, as the indexed accessor of 
XmlBeans walks
+                // the list of elements from the start on every call
+                private final CTNumVal[] points = values.getPtArray();
                 private String formatCode = values.isSetFormatCode() ? 
values.getFormatCode() : null;
 
                 @Override
@@ -290,7 +310,7 @@ public class XDDFDataSourcesFactory {
 
                 @Override
                 public Double getPointAt(int index) {
-                    return Double.valueOf(values.getPtArray(index).getV());
+                    return Double.valueOf(points[index].getV());
                 }
 
                 @Override
diff --git a/poi-ooxml/src/main/java/org/apache/poi/xssf/usermodel/XSSFRow.java 
b/poi-ooxml/src/main/java/org/apache/poi/xssf/usermodel/XSSFRow.java
index 9cb3f919a8..93826bdc5b 100644
--- a/poi-ooxml/src/main/java/org/apache/poi/xssf/usermodel/XSSFRow.java
+++ b/poi-ooxml/src/main/java/org/apache/poi/xssf/usermodel/XSSFRow.java
@@ -41,6 +41,7 @@ import org.apache.poi.util.Beta;
 import org.apache.poi.util.Internal;
 import org.apache.poi.xssf.model.StylesTable;
 import org.apache.poi.xssf.usermodel.helpers.XSSFRowShifter;
+import org.apache.xmlbeans.XmlCursor;
 import org.openxmlformats.schemas.spreadsheetml.x2006.main.CTCell;
 import org.openxmlformats.schemas.spreadsheetml.x2006.main.CTRow;
 
@@ -582,33 +583,67 @@ public class XSSFRow implements Row, Comparable<XSSFRow> {
     }
 
     private void fixupCTCells(CTCell[] cArrayOrig) {
-        // copy all values to 2nd array and a map for lookup of index
-        CTCell[] cArrayCopy = new CTCell[cArrayOrig.length];
-        IdentityHashMap<CTCell, Integer> map = new 
IdentityHashMap<>(_cells.size());
+        // build a map for lookup of the index of a CTCell in the row
+        IdentityHashMap<CTCell, Integer> map = new 
IdentityHashMap<>(cArrayOrig.length);
         int i = 0;
         for (CTCell ctCell : cArrayOrig) {
-            cArrayCopy[i] = (CTCell) ctCell.copy();
             map.put(ctCell, i);
             i++;
         }
 
-        // populate _row.cArray correctly
+        // collect the CTCells in the order in which they need to appear in 
the XML
+        CTCell[] cArrayNew = new CTCell[_cells.size()];
+        boolean[] stillUsed = new boolean[cArrayOrig.length];
         i = 0;
         for (XSSFCell cell : _cells.values()) {
-            // no need to change anything if position is correct
             Integer correctPosition = map.get(cell.getCTCell());
             Objects.requireNonNull(correctPosition, "Should find CTCell in 
_row");
-            if(correctPosition != i) {
-                // we need to re-populate this CTCell
-                _row.setCArray(i, cArrayCopy[correctPosition]);
-                cell.setCTCell(_row.getCArray(i));
-            }
+            stillUsed[correctPosition] = true;
+            cArrayNew[i] = cArrayOrig[correctPosition];
             i++;
         }
 
-        // remove any remaining illegal references in _rows.cArray
-        while(_row.sizeOfCArray() > _cells.size()) {
-            _row.removeC(_cells.size());
+        // remove any remaining illegal references in _row.cArray
+        for (i = 0; i < cArrayOrig.length; i++) {
+            if (!stillUsed[i]) {
+                try (XmlCursor cursor = cArrayOrig[i].newCursor()) {
+                    cursor.removeXml();
+                }
+            }
+        }
+
+        // the CTCells at the start which are already in the correct order do 
not need to be moved
+        int matching = 0;
+        for (i = 0; i < cArrayOrig.length; i++) {
+            if (stillUsed[i]) {
+                if (matching < cArrayNew.length && cArrayNew[matching] == 
cArrayOrig[i]) {
+                    matching++;
+                } else {
+                    break;
+                }
+            }
+        }
+
+        // move the remaining CTCells in front of the last one, in the order 
in which
+        // they need to appear - moving the XML via cursors avoids the indexed 
XmlBeans
+        // accessors, which walk the list of elements from the start on every 
call
+        if (matching < cArrayNew.length - 1) {
+            try (XmlCursor dest = cArrayNew[cArrayNew.length - 1].newCursor()) 
{
+                for (int j = matching; j < cArrayNew.length - 1; j++) {
+                    try (XmlCursor src = cArrayNew[j].newCursor()) {
+                        src.moveXml(dest);
+                    }
+                }
+            }
+        }
+
+        // moving the XML replaces the CTCell instances, so the cells need to 
be
+        // re-attached to the CTCells which are now stored in the row
+        CTCell[] cArrayUpdated = _row.getCArray();
+        i = 0;
+        for (XSSFCell cell : _cells.values()) {
+            cell.setCTCell(cArrayUpdated[i]);
+            i++;
         }
     }
 
diff --git 
a/poi-ooxml/src/main/java/org/apache/poi/xssf/usermodel/helpers/ColumnHelper.java
 
b/poi-ooxml/src/main/java/org/apache/poi/xssf/usermodel/helpers/ColumnHelper.java
index a0ae0311f2..2703cfac5f 100644
--- 
a/poi-ooxml/src/main/java/org/apache/poi/xssf/usermodel/helpers/ColumnHelper.java
+++ 
b/poi-ooxml/src/main/java/org/apache/poi/xssf/usermodel/helpers/ColumnHelper.java
@@ -53,7 +53,10 @@ public class ColumnHelper {
         int i;
         for (i = 0; i < colsArray.length; i++) {
             CTCols cols = colsArray[i];
-            for (CTCol col : cols.getColList()) {
+            // fetching the array is much quicker than iterating the list, as 
the
+            // list resolves each element via the indexed getter, which walks 
the
+            // list of elements from the start on every call
+            for (CTCol col : cols.getColArray()) {
                 addCleanColIntoCols(newCols, col, trackedCols);
             }
         }
@@ -73,7 +76,7 @@ public class ColumnHelper {
         // read above.
         TreeSet<CTCol> trackedCols = new TreeSet<>(
                 CTColComparator.BY_MIN_MAX);
-        trackedCols.addAll(cols.getColList());
+        trackedCols.addAll(Arrays.asList(cols.getColArray()));
         addCleanColIntoCols(cols, newCol, trackedCols);
         cols.setColArray(trackedCols.toArray(new CTCol[0]));
         return cols;
@@ -317,7 +320,7 @@ public class ColumnHelper {
     }
 
     private boolean columnExists(CTCols cols, long min, long max) {
-        for (CTCol col : cols.getColList()) {
+        for (CTCol col : cols.getColArray()) {
             if (col.getMin() == min && col.getMax() == max) {
                 return true;
             }
@@ -328,7 +331,7 @@ public class ColumnHelper {
     public int getIndexOfColumn(CTCols cols, CTCol searchCol) {
         if (cols == null || searchCol == null) return -1;
         int i = 0;
-        for (CTCol col : cols.getColList()) {
+        for (CTCol col : cols.getColArray()) {
             if (col.getMin() == searchCol.getMin() && col.getMax() == 
searchCol.getMax()) {
                 return i;
             }


---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Reply via email to