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-xmlbeans.git
The following commit(s) were added to refs/heads/trunk by this push:
new 78fcd314 Keep the nth-child cache from losing the outer level of a
nested walk (#105)
78fcd314 is described below
commit 78fcd3147c246bf2c62b75af76a3191b8398de5b
Author: PJ Fanning <[email protected]>
AuthorDate: Fri Sep 4 11:03:07 2026 +0100
Keep the nth-child cache from losing the outer level of a nested walk (#105)
find_element_user resumes an indexed walk from the last child returned,
which
made a flat getXxxArray(i) pass linear. A nested pass stayed quadratic: the
two
cache entries were picked with da <= db, so when neither matched the parent
-
which is every time the inner level starts at n == 0 - the entry chosen to
be
re-seeded was the one the outer level was resting on. The outer walk then
began
again from the first child on every step.
Pick the closest entry as before, but settle a tie in favour of the least
recently used one and move the entry used to the front, so the entry
evicted is
the one no level is on. Widen it from two entries to four while doing so,
since
three levels of repeated elements nest often enough to be worth holding.
On the largest worksheet of POI's bug62181.xlsx, 19,456 rows, Temurin 17: a
nested getXxxArray(i) pass goes from 1,012 ms to 37 ms and a nested
getXxxList() pass from 969 ms to 50 ms. Flat passes and the no-arg
getXxxArray() walk are unchanged.
The store counts the children it steps over so that the difference is
visible
to a test - the answers are the same either way, only the work differs. On
the
same benchmark the counter is not measurable against the walk it sits in.
Co-authored-by: Claude Opus 5 <[email protected]>
---
.../org/apache/xmlbeans/impl/store/Locale.java | 59 ++++++++---
.../xmlbeans/impl/store/NthChildCacheTest.java | 115 +++++++++++++++++++++
.../checkin/IndexedElementAccessTest.java | 95 ++++++++++++++++-
3 files changed, 256 insertions(+), 13 deletions(-)
diff --git a/src/main/java/org/apache/xmlbeans/impl/store/Locale.java
b/src/main/java/org/apache/xmlbeans/impl/store/Locale.java
index 06d4f33e..38991a36 100755
--- a/src/main/java/org/apache/xmlbeans/impl/store/Locale.java
+++ b/src/main/java/org/apache/xmlbeans/impl/store/Locale.java
@@ -1320,20 +1320,33 @@ public final class Locale
return null;
}
- int da = _nthCache_A.distance(parent, name, set, n);
- int db = _nthCache_B.distance(parent, name, set, n);
+ // Take the cache that is closest to the wanted position. Scanning
from the back means
+ // that a tie is settled in favour of the least recently used entry,
which is what makes
+ // a nested pass work: when neither entry matches the parent, the one
re-seeded is the
+ // one the outer level is not sitting on.
+ int best = _nthCaches.length - 1;
+ int bestDistance = _nthCaches[best].distance(parent, name, set, n);
- Xobj x =
- da <= db
- ? _nthCache_A.fetch(parent, name, set, n)
- : _nthCache_B.fetch(parent, name, set, n);
+ for (int i = _nthCaches.length - 2; i >= 0; i--) {
+ int distance = _nthCaches[i].distance(parent, name, set, n);
- if (da == db) {
- nthCache temp = _nthCache_A;
- _nthCache_A = _nthCache_B;
- _nthCache_B = temp;
+ if (distance < bestDistance) {
+ bestDistance = distance;
+ best = i;
+ }
}
+ nthCache cache = _nthCaches[best];
+
+ Xobj x = cache.fetch(parent, name, set, n);
+
+ // move it to the front, so that the entry at the back is always the
one to evict next
+ for (int i = best; i > 0; i--) {
+ _nthCaches[i] = _nthCaches[i - 1];
+ }
+
+ _nthCaches[0] = cache;
+
return x;
}
@@ -1637,6 +1650,8 @@ public final class Locale
_n = -1;
for (Xobj x = parent._firstChild; x != null; x =
x._nextSibling) {
+ Locale.this._nthCacheSteps++;
+
if (x.isElem() && nameHit(name, set, x._name)) {
_child = x;
_n = 0;
@@ -1656,6 +1671,8 @@ public final class Locale
return null;
}
+ Locale.this._nthCacheSteps++;
+
if (x.isElem() && nameHit(name, set, x._name)) {
_child = x;
_n++;
@@ -1671,6 +1688,8 @@ public final class Locale
return null;
}
+ Locale.this._nthCacheSteps++;
+
if (x.isElem() && nameHit(name, set, x._name)) {
_child = x;
_n--;
@@ -2818,8 +2837,24 @@ public final class Locale
int _posTemp;
- nthCache _nthCache_A = new nthCache();
- nthCache _nthCache_B = new nthCache();
+ // One entry per level of element nesting that a pass can be walking at
once. Two was enough
+ // for a flat pass but not for a nested one, where the inner level would
evict the outer.
+ private static final int NTH_CACHE_COUNT = 4;
+
+ final nthCache[] _nthCaches = newNthCaches();
+
+ /** How many children the nth-child caches have stepped over, summed
across all lookups. */
+ long _nthCacheSteps;
+
+ private nthCache[] newNthCaches() {
+ nthCache[] caches = new nthCache[NTH_CACHE_COUNT];
+
+ for (int i = 0; i < caches.length; i++) {
+ caches[i] = new nthCache();
+ }
+
+ return caches;
+ }
domNthCache _domNthCache_A = new domNthCache();
domNthCache _domNthCache_B = new domNthCache();
diff --git
a/src/test/java/org/apache/xmlbeans/impl/store/NthChildCacheTest.java
b/src/test/java/org/apache/xmlbeans/impl/store/NthChildCacheTest.java
new file mode 100644
index 00000000..5961aec2
--- /dev/null
+++ b/src/test/java/org/apache/xmlbeans/impl/store/NthChildCacheTest.java
@@ -0,0 +1,115 @@
+/* Copyright 2004 The Apache Software Foundation
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * limitations under the License.
+ */
+
+package org.apache.xmlbeans.impl.store;
+
+import org.apache.xmlbeans.XmlException;
+import org.apache.xmlbeans.impl.values.TypeStoreUser;
+import org.junit.jupiter.api.Test;
+import org.openuri.nameworld.Loc;
+import org.openuri.nameworld.NameworldDocument;
+import org.openuri.nameworld.NameworldDocument.Nameworld;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertTrue;
+
+/**
+ * The store resumes an indexed walk from the last child it returned, per
parent. What that is
+ * worth cannot be seen from the outside - the answers are the same either
way, only the number of
+ * child lists walked differs - so these read the re-seed counter the store
keeps.
+ *
+ * <p>A pass that resumes properly steps over each child about once. A pass
that keeps losing its
+ * place walks the child list again from the start on every step, which is
quadratic.</p>
+ */
+class NthChildCacheTest {
+
+ private static Nameworld nameworld(int islands, int locations) throws
XmlException {
+ StringBuilder xml = new StringBuilder("<nameworld
xmlns='http://openuri.org/nameworld'>");
+ for (int i = 0; i < islands; i++) {
+ xml.append("<island targetNamespace='is").append(i).append("'>");
+ for (int l = 0; l < locations; l++) {
+ xml.append("<location name='loc").append(l).append("'/>");
+ }
+ xml.append("</island>");
+ }
+ xml.append("</nameworld>");
+
+ return NameworldDocument.Factory.parse(xml.toString()).getNameworld();
+ }
+
+ private static Locale locale(Nameworld world) {
+ return ((Xobj) ((TypeStoreUser) world).get_store())._locale;
+ }
+
+ /** A nested indexed pass, returning how many children the caches stepped
over. */
+ private static long stepsForNestedPass(int islands, int locations) throws
XmlException {
+ Nameworld world = nameworld(islands, locations);
+ Locale locale = locale(world);
+ locale._nthCacheSteps = 0;
+
+ for (int i = 0; i < islands; i++) {
+ Nameworld.Island island = world.getIslandArray(i);
+
+ for (int l = 0; l < locations; l++) {
+ Loc location = island.getLocationArray(l);
+ assertEquals("loc" + l, location.getName());
+ }
+ }
+
+ return locale._nthCacheSteps;
+ }
+
+ @Test
+ void aNestedPassWalksEachChildAboutOnce() throws Exception {
+ int islands = 400;
+ int locations = 4;
+
+ long steps = stepsForNestedPass(islands, locations);
+
+ // a pass that keeps its place steps over each child about once:
islands * locations,
+ // plus the islands themselves. Losing the outer position makes the
outer walk quadratic.
+ long walked = (long) islands * locations + islands;
+
+ assertTrue(steps <= 4 * walked,
+ "expected about " + walked + " steps, got " + steps);
+ }
+
+ @Test
+ void theWalkGrowsWithTheWorkNotWithItsSquare() throws Exception {
+ // twice the islands is twice the parents, so twice the re-seeds - not
four times
+ long small = stepsForNestedPass(200, 4);
+ long large = stepsForNestedPass(400, 4);
+
+ assertTrue(large < small * 3,
+ "steps went from " + small + " to " + large + " when the work only
doubled");
+ }
+
+ @Test
+ void deeperNestingStillResumesEachLevel() throws Exception {
+ // three levels of parents at once, which is what the cache has to hold
+ int islands = 400;
+ Nameworld world = nameworld(islands, 6);
+ Locale locale = locale(world);
+ locale._nthCacheSteps = 0;
+
+ for (int i = 0; i < islands; i++) {
+ for (int l = 0; l < 6; l++) {
+ assertEquals("loc" + l,
world.getIslandArray(i).getLocationArray(l).getName());
+ }
+ }
+
+ assertTrue(locale._nthCacheSteps <= 4 * ((long) islands * 6 + islands),
+ "steps: " + locale._nthCacheSteps);
+ }
+}
diff --git a/src/test/java/xmlobject/checkin/IndexedElementAccessTest.java
b/src/test/java/xmlobject/checkin/IndexedElementAccessTest.java
index 8259a3b0..1f0d33d6 100644
--- a/src/test/java/xmlobject/checkin/IndexedElementAccessTest.java
+++ b/src/test/java/xmlobject/checkin/IndexedElementAccessTest.java
@@ -21,6 +21,9 @@ import com.easypo.XmlPurchaseOrderDocumentBean.PurchaseOrder;
import org.apache.xmlbeans.XmlCursor;
import org.apache.xmlbeans.XmlException;
import org.junit.jupiter.api.Test;
+import org.openuri.nameworld.Loc;
+import org.openuri.nameworld.NameworldDocument;
+import org.openuri.nameworld.NameworldDocument.Nameworld;
import org.openuri.sgs.RootDocument;
import javax.xml.namespace.QName;
@@ -56,7 +59,8 @@ class IndexedElementAccessTest {
/** A root whose children cycle through the A/B/C substitution group, so
the accessor matches on a QNameSet. */
private static RootDocument.Root substitutionGroupRoot(int children)
throws XmlException {
String[] names = {"A", "B", "C"};
- StringBuilder xml = new StringBuilder("<root xmlns='" + SGS + "'>");
+ StringBuilder xml = new StringBuilder();
+ xml.append("<root xmlns='").append(SGS).append("'>");
for (int i = 0; i < children; i++) {
String name = names[i % names.length];
xml.append('<').append(name).append('>').append("v").append(i).append("</").append(name).append('>');
@@ -83,6 +87,28 @@ class IndexedElementAccessTest {
return order;
}
+ private static final String NW = "http://openuri.org/nameworld";
+
+ /** Three levels of repeated elements, so that a pass over it walks nested
parents. */
+ private static Nameworld nameworld(int islands, int locations, int
references) throws XmlException {
+ StringBuilder xml = new StringBuilder();
+ xml.append("<nameworld xmlns='").append(NW).append("'
xmlns:nw='").append(NW).append("'>");
+ for (int i = 0; i < islands; i++) {
+ xml.append("<island targetNamespace='is").append(i).append("'>");
+ for (int l = 0; l < locations; l++) {
+ xml.append("<location
name='is").append(i).append("-loc").append(l).append("'>");
+ for (int r = 0; r < references; r++) {
+ xml.append("<reference to='nw:r").append(r).append("'/>");
+ }
+ xml.append("</location>");
+ }
+ xml.append("</island>");
+ }
+ xml.append("</nameworld>");
+
+ return NameworldDocument.Factory.parse(xml.toString()).getNameworld();
+ }
+
@Test
void indexedAccessAgreesWithTheBulkArrayInAnyOrder() throws Exception {
PurchaseOrder po = order(COUNT);
@@ -215,4 +241,71 @@ class IndexedElementAccessTest {
assertEquals(3, po.sizeOfLineItemArray());
assertEquals("item2", po.getLineItemArray(1).getDescription());
}
+
+ @Test
+ void nestedIndexedAccessKeepsEachLevelOnItsOwnParent() throws Exception {
+ // The store caches the last child it returned per parent. An inner
level must not be able
+ // to take the entry the level above it is resting on, or the outer
walk restarts every time.
+ Nameworld world = nameworld(12, 6, 4);
+ assertEquals(12, world.sizeOfIslandArray());
+
+ for (int i = 0; i < 12; i++) {
+ Nameworld.Island island = world.getIslandArray(i);
+ assertEquals("is" + i, island.getTargetNamespace());
+ assertEquals(6, island.sizeOfLocationArray());
+
+ for (int l = 0; l < 6; l++) {
+ Loc location = island.getLocationArray(l);
+ assertEquals("is" + i + "-loc" + l, location.getName());
+ assertEquals(4, location.sizeOfReferenceArray());
+
+ for (int r = 0; r < 4; r++) {
+ assertEquals("r" + r,
location.getReferenceArray(r).getTo().getLocalPart());
+ }
+ }
+ }
+ }
+
+ @Test
+ void nestedListIterationKeepsEachLevelOnItsOwnParent() throws Exception {
+ Nameworld world = nameworld(12, 6, 4);
+
+ int islands = 0;
+ for (Nameworld.Island island : world.getIslandList()) {
+ assertEquals("is" + islands, island.getTargetNamespace());
+
+ int locations = 0;
+ for (Loc location : island.getLocationList()) {
+ assertEquals("is" + islands + "-loc" + locations,
location.getName());
+
+ int references = 0;
+ for (Loc.Reference reference : location.getReferenceList()) {
+ assertEquals("r" + references++,
reference.getTo().getLocalPart());
+ }
+ assertEquals(4, references);
+
+ locations++;
+ }
+ assertEquals(6, locations);
+
+ islands++;
+ }
+ assertEquals(12, islands);
+ }
+
+ @Test
+ void aNestedWalkLeavesTheOuterLevelResumable() throws Exception {
+ // walk the outer level forwards, dipping into the inner level between
steps, then read the
+ // outer level again out of order - a cache the inner walk corrupted
would answer wrongly
+ Nameworld world = nameworld(16, 4, 2);
+
+ for (int i = 0; i < 16; i++) {
+ assertEquals("is" + i,
world.getIslandArray(i).getTargetNamespace());
+ assertEquals("is" + i + "-loc3",
world.getIslandArray(i).getLocationArray(3).getName());
+ }
+
+ for (int i : shuffled(16)) {
+ assertEquals("is" + i,
world.getIslandArray(i).getTargetNamespace());
+ }
+ }
}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]