'urllib.quote' delegates to '_fast_quote' for the common
case that the user has passed no 'safe' argument.  However,
'_fast_quote' isn't really very fast, especially for
the case that
 it doesn't need to quote anything.

Zope (and presumably other web frameworks) can end up
calling 'quote' dozens, hundreds, even thousands of times
to render a page, which makes this a potentially big win
for them.

I will attach a speed test script which demonstrates the
speed penalty, along with a patch which implements the
speedup.

Logged In: YES 
user_id=2772

Tested on Python 2.4.0.  The patch fails on the first chunk
because the list of imports don't match.

The urllib_fast_quote_speed_test.py doesn't run once urllib
has been patched.

I reverted the patch to urllib.py and re-ran.  I got
"faster" values from 0.758 to 0.964.

Logged In: YES 
user_id=127625

I'm attaching a patch against 2.4's version

Logged In: YES 
user_id=127625

Note that the speed test script shows equivalent speedups for
both 2.3 and 2.4, ranging from 90% (for the empty string) down
to 73% (for a string with a single character).  The more
"normal"
cases range from 82% to 89% speedups.

Logged In: YES 
user_id=80475

Checked in a speed-up for Py2.5.
See Lib/urllib.py 1.169.

The check-in provides fast-quoting for all cases (not just
for the default safe argument).  Even the fast path is
quicker.  With translation for both safe and unsafe
characters, it saves len(s) trips through the eval loop,
computes of non-safe replacements just once, and eliminates
the if-logic.  The new table is collision free and has no
failed lookups, so each lookup requires exactly one probe. 
One my machine, timings improved by a factor of two to three
depending on the length of input and number of escaped
characters.

The check-in also simplifies and speeds-up quote_plus() by
using str.replace() instead of a split

Leaving this SF report open because the OP's idea may
possibly provide further improvement -- the checkin itself
was done because it is a clear win over the existing version.

The OP's patch uses regexps to short-circuit when no changes
are needed.  Unless the regexp is cheap and short-circuits
often, the cost of testing will likely exceed the average
amount saved.

Determining whether the regexp is cheaper than the
checked-in version just requires a few timings.  But,
determining the short-circuit percentage requires collecting
statistics from real programs with real data.  For the idea
to be a winner, regexps have to be much faster than the
map/lookup/join step AND the short-circuit case must occur
frequently.

Am lowering the priority until a better patch is received
along with timings and statistical evidence demonstrating a
significant improvement.  Also, reclassifying as a Feature
Request because the existing code is functioning as
documented and passing tests.

This is what I found doing some timings:

For the short-circuit path, the regexp can make quote 10x as fast in
exceptional cases, even comparing to the faster version in trunk. The
average win for short-circuit seems to be twice as fast as the map in my
timings. This sounds good.

For the normal path, the overhead can make quote 50% slower. This IMHO
makes it unfit for quote replacement. Perhaps good for a cookbook recipe? 

Regarding the OP's use case, I believe either adding a string cache to
quote or flagging stored strings as "safe" or "must quote" would result
in a much greater impact on performance.

Attaching patch against trunk. Web framework developers should be
interested in testing this and could provide the use cases/data needed
for settling this issue.

If someone needs a faster quote(), it's probably easy to write an
insanely fast C version...

I'm uploading a saner version of the speed test which uses timeit's support for passing a callable as a statement:  it is much easier to
see what the test is actually doing.

On my machine, running against the release26-maint branch, my version runs anywhere from 67% to 85% faster on the cases where no quoting actually needs to be done.  In production use, where urlib.quote is used as a safety check, these cases far outweigh the cases which actually require quoting.

Tres, can you update your patch against SVN trunk?
Also, please do an unified diff, we are mostly used to this format.

Updated patch against the trunk attached.

Note that I prefer unidiff myself, but was following a bit of guidance that Guido (used to, anyway) prefer context diffs.

The updated speed test run against the stdlib with this patch shows only a 12% to 16% hit against my simpler version (which didn't handle cases where the 'safe' argument was not the default "/").

I reviewed the patch and the speed test attached. 
Well, yes, the patch does achieve a certain level of speed improvement but I also saw that in cases when the quoting is really required (special characters, the current stdlib is faster). 

The speed improvement proposed is really not a convincing enough reason to replace the code of the current quote. rhettinger's comment in this issue might taken as reference to work out if there are any statistical evidence (:)?) that if the frameworks use it, would they benefit.

Few more points.

- quote is a generic function, checking for empty string, returning it  and marking it speed improvement, really is not a improvement (practically the person using the quote can avoid it too and thereby increase the speed).

- Some framework might try this , like django or zope for e.g and see if its really a worthy case in using re to check for chars to be quoted and quote only those (and see if there is any improvement).

- Might provide this as an activestate recipe and see if there any takers (again for reasons of use-case)

It is correctly a low priority one, or it can just be rejected too.

BTW, there is a feature request on quote support unicode char with patch, when that is in place, I think this request may suffer further.

I can only reiterate that Zope apps can call 'urllib.quote' dozens,
hundreds, even thousands of times on a single request:  the
reason for the original bug report was that 'urllib.quote' was
showing up frequently on profiling output for such requests.
Short-circuiting the case for the empty string and the case that
the string being quoted actually contains only safe characters
together made 'urllib.quote' disappear from the profiler output.

Newer frameworks, such as 'repoze.bfg', avoid using
'urliib.quote' at all for just this reason.

I've tested a variant of the previous patch.
On my laptop, it gives good performance for simple cases, and the penalty for real-quoting case is very low.

I've tested a short-circuit for the unquote() function too.

Lets also see how this fares in py3k (where quote function takes an encoding ) and possibly push it in.
If there is any hesitation we can consult python-dev or wsgi groups where frameworks developers might review and voice concerns, if they have any.

New patch, using str.translate instead of regexp.
It is faster for normal cases (85% less time than stdlib quote), and the penalty for the real-quoting case is less than 5%.

It should apply to 3.x with some adaptation.

The speed test script did not work on 2.5 (because timeit.Timer does not accept a callable).
Fixed version, which benchmarks the str.translate(...) version.

Change the '_new_quote_setup' assignment to test other variants.

actually, there's a simpler implementation, using s.rstrip(always_safe + safe).

It is as fast as the previous one.

Updated script for benchmarks (on 2.x and 3.x).
Inspired by the "Tools/iobench" script.

It benchmarks various quote/unquote implementations on 2.x and 3.x.

On 2.7 the fastest implementation is something like:

    def quote(s):
        if not s or not s.rstrip(safe):
            return s
        return ''.join(map(safe_get, s))


On 3.2 the fastest implementation uses list comprehension:

    def quote_from_bytes(s):
        if not s:
            return ''
        if not s.rstrip(safe):
            return s.decode()
        return ''.join([quoter(c) for c in s])


Note: the regexp implementation is slower in both cases.

Proposed patches for quote and unquote on 2.7 and 3.2.

Committed in r81265 for 2.7.

On Mon, May 17, 2010 at 01:38:57PM +0000, Florent Xicluna wrote:
> Committed in r81265 for 2.7.

Thanks. That was interesting. Without resorting to any drastic changes like
use of regex, interesting speed-up seems to have been achieved by
using rsplit and map.

In py3k, I think its 'okay' to go for rsplit, defaultdict and map
which will be similar to py2k version. I saw that map vs list
comprehension did not have much differences.

Committed to 3.2 in r81271, after some additional tuning.

Btw, I kept list comprehension in 3.2, because it is faster for small strings (even if the gain is ~10%).

Why was this merged to 2.6 after 2.6.6rc1 without approval?

flox reverted in r83967 for 2.6.6.

As per discussion on python-dev, this bug should probably be reopened and the patch maybe reverted as relying on the refcounting hack is both dodgy and hurts other implementations, like PyPy.

Proposed patches not only get rid of the refcount hack, but make unquote() and unquote_to_bytes() even significant faster for large strings.

Applying this patch - I tried this hypothetical test.

$ ./python.exe -m timeit -s "import urllib.parse; x='a%20' * 100000"
"urllib.parse.unquote(x)"
10 loops, best of 3: 205 msec per loop

Without the patch, the above test will run for minutes!

This creates a significant difference for extremely long query
strings. For small strings the performance is negligible.

Serhiy: One question. Is there a need to have  -

+ append = res.append

And then use 'append'? res.append is easier for readability IMO.
Besides that I dont have any other comments. Maciej's comment could be
sought as he (correctly) brought up this issue.

I wrongly minutes. Here is actual data of execution speeds.  There is
magnitude of difference (almost 130x faster). Measured on  macbook pro
with 2 cores and 4 Gig mem.

Before Patch:

$ ./python.exe -m timeit -s "import urllib.parse; x='a%20' * 100000"
"urllib.parse.unquote(x)"
10 loops, best of 3: 26.8 sec per loop

After Patch:

$ ./python.exe -m timeit -s "import urllib.parse; x='a%20' * 100000"
"urllib.parse.unquote(x)"
10 loops, best of 3: 205 msec per loop

> Serhiy: One question. Is there a need to have  -
>
> + append = res.append
>
> And then use 'append'?

This speed up unquote_to_bytes by 15%.

> Serhiy Storchaka added the comment:
>>
>> + append = res.append
>>
>> And then use 'append'?
>
> This speed up unquote_to_bytes by 15%.

Thanks for the response. In fact, writing the whole _hextobyte
verbatim would further increase the speed, but that would be huge
dis-advantage in terms of space occupied by that dict in the code. I
am +1 with the patch, please go ahead with committing it.

Serhiy  - Is there any technical issue that is holding up this patch? (I dont see any). If nothing is holding up and you are busy, I shall go ahead with committing this one. /cc flox

New changeset 4927899bea8d by Serhiy Storchaka in branch '2.7':
Issue #1285086: Get rid of the refcounting hack and speed up urllib.unquote().
http://hg.python.org/cpython/rev/4927899bea8d

New changeset 3cb07925fcb9 by Serhiy Storchaka in branch '3.2':
Issue #1285086: Get rid of the refcounting hack and speed up
http://hg.python.org/cpython/rev/3cb07925fcb9

New changeset 209a9c2de9bd by Serhiy Storchaka in branch '3.3':
Issue #1285086: Get rid of the refcounting hack and speed up
http://hg.python.org/cpython/rev/209a9c2de9bd

New changeset 9367411a261e by Serhiy Storchaka in branch 'default':
Issue #1285086: Get rid of the refcounting hack and speed up
http://hg.python.org/cpython/rev/9367411a261e

Sorry, I perhaps missed your response, Senthil. Now committed and closed again.