This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Author serhiy.storchaka
Recipients Robert Haschke, berker.peksag, guihome, serhiy.storchaka
Date 2016-06-17.14:39:06
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <>
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 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
Python 2.7:
time for 5000 iterations: 0.037805

Python 3.6:
time for 5000 iterations: 0.015566
Date User Action Args
2016-06-17 14:39:06serhiy.storchakasetrecipients: + serhiy.storchaka, berker.peksag, Robert Haschke, guihome
2016-06-17 14:39:06serhiy.storchakasetmessageid: <>
2016-06-17 14:39:06serhiy.storchakalinkissue24424 messages
2016-06-17 14:39:06serhiy.storchakacreate