Faster ElementTree iterating

[serhiy-storchaka]

BPO	25873
Nosy	@brettcannon, @scoder, @vadmium, @serhiy-storchaka
Files	etree_iter.patch etree_iter2.patch

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/serhiy-storchaka'
closed_at = <Date 2015-12-21.11:51:17.800>
created_at = <Date 2015-12-15.19:17:03.640>
labels = ['extension-modules', 'expert-XML', 'performance']
title = 'Faster ElementTree iterating'
updated_at = <Date 2015-12-21.11:51:17.799>
user = 'https://github.com/serhiy-storchaka'

bugs.python.org fields:

activity = <Date 2015-12-21.11:51:17.799>
actor = 'serhiy.storchaka'
assignee = 'serhiy.storchaka'
closed = True
closed_date = <Date 2015-12-21.11:51:17.800>
closer = 'serhiy.storchaka'
components = ['Extension Modules', 'XML']
creation = <Date 2015-12-15.19:17:03.640>
creator = 'serhiy.storchaka'
dependencies = []
files = ['41318', '41324']
hgrepos = []
issue_num = 25873
keywords = ['patch']
message_count = 6.0
messages = ['256472', '256495', '256502', '256507', '256674', '256795']
nosy_count = 5.0
nosy_names = ['brett.cannon', 'scoder', 'python-dev', 'martin.panter', 'serhiy.storchaka']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue25873'
versions = ['Python 3.6']

[serhiy-storchaka]

Proposed patch refactors and optimize the code for iterating ElementTree. Refactoring and minor optimization makes the code about 30 lines smaller and 2-3% faster. Using a continuous array instead of linked list makes the code up to 40% faster (lxml benchmark was used to measurement).

In addition the patch fixes possible issue with owning references.

[vadmium]

Looks technically correct as far as my knowledge of the malloc routines goes. What was the problem with references that you fixed? Maybe with parent_stack_push_new() failure?

The main reference counting bug that sticks out to me is with the text and tail elements, because element_get_text() etc return a borrowed reference. It might be good to fix this while you are at it:

>>> element = Element("tag")
>>> class Text:
...     def __bool__(self):
...         element.text = "changed"
...         return True
... 
>>> element.text = Text()
>>> i = element.itertext()
>>> next(i)
Segmentation fault (core dumped)
[Exit 139]

[serhiy-storchaka]

Good catch Martin. I missed this case. Following patch fixes it.

Other bugs look similar. They presumably can be triggered when remove the element itself during executing the __next__() method. I have no a reproducer though.

I don't know wherever it is worth to fix these bugs in maintained releases.

[vadmium]

The new changes look good.

I see these kind of reference counting bugs as fairly low priority. I suspect there are plenty more in this module, at least bpo-24103 and bpo-24104.

[serhiy-storchaka]

Thank you for your review Martin. I have opened a separate bpo-25902 for refcount bugs in iteration. Its patch is purposed for all versions, while this issue is for developer version only.

[python-dev]

New changeset 5a5d5268afd5 by Serhiy Storchaka in branch 'default':
Issue bpo-25873: Optimized iterating ElementTree.
https://hg.python.org/cpython/rev/5a5d5268afd5