Adding many routes to CompiledRouter is slow (takes O(n^2) time)

[fengyong]

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

_{Sent with GitHawk}

[vytas7]

Hi @fengyong !
And thanks for reporting the issue.
Indeed, the default CompiledRouter is recompiling all the routes upon adding a new one, and as such it has at least O(n^2) complexity.

In my test, adding 400 routes takes about 4 seconds, which could probably be still acceptable for some cases? OTOH I realize that may render unit tests unusable slow, as well as one would eventually hit the limit of what is reasonable with even more routes.

Potential solutions:

• Register/inspect the amount of routes already added, and compile in a check to defer compilation to the first routing in case the number of routes is larger than threshold. Recompiling would remove this check, so it would have no implications on performance. Care would need to be taken of handling the first request in a thread-safe manner.
• Allow adding more routes at once, add_routes, or similar

[fengyong]

i fixed this by add a patch, it works great, but ugly, i wish there will be a better official version
1 preserve origin falcon_compile and set_error_serializer
2 nullify the compile action.
2 wait until a proper time : after calling 'set_error_serializer' , then original falcon compile:

it only takes 2 lines if directly modify falcon's source code, but it need to deliberate the side-affects.

def __do_nothing(self):
    pass

def __reset_falcon_find(self):
    self._find = self._compile()


import falcon

origin_falcon_compile = falcon.routing.compiled.CompiledRouter._compile
origin_set_error_serializer = falcon.api.API.set_error_serializer

#disable _compile to save time
falcon.routing.compiled.CompiledRouter._compile = __do_nothing
falcon.routing.compiled.CompiledRouter.__reset_falcon_find = __reset_falcon_find


def wrapper_set_error_serializer(self, serializer):
    falcon.routing.compiled.CompiledRouter._compile = origin_falcon_compile
    self._router.__reset_falcon_find()
    return origin_set_error_serializer(self, serializer)


falcon.api.API.set_error_serializer = wrapper_set_error_serializer

[fengyong]

4 seconds for 400 routes is acceptable in fact.
It just weaken the reputation of python or hug or falcon. somebody who is not familar with python/falcon will say " python/hug is so slow, we should consider migrate to other languages/framework, like golang".
this kind of misunderstanding really happened a lot.

Hi @fengyong !
And thanks for reporting the issue.
Indeed, the default CompiledRouter is recompiling all the routes upon adding a new one, and as such it has at least O(n^2) complexity.

In my test, adding 400 routes takes about 4 seconds, which could probably be still acceptable for some cases? OTOH I realize that may render unit tests unusable slow, as well as one would eventually hit the limit of what is reasonable with even more routes.

Potential solutions:

• Register/inspect the amount of routes already added, and compile in a check to defer compilation to the first routing in case the number of routes is larger than threshold. Recompiling would remove this check, so it would have no implications on performance. Care would need to be taken of handling the first request in a thread-safe manner.
• Allow adding more routes at once, add_routes, or similar

[kgriffs]

I think it would be reasonable to set a flag that delays code generation until the first call to find(). It seems unlikely that a large number of routes would be added after the first attempt to match a route, except perhaps once in a while in a testing context.

[CaselIT]

As an alternative the every time a new route is added to the router self._find could be set to

def _compile_and_find(self, *args):
    self._find = self._compile(...)
    return self._find(*args)

so that it will compile only on the first call. This would also avoid the condition to check if a compilation is need in the find method

[CaselIT]

I've tried creating a poc at #1665. By delaying compilation 400 routes are added in 50 ms