Opened 5 years ago

Closed 5 years ago

Last modified 5 years ago

#12632 closed (fixed)

Creation of SortedDict's has non-linear performance

Reported by: Alex Owned by: Alex
Component: Core (Other) Version: master
Severity: Keywords:
Cc: Triage Stage: Ready for checkin
Has patch: yes Needs documentation: no
Needs tests: no Patch needs improvement: no
Easy pickings: UI/UX:

Description

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.

Attachments (1)

sorted-dict.diff (638 bytes) - added by Alex 5 years ago.
After benchmarking this is demonstrated to be the most efficient approach, for both large and small N.

Download all attachments as: .zip

Change History (6)

Changed 5 years ago by Alex

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

comment:1 Changed 5 years ago by Alex

  • Has patch set
  • Needs documentation unset
  • Needs tests unset
  • Patch needs improvement unset
  • Triage Stage changed from Unreviewed to Accepted

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

comment:2 Changed 5 years ago by Alex

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.

comment:3 Changed 5 years ago by mtredinnick

  • Component changed from Uncategorized to Core framework
  • Triage Stage changed from Accepted to Ready for checkin

comment:4 Changed 5 years ago by jbronn

  • Resolution set to fixed
  • Status changed from new to closed

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

comment:5 Changed 5 years ago by jbronn

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

Backport of r13742 from trunk.

Note: See TracTickets for help on using tickets.
Back to Top