pjfanning opened a new pull request, #105: URL: https://github.com/apache/poi-xmlbeans/pull/105
Follow-up to #104. That change made a flat `getXxxArray(i)` pass linear by resuming from the last child returned. A nested pass stayed quadratic, and this fixes that. ### The problem `findNthChildElem` chose between the two cache entries with `da <= db`. When neither entry matched the parent both distances were `Integer.MAX_VALUE`, so the tie always fell to `_nthCache_A` — and the inner level of a nested pass starts at `n == 0`, which forces a re-seed. Every inner-loop start therefore evicted whatever the outer level was resting on, and the outer walk restarted from the first child on each step. The `if (da == db)` swap that followed made it worse, demoting the entry that had just been seeded. ### The change Pick the closest entry as before, but scan back-to-front so a tie is settled in favour of the least recently used entry, and move the entry used to the front. Eviction then falls on the entry no level is sitting on. Widened from two entries to four at the same time, since three levels of repeated elements nest often enough to be worth holding. ### Measured Largest worksheet of POI's `bug62181.xlsx`, 19,456 rows, Temurin 17, JMH, 6x2s iterations: | | 5.4.1-RC0 | this branch | | |---|---|---|---| | nested `getXxxArray(i)` pass | 1011.8 ± 449.8 ms | **37.3 ± 2.4 ms** | 27x | | nested `getXxxList()` pass | 969.4 ± 92.9 ms | **50.4 ± 16.5 ms** | 19x | | flat indexed pass | 2.67 ± 0.45 ms | 3.50 ± 0.52 ms | unchanged | | no-arg `getXxxArray()` walk | 31.4 ± 17.0 ms | 32.1 ± 15.1 ms | unchanged | Nested list iteration now sits 1.6x off the no-arg array walk, against 31x before. ### Tests Correctness tests alone do not cover this: the accessors return the same elements either way, only the amount of walking differs. Plain nested-access tests pass on the unpatched store. So the store counts the children the caches step over, and `NthChildCacheTest` asserts on that count. It discriminates: 2,000 steps with this change against 42,601 without, and the scaling test catches the quadratic directly — 11,301 to 42,601 when the work only doubled. No timing involved, so nothing flaky. `IndexedElementAccessTest` also gains nested indexed, nested list-iteration and resume-after-nesting cases over the three-level `nameworld` schema. The counter is a `long` increment on three loops in `nthCache.fetch`. I A/B'd a build without it and the difference is not measurable — faster on one benchmark, slower on another, both inside the noise. Happy to drop it and `NthChildCacheTest` if you would rather not carry instrumentation in the store. All 3159 tests pass. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
