Sorting by number of childrens is not usefull
chmike opened this issue · 2 comments
I implemented a simple radix tree and did some tests. Based on my benchmarking tests, this algorithm is so fast that sorting doesn't make any significant difference. I would suggest you reconsider sorting by number of children.
What might show a difference is to put expensive tests last. So static path segments first, parameters without regex next and parameters with regex last. Sorting in this order needs only to update the modified children array.
I like to take the opportunity to congratulate you for the remarkable performance of your routing package. The no surprise is perfect too. Thank you.
Merci également ! 🙏
Most subnodes on top = most handlers on top = more chances to match a request earlier.
That was my trivial logic.
Concretely, I loose ~30 ns in the BenchmarkFindRoute test without this sort.
Not a big difference; but as we talk raw performance, it's still a loss.
And the sort is only done at the beginning, while making the tree, not at serve time.
So there are only benefits. Don't you think so?
What might show a difference is to put expensive tests last. So static path segments first, parameters without regex next and parameters with regex last.
Putting regex nodes at the end will make them unreachable: the parameter without regex will match all values.
As for the static nodes, they are already on top.
I should check my own benchmark then. :)