Repository: aio-libs/aiohttp
Pull request: Index resources in the UrlDispatcher to avoid linear search for most cases
<!-- Thank you for your contribution! -->

## What do these changes do?

The time complexity of the UrlDispatcher on a hit averaged `O(n)`

The UrlDispatcher now keeps an index of all resources and will attempt to avoid doing a linear search to resolve.  On a hit the performance should be nearly `O(url_parts)` on a miss the time complexity will be `O(domains) + O(url_parts)`

This works for prefixed subapps as well.

sub apps added by `add_domain` (aka `MatchedSubAppResource`) will fallback to linear searching as they are not indexable since they support wildcard/regexs

## Are there changes in behavior for the user?

A fixed/static path will always be preferred over a dynamic path.

## Related issue number

fixes #7828

benchmark
```python
import asyncio
import timeit
from unittest.mock import MagicMock, AsyncMock

from yarl import URL

from aiohttp import web
from aiohttp.web_urldispatcher import (
    UrlDispatcher,
)

URL_COUNT = 5000


def make_mock_request(url: str) -> web.Request:
    return web.Request(
        MagicMock(url=URL(url), method="GET"),
        MagicMock(),
        protocol=MagicMock(),
        host="example.com",
        task=MagicMock(),
        loop=asyncio.get_running_loop(),
        payload_writer=MagicMock(),
    )


async def url_dispatcher_performance():
    """Filter out large cookies from the cookie jar."""
    dispatcher = UrlDispatcher()
    for i in range(URL_COUNT):
        dispatcher.add_get(f"/static/sub/path{i}", AsyncMock())

    first_url = "/static/sub/path0"
    last_url = f"/static/sub/path{URL_COUNT-1}"
    long_url = "/static/lots/of/sub/path/segments/0/1/2/3/4/5/6/7/8/9/10/11/12/13/14/15"
    mid_size_url = "/static/midsize/of/sub/path/segments"
    miss_url = "/is/a/miss"
    long_miss_url = "/is/a/miss/with/lots/of/sub/path/segments/0/1/2/3/4/5/6/7/8/9/10/11/12/13/14/15"

    dispatcher.add_get(long_url, AsyncMock())
    dispatcher.add_get(mid_size_url, AsyncMock())

    request_first_url = make_mock_request(first_url)
    match_info = await dispatcher.resolve(request_first_url)
    assert match_info.route.resource.canonical == first_url

    request_last_url = make_mock_request(last_url)
    match_info = await dispatcher.resolve(request_last_url)
    assert match_info.route.resource.canonical == last_url

    request_long_url = make_mock_request(long_url)
    match_info = await dispatcher.resolve(request_long_url)
    assert match_info.route.resource.canonical == long_url

    request_mid_size_url = make_mock_request(mid_size_url)
    match_info = await dispatcher.resolve(request_mid_size_url)
    assert match_info.route.resource.canonical == mid_size_url

    request_miss_url = make_mock_request(miss_url)
    match_info = await dispatcher.resolve(request_miss_url)
    assert match_info.route.status == 404

    request_long_miss_url = make_mock_request(long_miss_url)
    match_info = await dispatcher.resolve(request_long_miss_url)
    assert match_info.route.status == 404

    async def resolve_times(request: web.Request, times: int) -> float:
        start = timeit.default_timer()
        for _ in range(times):
            await dispatcher.resolve(request)
        end = timeit.default_timer()
        return end - start

    run_count = 2000
    resolve_time_first_url = await resolve_times(request_first_url, run_count)
    resolve_time_last_url = await resolve_times(request_last_url, run_count)
    resolve_time_mid_size_url = await resolve_times(request_mid_size_url, run_count)
    resolve_time_long_url = await resolve_times(request_long_url, run_count)
    resolve_time_miss = await resolve_times(request_miss_url, run_count)
    resolve_time_long_miss = await resolve_times(request_long_miss_url, run_count)
    print(f"resolve_time_first_url: {resolve_time_first_url}")
    print(f"resolve_time_last_url: {resolve_time_last_url}")
    print(f"resolve_time_mid_size_url: {resolve_time_mid_size_url}")
    print(f"resolve_time_long_url: {resolve_time_long_url}")
    print(f"resolve_time_miss: {resolve_time_miss}")
    print(f"resolve_time_long_miss: {resolve_time_long_miss}")


asyncio.run(url_dispatcher_performance())
```

before (5002 urls)
```
resolve_time_first_url: 0.0016546659753657877
resolve_time_last_url: 2.253484041953925
resolve_time_mid_size_url: 2.1529546250239946
resolve_time_long_url: 2.136738500033971
resolve_time_miss: 2.152159374963958
resolve_time_long_miss: 2.173428333015181
```
before (7 urls)
```
resolve_time_first_url: 0.0019221249967813492
resolve_time_last_url: 0.0038797500310465693
resolve_time_mid_size_url: 0.004664750013034791
resolve_time_long_url: 0.004066875029820949
resolve_time_miss: 0.00846966594690457
resolve_time_long_miss: 0.008330333046615124
```

after (5002 urls)
```
resolve_time_first_url: 0.0019938750192523003
resolve_time_last_url: 0.0020484999986365438
resolve_time_mid_size_url: 0.002027958049438894
resolve_time_long_url: 0.0019290419877506793
resolve_time_miss: 0.0035507080028764904
resolve_time_long_miss: 0.007968166959472
```
after (7 urls)
```
resolve_time_first_url: 0.0019937920151278377
resolve_time_last_url: 0.002007792005315423
resolve_time_mid_size_url: 0.0019652920309454203
resolve_time_long_url: 0.0019985410035587847
resolve_time_miss: 0.003473666962236166
resolve_time_long_miss: 0.007722083013504744
```

## Checklist

- [x] I think the code is well written
- [ ] Unit tests for the changes exist
- [ ] Documentation reflects the changes
- [ ] If you provide code modification, please add yourself to `CONTRIBUTORS.txt`
  * The format is &lt;Name&gt; &lt;Surname&gt;.
  * Please keep alphabetical order, the file is sorted by names.
- [ ] Add a new news fragment into the `CHANGES` folder
  * name it `<issue_id>.<type>` for example (588.bugfix)
  * if you don't have an `issue_id` change it to the pr id after creating the pr
  * ensure type is one of the following:
    * `.feature`: Signifying a new feature.
    * `.bugfix`: Signifying a bug fix.
    * `.doc`: Signifying a documentation improvement.
    * `.removal`: Signifying a deprecation or removal of public API.
    * `.misc`: A ticket has been closed, but it is not of interest to users.
  * Make sure to use full sentences with correct case and punctuation, for example: "Fix issue with non-ascii contents in doctest text files."


Problem statement:
UrlDispatcher improvements
### Describe the bug

The UrlDispatcher currently has to do a linear search to dispatch urls which has an average time complexity of `O(n)`. This means that urls that are registered first can be found faster than urls that are registered later.  


### To Reproduce

Results
```
% python3 url_dispatcher.py
resolve_time_first_url: 0.0017513339989818633
resolve_time_last_url: 2.258735582989175
```

This can be demonstrated with the following benchmark script
```python
import asyncio
import timeit
from unittest.mock import MagicMock, AsyncMock

from yarl import URL

from aiohttp import web
from aiohttp.web_urldispatcher import (
    UrlDispatcher,
)

URL_COUNT = 5000


async def url_dispatcher_performance():
    """Filter out large cookies from the cookie jar."""
    dispatcher = UrlDispatcher()
    for i in range(URL_COUNT):
        dispatcher.add_get(f"/static/sub/path{i}", AsyncMock())

    first_url = "/static/sub/path0"
    last_url = f"/static/sub/path{URL_COUNT-1}"

    request_first_url = web.Request(
        MagicMock(url=URL(first_url), method="GET"),
        MagicMock(),
        protocol=MagicMock(),
        host="example.com",
        task=MagicMock(),
        loop=asyncio.get_running_loop(),
        payload_writer=MagicMock(),
    )
    match_info = await dispatcher.resolve(request_first_url)
    assert match_info.route.resource.canonical == first_url

    request_last_url = web.Request(
        MagicMock(url=URL(last_url), method="GET"),
        MagicMock(),
        protocol=MagicMock(),
        host="example.com",
        task=MagicMock(),
        loop=asyncio.get_running_loop(),
        payload_writer=MagicMock(),
    )
    match_info = await dispatcher.resolve(request_last_url)
    assert match_info.route.resource.canonical == last_url

    async def resolve_times(request: web.Request, times: int) -> float:
        start = timeit.default_timer()
        for _ in range(times):
            await dispatcher.resolve(request)
        end = timeit.default_timer()
        return end - start

    run_count = 2000
    resolve_time_first_url = await resolve_times(request_first_url, run_count)
    resolve_time_last_url = await resolve_times(request_last_url, run_count)
    print(f"resolve_time_first_url: {resolve_time_first_url}")
    print(f"resolve_time_last_url: {resolve_time_last_url}")


asyncio.run(url_dispatcher_performance())

```

### Expected behavior

Ideally the time complexity is at most `O(url_parts)`

### Logs/tracebacks

```python-traceback
n/a
```


### Python Version

```console
n/a
```


### aiohttp Version

```console
master
```


### multidict Version

```console
n/a
```


### yarl Version

```console
n/a
```


### OS

n/a

### Related component

Server

### Additional context

_No response_

### Code of Conduct

- [X] I agree to follow the aio-libs Code of Conduct

Hints from issue discussion:

Commit message: copy to both places so they do not miss it

Patch to review:
diff --git a/CHANGES/7829.misc b/CHANGES/7829.misc
new file mode 100644
index 00000000000..7b98989a89e
--- /dev/null
+++ b/CHANGES/7829.misc
@@ -0,0 +1 @@
+Index resources in the UrlDispatcher to avoid linear search for most cases
diff --git a/aiohttp/web_urldispatcher.py b/aiohttp/web_urldispatcher.py
index 5c8032364c2..1502bb468e2 100644
--- a/aiohttp/web_urldispatcher.py
+++ b/aiohttp/web_urldispatcher.py
@@ -716,13 +716,20 @@ class PrefixedSubAppResource(PrefixResource):
     def __init__(self, prefix: str, app: "Application") -> None:
         super().__init__(prefix)
         self._app = app
-        for resource in app.router.resources():
-            resource.add_prefix(prefix)
+        self._add_prefix_to_resources(prefix)
 
     def add_prefix(self, prefix: str) -> None:
         super().add_prefix(prefix)
-        for resource in self._app.router.resources():
+        self._add_prefix_to_resources(prefix)
+
+    def _add_prefix_to_resources(self, prefix: str) -> None:
+        router = self._app.router
+        for resource in router.resources():
+            # Since the canonical path of a resource is about
+            # to change, we need to unindex it and then reindex
+            router.unindex_resource(resource)
             resource.add_prefix(prefix)
+            router.index_resource(resource)
 
     def url_for(self, *args: str, **kwargs: str) -> URL:
         raise RuntimeError(".url_for() is not supported " "by sub-application root")
@@ -979,12 +986,39 @@ def __init__(self) -> None:
         super().__init__()
         self._resources: List[AbstractResource] = []
         self._named_resources: Dict[str, AbstractResource] = {}
+        self._resource_index: dict[str, list[AbstractResource]] = {}
+        self._matched_sub_app_resources: List[MatchedSubAppResource] = []
 
     async def resolve(self, request: Request) -> UrlMappingMatchInfo:
-        method = request.method
+        url_parts = request.rel_url.raw_parts
+        resource_index = self._resource_index
         allowed_methods: Set[str] = set()
 
-        for resource in self._resources:
+        # Walk the url parts looking for candidates. We walk the url backwards
+        # to ensure the most explicit match is found first. If there are multiple
+        # candidates for a given url part because there are multiple resources
+        # registered for the same canonical path, we resolve them in a linear
+        # fashion to ensure registration order is respected.
+        for i in range(len(url_parts), 0, -1):
+            url_part = "/" + "/".join(url_parts[1:i])
+            if (resource_candidates := resource_index.get(url_part)) is not None:
+                for candidate in resource_candidates:
+                    match_dict, allowed = await candidate.resolve(request)
+                    if match_dict is not None:
+                        return match_dict
+                    else:
+                        allowed_methods |= allowed
+
+        #
+        # We didn't find any candidates, so we'll try the matched sub-app
+        # resources which we have to walk in a linear fashion because they
+        # have regex/wildcard match rules and we cannot index them.
+        #
+        # For most cases we do not expect there to be many of these since
+        # currently they are only added by `add_domain`
+        #
+        method = request.method
+        for resource in self._matched_sub_app_resources:
             match_dict, allowed = await resource.resolve(request)
             if match_dict is not None:
                 return match_dict
@@ -1050,6 +1084,32 @@ def register_resource(self, resource: AbstractResource) -> None:
             self._named_resources[name] = resource
         self._resources.append(resource)
 
+        if isinstance(resource, MatchedSubAppResource):
+            # We cannot index match sub-app resources because they have match rules
+            self._matched_sub_app_resources.append(resource)
+        else:
+            self.index_resource(resource)
+
+    def _get_resource_index_key(self, resource: AbstractResource) -> str:
+        """Return a key to index the resource in the resource index."""
+        canonical = resource.canonical
+        if "{" in canonical:  # strip at the first { to allow for variables
+            canonical = canonical.partition("{")[0].rstrip("/")
+        return canonical or "/"
+
+    def index_resource(self, resource: AbstractResource) -> None:
+        """Add a resource to the resource index."""
+        resource_key = self._get_resource_index_key(resource)
+        # There may be multiple resources for a canonical path
+        # so we keep them in a list to ensure that registration
+        # order is respected.
+        self._resource_index.setdefault(resource_key, []).append(resource)
+
+    def unindex_resource(self, resource: AbstractResource) -> None:
+        """Remove a resource from the resource index."""
+        resource_key = self._get_resource_index_key(resource)
+        self._resource_index[resource_key].remove(resource)
+
     def add_resource(self, path: str, *, name: Optional[str] = None) -> Resource:
         if path and not path.startswith("/"):
             raise ValueError("path should be started with / or be empty")
diff --git a/docs/web_quickstart.rst b/docs/web_quickstart.rst
index 7bfb311e670..d047d2aae98 100644
--- a/docs/web_quickstart.rst
+++ b/docs/web_quickstart.rst
@@ -196,6 +196,20 @@ First one is *optimized*. You have got the idea.
 Variable Resources
 ^^^^^^^^^^^^^^^^^^
 
+.. versionchanged:: 3.10
+
+    Fixed paths are preferred over variable paths. For example,
+    if you have two routes ``/a/b`` and ``/a/{name}``, then the first
+    route will always be preferred over the second one.
+
+    If there are multiple dynamic paths with the same fixed prefix,
+    they will be resolved in order of registration.
+
+    For example, if you have two dynamic routes that are prefixed
+    with the fixed ``/users`` path such as ``/users/{x}/{y}/z`` and
+    ``/users/{x}/y/z``, the first one will be preferred over the
+    second one.
+
 Resource may have *variable path* also. For instance, a resource with
 the path ``'/a/{name}/c'`` would match all incoming requests with
 paths such as ``'/a/b/c'``, ``'/a/1/c'``, and ``'/a/etc/c'``.
diff --git a/docs/web_reference.rst b/docs/web_reference.rst
index 6652edb8490..554cb26f4ed 100644
--- a/docs/web_reference.rst
+++ b/docs/web_reference.rst
@@ -1865,20 +1865,38 @@ unique *name* and at least one :term:`route`.
 
 :term:`web-handler` lookup is performed in the following way:
 
-1. Router iterates over *resources* one-by-one.
-2. If *resource* matches to requested URL the resource iterates over
-   own *routes*.
-3. If route matches to requested HTTP method (or ``'*'`` wildcard) the
-   route's handler is used as found :term:`web-handler`. The lookup is
-   finished.
-4. Otherwise router tries next resource from the *routing table*.
-5. If the end of *routing table* is reached and no *resource* /
-   *route* pair found the *router* returns special :class:`~aiohttp.abc.AbstractMatchInfo`
+1. The router splits the URL and checks the index from longest to shortest.
+   For example, '/one/two/three' will first check the index for
+   '/one/two/three', then '/one/two' and finally '/'.
+2. If the URL part is found in the index, the list of routes for
+   that URL part is iterated over. If a route matches to requested HTTP
+   method (or ``'*'`` wildcard) the route's handler is used as found
+   :term:`web-handler`. The lookup is finished.
+3. If the route is not found in the index, the router tries to find
+   the route in the list of :class:`~aiohttp.web.MatchedSubAppResource`,
+   (current only created from :meth:`~aiohttp.web.Application.add_domain`),
+   and will iterate over the list of
+   :class:`~aiohttp.web.MatchedSubAppResource` in a linear fashion
+   until a match is found.
+4. If no *resource* / *route* pair was found, the *router*
+   returns special :class:`~aiohttp.abc.AbstractMatchInfo`
    instance with :attr:`aiohttp.abc.AbstractMatchInfo.http_exception` is not ``None``
    but :exc:`HTTPException` with  either *HTTP 404 Not Found* or
    *HTTP 405 Method Not Allowed* status code.
    Registered :meth:`~aiohttp.abc.AbstractMatchInfo.handler` raises this exception on call.
 
+Fixed paths are preferred over variable paths. For example,
+if you have two routes ``/a/b`` and ``/a/{name}``, then the first
+route will always be preferred over the second one.
+
+If there are multiple dynamic paths with the same fixed prefix,
+they will be resolved in order of registration.
+
+For example, if you have two dynamic routes that are prefixed
+with the fixed ``/users`` path such as ``/users/{x}/{y}/z`` and
+``/users/{x}/y/z``, the first one will be preferred over the
+second one.
+
 User should never instantiate resource classes but give it by
 :meth:`UrlDispatcher.add_resource` call.
 
@@ -1900,7 +1918,10 @@ Resource classes hierarchy::
      Resource
        PlainResource
        DynamicResource
+     PrefixResource
        StaticResource
+       PrefixedSubAppResource
+          MatchedSubAppResource
 
 
 .. class:: AbstractResource
diff --git a/tests/test_web_urldispatcher.py b/tests/test_web_urldispatcher.py
index a455e5d59b0..41ede728c29 100644
--- a/tests/test_web_urldispatcher.py
+++ b/tests/test_web_urldispatcher.py
@@ -10,7 +10,7 @@
 
 from aiohttp import web
 from aiohttp.pytest_plugin import AiohttpClient
-from aiohttp.web_urldispatcher import SystemRoute
+from aiohttp.web_urldispatcher import Resource, SystemRoute
 
 
 @pytest.mark.parametrize(
@@ -544,3 +544,79 @@ async def handler(request: web.Request) -> web.Response:
     r = await client.get(yarl.URL(urlencoded_path, encoded=True))
     assert r.status == expected_http_resp_status
     await r.release()
+
+
+async def test_order_is_preserved(aiohttp_client: AiohttpClient) -> None:
+    """Test route order is preserved.
+
+    Note that fixed/static paths are always preferred over a regex path.
+    """
+    app = web.Application()
+
+    async def handler(request: web.Request) -> web.Response:
+        assert isinstance(request.match_info._route.resource, Resource)
+        return web.Response(text=request.match_info._route.resource.canonical)
+
+    app.router.add_get("/first/x/{b}/", handler)
+    app.router.add_get(r"/first/{x:.*/b}", handler)
+
+    app.router.add_get(r"/second/{user}/info", handler)
+    app.router.add_get("/second/bob/info", handler)
+
+    app.router.add_get("/third/bob/info", handler)
+    app.router.add_get(r"/third/{user}/info", handler)
+
+    app.router.add_get(r"/forth/{name:\d+}", handler)
+    app.router.add_get("/forth/42", handler)
+
+    app.router.add_get("/fifth/42", handler)
+    app.router.add_get(r"/fifth/{name:\d+}", handler)
+
+    client = await aiohttp_client(app)
+
+    r = await client.get("/first/x/b/")
+    assert r.status == 200
+    assert await r.text() == "/first/x/{b}/"
+    await r.release()
+
+    r = await client.get("/second/frank/info")
+    assert r.status == 200
+    assert await r.text() == "/second/{user}/info"
+    await r.release()
+
+    # Fixed/static paths are always preferred over regex paths
+    r = await client.get("/second/bob/info")
+    assert r.status == 200
+    assert await r.text() == "/second/bob/info"
+    await r.release()
+
+    r = await client.get("/third/bob/info")
+    assert r.status == 200
+    assert await r.text() == "/third/bob/info"
+    await r.release()
+
+    r = await client.get("/third/frank/info")
+    assert r.status == 200
+    assert await r.text() == "/third/{user}/info"
+    await r.release()
+
+    r = await client.get("/forth/21")
+    assert r.status == 200
+    assert await r.text() == "/forth/{name}"
+    await r.release()
+
+    # Fixed/static paths are always preferred over regex paths
+    r = await client.get("/forth/42")
+    assert r.status == 200
+    assert await r.text() == "/forth/42"
+    await r.release()
+
+    r = await client.get("/fifth/21")
+    assert r.status == 200
+    assert await r.text() == "/fifth/{name}"
+    await r.release()
+
+    r = await client.get("/fifth/42")
+    assert r.status == 200
+    assert await r.text() == "/fifth/42"
+    await r.release()


Code review comments:
diff_hunk: @@ -979,12 +986,39 @@ def __init__(self) -> None:
         super().__init__()
         self._resources: List[AbstractResource] = []
         self._named_resources: Dict[str, AbstractResource] = {}
+        self._resource_index: dict[str, list[AbstractResource]] = {}
+        self._matched_sub_app_resources: List[MatchedSubAppResource] = []
 
     async def resolve(self, request: Request) -> UrlMappingMatchInfo:
-        method = request.method
+        url_parts = request.rel_url.raw_parts
+        resource_index = self._resource_index
         allowed_methods: Set[str] = set()
 
-        for resource in self._resources:
+        # Walk the url parts looking for candidates. We walk the url backwards
+        # to ensure the most explicit match is found first. If there are multiple
+        # candidates for a given url part because there are multiple resources
+        # registered for the same canonical path, we resolve them in a linear
+        # fashion to ensure registration order is respected.
+        for i in range(len(url_parts), 0, -1):
+            url_part = "/" + "/".join(url_parts[1:i])
+            if (resource_candidates := resource_index.get(url_part)) is not None:
+                for candidate in resource_candidates:
+                    match_dict, allowed = await candidate.resolve(request)
+                    if match_dict is not None:
+                        return match_dict
+                    else:
+                        allowed_methods |= allowed
+
+        #
+        # We didn't find any candidates, so we'll try the matched sub-app
+        # resources which we have to walk in a linear fashion because they
+        # have regex/wildcard match rules and we cannot index them.
+        #
+        # For most cases we do not expect there to be many of these since
+        # currently they are only added by `add_domain`
+        #
+        method = request.method
path: aiohttp/web_urldispatcher.py
text: @user1:
I don't think this is used?
```suggestion
```

@author:
Yup, looks stale

diff_hunk: @@ -544,3 +544,79 @@ async def handler(request: web.Request) -> web.Response:
     r = await client.get(yarl.URL(urlencoded_path, encoded=True))
     assert r.status == expected_http_resp_status
     await r.release()
+
+
+async def test_order_is_preserved(aiohttp_client: AiohttpClient) -> None:
+    """Test route order is preserved.
+
+    Note that fixed/static paths are always preferred over a regex path.
+    """
+    app = web.Application()
+
+    async def handler(request: web.Request) -> web.Response:
+        assert isinstance(request.match_info._route.resource, Resource)
+        return web.Response(text=request.match_info._route.resource.canonical)
+
+    app.router.add_get("/first/x/{b}/", handler)
+    app.router.add_get(r"/first/{x:.*/b}", handler)
+
+    app.router.add_get(r"/second/{user}/info", handler)
+    app.router.add_get("/second/bob/info", handler)
+
+    app.router.add_get("/third/bob/info", handler)
+    app.router.add_get(r"/third/{user}/info", handler)
+
+    app.router.add_get(r"/forth/{name:\d+}", handler)
+    app.router.add_get("/forth/42", handler)
+
+    app.router.add_get("/fifth/42", handler)
+    app.router.add_get(r"/fifth/{name:\d+}", handler)
+
+    client = await aiohttp_client(app)
+
+    r = await client.get("/first/x/b/")
+    assert r.status == 200
+    assert await r.text() == "/first/x/{b}/"
+    await r.release()
+
+    r = await client.get("/second/frank/info")
+    assert r.status == 200
+    assert await r.text() == "/second/{user}/info"
+    await r.release()
+
+    # Fixed/static paths are always preferred over regex paths
+    r = await client.get("/second/bob/info")
+    assert r.status == 200
+    assert await r.text() == "/second/bob/info"
+    await r.release()
+
+    r = await client.get("/third/bob/info")
+    assert r.status == 200
+    assert await r.text() == "/third/bob/info"
+    await r.release()
+
+    r = await client.get("/third/frank/info")
+    assert r.status == 200
+    assert await r.text() == "/third/{user}/info"
+    await r.release()
+
+    r = await client.get("/forth/21")
+    assert r.status == 200
+    assert await r.text() == "/forth/{name}"
+    await r.release()
+
+    # Fixed/static paths are always preferred over regex paths
+    r = await client.get("/forth/42")
+    assert r.status == 200
+    assert await r.text() == "/forth/42"
+    await r.release()
+
+    r = await client.get("/fifth/21")
+    assert r.status == 200
+    assert await r.text() == "/fifth/{name}"
+    await r.release()
+
+    r = await client.get("/fifth/42")
+    assert r.status == 200
+    assert await r.text() == "/fifth/42"
+    await r.release()
path: tests/test_web_urldispatcher.py
text: @user1:
Strictly speaking, these aren't necessary. The connection is already released once .text() returns.

@author:
d126a828a821f828b41f10496d00502d1b51aee7

@user2:
@user1 I've been sticking these around all over, at some point. The reason is that some things were leaking into the following tests, whenever responses or sessions weren't closed. Sometimes this led to flaky resource warnings that were hard to spot because they failed a different test than the one causing the leak.

@user1:
Yeah, but we know they are closed if there is a .read() call completed. It's the other ones that are actually causing problems. Like, for example, this test failed because in some of the test cases it didn't call .read() and could result in the connection not being closed:
https://github.com/aio-libs/aiohttp/pull/7896/files#diff-e708432f3ba422740bfc04230f149eac4ff3787dde29204b6ee22b622a0e8915R77-R79

@user2:
This must be what I'm remembering: https://github.com/aio-libs/aiohttp/pull/5494/files#diff-e708432f3ba422740bfc04230f149eac4ff3787dde29204b6ee22b622a0e8915R137

diff_hunk: @@ -979,12 +986,39 @@ def __init__(self) -> None:
         super().__init__()
         self._resources: List[AbstractResource] = []
         self._named_resources: Dict[str, AbstractResource] = {}
+        self._resource_index: dict[str, list[AbstractResource]] = {}
+        self._matched_sub_app_resources: List[MatchedSubAppResource] = []
 
     async def resolve(self, request: Request) -> UrlMappingMatchInfo:
-        method = request.method
+        url_parts = request.rel_url.raw_parts
+        resource_index = self._resource_index
         allowed_methods: Set[str] = set()
 
-        for resource in self._resources:
+        # Walk the url parts looking for candidates. We walk the url backwards
+        # to ensure the most explicit match is found first. If there are multiple
+        # candidates for a given url part because there are multiple resources
+        # registered for the same canonical path, we resolve them in a linear
+        # fashion to ensure registration order is respected.
+        for i in range(len(url_parts), 0, -1):
+            url_part = "/" + "/".join(url_parts[1:i])
path: aiohttp/web_urldispatcher.py
text: @user1:
Maybe I'm overthinking it, but I wonder if there's any optimisation here if we do something along the lines of:
```
url_part = "/" + "/".join(url_parts)
while url_part:
    url_part = url_part.rsplit("/", maxsplit=1)[0]
```

@user1:
And, maybe too complicated, but a tree structure might allow bailing out quickly. Maybe it would look something like:
```
candidates = [tree := tree.get(p) for p in url_parts if tree]
for tree in candidates[::-1]:
    for c in tree[None]:  # str keys are used for the prefix matching, None contains candidates?
```

@user1:
I'm just throwing around ideas here, feel free to ignore them. But, might be interesting to see if there's some further performance gains to be had.

@author:
optimized in 5810f02750c88dfa6df7c3166eb5c0242f2c502c

@author:
before
```
resolve_time_first_url: 0.002494540996849537
resolve_time_last_url: 0.0025858330773189664
resolve_time_miss: 0.007047250051982701
```

after
```
resolve_time_first_url: 0.0019859170133713633
resolve_time_last_url: 0.0020277079893276095
resolve_time_miss: 0.00666537499637343
```

@author:
Looks like a little too much .. tests are failing now..

@author:
Needed to use the `raw_path`

@author:
and that seems to be a bit faster as well
```
resolve_time_first_url: 0.0018852080102078617
resolve_time_last_url: 0.0018728750001173466
resolve_time_miss: 0.005776290985522792
```

@user1:
Nice, so looks like it may be performing better than the original code even in the first_url condition now.

@author:
Thanks for pushing me to optimize it more. Almost nobody ever does that in reviews.

I'm working on down streaming the changes today so I can validate in my production 

@user1:
By the way, I only just realised while I was thinking about it overnight, but the benchmarks are biased.
Rather than first/last URL, it should really be best/worst time.
For the old code, the worst time will be the last URL. But, for the new code the worst time will be the one that is most nested and needs to go through multiple checks. The miss time is probably a reasonable estimate of the worst case, though it is really dependent on the layout of a given app.

@author:
I updated the benchmarks to include a few more cases

@author:
I added 7 url case and 5002 url case.

The new code still beats the old 7 url case (although it doesn't make much difference)

I guess we could probably optimize the 404 handler a bit more

@author:
I sped up the 404 case quite a bit

@author:

before (5002 urls)
```
resolve_time_first_url: 0.0016546659753657877
resolve_time_last_url: 2.253484041953925
resolve_time_mid_size_url: 2.1529546250239946
resolve_time_long_url: 2.136738500033971
resolve_time_miss: 2.152159374963958
resolve_time_long_miss: 2.173428333015181
```
before (7 urls)
```
resolve_time_first_url: 0.0019221249967813492
resolve_time_last_url: 0.0038797500310465693
resolve_time_mid_size_url: 0.004664750013034791
resolve_time_long_url: 0.004066875029820949
resolve_time_miss: 0.00846966594690457
resolve_time_long_miss: 0.008330333046615124
```

after (5002 urls)
```
resolve_time_first_url: 0.001852833025623113
resolve_time_last_url: 0.0018547910149209201
resolve_time_mid_size_url: 0.0019565830007195473
resolve_time_long_url: 0.001857625029515475
resolve_time_miss: 0.0009622920188121498
resolve_time_long_miss: 0.005029833992011845
```
after (7 urls)
```
resolve_time_first_url: 0.001815625000745058
resolve_time_last_url: 0.0018432079814374447
resolve_time_mid_size_url: 0.001861582975834608
resolve_time_long_url: 0.0017958339885808527
resolve_time_miss: 0.0009489589720033109
resolve_time_long_miss: 0.005105625023134053
```

@user1:
Nice

@author:
Looks like I'm going to have to revert it since the web.Application handler always adds the app every time and than throws away the handler and refactoring that would probably be outside of scope for this PR

@author:
Was able to keep at least one object creation reduction so its still faster


after (5002 urls)
```
resolve_time_first_url: 0.0019938750192523003
resolve_time_last_url: 0.0020484999986365438
resolve_time_mid_size_url: 0.002027958049438894
resolve_time_long_url: 0.0019290419877506793
resolve_time_miss: 0.0035507080028764904
resolve_time_long_miss: 0.007968166959472
```
after (7 urls)
```
resolve_time_first_url: 0.0019937920151278377
resolve_time_last_url: 0.002007792005315423
resolve_time_mid_size_url: 0.0019652920309454203
resolve_time_long_url: 0.0019985410035587847
resolve_time_miss: 0.003473666962236166
resolve_time_long_miss: 0.007722083013504744
```

diff_hunk: @@ -196,6 +196,20 @@ First one is *optimized*. You have got the idea.
 Variable Resources
 ^^^^^^^^^^^^^^^^^^
 
+.. versionchanged:: 3.10
+
+    Fixed paths are preferred over variable paths. For example,
+    if you have two routes ``/a/b`` and ``/a/{name}``, then the first
+    route will always be preferred over the second one.
+
+    If there are multiple dynamic paths with the same fixed prefix,
+    they will be resolved in order of registration.
+
+    For example, if you have two dynamic routes that are prefixed
+    with the fixed ``/users`` path such as ``/users/{x}/{y}/z`` and
+    ``/users/{x}/y/z``, the first one will be preferred over the
+    second one.
path: docs/web_quickstart.rst
text: @user1:
Given this is supposed to be a quickstart, and we've got the exact same description in reference, I'd suggest dropping this. (I think I'd like to take a look at dropping most of this quickstart at some point, and merging it with the tutorial).

@author:
removed in 2bac4583ee22a55a7ea2a7f3316fe9a8746952e1

diff_hunk: @@ -1050,6 +1084,32 @@ def register_resource(self, resource: AbstractResource) -> None:
             self._named_resources[name] = resource
         self._resources.append(resource)
 
+        if isinstance(resource, MatchedSubAppResource):
+            # We cannot index match sub-app resources because they have match rules
+            self._matched_sub_app_resources.append(resource)
+        else:
+            self.index_resource(resource)
+
+    def _get_resource_index_key(self, resource: AbstractResource) -> str:
+        """Return a key to index the resource in the resource index."""
+        canonical = resource.canonical
+        if "{" in canonical:  # strip at the first { to allow for variables
+            canonical = canonical.partition("{")[0].rstrip("/")
path: aiohttp/web_urldispatcher.py
text: @user1:
This works without the if?
```suggestion
        # strip at the first { to allow for variables
        canonical = resource.canonical.partition("{")[0].rstrip("/")
```

diff_hunk: @@ -979,12 +986,39 @@ def __init__(self) -> None:
         super().__init__()
         self._resources: List[AbstractResource] = []
         self._named_resources: Dict[str, AbstractResource] = {}
+        self._resource_index: dict[str, list[AbstractResource]] = {}
+        self._matched_sub_app_resources: List[MatchedSubAppResource] = []
 
     async def resolve(self, request: Request) -> UrlMappingMatchInfo:
-        method = request.method
+        url_parts = request.rel_url.raw_parts
+        resource_index = self._resource_index
         allowed_methods: Set[str] = set()
 
-        for resource in self._resources:
+        # Walk the url parts looking for candidates. We walk the url backwards
+        # to ensure the most explicit match is found first. If there are multiple
+        # candidates for a given url part because there are multiple resources
+        # registered for the same canonical path, we resolve them in a linear
+        # fashion to ensure registration order is respected.
+        for i in range(len(url_parts), 0, -1):
+            url_part = "/" + "/".join(url_parts[1:i])
+            if (resource_candidates := resource_index.get(url_part)) is not None:
+                for candidate in resource_candidates:
+                    match_dict, allowed = await candidate.resolve(request)
+                    if match_dict is not None:
+                        return match_dict
+                    else:
+                        allowed_methods |= allowed
path: aiohttp/web_urldispatcher.py
text: @user1:
```suggestion
            for candidate in resource_index.get(url_part, ()):
                match_dict, allowed = await candidate.resolve(request)
                if match_dict is not None:
                    return match_dict
                else:
                    allowed_methods |= allowed
```