Closed andrewjsaid closed 6 months ago
+@javiercn @JamesNK you two are familiar with routing
I know what the ILEmitTrie does but I've never touched it. From looking at the file history, no one has made significant changes to it since @rynowak wrote it years ago. Snaps for Ryan.
If the tests all pass and perf is good then we're halfway there. I'd like to get someone to double check the vertorized path. I don't have enough expertise to review code and offer an opinion.
What should think about:
@andrewjsaid Go ahead and create a PR. We should have discussion in the PR.
There are rules about what jump table to create. There is a check that prefers a dictionary jump table over a trie above 100 items. Should this change?
I can probably provide some degree of feedback on topics like this in the PR. Unfortunately it's all from memory because I didn't work on this code much after the original version 😓
The good news is that I think the stakes probably pretty low. Most of the decisions like the switch between emit and dictionary were made empirically based on the benchmarks. So if the benchmarks change then the breakpoints should change too.
Binary search wasn't something I thought of while building the original version. Compared to the previous version of routing all of this work was in a different galaxy perf-wise 🪐 . Most of my time was spent worrying about overhead in the N == 1
case.
Is the new generated IL significantly larger? There can be a lot of trie jump tables so we need to keep its size in check
I think @JamesNK raises a good point about code size. Changing the complexity to log(N)
means that the emit approach will scale to a higher breakpoint (where dictionary becomes better) than the linear version. We may not want to make this decision solely based on the throughput. In my anecdotal experience a "big" node of the routing tree has 10+ branches, not hundreds or thousands so cases that would result in big tries aren't that common.
The proposal here is that we can improve
ILEmitTrie
by using binary search instead of the linear search we currently do for both finding the length as well as the vectorized search.This improves the MicroBenchmarks as follows:
Implementation in https://github.com/andrewjsaid/dotnet-aspnetcore/pull/1. The PR template implied I had to first create an issue before the PR so I did so. Please let me know if design makes sense I can then point the PR to here for detailed code review.
In the linked PR you can see the changes are:
Before
After