pjfanning opened a new pull request, #104: URL: https://github.com/apache/poi-xmlbeans/pull/104
`getXxxArray(i)` walked the child list from the first child on every call, so an indexed pass over one element's children was O(n^2). Iterating the list returned by `getXxxList()` was worse again: `AbstractList`'s iterator asks the list for its `size()` on every `hasNext()`, and for these lists `size()` is `count_elements`, another full walk over the children. **1. `find_element_user` now goes through the nth-child cache.** `Locale` already keeps two version-stamped nth-child caches so that sequential access resumes from the last child it returned; cursor navigation (`Locale.toChild`) and `insert_element_user` both use it, but `Xobj.find_element_user` scanned from `_firstChild` instead. It now calls `findNthChildElem` like its neighbours do, which makes a forward or backward pass amortized O(1) per element. The `QNameSet` half of that cache never worked: `nthCache.fetch` assigned `_name` but not `_set`, so `cacheSame` could never match a set lookup and every one of them re-seeded from the first child. Assigning both keys together fixes that and keeps them consistent - leaving a stale `_set` behind while re-seeding by name would let a later set lookup match a position that was seeded by name. A negative index still resolves to the first matching element, as it always has. **2. The lists returned by `getXxxList()` have their own iterator.** `JavaListIterator` reads the size when it thinks it has reached the end rather than before every element, so a pass costs one `size()` call instead of n. The list stays live - elements appended while an iteration is running are still picked up, because reaching the end of the run re-reads the size before giving up. `iterator()` and `listIterator(int)` both use it, so `indexOf`, `equals` and `hashCode` benefit too. The one behaviour that changes: if the list shrinks *below* the iterator's position mid-iteration, that is now noticed when the iterator next reaches the end of what it believes the list to be, rather than immediately. Mutating a list while a `for` loop is walking it already threw `NoSuchElementException` in most cases; it still does. ### Measured One full pass over the children of a single element, `line-item` elements in a purchase order, Temurin 17: | n | | `getXxxArray()` | `getXxxList()` pass | `getXxxArray(i)` loop | |---|---|---|---|---| | 1,000 | before | 0.8 ms | 11.3 ms | 2.9 ms | | 1,000 | after | 1.0 ms | 0.6 ms | 0.2 ms | | 16,000 | before | 13.5 ms | 3,670 ms | 1,030 ms | | 16,000 | after | 15.1 ms | 8.3 ms | 3.3 ms | `getXxxArray()` is unchanged - it was already a single walk. ### Tests `IndexedElementAccessTest` checks that indexed access agrees with the bulk array whatever order the indexes are asked for in (forward, backward, shuffled, repeated), that it follows inserts, removes and edits, and that a `QNameSet` accessor (substitution group) and a cursor lookup by name against the same parent do not poison each other's cached position. `JavaListIteratorTest` covers the iterator against a counting backing list: a pass asks for the size twice rather than n times, appends during iteration are seen, and `remove`/`set`/`add`/`previous` behave. -- 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]
