homepage

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!

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

kindly ping

Please attach the patch in unified diff format. See https://docs.python.org/devguide/patch.html for details.

Uploaded a "hg diff" against the recent 2.7 branch of the source repo.

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.

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.

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

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 ;-)

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.

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.

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.

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.