Repository: falconry/falcon

Issue:
Adding many routes to CompiledRouter is slow (takes O(n^2) time)
i have about 400 api route to add
falcon compiles method “find” each time and slower as the count grows
it slows down hug booting
does anyone else have same problem？
i made a patch to fix it，but not very elegent，
i wish there will be a better solution

<sub>Sent with <a href="http://githawk.com">GitHawk</a></sub>

Discussion:
CaselIT: I've added to the table the times with a very naive stand alone compile for every added route on a new router to check if the route it can actually compile
this is the check:
```py
        if kwargs.get("_check") is not True:
            temp = CompiledRouter()
            temp._options = self._options
            temp.add_route(uri_template, resource, _check=True, **kwargs)
```
CaselIT: I've had another look at the compile functions of the route and I think that safest way to ensure that every route can compile on its own is to have another instance of the router that we use for this standalone compile. Doing otherwise may have unintended side effects of the router instance, but I'm not very familiar with the compiled router so I may be missing an easier / cleaner solution.
I'm not sure if this should be configurable or not. I guess an option in the router options would not hurt

Regarding the implementation, I think the delayed compilation could be the default and `add_route` could have a new kwarg `compile` that when set compiles the router, retaining the current behavior.
This allows users to compile the router when they add the last route if he prefer to avoid the penalty on the first request.

@kgriffs @vytas7 what do you think?
codecov[bot]: # [Codecov](https://codecov.io/gh/falconry/falcon/pull/1665?src=pr&el=h1) Report
> Merging [#1665](https://codecov.io/gh/falconry/falcon/pull/1665?src=pr&el=desc) into [master](https://codecov.io/gh/falconry/falcon/commit/8e513adf88929b0389e266b10987be2900141c53?src=pr&el=desc) will **decrease** coverage by `0.03%`.
> The diff coverage is `94.73%`.

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

```diff
@@            Coverage Diff             @@
##           master    #1665      +/-   ##
==========================================
- Coverage     100%   99.96%   -0.04%     
==========================================
  Files          45       45              
  Lines        3134     3148      +14     
  Branches      482      485       +3     
==========================================
+ Hits         3134     3147      +13     
- Partials        0        1       +1
```


| [Impacted Files](https://codecov.io/gh/falconry/falcon/pull/1665?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [falcon/routing/compiled.py](https://codecov.io/gh/falconry/falcon/pull/1665/diff?src=pr&el=tree#diff-ZmFsY29uL3JvdXRpbmcvY29tcGlsZWQucHk=) | `99.71% <94.73%> (-0.29%)` | :arrow_down: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/falconry/falcon/pull/1665?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/1665?src=pr&el=footer). Last update [8e513ad...bd8c064](https://codecov.io/gh/falconry/falcon/pull/1665?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

CaselIT: @kgriffs @vytas7 This should be ready for review.
I'm not sure about the name of the option `verify_route_on_add`. I'm usually not very good at naming things. If you came up with a better name I would be happy to change it.

I've updated the inital post table 
kgriffs: > Regarding the implementation, I think the delayed compilation could be the default and `add_route` could have a new kwarg `compile` that when set compiles the router, retaining the current behavior.
> This allows users to compile the router when they add the last route if they prefer to avoid the penalty on the first request.

I'm cool with this approach. We just need the docs to mention the reason someone might use the param, as you outlined above.
CaselIT: I've added a lock to guard the router compile. While the compile itself may be thread safe, and python has the gil, this avoids wasting time compiling multiple times the router.

I've also update the documentation. 

I'm not sure if we should mention that the router is "lazy" here https://github.com/falconry/falcon/blob/0d419ef49f26a41a335b67d5eeeed29365c35308/docs/api/routing.rst#default-router
Something along the lines of 
```rst
By default the decision three is compiled only when the router receives the first request.
See :class:`.CompiledRouter` for more information on this
```
CaselIT: Moving here from the review comment.

I've had another look and I think we could avoid the standalone compilation step of every route, by trying to also instantiate the field converters in the `_validate_template_segment`. 
https://github.com/falconry/falcon/blob/c3e91875f1030c68d17efa27cf8df3d18f337761/falcon/routing/compiled.py#L282
This is the only check that is not currently performed by the `add_route` that is left to the compile step.

I think with this the implementation would be a lot cleaner, since there would be no need for the internal router instance, the new router options, etc
CaselIT: I've updated the `_validate_template_segment` function to also verify that a converter can be instantiated with the provided params
CaselIT: Thanks for the review, 
I've updated the documentation with the suggestions.

> I would suggest to mention the new compile keyword argument in App.add_route(...) docs,

I've added a short documentation there, linking to the more complete one on the router implementation 

CaselIT: I think that restarting the failed job should clear the failure

Patch:
diff --git a/docs/_newsfragments/1550.feature.rst b/docs/_newsfragments/1550.feature.rst
new file mode 100644
index 0000000..dfff571
--- /dev/null
+++ b/docs/_newsfragments/1550.feature.rst
@@ -0,0 +1,3 @@
+Change :class:`falcon.routing.CompiledRouter` to compile the routes
+only when the first request is routed. This can be changed by
+passing ``compile=True`` to :meth:`falcon.routing.CompiledRouter.add_route`.
diff --git a/docs/api/routing.rst b/docs/api/routing.rst
index ec39194..789a7d5 100644
--- a/docs/api/routing.rst
+++ b/docs/api/routing.rst
@@ -57,6 +57,8 @@ Default Router
 
 Falcon's default routing engine is based on a decision tree that is
 first compiled into Python code, and then evaluated by the runtime.
+By default, the decision tree is compiled only when the router handles
+the first request. See :class:`.CompiledRouter` for more details.
 
 The :meth:`falcon.App.add_route` and :meth:`falcon.asgi.App.add_route` methods
 are used to associate a URI template with a resource. Falcon then maps incoming
diff --git a/falcon/app.py b/falcon/app.py
index c99ccf9..cdd111c 100644
--- a/falcon/app.py
+++ b/falcon/app.py
@@ -470,6 +470,10 @@ class App:
                 Another class might use a suffixed responder to handle
                 a shortlink route in addition to the regular route for the
                 resource.
+            compile (bool): Optional flag that can be provided when using the default
+                :class:`.CompiledRouter` to compile the routing logic on this call,
+                since it will otherwise delay compilation until the first request
+                is routed. See :meth:`.CompiledRouter.add_route` for further details.
 
         Note:
             Any additional keyword arguments not defined above are passed
diff --git a/falcon/routing/compiled.py b/falcon/routing/compiled.py
index 0946368..b319884 100644
--- a/falcon/routing/compiled.py
+++ b/falcon/routing/compiled.py
@@ -19,6 +19,7 @@ from inspect import iscoroutinefunction
 import keyword
 import re
 import textwrap
+from threading import Lock
 
 from falcon.routing import converters
 from falcon.routing.util import map_http_methods, set_default_responders
@@ -51,6 +52,21 @@ class CompiledRouter:
     tree for each look-up, it generates inlined, bespoke Python code to
     perform the search, then compiles that code. This makes the route
     processing quite fast.
+
+    The compilation process is delayed until the first use of the router (on the
+    first routed request) to reduce the time it takes to start the application.
+    This may noticeably delay the first response of the application when a large
+    number of routes have been added. When adding the last route
+    to the application a `compile` flag may be provided to force the router
+    to compile immediately, thus avoiding any delay for the first response.
+
+    Note:
+        When using a multi-threaded web server to host the application, it is
+        possible that multiple requests may be routed at the same time upon
+        startup. Therefore, the framework employs a lock to ensure that only a
+        single compilation of the decision tree is performed.
+
+    See also :meth:`.CompiledRouter.add_route`
     """
 
     __slots__ = (
@@ -63,6 +79,7 @@ class CompiledRouter:
         '_patterns',
         '_return_values',
         '_roots',
+        '_compile_lock',
     )
 
     def __init__(self):
@@ -80,9 +97,10 @@ class CompiledRouter:
         self._return_values = None
         self._roots = []
 
-        # NOTE(kgriffs): Call _compile() last since it depends on
-        # the variables above.
-        self._find = self._compile()
+        # NOTE(caselit): set _find to the delayed compile method to ensure that
+        # compile is called when the router is first used
+        self._find = self._compile_and_find
+        self._compile_lock = Lock()
 
     @property
     def options(self):
@@ -90,6 +108,10 @@ class CompiledRouter:
 
     @property
     def finder_src(self):
+        # NOTE(caselit): ensure that the router is actually compiled before
+        # returning the finder source, since the current value may be out of
+        # date
+        self.find('/')
         return self._finder_src
 
     def map_http_methods(self, resource, **kwargs):
@@ -142,6 +164,20 @@ class CompiledRouter:
                 Another class might use a suffixed responder to handle
                 a shortlink route in addition to the regular route for the
                 resource.
+            compile (bool): Optional flag that can be used to compile the
+                routing logic on this call. By default, :class:`.CompiledRouter`
+                delays compilation until the first request is routed. This may
+                introduce a noticeable amount of latency when handling the first
+                request, especially when the application implements a large
+                number of routes. Setting `compile` to ``True`` when the last
+                route is added ensures that the first request will not be
+                delayed in this case (defaults to ``False``).
+
+                Note:
+                    Always setting this flag to ``True`` may slow down the
+                    addition of new routes when hundreds of them are added at
+                    once. It is advisable to only set this flag to ``True`` when
+                    adding the final route.
         """
 
         # NOTE(kgriffs): falcon.asgi.App injects this private kwarg; it is
@@ -206,7 +242,12 @@ class CompiledRouter:
                 insert(new_node.children, path_index + 1)
 
         insert(self._roots)
-        self._find = self._compile()
+        # NOTE(caselit): when compile is True run the actual compile step, otherwise reset the
+        # _find, so that _compile will be called on the next find use
+        if kwargs.get('compile', False):
+            self._find = self._compile()
+        else:
+            self._find = self._compile_and_find
 
     def find(self, uri, req=None):
         """Search for a route that matches the given partial URI.
@@ -317,9 +358,15 @@ class CompiledRouter:
                 raise ValueError(msg)
 
             name = field.group('cname')
-            if name and name not in self._converter_map:
-                msg = 'Unknown converter: "{0}"'.format(name)
-                raise ValueError(msg)
+            if name:
+                if name not in self._converter_map:
+                    msg = 'Unknown converter: "{0}"'.format(name)
+                    raise ValueError(msg)
+                try:
+                    self._instantiate_converter(self._converter_map[name], field.group('argstr'))
+                except Exception as e:
+                    msg = 'Cannot instantiate converter "{}"'.format(name)
+                    raise ValueError(msg) from e
 
     def _generate_ast(self, nodes, parent, return_values, patterns, level=0, fast_return=True):
         """Generates a coarse AST for the router."""
@@ -531,6 +578,25 @@ class CompiledRouter:
         src = '{0}({1})'.format(klass.__name__, argstr)
         return eval(src, {klass.__name__: klass})
 
+    def _compile_and_find(self, path, _return_values, _patterns, _converters, params):
+        """Compile the router, sets the `_find` attribute and returns its result.
+
+        This method is set to the `_find` attribute to delay the compilation of the
+        router until it's used for the first time. Subsequent calls to `_find` will
+        be processed by the actual routing function.
+        This method must have the same signature as the function returned by the
+        :meth:`.CompiledRouter._compile`.
+        """
+        with self._compile_lock:
+            if self._find == self._compile_and_find:
+                # NOTE(caselit): replace the find with the result of the router compilation
+                self._find = self._compile()
+        # NOTE(caselit): return_values, patterns, converters are reset by the _compile
+        # method, so the updated ones must be used
+        return self._find(
+            path, self._return_values, self._patterns, self._converters, params
+        )
+
 
 class CompiledRouterNode:
     """Represents a single URI segment in a URI."""


Test patch:
diff --git a/tests/test_compiled_router.py b/tests/test_compiled_router.py
new file mode 100644
index 0000000..e141719
--- /dev/null
+++ b/tests/test_compiled_router.py
@@ -0,0 +1,116 @@
+from threading import Barrier, Thread
+from time import sleep
+from unittest.mock import MagicMock
+
+import pytest
+
+from falcon.routing import CompiledRouter
+
+
+def test_find_src(monkeypatch):
+    called = False
+    find = CompiledRouter.find
+
+    def mock(*args):
+        nonlocal called
+        called = True
+        find(*args)
+
+    monkeypatch.setattr(CompiledRouter, 'find', mock)
+    router = CompiledRouter()
+
+    assert router.finder_src is not None
+    assert called
+
+
+@pytest.fixture
+def patch_add_route(monkeypatch):
+    add_route = CompiledRouter.add_route
+    mock = MagicMock(side_effect=lambda *a, **k: add_route(router, *a, **k))
+    monkeypatch.setattr(CompiledRouter, 'add_route', mock)
+    router = CompiledRouter()
+    return mock, router
+
+
+@pytest.mark.parametrize(
+    'kwargs',
+    (
+        {},
+        {'compile': False},
+        {'compile': False, 'suffix': 'other'},
+        {'suffix': 'other'},
+    ),
+)
+def test_no_compile_kw(patch_add_route, kwargs):
+    mock, router = patch_add_route
+
+    res = MockResource()
+    router.add_route('/foo', res, **kwargs)
+
+    assert mock.call_count == 1
+    mock.assert_has_calls(((('/foo', res), kwargs), ))
+    assert router._find == router._compile_and_find
+
+
+def test_compile(patch_add_route):
+    mock, router = patch_add_route
+
+    res = MockResource()
+    router.add_route('/foo', res, compile=True)
+    assert mock.call_count == 1
+    assert router._find != router._compile_and_find
+
+
+def test_add_route_after_first_request():
+    router = CompiledRouter()
+
+    router.add_route('/foo', MockResource())
+    assert router.find('/foo') is not None
+    assert router._find != router._compile_and_find
+
+    router.add_route('/bar', MockResource(), suffix='other')
+    assert router._find == router._compile_and_find
+    assert router.find('/bar') is not None
+    assert router._find != router._compile_and_find
+
+
+def test_multithread_compile(monkeypatch):
+    def side_effect():
+        sleep(0.05)
+        return lambda *args: None
+
+    mock = MagicMock(side_effect=side_effect)
+    monkeypatch.setattr(CompiledRouter, '_compile', mock)
+
+    router = CompiledRouter()
+    mr = MockResource()
+
+    router.add_route('/foo', mr)
+
+    calls = 0
+    num_threads = 3
+    barrier = Barrier(num_threads)
+
+    def find():
+        nonlocal calls
+        barrier.wait()
+        assert router.find('/foo') is None
+        calls += 1
+
+    threads = [Thread(target=find) for i in range(num_threads)]
+    for t in threads:
+        t.start()
+
+    for t in threads:
+        t.join()
+
+    assert calls == 3
+    mock.assert_called_once_with()
+
+
+class MockResource:
+    def on_get(self, req, res):
+        pass
+
+    def on_get_other(self, req, res):
+        pass
diff --git a/tests/test_default_router.py b/tests/test_default_router.py
index 653ee91..13c357e 100644
--- a/tests/test_default_router.py
+++ b/tests/test_default_router.py
@@ -461,9 +461,11 @@ def test_converters_with_invalid_options(router, uri_template):
     # NOTE(kgriffs): Sanity-check that errors are properly bubbled up
     # when calling add_route(). Additional checks can be found
     # in test_uri_converters.py
-    with pytest.raises(ValueError):
+    with pytest.raises(ValueError, match='Cannot instantiate converter') as e:
         router.add_route(uri_template, ResourceWithId(1))
 
+    assert e.value.__cause__ is not None
+
 
 @pytest.mark.parametrize('uri_template', [
     '/foo/{bar:}',