Methods relative() and isWithin() should be faster when work with absolute paths

[scheglov]

@munificent @nex3 @bwilkerson

I tried to rollback our AbsolutePathContext and switch to package:path version 1.3.7.
Unfortunately it is still slow.
As you can see, it uses about 30% of total analysis time.

For comparison, with our AbsolutePathContext the method isWithin is barely visible.

[scheglov]

I know that package:watcher is a separate problem, but I just want to give you some additional numbers, because they may be interesting in the context of package:path.

Even with our AbsolutePathContext we have some significant use of package:path, accounting for about 12% of total time.

BTW, the difference before the previous and this performance profiler is cause by the fact that I turned off our internal logging. Most of the users don't have it on, so that's what they see.

[nex3]

Can you provide some example arguments that you provide to relative() and isWithin()?

[scheglov]

relative() is mostly called from isWithin() with the arguments as in the attached file.

The rest is called from package:glob with the similar set of second argument paths and patterns like samples/** and lib/_templates/**.

package-path-samples.txt

[munificent]

Thank you for filing this bug! Details like this are really helpful when optimizing.

[nex3]

@scheglov Does the performance improvement from my latest patch meet your needs? I benchmarked it as about 11.5x faster on the data you provided.

[scheglov]

When I upgrade to the version 1.3.8, and reimplement AbsolutePathContext using the path package, I see 30% performance loss. The analysis time goes up from 3000 ms to 4000 ms. The functions isWithin and relative consume a significant part of the total analysis time.

I will e-mail you the complete list of parent/child pairs used for isWithin.

[nex3]

30% relative to path 1.3.7, or relative to the current implementation of AbsolutePathContext? We're never going to be able to match AbsolutePathContext's performance, because its functions sacrifice correctness for speed and that's not a bargain the path package can make.

[nex3]

That said, looking at your test data, it looks like we're not hitting the fast track when one of the paths contains /., including situations like path/.pub-cache. That's definitely something we can improve.

[scheglov]

The whole analysis time is 30% more than with the current implementation of AbsolutePathContext.
This mean that the path package itself is much slower than AbsolutePathContext.

We cannot sacrifice so much performance just because path cannot be fast. Why would we check and recheck whether the given paths are absolute and don't have .. when we already know this? The fastest code is the code you don't need to execute at all.

That said, I still don't believe that the current path implementation is the most optimal one.
It's not even close to this. For example I don't believe that we need to use isRelative and split to implement isWithin for absolute paths.