Opened 17 years ago

Closed 17 years ago

#4566 closed (fixed)

URL reverse() function has something like O(n^2) behaviour. Could be better.

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

Description

Two improvements that we should implement in URL resolving:

  1. Both reverse() and resolve() construct a RegexURLResolver instance every time they are called. Since that instance only varies based on the value of urlconf, we can have a module-level cache that stores the instance using urlconf as the key and only creates it when the right key doesn't exist. That saves one scan through the list of URL patterns each time, on average.
  2. Reverse resolving does a linear scan through the list of patterns looking for a name to match. Since these names are known in advance, we can build up a hash table mapping view function names and url names to patterns, turning the linear scan into an O(1) lookup.

Attachments (3)

urlresolvers.py (10.8 KB ) - added by anonymous 17 years ago.
urlresolvers.py with described speedups
reverse-speedup.diff (3.9 KB ) - added by smoo 17 years ago.
patch with above changes
reverse-speedup2.diff (4.4 KB ) - added by smoo 17 years ago.
patch with above changes + cached callback lookup (reduces inititial overhead)

Download all attachments as: .zip

Change History (10)

comment:1 by Malcolm Tredinnick, 17 years ago

Triage Stage: UnreviewedAccepted

comment:2 by Chris Beaven, 17 years ago

Keywords: performance added

by anonymous, 17 years ago

Attachment: urlresolvers.py added

urlresolvers.py with described speedups

comment:3 by smoo, 17 years ago

I don't know the proceedure for this, but I attached the changed urlresolvers.py with both optimizations described above. I also added module level caching of the view function resolution, as this was taking ~20ms on my machine.
With these changes, the cost of reverse() appears to become negligable (at least for me).

comment:4 by Malcolm Tredinnick, 17 years ago

Thanks for doing this. Could you please run "svn diff > resolvers.diff" (choose your own filename, of course) and just upload the patch?

That way we can easily review what has changed and the patch will still apply if other changes are made to this file in the interim.

comment:5 by Malcolm Tredinnick, 17 years ago

Oh, also... feel free to add a change to AUTHORS to include your name if you wish. Just include that change in the same patch (run "svn diff" from the top-level directory and it will pick up all the changes).

by smoo, 17 years ago

Attachment: reverse-speedup.diff added

patch with above changes

comment:6 by Simon G. <dev@…>, 17 years ago

Has patch: set
Triage Stage: AcceptedReady for checkin

by smoo, 17 years ago

Attachment: reverse-speedup2.diff added

patch with above changes + cached callback lookup (reduces inititial overhead)

comment:7 by Malcolm Tredinnick, 17 years ago

Resolution: fixed
Status: newclosed

(In [5516]) Fixed #4566 -- Added caching speed-ups to reverse URL matching. Based on a
patch from smoo.master@….

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