Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

perf: _find_all_targets() has quadratic complexity because of Git.is_tracked() #3000

Closed
Suor opened this issue Dec 23, 2019 · 2 comments · Fixed by #3053
Closed

perf: _find_all_targets() has quadratic complexity because of Git.is_tracked() #3000

Suor opened this issue Dec 23, 2019 · 2 comments · Fixed by #3053
Labels
enhancement Enhances DVC p2-medium Medium priority, should be done, but less important performance improvement over resource / time consuming tasks

Comments

@Suor
Copy link
Contributor

Suor commented Dec 23, 2019

Git.is_tracked() recreates a list of tracked files for each call and is called for each file walk_files() will find. Both lists are proportional to repo size, which makes _find_all_targets() ~ O(repo_size ** 2).
@triage-new-issues triage-new-issues bot added the triage Needs to be triaged label Dec 23, 2019
@efiop
Copy link
Contributor

efiop commented Dec 24, 2019

https://github.com/iterative/dvc/blob/0.77.3/dvc/scm/git/__init__.py#L236

@efiop efiop added enhancement Enhances DVC performance improvement over resource / time consuming tasks labels Dec 24, 2019
@triage-new-issues triage-new-issues bot removed the triage Needs to be triaged label Dec 24, 2019
@efiop efiop added the p2-medium Medium priority, should be done, but less important label Dec 24, 2019
@Suor
Copy link
Contributor Author

Suor commented Dec 24, 2019 •
edited
Loading

There should be a way to access git index by name and thus implement Git.is_tracked() in O(1), making things linear overall.

@weekly-digest weekly-digest bot mentioned this issue Dec 29, 2019
Closed
Suor added a commit to Suor/dvc that referenced this issue Jan 4, 2020
@Suor
dvc: optimize Git.is_tracked()
a19deb2 
Closes iterative#3000
@Suor Suor mentioned this issue Jan 4, 2020
Merged
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
enhancement Enhances DVC p2-medium Medium priority, should be done, but less important performance improvement over resource / time consuming tasks
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

dvc: optimize Git.is_tracked() Suor/dvc
2 participants
@Suor @efiop