Improve performance of finding indexables

[natematykiewicz]

Currently, all folders and files in the current tree are turned into IndexablePath, and then excluded files are filtered out after.

When there are large file trees that are meant to be excluded, this results in a lot of unnecessary work.

ActiveStorage stores files in the tmp directory in many many small folders. So does Bootsnap. Ruby LSP has to traverse all of these files, even though the entire directory should just be ignored.

Rubocop has solved this by breaking the includes patterns up into many patterns, applying the exclusions before the Dir.glob, so I followed in their footsteps. This works great for exclusions that end in "**/*". We still need to loop through all IndexablePath objects and see if they're excluded, in the case that an extension was provided on the excluded path, but this can cut down load time dramatically.

Before this PR in my Rails app, indexables took 76 seconds to run. Now it takes, 0.19 seconds. Before and after code both return the same exact file list.

Additionally, I added node_modules to the list of excluded trees, since that can be very large and never includes Ruby files.

I also removed the *.rb from the bundler path. Having a file extension on that means we need to scan all files. But we simply want to ignore the entire bundler path tree. I kind of wonder if we should always replace *.rb with *, to help people improve performance. Excluding an actual file name or partial file name makes sense. But excluding the only file extension we scan means we can do it faster by excluding the whole folder.

Motivation

Opening a ruby file caused my LSP server to print "Ruby LSP: indexing files" for 76 seconds at 0% before the progress bar starts moving.

Implementation

I knew that Rubocop has solved this problem before, so I looked at this file and followed what they did.

Automated Tests

I added tests for the new pattern exclude_pattern that gets used with fnmatch, while ensuring I didn't break any existing tests.

Manual Tests

I made a file that has both implementations of indexables on my computer. Then ran this in the Rails Console:

Benchmark.measure { RubyIndexer::Configuration.new.indexables }
=>
#<Benchmark::Tms:0x000000012a2dead0
 @cstime=0.0,
 @cutime=0.0,
 @label="",
 @real=0.19083199999295175,
 @stime=0.0784180000000001,
 @total=0.18055299999999974,
 @utime=0.10213499999999964>


Benchmark.measure { RubyIndexer::Configuration.new.old_indexables }
=>
#<Benchmark::Tms:0x000000012a374b20
 @cstime=0.0,
 @cutime=0.0,
 @label="",
 @real=76.83584400010295,
 @stime=13.666566,
 @total=14.943883,
 @utime=1.277317>

old_indexables = RubyIndexer::Configuration.new.old_indexables
indexables = RubyIndexer::Configuration.new.indexables

indexables.size == old_indexables.size
=> true

indexables.map(&:full_path).sort == old_indexables.map(&:full_path).sort
=> true

indexables.size
=> 13933

So here you can see that it finds the same ~14k files in 0.25% of the time.

[natematykiewicz]

I just resolved the merge conflict

[natematykiewicz]

@vinistock I believe I've addressed all of your comments

[natematykiewicz]

@vinistock do you need anything else from me on this?

[vinistock]

I brought this back to the team for discussion and we reached a consensus. We do not want to copy whatever RuboCop is doing. It's hard to tell if there is legacy code or decisions baked in there that are not relevant for the Ruby LSP.

In addition to that, the majority of the gains will come from ignoring the directories at the first level, so we can instead focus on that for the performance improvement.

Can we please switch to doing this instead:

1. Keep the node_modules exclusion
2. Combine the included and excluded patterns only at the first level of directories. Without trying to go all the way descending directories. Essentially, something like this:

def combined_patterns
  # code that will return a glob pattern with only the relevant directories combined
  # on the first level below Dir.pwd

  "**/{lib,app,whatever}/**/*.rb"
end

3. Remove anything related to symlinks and the descending of several directory levels

Remember, we will still need to keep the excluded check loop, since someone could be excluding files that are a few directories below (which is fine).

[natematykiewicz]

I brought this back to the team for discussion and we reached a consensus. We do not want to copy whatever RuboCop is doing. It's hard to tell if there is legacy code or decisions baked in there that are not relevant for the Ruby LSP.

In addition to that, the majority of the gains will come from ignoring the directories at the first level, so we can instead focus on that for the performance improvement.

Can we please switch to doing this instead:

1. Keep the node_modules exclusion
2. Combine the included and excluded patterns only at the first level of directories. Without trying to go all the way descending directories. Essentially, something like this:

def combined_patterns
  # code that will return a glob pattern with only the relevant directories combined
  # on the first level below Dir.pwd

  "**/{lib,app,whatever}/**/*.rb"
end

3. Remove anything related to symlinks and the descending of several directory levels

Remember, we will still need to keep the excluded check loop, since someone could be excluding files that are a few directories below (which is fine).

That sounds good! I think this will end up being a lot simpler. Avoiding traversing tmp and node_modules are going to be the biggest wins anyways. I doubt many people have some massive subdirectory that they want excluded (like app/foo/**/*).

[natematykiewicz]

@vinistock I just found a slight problem with only excluding top-level folders. So, we want to exclude the Bundler path if it's inside of the pwd. That's something the initialize method already does. Well, a common path for that is vendor/bundle. Ideally we'd avoid traversing into vendor/bundle, since it might be rather large, and we want to ignore it. But if we're only excluding top-level directories, then we'll have to traverse all the way through the gems, allocating IndexablePath objects for every Gem file, just to remove them in the indexables.reject! loop.

Thoughts? Do we just default exclude vendor/**/* too?

[natematykiewicz]

2nd question @vinistock. Where'd we land on treating included_patterns and excluded_patterns as relative to Dir.pwd? It doesn't make much sense to me that someone would put an absolute path in there, because that would only work on 1 computer. This decision heavily affects how I go about solving this.

[vinistock]

For the first question: I'm not sure we can always just exclude the entire vendor directory. Theoretically, there could be vendored dependencies not managed by Bundler in there. I would say let's start simple, with only the first level of directories and we can then follow up with an improvement. Maybe we can treat the BUNDLE_PATH inside the workspace as a special case.

For the second one, yeah, let's make all patterns relative to the workspace.

[natematykiewicz]

Sounds good, thanks!

[andyw8]

I'll set this to draft until @natematykiewicz has chance to return to it.

[natematykiewicz]

Thanks @andyw8!

One thing that's been tripping me up is the lack of normalization to the paths.

Vini said a few comments above that everything can be assumed to be relative to the workspace. The default path is a full absolute path to the directory, but I believe users would be passing in relative paths.

Perhaps you guys could get all paths to either be relative paths or absolute paths, instead of both? Then I'd have a much easier time doing this PR. I feel like I'm having to make a lot of decisions trying to normalize these paths (do the instance variables hold relative or absolute paths?), and realizing it's probably out of scope of this performance improvement PR anyways.

[natematykiewicz]

That last comment was about both the @included_patterns and @excluded_patterns instance variables, which in the real world seem to have a mix of absolute and relative paths.

[natematykiewicz]

I just saw that https://github.com/Shopify/ruby-lsp/pull/2424 was merged. That should make this PR much simpler.

[natematykiewicz]

@vinistock @andyw8 I just force pushed to this branch. I started over from main, and did what Vini said -- exclude top-level directories if the entire tree has been excluded (such as tmp/**/*).

This change actually made this all massively easier. No longer having to consider leading **/ on the excludes was really helpful.

All in all, this PR is much simpler now.

[natematykiewicz]

Note, since we're only excluding the very top-level directories, vendor/bundle still gets traversed even though it's my BUNDLE_PATH. As Vini alluded to, things get a lot more complicated if we try skip multiple layers to top-level directories (like vendor/bundle/**/*). I left a comment calling that out as well.

[natematykiewicz]

@vinistock just so you know, I think I've handled all of your feedback

[vinistock]

The changes look good to me, but could you please confirm if this produced any significant speed ups? I benchmarked these changes in two ways and saw no difference for our app, so I just want to confirm that it will actually achieve the desired outcome.

Benchmark 1

• On main, run the script 5 times. Calculate the average of the time spent indexing
• Switch to your branch and repeat
• Is there a noticeable difference?

# frozen_string_literal: true

require "bundler/setup"
require "benchmark"
require "ruby_lsp/load_sorbet"
require "ruby_lsp/internal"

T::Utils.run_all_sig_blocks

index = RubyIndexer::Index.new
RubyVM::YJIT.enable

r = Benchmark.realtime do
  index.index_all
end

puts r

Benchmark 2 (IPS)

This needs benchmark-ips.

• On main, run the script once
• Switch to your branch
• Run the script again
• What is the reported result?

# frozen_string_literal: true

require "bundler/setup"
require "benchmark/ips"
require "ruby_lsp/load_sorbet"
require "ruby_lsp/internal"

T::Utils.run_all_sig_blocks

index = RubyIndexer::Index.new
RubyVM::YJIT.enable

Benchmark.ips do |x|
  x.report("old") { index.configuration.indexables }
  x.report("new") { index.configuration.indexables }
  x.hold!("tmp_results")
  x.compare!
end

[natematykiewicz]

So, how much this change helps entirely depends on how big the excluded directories are. I recently wiped my tmp/storage because it became unbearable to use RubyLsp with how large it was.

I just rebased my branch. On main, RubyIndexer::Index.new.index_all takes 12 seconds. On my branch it takes 8 seconds. At the beginning of this branch (back in May) it was taking 76 seconds to find the indexables.

Looking at just the indexables part right now, this is a ~4 second improvement. But again, the "before" was taking 76 seconds before. I'm just not sure how much of that ~72 second difference between my old "before" and me current "before" is a smaller tmp tree, and how much is the hundreds of commits that have happened between now and then.

# "main" branch code
Benchmark.measure { RubyIndexer::Configuration.new.indexables }
=>
#<Benchmark::Tms:0x00000001197b3ee0
 @cstime=0.0,
 @cutime=0.0,
 @label="",
 @real=4.37744399998337,
 @stime=1.801075,
 @total=2.530652,
 @utime=0.7295769999999999>

# my changes
Benchmark.measure { RubyIndexer::Configuration2.new.indexables }
=>
#<Benchmark::Tms:0x000000011b9da8c0
 @cstime=0.0,
 @cutime=0.0,
 @label="",
 @real=0.7563209999352694,
 @stime=0.19453800000000054,
 @total=0.754276,
 @utime=0.5597379999999994>

[natematykiewicz]

Thank you @vinistock!