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 (iterative/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:
iterative/dvc-bench#41

[efiop]

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

@karajan1001 No, same as gitignore, it cannot look back in the tree.

[karajan1001]

README

Thank you

[efiop]

@pared Should we keep this open or are we fully done here?

[pared]

@efiop sorry, autoclose. Seems to me we should leave it open. The issue potentially is still present in the case of multiple dvcignore files. Also, points noted by @Suor (#3869 (comment)) still need to be addressed.

EDIT:
#3967 addresses 2 points out of 5 (addressed points are 3 and 4)

[pared]

@efiop I think we should keep this issue open. There have been a lot of optimizations done thanks to @karajan1001 hard work.
Still, looking at @Suor original comment, the first 2 issues are still present and we will need to investigate them.

[efiop]

@pared Oops, closed by accident.

[karajan1001]

Benchmark result before and after #4242, it had been closed and not linked to this issue.

This update saves about 5ms.

[efiop]

Thank you @karajan1001 ! Amazing stuff! 🙏

Just to summarize: the only major thing that is left here is to tell dvcignore not to walk into output directories searching for .dvcignores. So kinda like dvcignore for dvcingores 🙂 Related to #3369 .

[skshetry]

@efiop, another simpler optimization could be to not reset dvcignore at all (except on brancher, but on those repo._tree changes which change dvcignore anyway).

[efiop]

@skshetry Not sure what resetting has to do with that. Currently, it doesn't know about outputs at all.

[skshetry]

Just saying that there's no need to reset dvcignore at all, so we could only collect dvcignores (dynamically once) and use it for the whole DVC session. Right now, we reset it each time we add a new output:

dvc/dvc/repo/add.py

Line 150 in d8b0373

repo._reset() # pylint: disable=protected-access

Or, every time we run a stage:

dvc/dvc/stage/decorators.py

Line 43 in d8b0373

stage.repo._reset() # pylint: disable=protected-access

But, we don't really need to start clean for dvcignores.

[efiop]

@skshetry That's a bit dangerous, and we do that to ensure that there is no hidden unwanted state when we use API (i mean Repo). We also need to reset it when walking the branches, as dvcignore might be different.

[skshetry]

@efiop, when walking the branches, the tree will have their own dvcignore. Also, I have to point out that since CleanTree, we did not use to clear dvcignore (but of course, this was an error on our part), so should be safe?

[efiop]

@skshetry Ah, totally missed that! Great point! Indeed, seems like we no longer need to reset it and it won't cause us problems.

[karajan1001]

Thank you @karajan1001 ! Amazing stuff! 🙏

Just to summarize: the only major thing that is left here is to tell dvcignore not to walk into output directories searching for .dvcignores. So kinda like dvcignore for dvcingores 🙂 Related to #3369 .
@efiop
Sorry, I had look through #3369, but I can't get this word.
tell dvcignore not to walk into output directories searching for ".dvcignore" s
Can you give me some more details?

[skshetry]

@karajan1001, right now, we have to collect stages most of the time. So, even though we have dynamic dvcignore now, we still have to look in every nook and corner inside of the repo to collect those stages. We might even be traversing to the depths of directories that are dvc-tracked and might be searching for ".dvcignore" dynamically.

So, the idea is to either read ".gitignore"s or, @efiop mentioned, as we are already collecting for the stages, we could find out the outputs, and never enter into those directories at all.

Also to extend this idea, we could create a concept of "exhaustive" search inside dvcignore, so that after we are done looking for the stages, we can tell dvcignore to not even try updating dvcignore now (should make later dynamic calls faster), and what we have is what it is.

[karajan1001]

@skshetry , @efiop
Seems that after we collecting stages, all the node of the dvcignore trie tree would be filled.

dvc/dvc/ignore.py

Lines 251 to 254 in 172032d

	def _get_trie_pattern(self, dirname):
	ignore_pattern = self.ignores_trie_tree.get(dirname)
	if ignore_pattern:
	return ignore_pattern

DvcIgnoreFilter would never try to update a node that it had looked in before. Actually it will never try to update a node twice and will update once only when a path calls it.

_reset() is, absolutely a big problem. I'm going to open a PR for it with a benchmark result.

[skshetry]

@karajan1001, yes, I got confused by that too. If there was a complete search, it won't try to look for dvcignore again, but it will still look into every places, even those directories that are dvc-tracked.

But I am not sure if this would make it slower or faster, as there will never be a dvcignore in those directories (so, an .exists() call is only wasted), and os.walk seems cheap enough. Maybe, if the dvc-tracked directories is of too-many levels, it might help.

---

To get an idea about the impact of this change, I tried to walk() Linux's source tree by converting it to DVC repo (added .dvc folder and renamed all .gitignore to .dvcignore, not quite a dvc repo but good enough for understanding dvcignore's impact).

0.94   -> 16m20s
latest -> 2.76s at first, 2.02s later on
latest (without dvcignore) -> 202ms

Half of those times are spent on .match() for regex patterns. So, that's quite an optimization. Cheers.

[skshetry]

Okay, I missed another important point: dvcignore has to still apply to the inside of the dvc-tracked directories, it's just the dvcignore that's not needed to be collected.