Repository: falconry/falcon

Issue:
Low performance in req._parse_form_urlencoded()
It's really slow when invoking req._parse_form_urlencoded() if the form body is huge. 
And after digging deeper, I found it was caused by the function named decode(encoded_uri, unquote_plus=True) defined in falcon/util/uri.py. The root cause is the low performance of list concatenation. 
A little refactor can improve performance greatly.
The code before:
```python
def decode(encoded_uri, unquote_plus=True):
    """Decodes percent-encoded characters in a URI or query string.
    This function models the behavior of `urllib.parse.unquote_plus`,
    albeit in a faster, more straightforward manner.
    Args:
        encoded_uri (str): An encoded URI (full or partial).
    Keyword Arguments:
        unquote_plus (bool): Set to ``False`` to retain any plus ('+')
            characters in the given string, rather than converting them to
            spaces (default ``True``). Typically you should set this
            to ``False`` when decoding any part of a URI other than the
            query string.
    Returns:
        str: A decoded URL. If the URL contains escaped non-ASCII
        characters, UTF-8 is assumed per RFC 3986.
    """

    decoded_uri = encoded_uri

    # PERF(kgriffs): Don't take the time to instantiate a new
    # string unless we have to.
    if '+' in decoded_uri and unquote_plus:
        decoded_uri = decoded_uri.replace('+', ' ')

    # Short-circuit if we can
    if '%' not in decoded_uri:
        return decoded_uri

    # NOTE(kgriffs): Clients should never submit a URI that has
    # unescaped non-ASCII chars in them, but just in case they
    # do, let's encode into a non-lossy format.
    decoded_uri = decoded_uri.encode('utf-8')

    # PERF(kgriffs): This was found to be faster than using
    # a regex sub call or list comprehension with a join.
    tokens = decoded_uri.split(b'%')
    decoded_uri = tokens[0]
    for token in tokens[1:]:
        token_partial = token[:2]
        try:
            decoded_uri += _HEX_TO_BYTE[token_partial] + token[2:]
        except KeyError:
            # malformed percentage like "x=%" or "y=%+"
            decoded_uri += b'%' + token

    # Convert back to str
    return decoded_uri.decode('utf-8', 'replace')
```

The code optimized:
```python
import io
def decode(encoded_uri, unquote_plus=True):
    """Decodes percent-encoded characters in a URI or query string.
    This function models the behavior of `urllib.parse.unquote_plus`,
    albeit in a faster, more straightforward manner.
    Args:
        encoded_uri (str): An encoded URI (full or partial).
    Keyword Arguments:
        unquote_plus (bool): Set to ``False`` to retain any plus ('+')
            characters in the given string, rather than converting them to
            spaces (default ``True``). Typically you should set this
            to ``False`` when decoding any part of a URI other than the
            query string.
    Returns:
        str: A decoded URL. If the URL contains escaped non-ASCII
        characters, UTF-8 is assumed per RFC 3986.
    """

    decoded_uri = encoded_uri

    # PERF(kgriffs): Don't take the time to instantiate a new
    # string unless we have to.
    if '+' in decoded_uri and unquote_plus:
        decoded_uri = decoded_uri.replace('+', ' ')

    # Short-circuit if we can
    if '%' not in decoded_uri:
        return decoded_uri

    # NOTE(kgriffs): Clients should never submit a URI that has
    # unescaped non-ASCII chars in them, but just in case they
    # do, let's encode into a non-lossy format.
    decoded_uri = decoded_uri.encode('utf-8')

    # PERF(kgriffs): This was found to be faster than using
    # a regex sub call or list comprehension with a join.
    tokens = decoded_uri.split(b'%')
    bytes = io.BytesIO()
    bytes.write(tokens[0])
    # decoded_uri = tokens[0]
    for token in tokens[1:]:
        token_partial = token[:2]
        try:
            bytes.write(_HEX_TO_BYTE[token_partial])
            bytes.write(token[2:])
            # decoded_uri += _HEX_TO_BYTE[token_partial] + token[2:]
        except KeyError:
            # malformed percentage like "x=%" or "y=%+"
            # decoded_uri += b'%' + token
            bytes.write(b'%')
            bytes.write(token)

    # Convert back to str
    # return decoded_uri.decode('utf-8', 'replace')
    return bytes.getvalue().decode('utf-8', 'replace')
```
And the time costs before optimizing is
python3.7 test.py 
2019-10-27 23:25:38,030 urllib3.connectionpool: DEBUG    Starting new HTTP connection (1): 127.0.0.1:8080
2019-10-27 23:26:04,819 urllib3.connectionpool: DEBUG    http://127.0.0.1:8080 "POST /api/import/postdata/async HTTP/1.1" 200 146
2019-10-27 23:26:04,820 __main__    : DEBUG    post data return: {"status":"ok","error_msg":"","successRecords":[],"failedRecords":[],"totalSuccessRecords":500,"totalFailedRecords":0,"timeElapsed":26.7830269337}
2019-10-27 23:26:04,821 __main__    : DEBUG    time elapsed: 27.266945600509644
After optimizing is:
python3.7 test.py 
2019-10-27 23:54:09,490 urllib3.connectionpool: DEBUG    Starting new HTTP connection (1): 127.0.0.1:8080
2019-10-27 23:54:09,791 urllib3.connectionpool: DEBUG    http://127.0.0.1:8080 "POST /api/import/postdata/async HTTP/1.1" 200 145
2019-10-27 23:54:09,794 __main__    : DEBUG    post data return: {"status":"ok","error_msg":"","successRecords":[],"failedRecords":[],"totalSuccessRecords":500,"totalFailedRecords":0,"timeElapsed":0.2936162949}
2019-10-27 23:54:09,794 __main__    : DEBUG    time elapsed: 0.862856388092041

As you can see, there is a great improvement


Discussion:
codecov[bot]: # [Codecov](https://codecov.io/gh/falconry/falcon/pull/1734?src=pr&el=h1) Report
> Merging [#1734](https://codecov.io/gh/falconry/falcon/pull/1734?src=pr&el=desc) into [master](https://codecov.io/gh/falconry/falcon/commit/0fc91cbf028779cf0f7a8761dded149683429adb&el=desc) will **decrease** coverage by `0.14%`.
> The diff coverage is `100.00%`.

[![Impacted file tree graph](https://codecov.io/gh/falconry/falcon/pull/1734/graphs/tree.svg?width=650&height=150&src=pr&token=zOtkfNQ3h6)](https://codecov.io/gh/falconry/falcon/pull/1734?src=pr&el=tree)

```diff
@@             Coverage Diff             @@
##            master    #1734      +/-   ##
===========================================
- Coverage   100.00%   99.85%   -0.15%     
===========================================
  Files           55       55              
  Lines         4967     4988      +21     
  Branches       804      808       +4     
===========================================
+ Hits          4967     4981      +14     
- Misses           0        6       +6     
- Partials         0        1       +1     
```


| [Impacted Files](https://codecov.io/gh/falconry/falcon/pull/1734?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [falcon/util/uri.py](https://codecov.io/gh/falconry/falcon/pull/1734/diff?src=pr&el=tree#diff-ZmFsY29uL3V0aWwvdXJpLnB5) | `100.00% <100.00%> (ø)` | |
| [falcon/asgi/\_\_init\_\_.py](https://codecov.io/gh/falconry/falcon/pull/1734/diff?src=pr&el=tree#diff-ZmFsY29uL2FzZ2kvX19pbml0X18ucHk=) | `77.77% <0.00%> (-22.23%)` | :arrow_down: |
| [falcon/util/misc.py](https://codecov.io/gh/falconry/falcon/pull/1734/diff?src=pr&el=tree#diff-ZmFsY29uL3V0aWwvbWlzYy5weQ==) | `96.77% <0.00%> (-3.23%)` | :arrow_down: |
| [falcon/util/reader.py](https://codecov.io/gh/falconry/falcon/pull/1734/diff?src=pr&el=tree#diff-ZmFsY29uL3V0aWwvcmVhZGVyLnB5) | `100.00% <0.00%> (ø)` | |
| [falcon/media/multipart.py](https://codecov.io/gh/falconry/falcon/pull/1734/diff?src=pr&el=tree#diff-ZmFsY29uL21lZGlhL211bHRpcGFydC5weQ==) | `100.00% <0.00%> (ø)` | |
| [falcon/request\_helpers.py](https://codecov.io/gh/falconry/falcon/pull/1734/diff?src=pr&el=tree#diff-ZmFsY29uL3JlcXVlc3RfaGVscGVycy5weQ==) | `100.00% <0.00%> (ø)` | |

------

[Continue to review full report at Codecov](https://codecov.io/gh/falconry/falcon/pull/1734?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/falconry/falcon/pull/1734?src=pr&el=footer). Last update [0fc91cb...33d78a2](https://codecov.io/gh/falconry/falcon/pull/1734?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).


Patch:
diff --git a/docs/_newsfragments/1594.bugfix.rst b/docs/_newsfragments/1594.bugfix.rst
new file mode 100644
index 0000000..814c057
--- /dev/null
+++ b/docs/_newsfragments/1594.bugfix.rst
@@ -0,0 +1,3 @@
+:meth:`falcon.uri.decode` and :meth:`falcon.uri.parse_query_string` no longer
+explode quadratically for a large number of percent-encoded characters. The
+time complexity of these utility functions is now always close to *O*(*n*).
diff --git a/falcon/util/uri.py b/falcon/util/uri.py
index 9af38b6..2ff296c 100644
--- a/falcon/util/uri.py
+++ b/falcon/util/uri.py
@@ -24,6 +24,8 @@ in the `falcon` module, and so must be explicitly imported::
 
 """
 
+import platform
+
 try:
     from falcon.cyutil.uri import (
         decode as _cy_decode,
@@ -51,6 +53,8 @@ _HEX_TO_BYTE = dict(((a + b).encode(), bytes([int(a + b, 16)]))
                     for a in _HEX_DIGITS
                     for b in _HEX_DIGITS)
 
+_PYPY = platform.python_implementation() == 'PyPy'
+
 
 def _create_char_encoder(allowed_chars):
 
@@ -168,6 +172,52 @@ Returns:
 """
 
 
+def _join_tokens_bytearray(tokens):
+    decoded_uri = bytearray(tokens[0])
+    for token in tokens[1:]:
+        token_partial = token[:2]
+        try:
+            decoded_uri += _HEX_TO_BYTE[token_partial] + token[2:]
+        except KeyError:
+            # malformed percentage like "x=%" or "y=%+"
+            decoded_uri += b'%' + token
+
+    # Convert back to str
+    return decoded_uri.decode('utf-8', 'replace')
+
+
+def _join_tokens_list(tokens):
+    decoded = tokens[:1]
+    # PERF(vytas): Do not copy list: a simple bool flag is fastest on PyPy JIT.
+    skip = True
+    for token in tokens:
+        if skip:
+            skip = False
+            continue
+
+        token_partial = token[:2]
+        try:
+            decoded.append(_HEX_TO_BYTE[token_partial] + token[2:])
+        except KeyError:
+            # malformed percentage like "x=%" or "y=%+"
+            decoded.append(b'%' + token)
+
+    # Convert back to str
+    return b''.join(decoded).decode('utf-8', 'replace')
+
+
+# PERF(vytas): The best method to join many byte strings depends on the Python
+#   implementation and many other factors such as the total string length,
+#   and the number of items to join.
+# Considering that CPython users are likely to choose the Cython implementation
+#   of decode anyway, we pick one best allrounder per platform:
+#   * On pure CPython, bytearray += often comes on top, also with the added
+#     benefit of being able to decode() off it directly.
+#   * On PyPy, b''.join(list) is the recommended approach, although it may
+#     narrowly lose to BytesIO on the extreme end.
+_join_tokens = _join_tokens_list if _PYPY else _join_tokens_bytearray
+
+
 def decode(encoded_uri, unquote_plus=True):
     """Decodes percent-encoded characters in a URI or query string.
 
@@ -209,17 +259,23 @@ def decode(encoded_uri, unquote_plus=True):
     # PERF(kgriffs): This was found to be faster than using
     # a regex sub call or list comprehension with a join.
     tokens = decoded_uri.split(b'%')
-    decoded_uri = tokens[0]
-    for token in tokens[1:]:
-        token_partial = token[:2]
-        try:
-            decoded_uri += _HEX_TO_BYTE[token_partial] + token[2:]
-        except KeyError:
-            # malformed percentage like "x=%" or "y=%+"
-            decoded_uri += b'%' + token
-
-    # Convert back to str
-    return decoded_uri.decode('utf-8', 'replace')
+    # PERF(vytas): Just use in-place add for a low number of items:
+    if len(tokens) < 8:
+        decoded_uri = tokens[0]
+        for token in tokens[1:]:
+            token_partial = token[:2]
+            try:
+                decoded_uri += _HEX_TO_BYTE[token_partial] + token[2:]
+            except KeyError:
+                # malformed percentage like "x=%" or "y=%+"
+                decoded_uri += b'%' + token
+
+        # Convert back to str
+        return decoded_uri.decode('utf-8', 'replace')
+
+    # NOTE(vytas): Decode percent-encoded bytestring fragments and join them
+    # back to a string using the platform-dependent method.
+    return _join_tokens(tokens)
 
 
 def parse_query_string(query_string, keep_blank=False, csv=True):


Test patch:
diff --git a/tests/test_utils.py b/tests/test_utils.py
index af300ad..8c5d430 100644
--- a/tests/test_utils.py
+++ b/tests/test_utils.py
@@ -31,6 +31,15 @@ def _arbitrary_uris(count, length):
     )
 
 
+@pytest.fixture(params=['bytearray', 'join_list'])
+def decode_approach(request, monkeypatch):
+    method = uri._join_tokens_list
+    if request.param == 'bytearray':
+        method = uri._join_tokens_bytearray
+    monkeypatch.setattr(uri, '_join_tokens', method)
+    return method
+
+
 class TestFalconUtils:
 
     def setup_method(self, method):
@@ -196,7 +205,7 @@ class TestFalconUtils:
         assert uri.encode_value('ab/cd') == 'ab%2Fcd'
         assert uri.encode_value('ab+cd=42,9') == 'ab%2Bcd%3D42%2C9'
 
-    def test_uri_decode(self):
+    def test_uri_decode(self, decode_approach):
         assert uri.decode('abcd') == 'abcd'
         assert uri.decode('ab%20cd') == 'ab cd'
 
@@ -210,16 +219,24 @@ class TestFalconUtils:
             'http://example.com?x=ab%2Bcd%3D42%2C9'
         ) == 'http://example.com?x=ab+cd=42,9'
 
+    @pytest.mark.parametrize('encoded,expected', [
+        ('ab%2Gcd', 'ab%2Gcd'),
+        ('ab%2Fcd: 100% coverage', 'ab/cd: 100% coverage'),
+        ('%s' * 100, '%s' * 100),
+    ])
+    def test_uri_decode_bad_coding(self, encoded, expected, decode_approach):
+        assert uri.decode(encoded) == expected
+
     @pytest.mark.parametrize('encoded,expected', [
         ('+%80', ' �'),
         ('+++%FF+++', '   �   '),  # impossible byte
         ('%fc%83%bf%bf%bf%bf', '������'),  # overlong sequence
         ('%ed%ae%80%ed%b0%80', '������'),  # paired UTF-16 surrogates
     ])
-    def test_uri_decode_replace_bad_unicode(self, encoded, expected):
+    def test_uri_decode_bad_unicode(self, encoded, expected, decode_approach):
         assert uri.decode(encoded) == expected
 
-    def test_uri_decode_unquote_plus(self):
+    def test_uri_decode_unquote_plus(self, decode_approach):
         assert uri.decode('/disk/lost+found/fd0') == '/disk/lost found/fd0'
         assert uri.decode('/disk/lost+found/fd0', unquote_plus=True) == (
             '/disk/lost found/fd0')