[issue24424] xml.dom.minidom: performance issue with Node.insertBefore()

Robert Haschke added the comment: 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

[issue24424] xml.dom.minidom: performance issue with Node.insertBefore()

Serhiy Storchaka added the comment: 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. -- Added file: http://bugs.python.org/file43445/minidom.insertBefore2.patch

[issue24424] xml.dom.minidom: performance issue with Node.insertBefore()

Robert Haschke added the comment: 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

[issue24424] xml.dom.minidom: performance issue with Node.insertBefore()

Serhiy Storchaka added the comment: 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.

[issue24424] xml.dom.minidom: performance issue with Node.insertBefore()

Robert Haschke added the comment: 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

[issue24424] xml.dom.minidom: performance issue with Node.insertBefore()

Changes by Serhiy Storchaka : Added file: http://bugs.python.org/file43439/etree_example.py ___ Python tracker ___

[issue24424] xml.dom.minidom: performance issue with Node.insertBefore()

Serhiy Storchaka added the comment: 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

[issue24424] xml.dom.minidom: performance issue with Node.insertBefore()

Robert Haschke added the comment: 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

[issue24424] xml.dom.minidom: performance issue with Node.insertBefore()

Serhiy Storchaka added the comment: 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. -- assignee: -> serhiy.storchaka

[issue24424] xml.dom.minidom: performance issue with Node.insertBefore()

Changes by Berker Peksag : -- nosy: +serhiy.storchaka ___ Python tracker ___ ___

[issue24424] xml.dom.minidom: performance issue with Node.insertBefore()

Robert Haschke added the comment: Uploaded a "hg diff" against the recent 2.7 branch of the source repo. -- Added file: http://bugs.python.org/file43414/minidom.insertBefore.patch ___ Python tracker

[issue24424] xml.dom.minidom: performance issue with Node.insertBefore()

Berker Peksag added the comment: Please attach the patch in unified diff format. See https://docs.python.org/devguide/patch.html for details. -- nosy: +berker.peksag ___ Python tracker

[issue24424] xml.dom.minidom: performance issue with Node.insertBefore()

GuiHome added the comment: kindly ping -- ___ Python tracker ___ ___ Python-bugs-list mailing list

[issue24424] xml.dom.minidom: performance issue with Node.insertBefore()

GuiHome added the comment: 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 -- nosy: +guihome ___ Python tracker

[issue24424] xml.dom.minidom: performance issue with Node.insertBefore()

New submission from Robert Haschke: 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