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

[Malcolm Tredinnick]

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.

[anonymous]

urlresolvers.py with described speedups

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

[Malcolm Tredinnick]

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.

[Malcolm Tredinnick]

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

[smoo]

patch with above changes

[smoo]

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

[Malcolm Tredinnick]

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