Improve router performance

[iceboy233]

We found out that aiohttp's router performance is very slow.

In our webapp, there are currently 127 routes. If we delete all routes except main page, the performance is 2544qps. After restoring all routes, the performance becomes 1727qps. Test is done on a MacBook with single process.

We could implement tree-based routing which should have good performance in most real-world case, or implement an NFA-based router for optimal performance.

[jettify]

Interesting, i have couple questions, your main page route is on top of routing table? Do you have any regex routes?

[iceboy233]

The main page route is in the middle of the routes. There are a couple of regex routes.

[asvetlov]

@iceboy-sjtu personally I have no plan to work on the issue in the nearest future.
But you may try to implement router improvements on your own.
Since Application accepts router parameter (http://aiohttp.readthedocs.io/en/stable/web_reference.html#aiohttp.web.Application) you even don't need to monkey-patch aiohttp!
If you'll get impressive results let's return to the topic.
I'm open to routing improvements but now I'm concentrating on other issues.

[nitely]

Not a dev here, but I was looking for a particular issue and stumbled across this one.

@iceboy-sjtu I built a Trie based router just the other day, it may be useful as inspiration to implement something similar for aiohttp.

[iceboy233]

@nitely Well, we use router.url() heavily, which composes url by route name and keyword arguments. It seems that your router doesn't have this mechanism.

[nitely]

@iceboy-sjtu It does not, it would be trivial to implement that on top of it, though. However, reading your first post I thought you were thinking of implementing a trie router from scratch, that's why I mentioned that router at all.

[asvetlov]

url generation is really trivial.
The tricky part is supporting variable routes like router.add_get('/{:.+}', handler) with keeping route ordering.

[nitely]

Keeping the current API would be tricky indeed, but doable.

Last node of the Trie has the Router handler (variable param names and the handler/callback/controller), that can be replaced by a list of Routers (ie: clashing URLs) and each Router would have the regexes, then you can check URL variable parts for each regex pattern, if it does not match then try the next one, if all fail then try next Trie branch. So the only thing to implement would be the regex matching logic, everything else is already taken care of.

This would handle a case like:

router.add_get('/{:\d+}', handler)
router.add_get('/{:.+}', handler)

# and

router.add_get('/{:.+}', handler)
router.add_get('/{:\d+}', handler)

# Although the second handler will never match

But it breaks behaviour in a case like:

router.add_get('/{:.+}', handler)
router.add_get('/foo', handler)

In the current implementation there is no way to reach the second handler because the first one always matches (I think, did't try it though). In the Trie router, static parts take precedence, so https://whateves.com/foo will actually match, however I would argue both behaviours are undesirable.

[asvetlov]

No, for sake of backward compatibility we should keep ordering.
Think about:

router.add_get('/{:bar.+}', handler)
router.add_get('/foo', handler)

[fafhrd91]

'router' should be replaceable. I'd just create aio libs project and over time we could move it into aiohttp

[asvetlov]

@fafhrd91 please don't rush.
aio-libs assume a maintenance burden, but keeping alternative router means constant work.
If you want to experiment -- please do it in your own repo.

I believe trie is not the only possible implementation, maybe we can invite something without breaking backward compatibility. Say, joining all regexps together into super-expression may improve performance very well, but we need to test it.

But I want to publish aiohttp 1.0 first.

[nitely]

@asvetlov Yeah, if you want to keep that behaviour, Trie is not the way to go IMHO.

joining all regexps together into super-expression may improve performance

Yes, actually that would be a good approach [0].

[0] http://nikic.github.io/2014/02/18/Fast-request-routing-using-regular-expressions.html

[fafhrd91]

I am more about how to prove idea, that's it. I personally never had situation when aiohttp is the bottleneck

[iceboy233]

joining all regexps together into super-expression may improve performanc

It seems that python's built-in re module does not support the "?|" extension.

[asvetlov]

>>> re.match(r'(^/path/(?P<to>\w+)$)|(^/other$)', '/path/to').lastindex
1
>>> re.match(r'(^/path/(?P<to>\w+)$)|(^/other$)', '/other').lastindex
3

[iceboy233]

Tried the approach in [0]. It doubles (3000->7000) the performance when there are 100+ routes and the handlers are trivial. Also looking at r3.

[iceboy233]

Created aiohttp-r3 to use r3 :)

[fafhrd91]

pretty cool. I would deprecate aiohttp's path dispatcher, in favor of something like this.

[iceboy233]

Although r3 seems to be already used in many places, I found bugs in both 1.3.4 and 2.0 branch (c9s/r3#99, c9s/r3#100), and it lacks feature for static files and url reversing.

r3 is a random pick. Are there any other libraries that worth a try?

[fafhrd91]

I just want to say, I do not want to maintain code if we can find good alternatives

[lock]

This thread has been automatically locked since there has not been
any recent activity after it was closed. Please open a new issue for
related bugs.

If you feel like there's important points made in this discussion,
please include those exceprts into that new issue.