classification
Title: xml.dom.minidom: performance issue with Node.insertBefore()
Type: performance Stage: patch review
Components: XML Versions: Python 3.6
process
Status: open Resolution:
Dependencies: Superseder:
Assigned To: serhiy.storchaka Nosy List: Robert Haschke, benjamin.peterson, berker.peksag, guihome, serhiy.storchaka
Priority: normal Keywords: patch

Created on 2015-06-10 13:29 by Robert Haschke, last changed 2016-06-18 15:21 by Robert Haschke.

Files
File name Uploaded Description Edit
minidom.insertBefore.patch Robert Haschke, 2015-06-10 13:29 simple patch for this issue
minidom.insertBefore.patch Robert Haschke, 2016-06-16 14:52 patch in unified diff format review
minidom_example.py Robert Haschke, 2016-06-17 12:45 example demonstrating the performance boost
minidom_example2.py serhiy.storchaka, 2016-06-17 14:39 example demonstrating the performance regression
etree_example.py serhiy.storchaka, 2016-06-17 14:39
minidom.insertBefore2.patch serhiy.storchaka, 2016-06-18 06:41 review
Messages (13)
msg245128 - (view) Author: Robert Haschke (Robert Haschke) * Date: 2015-06-10 13:29
Node.insertBefore() has a serious performance issue:

Using self.childNodes.index(refChild) it searches for the correct index in childNodes where the newChild should be inserted.
However, index() is linear in time w.r.t. the size of childNodes.
Hence, if there are many children, runtime dramatically increases.

Adding a simple caching mechanism (caching the previously used reference)
I was able to reduce runtime in my particular case from 16s to 1.6s, i.e. a factor of 10!
msg254134 - (view) Author: GuiHome (guihome) Date: 2015-11-05 19:20
We have been running this patch for several month now without any issue. 
Would be glad if a maintainer could review it and merge it upstream.

thanks
msg268664 - (view) Author: GuiHome (guihome) Date: 2016-06-16 13:09
kindly ping
msg268669 - (view) Author: Berker Peksag (berker.peksag) * (Python committer) Date: 2016-06-16 14:01
Please attach the patch in unified diff format. See https://docs.python.org/devguide/patch.html for details.
msg268671 - (view) Author: Robert Haschke (Robert Haschke) * Date: 2016-06-16 14:52
Uploaded a "hg diff" against the recent 2.7 branch of the source repo.
msg268710 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2016-06-17 06:19
Could you please provide a simple example that benefits from this change?

Besides index() Node.insertBefore() uses insert() that has linear complexity too.

In any case this is a new feature that can go only in 3.6.
msg268722 - (view) Author: Robert Haschke (Robert Haschke) * Date: 2016-06-17 12:45
I uploaded a simple example to illustrate the tremendous performance boost. Obviously, the example exploits the caching improvement as much as possible: The code assembles a XML document by inserting new nodes before the last one...
These are the timing results:
$ python minidom_example.py old new
oldtime for 5000 iterations: 18.422152
newtime for 5000 iterations: 0.129384

$ python minidom_example.py old new
oldtime for 10000 iterations: 68.305351
newtime for 10000 iterations: 0.142071

You see the quadratic increase of time...
IMHO, this is clearly a (performance) bug and really many people in the ROS community are affected. Hence, I hope that this patch will find its way into some python versions currently used by standard Linux distributions.
msg268726 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2016-06-17 14:39
Thank you for your example Robert.

If modify your example for inserting new nodes before the first one, it shows the slowdown with your patch.

$ ./python minidom_example2.py old new
oldtime for 5000 iterations: 0.189058
newtime for 5000 iterations: 0.254402

The question is whether your case is enough common to compensate the slowdown of other cases.

Yest one disadvantage of your patch is increasing memory consumption (this can be partly compensated by adding '_index_cache' to slots).

Have you considered the option of using Python 3? In Python 3 your example is much faster even without your patch (but still has quadratic complexity).

Python 2.7:
oldtime for 5000 iterations: 68.485284
newtime for 5000 iterations: 0.237943

Python 3.6:
oldtime for 5000 iterations: 0.695023
newtime for 5000 iterations: 0.212854

And the best option is using ElementTree. It accepts an index instead of a subelement for insertion.

$ ./python etree_example.py
Python 2.7:
time for 5000 iterations: 0.037805

Python 3.6:
time for 5000 iterations: 0.015566
msg268731 - (view) Author: Robert Haschke (Robert Haschke) * Date: 2016-06-17 16:07
Indeed there is a small slow down for insertion at the beginning.
However, this is simply due to the extra function _index() and thus linear in the number of insertion operations.

My patch essentially boosts insertions before /any fixed/ node.
If this reference node changes between insertions (as in your "before first" example), there is no gain anymore.

Of course, this optimization comes at the cost of an additional integer per node. There is no free lunch!

I know, that there are other parsers (e.g. etree) available. However
changing my existing code base from minidom to etree will be a heavy change, which isn't easily accepted as well.

I think, my minidom patch is a clean and simple fix to a common performance issue. As it mostly effects 2.7, it should primarily go there ;-)
msg268736 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2016-06-17 19:08
This slow down is not such small -- up to 25% for every insertBefore(). If most calls of insertBefore() are not with the same refChild, the benefit from the optimization of one special case can be dwarfed. Try to minimize the overhead of the optimization. If you succeed the chances of acceptance of the patch will increase.

I think that the availability of alternatives (upgrading to Python 3 or using ElementTree) plays against the acception of this optimization. Since it looks more as new feature to me, you have to convince the maintainer of 2.7 to take the patch in 2.7.
msg268741 - (view) Author: Robert Haschke (Robert Haschke) * Date: 2016-06-17 20:13
I don't see how to further minimize the checks - all of them are required. I think, the most common uses cases to create a document are appendChild(), which is not affected, and insertBefore() using the same refChild for a while. In that case, the patch gives a tremendous speedup.

If you as maintainers don't want to share this improvement with the community, it's your choice and I will be fine with that.
msg268767 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2016-06-18 06:41
There are different tricks that allow to minimize an overhead. Here is tuned patch.

But I still not sure that this special case is worth to be optimized.
msg268815 - (view) Author: Robert Haschke (Robert Haschke) * Date: 2016-06-18 15:21
Thank you very much for further improving the code. As I understand it, the trick is to use temporary variables to minimize access time. Learned something new.

I adapted your patch to python 2.7 again. Now, in python3, the new code is even faster than the old one (sometimes) for front insertions:

36 time for 10000 insertions at front: 0.117563
opt36 time for 10000 insertions at front: 0.116014

36 time for 10000 insertions at front: 0.114282
opt36 time for 10000 insertions at front: 0.116710

old time for 5000 insertions at front: 0.044055
new time for 5000 insertions at front: 0.075433
opt27 time for 5000 insertions at front: 0.052135

old time for 5000 insertions at back: 15.241450
new time for 5000 insertions at back: 0.071004
opt27 time for 5000 insertions at back: 0.046850

I hope you can consider, the patch for python 2.7. There the performance gain is most significant.
History
Date User Action Args
2016-06-18 15:21:46Robert Haschkesetmessages: + msg268815
2016-06-18 06:41:49serhiy.storchakasetfiles: + minidom.insertBefore2.patch

messages: + msg268767
2016-06-17 20:13:15Robert Haschkesetmessages: + msg268741
2016-06-17 19:08:58serhiy.storchakasetnosy: + benjamin.peterson
messages: + msg268736
2016-06-17 16:07:17Robert Haschkesetmessages: + msg268731
2016-06-17 14:39:42serhiy.storchakasetfiles: + etree_example.py
2016-06-17 14:39:06serhiy.storchakasetfiles: + minidom_example2.py

messages: + msg268726
2016-06-17 12:45:53Robert Haschkesetfiles: + minidom_example.py

messages: + msg268722
2016-06-17 06:19:42serhiy.storchakasetassignee: serhiy.storchaka
stage: patch review
messages: + msg268710
versions: + Python 3.6, - Python 2.7
2016-06-16 15:20:04berker.peksagsetnosy: + serhiy.storchaka
2016-06-16 14:52:52Robert Haschkesetfiles: + minidom.insertBefore.patch

messages: + msg268671
2016-06-16 14:01:21berker.peksagsetnosy: + berker.peksag
messages: + msg268669
2016-06-16 13:09:59guihomesetmessages: + msg268664
2015-11-05 19:20:56guihomesetnosy: + guihome
messages: + msg254134
2015-06-10 13:29:16Robert Haschkecreate