Improve GoToRelevantFile performance

[jenny-codes]

Description

Ruby LSP Information

Parent issue #2966

The GoToRelevantFile function added in #2985 works well with small size repos, but it has a noticeable lag when used on a larger codebase.

Benchmark measurements on the shopify core codebase on my machine

(In order: user CPU time, system CPU time, the sum of the user and system CPU times, elapsed real time)

  0.875498   0.938839   1.814337 (  2.438297)
  0.204476   0.908439   1.112915 (  1.319023)
  1.396747   1.401042   2.797789 (  3.252911)
  3.044789   4.278284   7.323073 (  6.205184)
  2.496724   4.009404   6.506128 (  5.499605)
  2.575118   4.419145   6.994263 (  5.775319)
  2.427883   3.813284   6.241167 (  5.337139)
  2.646134   3.806451   6.452585 (  5.554977)
  1.610006   3.839775   5.449781 (  4.531290)
  3.278136   4.539844   7.817980 (  6.581827)

Different random file are used each time. This is the measurement of the time it takes to run the GoToRelevantFile#perform only.

[domingo2000]

I provided an idea on how this could be optimized without chaning the strategy for finding relevant files that much. The idea is in this PR. ¿Do you have any feedback or other ideas?

[github-actions]

This issue is being marked as stale because there was no activity in the last 2 months

[vinistock]

Hello, @domingo2000! Thanks for putting up the proposal. While the implementation works well, the team would prefer going a simpler route first to avoid the cost of adding more indexing items at the time.

I think the biggest portion of the problem is that the glob pattern we're using will always search the entire repository, which is not necessary to find related files. For example, imagine that you have a large application split by different engines.

engines/
  blog/
    app/
      models/
        post.rb
    test/
      models/
        post_test.rb

  ...other_engines

If we are searching for related files either in post.rb or post_test.rb, it is not relevant to search every single engine in the repository since the related file can only be present within the root of the engine or component itself. Currently, we are always searching the entire repository, which I believe is where the major part of the slow down comes from.

We can instead try to always scope our glob searches based on the parent of the closest test directory, considering that as the root to search for related files. It's unlikely that related files are going to be further away in the file hierarchy, so this greatly reduces the scope of the search and will probably improve performance by a lot.

What do you think? Let me know if you want to take a stab at that approach.

[domingo2000]

I think the idea is good, specially because that will reduce the time usage of the glob, and finding the common ancestor root should not be costly. This also works for packwerk packs folders. I can give it a try implementing that aproach in the next weeks.

[domingo2000]

@vinistock better late than never.

I implemented the tree walking strategy as you suggested in this PR. Now the swap between implementation and test file is instant. Manually tested on the ~27K ruby files Buk Webapp project. Also tried the improvement in rails repository and rubocop repository and it seems to work well.

Happy to receive feedback on this.