Code

Opened 4 years ago

Closed 4 years ago

Last modified 4 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 4 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 4 years ago by Alex

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

comment:1 Changed 4 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 4 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 4 years ago by mtredinnick

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

comment:4 Changed 4 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 4 years ago by jbronn

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

Backport of r13742 from trunk.

Add Comment

Modify Ticket

Change Properties
<Author field>
Action
as closed
as The resolution will be set. Next status will be 'closed'
The resolution will be deleted. Next status will be 'new'
Author


E-mail address and user name can be saved in the Preferences.

 
Note: See TracTickets for help on using tickets.