A fAST new router

If you have read anything I have written about routing, you will know that I am somewhat frustrated by Sanic’s router for some time now. I have been itching to replace it. The problem is how? There are a few solutions out there.

@vltr went through a great exercise a couple years ago to benchmark various solutions: https://github.com/vltr/very-stupid-simple-routers-bench


  • Falcon is fast
  • xrtr is fast
  • Kua is not so impressive
  • Routes … No offense to the contributors, but I don’t understand by what basis they call it “Speedy”


First, let’s go through some of the mechanisms (ignoring Kua and Routes).


Sanic’s router works by regex. Basically it groups routes into a few buckets (example, do we need to pull params out of the path?), chooses the right bucket of routes, then loops through them stopping on a regex match.

This provides for a somewhat varied performance. Regular expressions have had a history of performance issues in Python. It has, to be fair, improved in recent Python releases. That aside, routes that are defined early will be faster to match than those defined later. More routes leads to performance decrease.

Perhaps one of my biggest complaints is that it needs to be called repeatedly in Sanic, and leads to a low level of flexibility.

One thing that it does to well, is make use of lru_cache so that when it sees the same URL again, it does not need to reevaluate.


The strategy employed by Falcon is interesting. Basically at run time it analyzes all the routes that have been added and generates a dynamic function (somewhat AST-like) that looks something like this:

def find(path, return_values, patterns, converters, params):
    path_len = len(path)
    if path_len > 0:
        if path[0] == 'foo':
            if path_len > 1:
                fragment = path[1]
                field_value = converters[0].convert(fragment)
                if field_value is not None:
                    params['id'] = field_value
                    if path_len == 2:
                        return return_values[0]
                    return None
            return None
        return None
    return None

Basically it is just a bunch of if statements. It is very efficient and very fast. It does slow down a bit when you need to start adding type conversions, and when doing multiple calls. It also does not appear to be capable of handling domain or header based routing.


This is a package that has been a work in progress by @vltr. The idea was to build a router using Cython. It is fast and flexible (it can handle routing of more than just URLs). It outperforms every other implementation, and can be a solid choice where appropriate.


This is a project that I started working on a few years ago to leverage hyperscan (the ridiculously fast C based regex engine). It is fully compatible with the styling and type conversion of the existing Sanic router, which none of the other solutions are. It works out of the box as a drop in replacement for Sanic.

It also is as fast as xrtr. But, because it uses hyperscan, it is not Windows compatible. It will remain for now as an unreleased repo on my machine.


In my recent post on RFC #1630, I am working on the signal implementation. One thing that I am working on requires signals to be routed to handlers. The existing Sanic router cannot handle this. So, I came back to the idea of perhaps building a new router that could do multiple types of routing.

With the urging of @vltr, I went back to the approach by Falcon and used it as inspiration. The idea I came up with:

  • Handles static routes (no params in URL) faster than any other solution out there
  • Is pure python
  • Can route based upon headers, domains, or ANYTHING else you want
  • Does not slow down for type conversion
  • Does not slow down based upon size and number of endpoints’
  • Leverages lru_cache
  • Fully compatible with Sanic as a drop in replacement with fairly minimal integration

Here is a benchmark I did.

New AST Router executed (new_router) for 50000 times in 0.016282 seconds
New AST Router best time was 0.000000 seconds

hyprtr Router executed (hyprtr_router) for 50000 times in 0.032355 seconds
hyprtr Router best time was 0.000001 seconds

xrtr Router executed (xrtr_router) for 50000 times in 0.038492 seconds
xrtr Router best time was 0.000001 seconds

Sanic Router executed (sanic_router) for 50000 times in 0.056148 seconds
Sanic Router best time was 0.000001 seconds

Falcon Router executed (falcon_router) for 50000 times in 0.148959 seconds
Falcon Router best time was 0.000003 seconds

What is telling about this test is that:

  • There are 100 routes per router.
  • They are testing against a dynamic route (need to grab params from route, therefore slower)
  • Type conversion, so that the params are cast to a specific type
  • Multiple calls to the router per test

I am thinking that I will create a repo on GitHub/huge-success to play around with it. But, I am getting excited that we may have a direction for replacing the existing Sanic router, and a tool for building out the signals API.

Name suggestions?


How to access New AST Router code? It looks very promising.

I’ll post it later today on GitHub and provide a link.

I’m glad you did this.

1 Like

Here is the POC: https://gist.github.com/ahopkins/9b91b950c94c1bc3c24df741b7fb02ef


Hey , I run Your code and It was a great experience to learn and understand experienced python developer’s thought of coding
but I run into some problems if add another route like:
router.add(“id:uuid/num:int”, handler4, “get”)
also I couldn’t understand why would generate find_route method …?!
I would appreciate your response ,thnx

Hi hamzabouissi !
I’m try to understand @ahopkins 's ast Router code, It’s quite complex on code generating part, the find_route method. But I may answer the question.

I tried add router.add(“id:uuid/num:int”, handler4, “get”) and print(self.find_src) before compiled_find = compile(self.find_src, "", "exec",) and get the genrated code:

def find_route(path, router, extra, basket):
        return router.static_routes[path], None
    except KeyError:
    parts = path.split(router.delimiter)
    num_parts = len(parts)
    if num_parts > 0:
        if parts[0] == '':
            if num_parts > 1:
                basket[1] = parts[1]
                if num_parts > 2:
                    if num_parts > 2:
                        basket[2] = parts[2]
                        if num_parts > 3:
                            if num_parts > 3:
                                basket[3] = parts[3]
                                if num_parts == 4:
                                    return router.dynamic_routes['/<foo:string>/<id:uuid>/<num:int>'], basket
                                raise NotFound
                            raise NotFound
                        raise NotFound
                basket[1] = parts[1]  # something goes wrong here
                elif num_parts > 2:
                    if num_parts > 2:
                        basket[2] = parts[2]
                        if num_parts == 3:
                            return router.dynamic_routes['/<id:uuid>/<num:int>'], basket
                        raise NotFound
                    raise NotFound
                raise NotFound
        raise NotFound

Python won’t allow any code betwenn if and elif in the same indention.
since the method either return the result or raise the exception within a if block, could we change elif into if?

I can’t expalin why would generate find_route method very well.

The method split a dynamic url into many parts with /, and then match each part in if statement, It will raise earlier when the static part won’t match compare to the origin implementation Sainc Router. More route is added more if statement is generated.

  1. What is the purpose of requirement param in Route class ?

  2. The REGEX_TYPES seems to be fixed. Could I write my own regex in a dynamic url? such as email?

  3. I can’t figure out the meaning of if statement below, I thought __depth__ always eaquls to level + 1, Did I miss something?

        if is_last:
            retval += [(indent + 2) * TAB + f"raise {self.exception.__name__}"]
            if branch["__depth__"] == level + 1:  # TODO: What does this if mean? 
                retval += [(indent + 1) * TAB + f"raise {self.exception.__name__}"]

:blush: If you could learn anything from that mess of code… not exactly a paradigm of clarity, more like a scratch pad.

Yes, it needs some work. This is no where near ready to be implemented. It is meant mainly as a proof of concept. The idea behind it works and is performant. The next thing to do is really hammer out the best way to build the AST.

Not 100% sure I understand the question. Let me try, and if I am do not answer, please let me know.

The idea behind this is that Python’s regular flow control with if/else is incredibly fast. Even if it is extremely basic, traversing through a complex web of finding a route is basically just like following a flow chart. If A, follow this course, if B, follow that instead.

So, the idea is to perform some analysis at run time and dynamically generate that code. I did it with simple strings, but Python also has an AST library that could be used to run this at server startup.

1 Like

Yes. This being a first crack at it, the implementation is far from complete or being without mistakes. I had identified that mistake after posting it, and am working on other ways to correct it. There probably needs to be a lot more context per URL part. I tried to keep it super simplistic, but might need to beef it up a little to handle more complex edge cases. This should not impact the overall performance, at request time. The extra work would be up front at startup.

This is to add additional controls to routing. In particular: domain based, and header based.

For example, if you have multiple domains going to the same Sanic instance, you could seperate some of the routes based upon the domain.

router.add("/foo/3", handler3, requirements={"domain": "foobar.com"})

This is also because I want a single router that is capable of also being used in the Signals RFC. I have some thoughts on how we can implement this, and it would also need a router. Having the requirements adds another level of flexibility for implementing with various applications.

Whatever implementation is decided upon, it needs to be backwards compatible on the surface of it. Meaning, if I am a long time Sanic user, I would not see a difference except hopefully in performance. The internals may change, but how I define routes, should not.

To that end, there does exist this ability now. For my limited example, there was no need to build that it.

Well, yes, but in that context level is constantly changing. One thing that does have an impact on performance is trying to bail out as quickly as possible. Therefore, at every possibility where there is nothing left to evaluate, it should bail rather then waiting for higher level scopes to be completed. This is definitely something that needs some more attention as my rather simplistic approach is just that: too simplistic.

Thanks for the attention to detail on this.

Thanks for replying, I learnt a lot from this new router(specially the Ast staff)!
I can fully understand the concept there.

1 Like

First of all nice stuff @ahopkins but I don’t have much time to fully check your POC, but in the first glance it looks nice, also as a contributor of Falcon I can confirm that Falcon uses AST stuff for routing.

Am I wondering whether we did the research for that case? for example to find some Data Structure which will satisfy our needs. I have been thinking about Prefix-Tree but right now, I’m not sure that suitable for us, need to do some research. Becase in our case, we also need to handle url parameters, segments etc.

1 Like

Thanks for the heads up. I agree that the data structure here needs some consideration. One of the things that both htprtr and xrtr do for optimization is exactly that. I agree that it should be worked in here. Also, I am using a simple structure, as opposed to what it looks like Falcon does with some custom classes. Something more robust is probably needed since there is a lot of meta-data per node level that needs to be considered, and the current implementation does not take some of this into consideration to optimize the structure (which is the errors being experienced above).

and the current implementation does not take some of this into consideration to optimize the structure (which is the errors being experienced above).

No problems at all here, just want to say that for the future implementation we should keep in mind the performance/easy scaling of the router, etc.

Also, what htprtr and xrtr means?

@vltr will need to explain xrtr. I imagine “extreme router”?

hyprtr is “hyperscan router”

I have some more tests to check performance on different ways to potentially handle tries to see if it is indeed faster than nested if/else statements.

A python data struct would be much more clear for me.The AST is also great but with less readable. Although the idea of AST is blowing my mind. Great work again.

I tried a few types of simple tests that could be used with a trie.

  • control - just continue if/elif with no trie
  • anding - if parts[2] == "bar" and parts[3] == "baz"
  • concat - if parts[2] + "/" + parts[3] == "bar/baz"
  • concat_s - if "%s/%s" % (parts[2], parts[3]) == "bar/baz"
  • concat_f - if f"{parts[2]}/{parts[3]}" == "bar/baz"


Timy executed (control) for 1000000 times in 0.995399 seconds
Timy best time was 0.000001 seconds
Timy executed (anding) for 1000000 times in 0.977669 seconds
Timy best time was 0.000001 seconds
Timy executed (concat) for 1000000 times in 1.208060 seconds
Timy best time was 0.000001 seconds
Timy executed (concat_s) for 1000000 times in 1.320606 seconds
Timy best time was 0.000001 seconds
Timy executed (concat_f) for 1000000 times in 1.247579 seconds
Timy best time was 0.000001 seconds

The take away is that using a trie may ever so incredibly slightly impact performance. I am debating whether that is even worth the extra effort. 18/1000 of a second over a million runs.

Granted, this was not a super nested structure. As the complexity increases, so should the theoretical difference.

Hm, good tests, also after yesterday discussing here, I think probably AST will be slightly faster than Trie, but the readability of Trie will be fairly better.

One more important point - AST will be harder to debug.

In general - hard choice :confounded:

The question on the last one was whether to build out a trie inside the AST. :woozy_face:

I do not think the AST-based router will be too hard to debug. Clearly we need a heavy test suite against it to cover as many edge cases as possible. But, in the end it is just Python code that can be output, viewed, and run like anything else.

Yes, agree! also would be cool to hear @vltr @ashleysommer thoughts.

1 Like