Creation of SortedDict's has non-linear performance

[Alex Gaynor]

Specifically line 81 causes this: ​http://code.djangoproject.com/browser/django/trunk/django/utils/datastructures.py#L67, resulting in O(n2) performance. There are 2 solutions that I can see, 1) maintain an auxilliary set() containing names that were already inserted in init, alternatively just use the update() implementation here. A third possible option is to drop our own implementation of SortedDict and bundle the OrderedDict implementation from CPython 3.1/2.7.

[Alex Gaynor]

After benchmarking this is demonstrated to be the most efficient approach, for both large and small N.

[Alex Gaynor]

​http://paste.pocoo.org/show/166540/ is the script used for benchmarking.

[Alex Gaynor]

TestSortedDict0, 1: 0.00848913192749
TestSortedDict1, 1: 0.00947690010071
TestSortedDict2, 1: 0.0104730129242
================================
TestSortedDict0, 10: 0.0177478790283
TestSortedDict1, 10: 0.0197200775146
TestSortedDict2, 10: 0.0345978736877
================================
TestSortedDict0, 100: 0.23953294754
TestSortedDict1, 100: 0.0862579345703
TestSortedDict2, 100: 0.247628927231
================================
TestSortedDict0, 1000: 13.4069559574
TestSortedDict1, 1000: 0.643974065781
TestSortedDict2, 1000: 2.02105689049
================================

Are the results for those who don't want to run it themselves. 0 is the current implementation, 1 is the auxiliary set() implementation, and 2 is the pure python (no super()) approach.

[jbronn]

(In [13742]) Fixed #12632 -- Improved performance of SortedDict. Thanks, Alex Gaynor.

[jbronn]

(In [13743]) [1.2.X] Fixed #12632 -- Improved performance of SortedDict. Thanks, Alex Gaynor.

Backport of r13742 from trunk.