Title: Make section block iteration linear in document size by scks1 · Pull Request #1635 · python-openxml/python-docx · GitHub
Open Graph Title: Make section block iteration linear in document size by scks1 · Pull Request #1635 · python-openxml/python-docx
X Title: Make section block iteration linear in document size by scks1 · Pull Request #1635 · python-openxml/python-docx
Description: Iterating the blocks of every section — the natural way to partition a document by section — currently costs time quadratic in the document size, because each section's blocks are computed from a document-prefix XPath. On a generated document with 400 sections and 16,000 paragraphs, partitioning takes ~307 s; with this change it takes ~2 s, with identical results. Problem _SectBlockElementIterator computes the blocks of section i by evaluating an XPath that returns every w:p/w:tbl from the start of the document through the end of section i, plus a count(...) XPath over the prefix through section i−1, and slicing. Each section therefore rescans the whole prefix before it. Measured in block elements materialized across a full partition: document blocks sections before after generated 1,000 25 25,000 1,025 generated 4,000 100 400,000 4,100 generated 8,000 50 400,000 8,050 generated 16,000 400 6,400,000 16,400 At fixed block count, the "before" work grows in direct proportion to the number of sections. This is the cost that led the unstructured project to rewrite its DOCX partitioning rather than ask python-docx for each section's blocks, citing severe slowdowns on documents with hundreds of sections and thousands of paragraphs. A profile of the stock code attributes ~93% of partition time to these two XPath evaluations. Change One file, docx/oxml/section.py: _SectBlockElementIterator first tries a sibling-navigation computation: a section's blocks are the body-level w:p/w:tbl siblings running back from the section's terminal node (the paragraph carrying its w:sectPr, or the body-level w:sectPr itself) to — but not including — the preceding section's terminal paragraph. Collecting them costs time proportional to the section's own size, independent of the document prefix, and keeps no state between calls. The original XPath implementation is retained verbatim as a fallback (_iter_sect_block_elements_xpath) and is used whenever the sectPr does not terminate a body-level section in the ordinary way — e.g. a sectPr nested in other content, or a paragraph carrying more than one sectPr — so behavior on such documents is unchanged by construction. No public API is added, removed, or altered. CT_SectPr.preceding_sectPr is intentionally untouched: I measured its preceding:: XPath first, and libxml2 stops at the nearest match, so its cost is already bounded by the size of the preceding section rather than the document prefix. Correctness A dump comparing, per document, every section's block elements (order and text), the preceding_sectPr chain, and header/footer inheritance resolution for all six header/footer kinds is byte-identical before and after the change, across generated documents (tables as blocks, 1-block sections, an empty final section, SDT-wrapped content) and a corpus of real-world-shaped documents (multi-section headers/footers, footnotes, comments, tracked changes, shapes, a LibreOffice-produced file). The full test suite passes as before: 1,600 passed, with the same 9 pre-existing collection/setup errors in tests/opc/test_phys_pkg.py on both versions in my environment (a pytest-9 warning-as-error artifact, unrelated to this change). Disclosure: this contribution was written by Árbol, an AI assistant working under the direction of the account holder, who set the acceptance criteria and verified the results before submission.
Open Graph Description: Iterating the blocks of every section — the natural way to partition a document by section — currently costs time quadratic in the document size, because each section's blocks are computed from...
X Description: Iterating the blocks of every section — the natural way to partition a document by section — currently costs time quadratic in the document size, because each section's blocks are computed ...
Opengraph URL: https://github.com/python-openxml/python-docx/pull/1635
X: @github
Domain: github.com
| react-profiling | 0 |
| react-import-map | react,react-dom,react-dom/client,react-dom/profiling,react-is,react/compiler-runtime,react/jsx-dev-runtime,react/jsx-runtime,scheduler@b8488ee2c322 |
| route-pattern | /:user_id/:repository/pull/:id/files(.:format) |
| route-controller | pull_requests |
| route-action | files |
| fetch-nonce | v2:7fea0622-bd2a-efa1-5c51-7269f3ec01c0 |
| current-catalog-service-hash | ae870bc5e265a340912cde392f23dad3671a0a881730ffdadd82f2f57d81641b |
| request-id | 9976:144E47:81C05E:96A17A:6AFF65D4 |
| html-safe-nonce | e8fee92b9b980b378e8b768a3cb1cde76d0539dbf717ff3a38e25ca197a1dc98 |
| visitor-payload | eyJyZWZlcnJlciI6IiIsInJlcXVlc3RfaWQiOiI5OTc2OjE0NEU0Nzo4MUMwNUU6OTZBMTdBOjZBRkY2NUQ0IiwidmlzaXRvcl9pZCI6IjE0MTgzNzMyNDAwMzE1MDM4MjgiLCJyZWdpb25fZWRnZSI6ImlhZCIsInJlZ2lvbl9yZW5kZXIiOiJpYWQifQ== |
| visitor-hmac | 7d6d50415c3a59c6b66964f458695e828671534162579d94805eb2ffca559a11 |
| hovercard-subject-tag | pull_request:5098524838 |
| github-keyboard-shortcuts | repository,pull-request-list,pull-request-conversation,pull-request-files-changed,copilot |
| google-site-verification | Apib7-x98H0j5cPqHWwSMm6dNU4GmODRoqxLiDzdx9I |
| octolytics-url | https://collector.github.com/github/collect |
| analytics-location | / |
| fb:app_id | 1401488693436528 |
| apple-itunes-app | app-id=1477376905, app-argument=https://github.com/python-openxml/python-docx/pull/1635/files |
| twitter:image | https://avatars.githubusercontent.com/u/126534658?s=400&v=4 |
| twitter:card | summary_large_image |
| og:image | https://avatars.githubusercontent.com/u/126534658?s=400&v=4 |
| og:image:alt | Iterating the blocks of every section — the natural way to partition a document by section — currently costs time quadratic in the document size, because each section's blocks are computed from... |
| og:site_name | GitHub |
| og:type | object |
| hostname | github.com |
| expected-hostname | github.com |
| None | 41b58589a1c4eda1e3c8904144a412b88ca4455f63ca2ad3629f2e9f3c3a1d12 |
| turbo-cache-control | no-preview |
| diff-view | unified |
| go-import | github.com/python-openxml/python-docx git https://github.com/python-openxml/python-docx.git |
| octolytics-dimension-user_id | 3403760 |
| octolytics-dimension-user_login | python-openxml |
| octolytics-dimension-repository_id | 13592924 |
| octolytics-dimension-repository_nwo | python-openxml/python-docx |
| octolytics-dimension-repository_public | true |
| octolytics-dimension-repository_is_fork | false |
| octolytics-dimension-repository_network_root_id | 13592924 |
| octolytics-dimension-repository_network_root_nwo | python-openxml/python-docx |
| turbo-body-classes | logged-out env-production page-responsive |
| disable-turbo | true |
| browser-stats-url | https://api.github.com/_private/browser/stats |
| browser-errors-url | https://api.github.com/_private/browser/errors |
| release | 8968d6d6acc65d74e4df332d23932dd3fd0502a4 |
| ui-target | full |
| theme-color | #1e2327 |
| color-scheme | light dark |
Links:
Viewport: width=device-width