perf: use a binary search for insertMatcher

skirtles-code commented 7 months ago

Inspired by #2132 and #2136, I had a go at speeding up insertMatcher().

The ordering algorithm

This PR changes insertMatcher() to use a binary search when trying to find the appropriate insertion point for a new matcher. This seems to give a similar performance gain to #2136, but without changing the public API for Vue Router.

When I first opened this PR, I noted some assumptions I'd made about the sort order. Some of those assumptions turned out to be incorrect, so the current changes proposed here are a little different from what I had originally.

I've written a lot of extra tests to check that the sort order hasn't changed, especially in the weird edge cases. Those tests aren't included in this PR. I did open #2138 to add a couple of them, but Eduardo didn't seem keen to merge those tests. I suspect he'd be even less enthusiastic about some of the others. :smile:

I believe the new sort order is equivalent to the old sort order, in the sense that the same paths will resolve to the same routes. I'm only aware of one exception to that, which I'll outline later.

The new ordering works roughly like this:

Route matchers are primarily ordered by their score. This is always the top priority.
If descendants and ancestors have the same score, descendants must come before ancestors.
The new matcher should be inserted as late in the list as possible, given the constraints above.

The algorithm to achieve this goes through two phases:

The first phase uses a binary search to try to find the insertion point based on the score. Existing matchers with the same score should come before the new matcher. If the new route doesn't have a parent then this is the point it will be inserted.
If the new route does have a parent then we enter phase two. This checks the new route's ancestors, to see whether any of them have the same score as the new route. Usually they won't. But if they do, we find that ancestor in the list and insert the new matcher immediately before it. Phase 1 is still valuable, as the relevant ancestor will always come before the point found in phase 1. In practice, the relevant ancestor is usually very close to the point found in phase 1, so phase 2 will find it very quickly.

That second phase requires the ancestors to be in the matchers array before the children are added. For that to work, I had to move the insertMatcher() call in addRoute() to come before the recursive calls to addRoute() for the children.

To put that another way, previously the insertMatcher() calls for the children would happen before the insertMatcher() call for the parent. This automatically led to children coming before the parent in the matchers array (assuming equal scores). I've changed the order of these calls, but the order of the matchers array should still be the same.

In addition to testing performance with the benchmark from #2136, I also used my own script that included some of the more advanced route matching features: https://gist.github.com/skirtles-code/5fc5dc24f51d7132119365d0646c140f.

'Breaking changes'

I'm using the term 'breaking changes' very loosely here. I don't think any documented behaviour is broken, but there are some changes to undocumented behaviour that could (at least in theory) break people's applications. I don't think any of these cases is actually worth worrying about, but I also don't think it helps to keep them secret.

The 'breaking changes' only occur when calling addRoute() directly. If routes are configured via the routes option then everything should behave as before.

Specifically, the difference occurs when adding a child route with addRoute(), if that child route has the same score as one of its ancestors. Here is a (somewhat convoluted and contrived) example that demonstrates the current behaviour:

Playground

The example shows two routers, router1 and router2. router1 specifies all the routes in the initial config. router2 only specifies the parent route, then adds the child later using addRoute(). Notice how this leads to different outcomes. With router1, the child route is given priority, whereas with router2, the parent route is given priority.

The reason this happens is that parent/child relationships aren't explicitly considered. With router1, the route in children is inserted first, then the parent, so the child gets priority. With router2, the parent gets added first, then the child, so the priority is reversed.

The one common case where this arises is for path: '' on a child. There is special handling in the current insertMatcher() to handle that specific case.

With the changes I've proposed here, using addRoute() to add a child would change to behave the same way as the children option. So router2 would now yield the same ordering as router1. I think this is more intuitive than the current behaviour. A consequence of this is that there's no longer any need to make path: '' a special case, we get that automatically.

But while the new behaviour seems more consistent in the previous example, there are other cases where it could appear less consistent. For example:

Playground

In this example, router2 and router3 both behave the same way, resolving /a/b to the route other. They differ from router1, but at least they're consistent with each other.

With the new behaviour, router3 would now be consistent with router1, resolving /a/b to the route child. Why? Because in router3 the parent route has the same score as its child, so the child is inserted before the parent, leapfrogging ahead of the route other.

To reiterate, I'm not saying these examples show important, real-world use cases. But I think they help to better understand what has changed. Perhaps they'll help to identify other use case that actually are important.

Further work

While the changes here are separate from the changes in #2148, it is worth noting that they would impact each other. That change splits up the matchers array into a tree structure, based on the static parts of the path. In that context, each tree node has its own array of matchers. There's still a need to find the right insertion point, but only matchers with the same static prefix would be considered. Importantly, ancestors can potentially have different prefixes from descendants, even with the same score, so 'phase 2' of the algorithm proposed here would only apply to matchers with the same prefix. Again, I believe this only makes a difference in some of the weird, undocumented, edge cases, such as the leapfrogging example I gave earlier.
I think this PR needs some tests adding. As mentioned earlier, I have already written some tests, but I'll hold back on trying to add them for now. If the changes I'm proposing here are deemed acceptable, I'll do some further work to decide which tests are worth adding.

netlify[bot] commented 7 months ago

Deploy Preview for vue-router canceled.

Name	Link
Latest commit	87320b738b21f6289f5ac79e4e0762ba32c8584d
Latest deploy log	https://app.netlify.com/sites/vue-router/deploys/6666fcca62dd9d000839dcb3

codecov-commenter commented 7 months ago

Codecov Report

Attention: Patch coverage is 92.30769% with 2 lines in your changes missing coverage. Please review.

Project coverage is 90.96%. Comparing base (d6d4dd3) to head (87320b7). Report is 5 commits behind head on main.

Files	Patch %	Lines
packages/router/src/matcher/index.ts	92.30%	1 Missing and 1 partial :warning:

Additional details and impacted files

```diff @@ Coverage Diff @@ ## main #2137 +/- ## ========================================== - Coverage 91.01% 90.96% -0.05% ========================================== Files 24 24 Lines 1135 1151 +16 Branches 351 355 +4 ========================================== + Hits 1033 1047 +14 - Misses 63 64 +1 - Partials 39 40 +1 ```

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

vuejs / router