Django

Code

Ticket #4566 (closed: fixed)

Opened 1 year ago

Last modified 1 year ago

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

Reported by: mtredinnick Assigned to: mtredinnick
Milestone: Component: Core framework
Version: SVN Keywords: performance
Cc: Triage Stage: Ready for checkin
Has patch: 1 Needs documentation: 0
Needs tests: 0 Patch needs improvement: 0

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

urlresolvers.py (10.8 kB) - added by anonymous on 06/14/07 19:50:31.
urlresolvers.py with described speedups
reverse-speedup.diff (3.9 kB) - added by smoo on 06/14/07 20:27:18.
patch with above changes
reverse-speedup2.diff (4.4 kB) - added by smoo on 06/15/07 12:02:49.
patch with above changes + cached callback lookup (reduces inititial overhead)

Change History

06/14/07 16:46:13 changed by mtredinnick

  • needs_better_patch changed.
  • stage changed from Unreviewed to Accepted.
  • needs_tests changed.
  • needs_docs changed.

06/14/07 17:16:38 changed by SmileyChris

  • keywords set to performance.

06/14/07 19:50:31 changed by anonymous

  • attachment urlresolvers.py added.

urlresolvers.py with described speedups

06/14/07 19:59:22 changed 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).

06/14/07 20:03:36 changed 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.

06/14/07 20:04:33 changed 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).

06/14/07 20:27:18 changed by smoo

  • attachment reverse-speedup.diff added.

patch with above changes

06/15/07 05:20:37 changed by Simon G. <dev@simon.net.nz>

  • has_patch set to 1.
  • stage changed from Accepted to Ready for checkin.

06/15/07 12:02:49 changed by smoo

  • attachment reverse-speedup2.diff added.

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

06/23/07 00:40:29 changed by mtredinnick

  • status changed from new to closed.
  • resolution set to fixed.

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

Add/Change #4566 (URL reverse() function has something like O(n^2) behaviour. Could be better.)




Change Properties
Action