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]