Enhancement: Rust, C or C++ bindings for path resolution

[Goldziher]

Starlite currently resolves paths using a tree structure, but in python. This is quite slow. It would be very helpful if we could create custom bindings in a low level and substantially faster language to implement the tree and its required parsing methods.

The data structure that is often used for this purpose is called a "radix prefix tree". This is not necessarily the only option we have - but its a strong one.

PRs are welcome, as are discussions.

[Bobronium]

Some links to the existing code in starlite would be helpful to start.

Also, have you considered/tried compiling starlite/parts of it with mypyc?

[peterschutt]

Also, have you considered/tried compiling starlite/parts of it with mypyc?

100% this. I'd love to see what the solution looks like in modern cython (i say modern because the last time I built anything of consequence with cython was before typing was really a thing) and mypyc.

Thinking about this issue on the next meta level up, an overall efficiency analysis of the two main things Starlite does is something that I'm keen to do. From my understanding so far, these two main things are:

1. serve requests, sounds obvious, the route from request entry to response return would benefit from some diagrams and docs, and even the smallest of optimizations along that path are +1 from me.
2. the handler -> controller -> router -> app walk on startup - the whole library is pretty much built on this and so it should be pretty optimal I think. I reckon it also might be neat to make this walk a feature of library startup and let users register hooks onto it. For example, I might want to register a hook onto the walk that logs the number of routes that I have nested under each router/controller and how many of them are unauthenticated and authenticated. Just an example, but it would be a neat and I think unique feature that we could promote.

[peterschutt]

Don't get me wrong, I'd also like to see what the solution looks like with py03 and rust too though :laughing:

It would be good for developer docs to have a diagram of that "radix prefix tree" pattern included. I'm glad you mentioned that @Goldziher as the code is a bit hard to follow (not a criticism but just by nature) - is that the algo in StarliteASGIRouter.__call__()?

[Goldziher]

I did some trials with cython and mypyc. Mypyc Didn't like async and some other stuff, so it could handle some parts of the codebase and not others. Cython required quite a few changes to the code to get the compiled code to actually work.

I'm not against this, but for my money these solutions are a compromise - offering a performance boost, but less so than native code.

As to code snippets, diagrams etc. Sure, I'll do this later today.

[peterschutt]

As to code snippets, diagrams etc. Sure, I'll do this later today.

Thanks!

[peterschutt]

I did some trials with cython and mypyc. Mypyc Didn't like async and some other stuff, so it could handle some parts of the codebase and not others. Cython required quite a few changes to the code to get the compiled code to actually work.

Was this trying to cythonize/mypycize the whole lib? Or just targeted stuff?

[Goldziher]

I did some trials with cython and mypyc. Mypyc Didn't like async and some other stuff, so it could handle some parts of the codebase and not others. Cython required quite a few changes to the code to get the compiled code to actually work.

Was this trying to cythonize/mypycize the whole lib? Or just targeted stuff?

Both.

I had more success with cython, but the performance boost wasn't great. The main issue for compiling the entire lib is pydantic - pydantic has cython, so if you install cython as part of your dependencies it will compile, giving you a speed boost. But any code that uses pydantic cannot be compiled itself.

[Goldziher]

So, lets start with code. The most updated version is the one in #173, so I will explain the code as it appears there which will also help by and by with the review of that PR.

There are two files that interest here - starlite/app,py and starlite/asgi.py. Lets start with whats happening inside the Starlite class. Specifically with the register method:

    def register(self, value: ControllerRouterHandler) -> None:  # type: ignore[override]
        """
        Register a Controller, Route instance or RouteHandler on the app.

        Calls Router.register() and then creates a signature model for all handlers.
        """
        routes = super().register(value=value)
        for route in routes:
            if isinstance(route, HTTPRoute):
                route_handlers = route.route_handlers
            else:
                route_handlers = [cast(Union[WebSocketRoute, ASGIRoute], route).route_handler]  # type: ignore
            for route_handler in route_handlers:
                self.create_handler_signature_model(route_handler=route_handler)
                route_handler.resolve_guards()
                route_handler.resolve_middleware()
                if isinstance(route_handler, HTTPRouteHandler):
                    route_handler.resolve_response_class()
                    route_handler.resolve_before_request()
                    route_handler.resolve_after_request()
            if isinstance(route, HTTPRoute):
                route.create_handler_map()
            elif isinstance(route, WebSocketRoute):
                route.handler_parameter_model = route.create_handler_kwargs_model(route.route_handler)
        self.construct_route_map()

This method is called in the init method for the application via a super call to the underlying Router class (Starlite router, not Starlette!). It basically iterates through all the routers, controllers and route handlers, processes them and in the end calls the method construct_route_map.

Note: This method is exposed to allow dynamic registeration of routes - even after app initialization.

The construct_route_map method is where the Starlite routing logic is created. Its very different from whats happening in Starlette and other frameworks (read Django, FastAPI etc.), because these frameworks rely on regex to match routes to their respective handlers / views etc. What they do is basically iterate through all the registered routes, trying to match them with a regex, and once there is a successful match, proceed.

The problem with this approach, which is btw also the same in the NodeJS framework Express and other popular non-python frameworks, is that it doesn't scale well. The more routes you have, the longer matching can take because each regex is tested against the incoming request's path. In other words - time complexity is not good.

Saying that, the one advantage this method does have in python is that the python regex engine is implemented in C, so its quite fast in comparison with normal python code. You will not see a significant difference in small apps with only a few routes, only with large apps. Still, I found this to be a bad design choice and decided to move away from it.

What does Starlite do? Basically we create whats called a radix tree or trie.

I decided to implement this using python dictionaries and combine it with sets, because of the particulars of how python implements these - dictionary key lookup is fast because it uses sets behind the scenes, while dictionary value access is faster than iteration, and sets are fast because they are implemented natively, with set lookup being exceptionally fast in python (respective of python that is).

This is basically whats happening inside the construct_route_map method, which sets the value self.route_map in the Starlite app instance:

def construct_route_map(self) -> None: 
        """
        Create a map of the app's routes. This map is used in the asgi router to route requests.

        """
        if "_components" not in self.route_map:
            self.route_map["_components"] = set()
        for route in self.routes:
            path = route.path
            if route.path_parameters or path in self.static_paths:
                for param_definition in route.path_parameters:
                    path = path.replace(param_definition["full"], "")
                path = path.replace("{}", "*")
                cur = self.route_map
                components = ["/", *[component for component in path.split("/") if component]]
                for component in components:
                    components_set = cast(Set[str], cur["_components"])
                    components_set.add(component)
                    if component not in cur:
                        cur[component] = {"_components": set()}
                    cur = cast(Dict[str, Any], cur[component])
            else:
                self.route_map[path] = {"_components": set()}
                self.plain_routes.add(path)
                cur = self.route_map[path]
            if "_path_parameters" not in cur:
                cur["_path_parameters"] = route.path_parameters # <- this is a set stored on each route instance
            if "_asgi_handlers" not in cur:
                cur["_asgi_handlers"] = {} # dict[str, ASGIApp]
            if "_is_asgi" not in cur:
                cur["_is_asgi"] = False # bool
            if path in self.static_paths:
                cur["static_path"] = path # str
                cur["_is_asgi"] = True
            asgi_handlers = cast(Dict[str, ASGIApp], cur["_asgi_handlers"])
            # construct an ASGIApp for the given route (path, or path + method for http)
            if isinstance(route, HTTPRoute):
                for method, handler_mapping in route.route_handler_map.items():
                    handler, _ = handler_mapping
                    asgi_handlers[method] = self.build_route_middleware_stack(route, handler)
            elif isinstance(route, WebSocketRoute):
                asgi_handlers["websocket"] = self.build_route_middleware_stack(route, route.route_handler)
            elif isinstance(route, ASGIRoute):
                asgi_handlers["asgi"] = self.build_route_middleware_stack(route, route.route_handler)
                cur["_is_asgi"] = True

The above code creates a tree structure with each node of the tree being identified by a path componen, containing data about any routes belonging to it and allowing access to child nodes via their respective path component.

Lets consider an example from the tests:

def test_handler_multi_paths() -> None:
    @get(path=["/", "/something", "/{some_id:int}", "/something/{some_id:int}"], media_type=MediaType.TEXT)
    def handler_fn(some_id: int = 1) -> str:
        assert some_id
        return str(some_id)
    with create_test_client(handler_fn) as client:
       # ....

If we inspect in the debugger the kind of mapping that is created above, we see this:

{
   '_components':{
      '/'
   },
   '/':{
      '_components':{
         'something',
         '*'
      },
      '_path_parameters':[

      ],
      '_asgi_handlers':{
         'GET':<bound method HTTPRoute.handle of <starlite.routes.HTTPRoute object at 0x106592ea0>>
      },
      '_is_asgi':False,
      '*':{
         '_components':set(),
         '_path_parameters':[
            {
               'name':'some_id',
               'type':<class'int'>,
               'full':'some_id:int'
            }
         ],
         '_asgi_handlers':{
            'GET':<bound method HTTPRoute.handle of <starlite.routes.HTTPRoute object at 0x106593760>>
         },
         '_is_asgi':False
      },
      'something':{
         '_components':{
            '*'
         },
         '*':{
            '_components':set(),
            '_path_parameters':[
               {
                  'name':'some_id',
                  'type':<class'int'>,
                  'full':'some_id:int'
               }
            ],
            '_asgi_handlers':{
               'GET':<bound method HTTPRoute.handle of <starlite.routes.HTTPRoute object at 0x106593a00>>
            },
            '_is_asgi':False
         }
      }
   },
   '/something':{
      '_components':set(),
      '_path_parameters':[

      ],
      '_asgi_handlers':{
         'GET':<bound method HTTPRoute.handle of <starlite.routes.HTTPRoute object at 0x1065937d0>>
      },
      '_is_asgi':False
   }
}

This brings us to the last method in the Starlite app that is of interest here - the method called build_middleware_stack, that is called as part of the mapping logic above - for each route handler:

    def build_route_middleware_stack(
        self, route: Union[HTTPRoute, WebSocketRoute, ASGIRoute], route_handler: BaseRouteHandler
    ) -> ASGIApp:
        """Constructs a middleware stack that serves as the point of entry for each route"""
        asgi_handler: ASGIApp = route.handle
        for middleware in route_handler.resolve_middleware():
            if isinstance(middleware, StarletteMiddleware):
                asgi_handler = middleware.cls(app=asgi_handler, **middleware.options)
            else:
                asgi_handler = middleware(app=asgi_handler)
        if self.allowed_hosts:
            asgi_handler = TrustedHostMiddleware(app=asgi_handler, allowed_hosts=self.allowed_hosts)
        if self.cors_config:
            asgi_handler = CORSMiddleware(app=asgi_handler, **self.cors_config.dict())
        return asgi_handler

This method creates the ASGIApp for each individual combination of route + route handling function, with the last component in the middleware stack to be called being the route.handle method and the first being the CORSMiddleware, if config for it is defined. This is stored under _asgi_handlers with the following type of keys GET, POST, PUT etc. and asgi / websocket for @asgi and @websocket route handlers respectively.

This now brings us to how these paths are resolved.

This happens in the ASGIRouter class's __call__ method, which is called by the Starlite app for each asgi request. This is how its called from the Starlite class:

    async def __call__(self, scope: Scope, receive: Receive, send: Send) -> None:
        scope["app"] = self
        if scope["type"] == "lifespan":
            await self.asgi_router.lifespan(scope, receive, send)
            return
        try:
            scope["state"] = {}
            await self.asgi_router(scope, receive, send) # <-- this is the call
        except Exception as e:  # pylint: disable=broad-except
            await self.handle_exception(scope=scope, receive=receive, send=send, exc=e)

And this is whats happening there:

    def parse_scope_to_route(self, scope: Scope) -> Tuple[Dict[str, ASGIApp], bool]:
        """
        Given a scope object, traverse the route mapping and retrieve the correct "leaf" in the route tree.
        """
        path_params: List[str] = []
        path = cast(str, scope["path"]).strip()
        if path != "/" and path.endswith("/"):
            path = path.rstrip("/")
        if path in self.app.plain_routes:
            cur: Dict[str, Any] = self.app.route_map[path]
        else:
            cur = self.app.route_map
            components = ["/", *[component for component in path.split("/") if component]]
            for component in components:
                components_set = cast(Set[str], cur["_components"])
                if component in components_set:
                    cur = cast(Dict[str, Any], cur[component])
                    continue
                if "*" in components_set:
                    path_params.append(component)
                    cur = cast(Dict[str, Any], cur["*"])
                    continue
                if cur.get("static_path"):
                    static_path = cast(str, cur["static_path"])
                    if static_path != "/":
                        scope["path"] = scope["path"].replace(static_path, "")
                    continue
                raise NotFoundException()
        scope["path_params"] = (
            parse_path_params(cur["_path_parameters"], path_params) if cur["_path_parameters"] else {}
        )
        asgi_handlers = cast(Dict[str, ASGIApp], cur["_asgi_handlers"])
        is_asgi = cast(bool, cur["_is_asgi"])
        return asgi_handlers, is_asgi

    @staticmethod
    def resolve_asgi_app(scope: Scope, asgi_handlers: Dict[str, ASGIApp], is_asgi: bool) -> ASGIApp:
        """
        Given a scope, retrieves the correct ASGI App for the route
        """
        if is_asgi:
            return asgi_handlers[ScopeType.ASGI]
        if scope["type"] == ScopeType.HTTP:
            if scope["method"] not in asgi_handlers:
                raise MethodNotAllowedException()
            return asgi_handlers[scope["method"]]
        return asgi_handlers[ScopeType.WEBSOCKET]

    async def __call__(self, scope: Scope, receive: Receive, send: Send) -> None:
        """
        The main entry point to the Router class.
        """
        try:
            asgi_handlers, is_asgi = self.parse_scope_to_route(scope=scope)
            asgi_handler = self.resolve_asgi_app(scope=scope, asgi_handlers=asgi_handlers, is_asgi=is_asgi)
        except KeyError as e:
            raise NotFoundException() from e
        await asgi_handler(scope, receive, send)

As you can see, the call method first calls parse_scope_to_route passing to it the ASGI scope. This method in turn. does the following (I will annotate the code):

 def parse_scope_to_route(self, scope: Scope) -> Tuple[Dict[str, ASGIApp], bool]:
        """
        Given a scope object, traverse the route mapping and retrieve the correct "leaf" in the route tree.
        """
        path_params: List[str] = [] # stored path params, we append them as we find them when traversing
        path = cast(str, scope["path"]).strip()
        if path != "/" and path.endswith("/"): # normalize the path - we do not care for trailing slashes
            path = path.rstrip("/")
         # the path is a "plain_route", meaning it has no path params, e.g. "/companies"
         # we therefore do not need to traverse the map and can simply use the normalized path as a key
        if path in self.app.plain_routes:
            cur: Dict[str, Any] = self.app.route_map[path]
        else: # we got here, which means the path we got is parameterized
            # we traversing the map via looping, each time we move a level, cur is going to be updated
            cur = self.app.route_map 
            components = ["/", *[component for component in path.split("/") if component]]
            # for "/foo/123/buzz" we will have here ["/", "foo", "123", "buzz"]
            for component in components:  
                # we are taking the component set we have, because its the fastest lookup
                components_set = cast(Set[str], cur["_components"])
                # if the component we have here is not a parameter, it should match, e.g. ["/", "foo", "buzz"]
                if component in components_set: 
                   # update cur to the next level
                    cur = cast(Dict[str, Any], cur[component])
                    continue
                # we have an "*" in the component_set, we therefore allow for a parameter
                if "*" in components_set: 
                    # we got to this point with the value "123", and we appent it to the path components
                    path_params.append(component)
                    # update cur to the next level
                    cur = cast(Dict[str, Any], cur["*"])
                    continue
                # special case for static paths
                if cur.get("static_path"):
                    static_path = cast(str, cur["static_path"])
                    if static_path != "/":
                        scope["path"] = scope["path"].replace(static_path, "")
                    continue
                # no matches, raise 404
                raise NotFoundException()
        # we use a helper function to transform url params, which are always strings, into their values.
        scope["path_params"] = (
            parse_path_params(cur["_path_parameters"], path_params) if cur["_path_parameters"] else {}
        )
        asgi_handlers = cast(Dict[str, ASGIApp], cur["_asgi_handlers"])
        is_asgi = cast(bool, cur["_is_asgi"])
        return asgi_handlers, is_asgi

Once the map has been traversed to the correct node - and if no exception has been raise - the _asgi_handlers dictionary and the _is_asgi boolean are returned, i.e. the two following keys of the node:

{
   '_asgi_handlers':{
      'GET':<bound method HTTPRoute.handle of <starlite.routes.HTTPRoute object at 0x106592ea0>>
   },
   '_is_asgi':False,
}

Additionally, the resolved path params have been injected into the scope object, which will allow them to be used later when we need to parse kwargs for the handling function and dependencies.

Finally, the actual handler is resolved in the method resolve_asgi_app:

    def resolve_asgi_app(scope: Scope, asgi_handlers: Dict[str, ASGIApp], is_asgi: bool) -> ASGIApp:
        """
        Given a scope, retrieves the correct ASGI App for the route
        """
        if is_asgi:
            return asgi_handlers[ScopeType.ASGI]
        if scope["type"] == ScopeType.HTTP:
            if scope["method"] not in asgi_handlers:
                raise MethodNotAllowedException()
            return asgi_handlers[scope["method"]]
        return asgi_handlers[ScopeType.WEBSOCKET]

This method simply uses data in the scope object and the node that was returned by the previous method call, to determine the correct handler key to retrieve - i.e. if its an @asgi function, it will use the ScopeType.ASGI, if its an http route it will use the method from scope (e.g. GET) and otherwise it will default to WebSocket. If a key error is raised, this is translated into a 404.

Summary

So as you can see above route resolution happens using a tree structure. The advantage of this approach is that route handlers are grouped in nodes, or branches, with shared path components serving as prefixes.

This scales horizontally (number of total routes) a lot better than regexes and is a good datastruture for handling addresses and urls. It does not scale so well when there are a lot of url parameters involved, because this requires a lot of traversal. Still, all in all I assume that the most applications will not have a huge number of url parameters and will tend to have more routes than complex urls.

I tried to make this as efficent as i knew how using python. Still, the traversal of the paths is limited by the runtime speed of python. This can probably be enhanced using a native binding, but I cannot say how much etc.

[peterschutt]

Wow @Goldziher - that's comprehensive! I'll take the time to review when I have some time and if I have any questions I'll ping you in discord.

Cheers.

[Goldziher]

@vrslev read up my explanation above, it will clarify the code you were looking at

[vrslev]

Thanks!

[egelja]

I think I might want to give a crack at this.

Which do you think would be better, making this part of starlite or placing the tree code in a serperate repository? Additionally, do we want to just use straight C++ classes with something like PyBind11, or use Python.h with C for better performance at the expense of some readability?

Here are some example Radix trees: Rax and radix_tree.

[Goldziher]

I think I might want to give a crack at this.

Which do you think would be better, making this part of starlite or placing the tree code in a serperate repository? Additionally, do we want to just use straight C++ classes with something like PyBind11, or use Python.h with C for better performance at the expense of some readability?

Here are some example Radix trees: Rax and radix_tree.

Go for it.

How drastic will the perf difference be? If it's small, say 10-20 percent, I'd say maintainability is paramount and thus c++ would be better.

Please use the same repository. We will need to create a testing setup for this code as well I guess.

[Bobronium]

Could you give some insights on why you're leaning towards C++ and not Rust? The later seems like a default modern choice now and I'm surprised to see that it's not.

For example, orjson is written in Rust so is pydantic-core.

Rust is growing in popularity and I often see it as C++ substitute. So doesn't it make more sense to use it?

[peterschutt]

I think it's just byproduct of the domain knowledge of the people sticking up their hands to have a crack at it.

No bias against rust, nor any requirement that we only make one implementation before we lock something in.

[nramos0]

I'll give writing the bindings in Rust a shot.

[Dr-Emann]

To clarify, I'm envisioning something like:

AnyRoute = Union[WebSocketRoute, ASGIRoute, HTTPRoute]

class RouteMap:
    def __init__(self): ...

    def add_routes(self, routes: Collection[AnyRoute]): ...

    def resolve_route(self, scope: Scope) -> ASGIRoute: ...

implemented as a compiled extension. Does that seem accurate?

[Goldziher]

To clarify, I'm envisioning something like:

AnyRoute = Union[WebSocketRoute, ASGIRoute, HTTPRoute]

class RouteMap:
    def __init__(self): ...

    def add_routes(self, routes: Collection[AnyRoute]): ...

    def resolve_route(self, scope: Scope) -> ASGIRoute: ...

implemented as a compiled extension. Does that seem accurate?

Pretty much

[Dr-Emann]

I had a go at trying to extract out such an interface in python first: https://github.com/Dr-Emann/starlite/blob/refactor_route_map/starlite/route_map.py

Unfortunately, I did find that I needed access to a Starlite instance for .static_paths and .build_route_middleware_stack() when adding routes, I added it as a param to __init__ in my code.

Is there an existing way to benchmark the routing, ideally by itself, or if not, an easy set-up?

Finally, a note about the difference between regex matching and this trie method: while the standard way of matching many regex-en against a string would be to try each regex in sequence, it's possible, depending on the regex engine, to compile a whole set of regexes together, and match on them all simultaneously, returning which one(s) matched. Given how optimized regex engines tend to be, I'd be interested in a comparison of trying to resolve the routes in that way, as well.

[Goldziher]

I had a go at trying to extract out such an interface in python first: https://github.com/Dr-Emann/starlite/blob/refactor_route_map/starlite/route_map.py

Unfortunately, I did find that I needed access to a Starlite instance for .static_paths and .build_route_middleware_stack() when adding routes, I added it as a param to __init__ in my code.

Is there an existing way to benchmark the routing, ideally by itself, or if not, an easy set-up?

Finally, a note about the difference between regex matching and this trie method: while the standard way of matching many regex-en against a string would be to try each regex in sequence, it's possible, depending on the regex engine, to compile a whole set of regexes together, and match on them all simultaneously, returning which one(s) matched. Given how optimized regex engines tend to be, I'd be interested in a comparison of trying to resolve the routes in that way, as well.

That's great!

So there is no test setup for this at present I'm afraid. And yes, testing compiled regexes is a good idea .

[nramos0]

I've ported the logic for the route map to a Rust extension very directly using the same trie method, but with a Rust struct containing HashMaps and HashSets to represent each of the attributes in the original Python node. The code is available at my fork of Starlite here.

The code passes all pytest tests, but I haven't benchmarked it vs the original implementation, I think maybe I can work more on that part soon / others can jump in and help? I believe the route map code is translated more or less correctly, but please take a look as well and let me know if there are any issues with it.

As for the package/release side of things, the Rust-Python interop uses PyO3, and builds with Maturin. I added an empty build script (though I'm not sure if it's necessary?) and set it up to run in pyproject.toml. Running maturin build in a Poetry shell will output different python version / platform-specific wheels for the extension to ./target/wheels, so maybe there is a way to directly include these in the end package through Poetry, but I'm not familiar with the settings for that so I didn't spend more time looking for it.

One potential issue with the current Rust implementation is that it needs handles to the function parse_path_params and types HTTPRoute, WebSocketRoute, and ASGIRoute, so they need to be directly passed in when calling Rust. I'm not sure if PyO3 has a simpler way to do this. For exceptions, there is a simple macro that can pull them in directly from the Python world.

The Python interface for the route map is here. Please let me know if there are any issues / things that need to be added.

[Goldziher]

I've ported the logic for the route map to a Rust extension very directly using the same trie method, but with a Rust struct containing HashMaps and HashSets to represent each of the attributes in the original Python node. The code is available at my fork of Starlite here.

The code passes all pytest tests, but I haven't benchmarked it vs the original implementation, I think maybe I can work more on that part soon / others can jump in and help? I believe the route map code is translated more or less correctly, but please take a look as well and let me know if there are any issues with it.

As for the package/release side of things, the Rust-Python interop uses PyO3, and builds with Maturin. I added an empty build script (though I'm not sure if it's necessary?) and set it up to run in pyproject.toml. Running maturin build in a Poetry shell will output different python version / platform-specific wheels for the extension to ./target/wheels, so maybe there is a way to directly include these in the end package through Poetry, but I'm not familiar with the settings for that so I didn't spend more time looking for it.

One potential issue with the current Rust implementation is that it needs handles to the function parse_path_params and types HTTPRoute, WebSocketRoute, and ASGIRoute, so they need to be directly passed in when calling Rust. I'm not sure if PyO3 has a simpler way to do this. For exceptions, there is a simple macro that can pull them in directly from the Python world.

The Python interface for the route map is here. Please let me know if there are any issues / things that need to be added.

First off - many thanks.

It seems there are now two possible implementations in place.

What I suggest is that you add a PR with your changes.

We will review it, and get it merged into a special branch in Starlite other than main. This will our baseline for the rust bindings and we can then then work on benchmarking.

We need build scripts and unit tests as well.

What do you guys think? @Dr-Emann @nramos0 @peterschutt

[egelja]

I think I might want to give a crack at this.

Which do you think would be better, making this part of starlite or placing the tree code in a serperate repository? Additionally, do we want to just use straight C++ classes with something like PyBind11, or use Python.h with C for better performance at the expense of some readability?

Here are some example Radix trees: Rax and radix_tree.

Here's my implementation (in C): https://github.com/MrAwesomeRocks/starlite/blob/NinoMaruszewski/issue-177-c-bindings/starlite/routing/.

The pure-python part (route_map.py) is done, the C implementation is still WIP.

[Goldziher]

I think I might want to give a crack at this.

Which do you think would be better, making this part of starlite or placing the tree code in a serperate repository? Additionally, do we want to just use straight C++ classes with something like PyBind11, or use Python.h with C for better performance at the expense of some readability?

Here are some example Radix trees: Rax and radix_tree.

Here's my implementation (in C): https://github.com/MrAwesomeRocks/starlite/blob/NinoMaruszewski/issue-177-c-bindings/starlite/routing/.

The pure-python part (route_map.py) is done, the C implementation is still WIP.

Thanks @MrAwesomeRocks. We will be going with Rust though, and work on the open PR as a basis. It's the best course of action for two reasons- 1. That implementation has a complete draft, and 2. Rust is easier to maintain for us in the long run and is as such future proofing.

You're welcome to chime there if course.

[Goldziher]

It appears that there is not sufficent benefit from this.

[winstxnhdw]

It appears that there is not sufficent benefit from this.

What happened here?

[JacobCoffee]

@winstxnhdw If this is what I remember from what I understand, the decision not to switch this part of the codebase to Rust, et. al., was based on several factors:

• At that time, there weren't many developers proficient in Rust available to contribute.
• Such a change would have introduced new complexities and increased the maintenance burden on current maintainers/contributors.
• The performance gains were not (might not have been?) significant enough to justify the switch.

[provinzkraut]

The performance gains were not (might not have been?) significant enough to justify the switch.

To expand on this: This still holds true today. The performance impact of the routing layer is negligible, and due to the nature of the router's architecture (radix based vs. prefix + regex map), it scales very well with a large number of routes as well. There's simply too little gain for too much effort.

[winstxnhdw]

Do you happen to remember what the performance gain of the Rust-based router was? Was it only on the order of a few milliseconds on a few hundred routes or path parameters?

[Dr-Emann]

I don't remember the specifics of the difference between the rust/python stuff, but I think I remember something along the lines of after profiling how much time is taken by the router part as part of benchmarks, and it was something like even if we reduced the time taken by that part to 0, it would have made less than a 1% difference in total time or something.