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]

Reply via email to