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