Repository navigation
Quadratic behavior in xml.etree.ElementPath Index Predicates #152674
Description
Element.findall() and fully-consumed Element.iterfind() exhibit O(n^2) time complexity when using XPath index predicates ([1], [last()], [last()-N]) on XML documents with many same-tag siblings.
Element.find() is only affected when the first match is near the end of the sibling list, such as with [last()] or [last()-N]; .//item[1] short-circuits after the first match.
(reported privately by @DarkaMaul)
Linked PRs
- gh-152674: Avoid quadratic behavior in xml.etree.ElementPath index predicates #152676
- [3.14] gh-152674: Avoid quadratic behavior in xml.etree.ElementPath index predicates (GH-152676) #154810
- [3.13] gh-152674: Avoid quadratic behavior in xml.etree.ElementPath index predicates (GH-152676) #154811
- [3.15] gh-152674: Avoid quadratic behavior in xml.etree.ElementPath index predicates (GH-152676) #154812
- [3.11] gh-152674: Avoid quadratic behavior in xml.etree.ElementPath index predicates (GH-152676) #154813
- [3.10] gh-152674: Avoid quadratic behavior in xml.etree.ElementPath index predicates (GH-152676) #154814
- [3.12] gh-152674: Avoid quadratic behavior in xml.etree.ElementPath index predicates (GH-152676) #154815
Activity
gh-152674: Avoid quadratic behavior in xml.etree.ElementPath index pr…
[3.15] gh-152674: Avoid quadratic behavior in xml.etree.ElementPath i…
[3.14] gh-152674: Avoid quadratic behavior in xml.etree.ElementPath i…
[3.13] gh-152674: Avoid quadratic behavior in xml.etree.ElementPath i…
[3.12] gh-152674: Avoid quadratic behavior in xml.etree.ElementPath i…
[3.11] gh-152674: Avoid quadratic behavior in xml.etree.ElementPath i…
[3.10] gh-152674: Avoid quadratic behavior in xml.etree.ElementPath i…
pythongh-152674: Avoid quadratic behavior in xml.etree.ElementPath in…
package/python3: security bump to v3.12.14