Opened 8 years ago

Closed 8 years ago

#4566 closed (fixed)

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

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

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 8 years ago.
urlresolvers.py with described speedups
reverse-speedup.diff (3.9 KB) - added by smoo 8 years ago.
patch with above changes
reverse-speedup2.diff (4.4 KB) - added by smoo 8 years ago.
patch with above changes + cached callback lookup (reduces inititial overhead)

Download all attachments as: .zip

Change History (10)

comment:1 Changed 8 years ago by mtredinnick

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

comment:2 Changed 8 years ago by SmileyChris

  • Keywords performance added

Changed 8 years ago by anonymous

urlresolvers.py with described speedups

comment:3 Changed 8 years ago by smoo

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 Changed 8 years ago by mtredinnick

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 Changed 8 years ago by mtredinnick

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).

Changed 8 years ago by smoo

patch with above changes

comment:6 Changed 8 years ago by Simon G. <dev@…>

  • Has patch set
  • Triage Stage changed from Accepted to Ready for checkin

Changed 8 years ago by smoo

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

comment:7 Changed 8 years ago by mtredinnick

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

(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