optimize dvcignore

[efiop]

From #3867 it is apparent that we need to bench dvcignore and research if anything else there requires optimization. A user (@courentin ) reported that something simple like

data/something
bash_projects
mlruns
notebooks
externals
examples
.circleci
.vscode
.pytest_cache
wandb

takes a significant time.

• add benchmark for this to dvc-bench project

[Suor]

Looked at this and I see several issues with code, most of which also affect performance:

1. DvcIgnore* classes designed around using them in walk(), which leads to excessively complex code handling check for full path.
2. All the complexity above is added to CleanTree, which makes it go into DvcIgnore* domain. It should really look like:

   def isfile(self, path):
       return self.tree.isfile(path) and not self.dvcignore.match_file(path)

3. DvcIgnore* hierarchy forces sequential check against all rules and regexes. This might be optimized by constructing single structure, i.e. a big regex or a prefix tree. This is complicated by the fact that dvcignores may contain negations though.
4. pathspec library also checks against all regexes sequentially, which adds to 3.
5. High level issue. I suspect that we recheck files found via walk, so we run ignores twice. It needs to be estimated whether this is an issue.

[courentin]

Thank you @Suor

It seems consistent with what I experienced. The more I add lines in .dvcignore, the slowest dvc status is.

[karajan1001]

Looked at this and I see several issues with code, most of which also affect performance:

1. DvcIgnore* classes designed around using them in walk(), which leads to excessively complex code handling check for full path.
2. All the complexity above is added to CleanTree, which makes it go into DvcIgnore* domain. It should really look like:

   def isfile(self, path):
       return self.tree.isfile(path) and not self.dvcignore.match_file(path)

3. DvcIgnore* hierarchy forces sequential check against all rules and regexes. This might be optimized by constructing single structure, i.e. a big regex or a prefix tree. This is complicated by the fact that dvcignores may contain negations though.
4. pathspec library also checks against all regexes sequentially, which adds to 3.
5. High level issue. I suspect that we recheck files found via walk, so we run ignores twice. It needs to be estimated whether this is an issue.

@Suor
I also have an interest in this issue and had looked into the code. And here is my solution to some of the issues above:

1. For point (1), walk() should use information from DvcIgnore. For example, exiting the .git directory at the beginning of the iteration.
2. For point (3), according to this article, tried tree or automaton would only perform better if the number of ignored-expressions was greater than several hundred.
3. For point (4), In pathspec

	matched = False
	for pattern in patterns:
		if pattern.include is not None:
			if file in pattern.match((file,)):
				matched = pattern.include
	return matched

It should stop if any of the patterns matched the file.
@courentin
And I think this is the main reason that It gets slower as the ignore list grows.

I'd like to try to solve these points this weekend.

[Suor]

@karajan1001

1. There is no issue with walk, the ignored dir won't we traversed. The issue is when we need to check whether some/path/abc/file.txt is ignored we need to build all of its parents and test them in an unnatural way.

It should stop if any of the patterns matched the file.

So for very common case that file is not ignored it will match it against all of those.

[karajan1001]

1. There is no issue with walk, the ignored dir won't we traversed. The issue is when we need to check whether some/path/abc/file.txt is ignored we need to build all of its parents and test them in an unnatural way.

Thank you
Dos Dvcignore support expressions like ../*.csv which influences files outside the current path?

[karajan1001]

Haha, underrated the difficulty of it. Only written the benchmark (treeverse/dvc-bench#30).

5. High level issue. I suspect that we recheck files found via walk, so we run ignores twice. It needs to be estimated whether this is an issue.

@Suor, According to @courentin 's call graph in #3867 it only runs once.

[karajan1001]

@efiop @pared
I have a question how could I test unmerged changes using dvc-bench.

[pared]

@karajan1001
Prepared PR explaining this in README, please take a look and review:
treeverse/dvc-bench#41