Fast directory walk by sinbad · Pull Request #1616 · git-lfs/git-lfs

sinbad · 2016-11-01T16:13:56Z

Provides a number of more optimal replacements for filepath.Walk. The easiest of which is tools.FastWalkGitRepo which automatically avoids walking .git and anything that matches any .gitignore it discovers as it walks.

Lower-level versions are available to include/exclude custom patterns.

I've used this in git lfs track to significantly speed up the enumeration of .gitattributes files, particularly when a repo contains a lot of files, most of which are in the .gitignore, as in #1611.

I've also refactored FilenamePassesIncludeExcludeFilter into the tools package, and extracted a utility function FileMatch which replaces filepath.Match by mirroring the behaviour of gitignore pattern matching, which wasn't completely supported before. This has a side effect of enhancing the capabilities of the include/exclude filters used elsewhere to support a more complete range of wildcard options including the "**" folder match.

…ctly

Used by FilenamePassesIncludeExcludeFilter

ttaylorr · 2016-11-02T15:44:42Z

Looks like the clone (with .lfsconfig) test is at least flaky on Windows, per this run. Going to give this a full review now 👍

ttaylorr

Looking good, few comments. I think the underlying implementation is correct, but the tests should verify that for me 👍

ttaylorr · 2016-11-02T15:51:34Z

commands/command_track.go

-	filepath.Walk(config.LocalWorkingDir, func(path string, info os.FileInfo, err error) error {
-		if err != nil {
-			return err
+	fchan, errchan := tools.FastWalkGitRepo(config.LocalWorkingDir)


Nice. What do you think about pulling this out to a private helper function in the commands package? I know the logic is duplicated in a few places across this PR, but I'm not so much thinking about that as I want the findAttributeFiles func to read cleanly.

It's only actually used once in production code, the other place is in the tests. Since what this findAttributeFiles function is doing is only hooking out items from the channel that are .gitattributes files it seems to me to make sense like it is, processing the channel and skipping anything else. I certainly don't want another function that builds a full list and then needs to be iterated, the other option is a function which takes search criteria but that's pretty specific and nothing else is using it yet. Maybe if something else needs it later it could be refactored but wrapping it speculatively right now might not actually be re-usable anyway.

ttaylorr · 2016-11-02T15:55:50Z

tools/filetools.go

+	}
+
+	if len(includePaths) > 0 {
+		matched := false


We could get rid of the above if by changing this line to:

matched := len(includePaths) == 0

But that conditional guards a lot more than just setting matched := false, in fact matched is deliberate scoped inside that block. It's that way because early-out by lack of inclusion requires checking every item and only concluding at the end, as opposed to early-out by exclusion which can return as soon as it's matched. That's why the exclusion block is simpler.

Ah, you're right; nice catch.

ttaylorr · 2016-11-02T15:56:41Z

tools/filetools.go

+				break
+			}
+		}
+		if !matched {


Or if we keep the if on L139, I don't think we need this one, since we break out whenever matched is true on L144.

I don't understand your logic, sorry. You'll need to write me the complete block as you see it because to me that doesn't seem to equate to the same result.

No worries, I think we can keep this as-is in the interest of merging this soon.

sinbad · 2016-11-02T16:49:58Z

Looks like the clone (with .lfsconfig) test is at least flaky on Windows, per this run. Going to give this a full review now 👍

Yeah and yet the very same commit worked fine in the other AppVeyor run. Seems dubious to me, I can't reproduce it.

sinbad · 2016-11-07T10:53:18Z

Re-tested everything on Windows this morning, totally fine. Looks like it's passing on AppVeyor now too, did someone re-run it? If so thanks, I don't have access to do that and was going to push a pointless change just to force it 😄

Appreciate if someone could approve this, I don't think any changes are needed. @ttaylorr @technoweenie

technoweenie

This looks good. I'd just prefer not to export anything in tools that isn't necessary.

technoweenie · 2016-11-07T17:38:45Z

tools/filetools.go

+// all be of the same type. includePaths/excludePaths can be nil.
+func FastWalk(dir string, includePaths, excludePaths []string) (<-chan FastWalkInfo, <-chan error) {
+	return FastWalkWithExcludeFiles(dir, "", includePaths, excludePaths)
+}


Do we need this func? Looks like it's only used in tests, while FastWalkGitRepo() is used in code.

sinbad · 2016-11-07T20:16:44Z

Since they’re all related variations of the same functionality it seemed sensible to expose them all in case it was useful to re-use them, but can be hidden if you prefer.

On 7 Nov 2016, at 18:55, risk danger olson notifications@github.com wrote:

@technoweenie approved this pull request.

This looks good. I'd just prefer not to export anything in tools that isn't necessary.

In tools/filetools.go:

Info os.FileInfo
+}

+// FastWalk is a more optimal implementation of filepath.Walk
+// It differs in the following ways:
+// * Provides a channel of information instead of using a callback func
+// * Uses goroutines to parallelise large dirs and descent into subdirs
+// * Does not provide sorted output; parents will always be before children but
+// there are no other guarantees. Use parentDir in the FastWalkInfo struct to
+// determine absolute path rather than tracking it yourself like filepath.Walk
+// * Supports include / exclude filters
+// Both dir and include/exclude paths can be relative or absolute, but they must
+// all be of the same type. includePaths/excludePaths can be nil.
+func FastWalk(dir string, includePaths, excludePaths []string) (<-chan FastWalkInfo, <-chan error) {

return FastWalkWithExcludeFiles(dir, "", includePaths, excludePaths)
+}
Do we need this func? Looks like it's only used in tests, while FastWalkGitRepo() is used in code.

—
You are receiving this because you authored the thread.
Reply to this email directly, view it on GitHub, or mute the thread.

ttaylorr

Looking awesome. Few minor nits here and there, otherwise I think this is ready to merge.

ttaylorr · 2016-11-07T22:58:57Z

tools/filetools.go

+
+// Main recursive implementation of fast walk
+// Increment waitg.Add(1) for each new goroutine launched internally
+func fastWalkItem(parentDir string, itemFi os.FileInfo, excludeFilename string,


This method's name is confusing, mainly because it does not specify what an item is in context. Is an item a directory? A file? Something else?

If you could specify what that refers to specifically, and improve the documentation to point out what some of the parameters mean (in particular, I'm thinking of itemFi and fiChan) that would be 👍

Is an item a directory? A file? Something else?

It's both, that's why I used Item and not File or Dir. Guess it could be fastWalkFileOrDir

ttaylorr · 2016-11-07T23:00:00Z

tools/filetools.go

+		return
+	}
+	defer df.Close()
+	jobSize := 100


This variable is effectively a constant. Would you mind extracting it and giving it a name outside of this method?

Why bother, unless something else needs to use the same size?

I figured that might be a good place to document why the number is what it is and what it's used for. I suppose that can be done inline, but that's just my preference 😄

Yeah I don't want to pollute the namespace, it's only a named var at all to self-document what it's for.

ttaylorr · 2016-11-07T23:00:21Z

tools/filetools.go

+	for children, err := df.Readdir(jobSize); err == nil; children, err = df.Readdir(jobSize) {
+		// Parallelise all dirs, and chop large dirs into batches
+		waitg.Add(1)
+		go func(subitems []os.FileInfo) {


Nice and clean. Love it!

ttaylorr · 2016-11-07T23:00:33Z

tools/filetools.go

+// If any changes are made a copy of the array is taken so the original is not
+// modified
+func loadExcludeFilename(filename, parentDir string, excludePaths []string) ([]string, error) {
+


Nit: please remove this newline.

ttaylorr · 2016-11-07T23:01:30Z

tools/filetools.go

+	defer f.Close()
+
+	retPaths := excludePaths
+	modified := false


For these variables that hold the zero-value of their type, I prefer the:

var modified bool

declaration, but that's just a stylistic preference, which you should feel free to ignore.

I prefer the way it is, lol. If this is later changed to require a default value of true, then the diff of that update would just be:

-modified := false +modified := true

Yeah I prefer explicitness of defaults, but maybe just because I come from languages that don't guarantee initialised variables

technoweenie · 2016-11-07T23:03:11Z

I think FastWalk can be removed, and FastWalkWithExcludeFiles should not be exported.

sinbad · 2016-11-08T11:33:55Z

All done - CLA check seems to be stalled though?

sinbad added 21 commits October 31, 2016 12:45

Refactor FilenamePassesIncludeExcludeFilter into tools package

3a7ef57

Draft version of FastWalk; optimised replacement for filepath.Walk

13a8af6

Close dir

ab6fd12

Load gitignore

e1a36e7

Sync correctly, basic test

b8c1012

Correctly walk from absolute paths

fb16579

Fix permissions

c870073

Exclude all nested git repos

546d6ad

Add better error reporting to gitignore loading & derive parent corre…

55cb397

…ctly

Enhanced FileMatch function to match gitignore style better

14e69a2

Used by FilenamePassesIncludeExcludeFilter

Couple more negative tests

ad79dcf

Improve test error reporting

068a866

Filematch should quote non-wildcards and only match to end not start

d06af7f

Add test to eliminate sub-matches from dot

34497b6

More understandable test output

5404e3e

Test for walking a git repo, skipping .git and reading .gitignore

1dfdea1

Clean expected entries to match on Windows

b0de634

Also clean dirs for Windows compatibility

f012a62

Use tools.FastWalk instead of filepath.Walk in track

f1fdc85

Support ‘**’ path separators in gitignore & use to match sub-gits

0859eb1

Fix false matches in middle of file name, regex match start of basename

91da732

sinbad added the review label Nov 1, 2016

ttaylorr reviewed Nov 2, 2016

View reviewed changes

technoweenie approved these changes Nov 7, 2016

View reviewed changes

ttaylorr reviewed Nov 7, 2016

View reviewed changes

sinbad added 3 commits November 8, 2016 09:48

PR feedback: better name/doc for fastWalkItem

07ee307

PR nits

8ac3c1c

PR feedback: export only FastWalkGitRepo

b3ef71d

technoweenie merged commit 7b3bc24 into master Nov 8, 2016

technoweenie deleted the fast-directory-walk branch November 8, 2016 15:52

technoweenie mentioned this pull request Nov 9, 2016

LFS Roadmap: v1.5.0 -> v2.0 #1632

Closed

ttaylorr mentioned this pull request Dec 9, 2016

git lfs track is very slow #1750

Closed

ttaylorr mentioned this pull request May 9, 2018

Define lockable files, make read-only in working copy when not locked #1822

Merged

Conversation

sinbad commented Nov 1, 2016

Uh oh!

ttaylorr commented Nov 2, 2016

Uh oh!

ttaylorr left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

sinbad commented Nov 2, 2016

Uh oh!

sinbad commented Nov 7, 2016 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

technoweenie left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

sinbad commented Nov 7, 2016

Uh oh!

ttaylorr left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

technoweenie commented Nov 7, 2016

Uh oh!

sinbad commented Nov 8, 2016

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

sinbad commented Nov 7, 2016 •

edited

Loading