path/filepath: Walk is slow compared to 'find' due to extra Stat calls

[bradfitz]

On my Mac laptop (SSD, warm caches),

bradfitz@laptop ~$ time (find src/ | wc -l)
   42408

real    0m0.177s
user    0m0.035s
sys     0m0.144s
bradfitz@laptop ~$ time (find src/ | wc -l)
   42408

real    0m0.178s
user    0m0.036s
sys     0m0.144s
bradfitz@laptop ~$ time (find src/ | wc -l)
   42408

real    0m0.177s
user    0m0.035s
sys     0m0.144s

But with a basic use of filepath.Walk instead of find:

$ cat walk.go 
package main

import (
        "fmt"
        "log"
        "os"
        "path/filepath"
)

func main() {
        err := filepath.Walk("src", func(path string, fi os.FileInfo, err error) error {
                if err != nil {
                        return err
                }
                fmt.Println(path)
                return nil
        })
        if err != nil {
                log.Fatal(err)
        }
}

It's much slower:

bradfitz@laptop ~$ time (./walk  | wc -l)
   42408

real    0m0.447s
user    0m0.123s
sys     0m0.406s
bradfitz@laptop ~$ time (./walk  | wc -l)
   42408

real    0m0.434s
user    0m0.120s
sys     0m0.399s
bradfitz@laptop ~$ time (./walk  | wc -l)
   42408

real    0m0.435s
user    0m0.119s
sys     0m0.398s

This is the bulk of the goimports execution time. goimports actually does a slightly parallelized walk with goroutines (which helps on NFS filesystems), but it doesn't seem to matter. I'm just trying to get any Go program to be closer in performance to find.

Any clues?

Speed tracking bug for goimports is #16367

/cc @josharian @ianlancetaylor

[bradfitz]

The same on Linux. This isn't just about OS X.

Actually on Linux it's even more pronounced:

bradfitz@dev-bradfitz-debian2:~$ time (find src/ | wc )
  97909   98025 5108045

real    0m0.146s
user    0m0.128s
sys     0m0.092s
bradfitz@dev-bradfitz-debian2:~$ time (find src/ | wc )
  97909   98025 5108045

real    0m0.147s
user    0m0.136s
sys     0m0.084s
bradfitz@dev-bradfitz-debian2:~$ time (find src/ | wc )
  97909   98025 5108045

real    0m0.150s
user    0m0.148s
sys     0m0.076s

Versus:

bradfitz@dev-bradfitz-debian2:~$ time (./walk | wc )
  97909   98025 5108044

real    0m0.530s
user    0m0.412s
sys     0m0.388s
bradfitz@dev-bradfitz-debian2:~$ time (./walk | wc )
  97909   98025 5108044

real    0m0.515s
user    0m0.344s
sys     0m0.432s
bradfitz@dev-bradfitz-debian2:~$ time (./walk | wc )
  97909   98025 5108044

real    0m0.528s
user    0m0.312s
sys     0m0.484s

[dgryski]

Walk sorts the file entries, but find doesn't. Not sure how much that affects the profiles though.

[bradfitz]

@dgryski, that's a bit of it, but it's looking like the actual problem is that filepath.Walk does a Readdirnames followed by a bunch of Stat calls on each to figure out what's a directory, when the underlying kernel interface supports telling you which are directories in the same call where you read the names, but Go doesn't take advantage of that on Unix platforms. (And path/filepath could do that on Windows, which Go's syscall and os package already supports, but it hard-codes the use of Readdirnames)

[bradfitz]

Actually, I realize now that the filepath.Walk (at least with our definition of os.FileInfo) is inherently slow, as its API guarantees you get a complete FileInfo with each call, which requires us to do a stat per file, even if the user doesn't want it.

I think I'll move away from using filepath.Walk for goimports.

[vincepri]

@bradfitz out of curiosity, is your idea here to rewrite readdirnames for unix/linux to make use of the Type in Dirent (https://golang.org/src/syscall/syscall_linux.go?h=ParseDirent#L773) as you were mentioning above?

It looks like some OSs may have that information but Go is discarding in favor of lstat.

[bradfitz]

@vinceprignano, yes, that's what I'm doing now.

[gopherbot]

CL https://golang.org/cl/25001 mentions this issue.

[YuriyNasretdinov]

In my observations there were 2 problems:

1. GC-unfriendly API for reading directory (no ability to do just readdir and get file types without all other stat structures, a lot of slice and struct pointer allocations)
2. That's it

I wrote an article (in russian, sorry for that) that describes how to achieve performance that is higher than find(1) has: https://habrahabr.ru/post/281382/ (google translate: https://translate.google.ru/translate?sl=ru&tl=en&js=y&prev=_t&hl=ru&ie=UTF-8&u=https%3A%2F%2Fhabrahabr.ru%2Fpost%2F281382%2F&edit-text=&act=url)

[dmitshur]

Actually, I realize now that the filepath.Walk (at least with our definition of os.FileInfo) is inherently slow, as its API guarantees you get a complete FileInfo with each call, which requires us to do a stat per file, even if the user doesn't want it.

I think I'll move away from using filepath.Walk for goimports.

I've run into a similar situation.

I created filepath.Walk-like functionality for http.FileSystem in https://godoc.org/github.com/shurcooL/httpfs/vfsutil#Walk. In my use cases, I often worked with virtual filesystems where files did not exist on disk, but rather virtually after doing some computation. So the act of "opening" a file was an a relatively expensive action. I ran into the same problem, the filepath.Walk behavior was suboptimal. It would open a virtual file (potentially somewhat expensive), do a stat on it to pass its os.FileInfo to walk func, then close the file. Then, inside the walk func, I would often need to access the file contents, so I'd have to open it again (somewhat expensive).

For those specific needs, I ended up creating https://godoc.org/github.com/shurcooL/httpfs/vfsutil#WalkFiles which would pass both the os.FileInfo but also the file contents as an io.ReadSeeker:

// WalkFiles walks the filesystem rooted at root, calling walkFn for each file or
// directory in the filesystem, including root. In addition to FileInfo, it passes an
// ReadSeeker to walkFn for each file it visits.
func WalkFiles(fs http.FileSystem, root string, walkFn WalkFilesFunc) error { ... }

// WalkFilesFunc is the type of the function called for each file or directory visited by Walk.
// It's like filepath.WalkFunc, except it provides an additional ReadSeeker parameter for file being visited.
type WalkFilesFunc func(path string, info os.FileInfo, rs io.ReadSeeker, err error) error

That worked well for my needs, but I like your idea of just not passing os.FileInfo at all, since computing even that can be expensive and sometimes not neccessary for caller. So it'd be simpler, more general, and more performant to just give the file path to walk func and let it do what it needs (stat, read file, etc.).

[ianlancetaylor]

@hirochachacha It sounds like you are describing a bug in the syscall package, a bug that should be fixed in any case. The syscall package provides ReadDirent and ParseDirent functions on all GNU/Linux targets; do those functions work on mips64?

[bradfitz]

@cherrymui, can you run go test golang.org/x/tools/imports on mips64?

[bradfitz]

@hirochachacha, please file a separate issue for that.

[hirochachacha]

x/sys/unix 's Getdents uses SYS_GETDENTS64.
So what I am saying is completely wrong.
I'm really sorry about confusing people.

I'll remove my comments above and close the opened issue.

Again, I'm sorry.

[mattn]

ref #16435

[cherrymui]

@bradfitz, on MIPS64

$ go test -v golang.org/x/tools/imports 
=== RUN   TestFastWalk_Basic
--- PASS: TestFastWalk_Basic (0.01s)
=== RUN   TestFastWalk_Symlink
--- PASS: TestFastWalk_Symlink (0.01s)
=== RUN   TestFastWalk_SkipDir
--- PASS: TestFastWalk_SkipDir (0.01s)
=== RUN   TestFastWalk_TraverseSymlink
--- PASS: TestFastWalk_TraverseSymlink (0.01s)
=== RUN   TestFixImports
--- PASS: TestFixImports (0.06s)
=== RUN   TestImportSymlinks
--- PASS: TestImportSymlinks (0.04s)
=== RUN   TestFixImportsVendorPackage
--- PASS: TestFixImportsVendorPackage (0.01s)
=== RUN   TestFindImportGoPath
--- PASS: TestFindImportGoPath (0.01s)
=== RUN   TestFindImportInternal
--- FAIL: TestFindImportInternal (0.03s)
    fix_test.go:1034: findImportGoPath("race", Acquire ...) = "", false; want "internal/race", false
=== RUN   TestFindImportRandRead
--- PASS: TestFindImportRandRead (0.00s)
=== RUN   TestFindImportVendor
--- PASS: TestFindImportVendor (0.01s)
=== RUN   TestProcessVendor
--- FAIL: TestProcessVendor (0.03s)
    fix_test.go:1127: Process("/home/a/src/git/go-official/src/math/x.go") did not add expected hpack import "golang_org/x/net/http2/hpack"; got:
        package http

        import "strings"

        func f() { strings.NewReader(); hpack.HuffmanDecode() }
=== RUN   TestFindImportStdlib
--- PASS: TestFindImportStdlib (0.00s)
=== RUN   TestRenameWhenPackageNameMismatch
--- PASS: TestRenameWhenPackageNameMismatch (0.03s)
=== RUN   TestOptimizationWhenInGoroot
--- PASS: TestOptimizationWhenInGoroot (0.03s)
=== RUN   TestIgnoreDocumentationPackage
--- PASS: TestIgnoreDocumentationPackage (0.03s)
=== RUN   TestImportPathToNameGoPathParse
--- PASS: TestImportPathToNameGoPathParse (0.03s)
=== RUN   TestIgnoreConfiguration
--- PASS: TestIgnoreConfiguration (0.03s)
=== RUN   TestSkipNodeModules
--- PASS: TestSkipNodeModules (0.03s)
=== RUN   TestPkgIsCandidate
--- PASS: TestPkgIsCandidate (0.00s)
FAIL
exit status 1
FAIL    golang.org/x/tools/imports  0.499s

$ go version
go version devel +1d2ca9e Mon Jul 18 21:07:34 2016 +0000 linux/mips64le

Is the failure related? Should I go look into it?

[bradfitz]

@cherrymui, those are old tests. I changed them to not rely on real GOROOT contents. Update & try again?

[cherrymui]

$ go get -u golang.org/x/tools/imports
$ go test -v golang.org/x/tools/imports
=== RUN   TestFastWalk_Basic
--- PASS: TestFastWalk_Basic (0.01s)
=== RUN   TestFastWalk_Symlink
--- PASS: TestFastWalk_Symlink (0.00s)
=== RUN   TestFastWalk_SkipDir
--- PASS: TestFastWalk_SkipDir (0.00s)
=== RUN   TestFastWalk_TraverseSymlink
--- PASS: TestFastWalk_TraverseSymlink (0.01s)
=== RUN   TestFixImports
--- PASS: TestFixImports (0.06s)
=== RUN   TestImportSymlinks
--- PASS: TestImportSymlinks (0.04s)
=== RUN   TestFixImportsVendorPackage
--- PASS: TestFixImportsVendorPackage (0.01s)
=== RUN   TestFindImportGoPath
--- PASS: TestFindImportGoPath (0.01s)
=== RUN   TestFindImportInternal
--- FAIL: TestFindImportInternal (0.03s)
    fix_test.go:1034: findImportGoPath("race", Acquire ...) = "", false; want "internal/race", false
=== RUN   TestFindImportRandRead
--- PASS: TestFindImportRandRead (0.00s)
=== RUN   TestFindImportVendor
--- PASS: TestFindImportVendor (0.01s)
=== RUN   TestProcessVendor
--- FAIL: TestProcessVendor (0.03s)
    fix_test.go:1127: Process("/home/a/src/git/go-official/src/math/x.go") did not add expected hpack import "golang_org/x/net/http2/hpack"; got:
        package http

        import "strings"

        func f() { strings.NewReader(); hpack.HuffmanDecode() }
=== RUN   TestFindImportStdlib
--- PASS: TestFindImportStdlib (0.00s)
=== RUN   TestRenameWhenPackageNameMismatch
--- PASS: TestRenameWhenPackageNameMismatch (0.03s)
=== RUN   TestOptimizationWhenInGoroot
--- PASS: TestOptimizationWhenInGoroot (0.03s)
=== RUN   TestIgnoreDocumentationPackage
--- PASS: TestIgnoreDocumentationPackage (0.03s)
=== RUN   TestImportPathToNameGoPathParse
--- PASS: TestImportPathToNameGoPathParse (0.03s)
=== RUN   TestIgnoreConfiguration
--- PASS: TestIgnoreConfiguration (0.03s)
=== RUN   TestSkipNodeModules
--- PASS: TestSkipNodeModules (0.03s)
=== RUN   TestPkgIsCandidate
--- PASS: TestPkgIsCandidate (0.00s)
FAIL
exit status 1
FAIL    golang.org/x/tools/imports  0.489s

I did a go get -u but see no difference...

[bradfitz]

@cherrymui, oh, sorry... there are still those two tests which still use the machine's real $GOROOT. I didn't convert those yet I guess. In any case, you can ignore those errors. They should go away when you sync your $GOROOT. I'll fix those tests.

But the real question was whether the TestFastWalk_ tests passed, which they did.

Thanks!

[cherrymui]

Ok, great. Thanks!

[rasky]

Not sure what the current plan is to fix this, but given that os.FileInfo is an interface, wouldn't make sense to return an object that does a lazy Lstat only when required? It could answer Name() and IsDir() using only information returned by ParseDirent, and anything else would lazily call Lstat.

[bradfitz]

@rasky, that doesn't work, as the Size() int64 method (or IsDir() bool) on the os.FileInfo has no means of returning an error if the lazy lstat fails.

[alexkreidler]

I've written a few benchmarks:

• a naive recursive using os.File.Readdir()
• parallelized recursive version using goroutines and wait groups
• and also included the one by @bradfitz up above using filepath.Walk()

Here they are: https://github.com/Tim15/golang-parallel-io.

They're all slower than find, probably due to the fact that os.File.Readdir() returns a complete os.FileInfo. I was surprised though that my parallel version was faster than filepath.Walk().

Hopefully this helps us figure this out!

[bradfitz]

@tim15, we already figured it out over a year ago. See the comment I linked you to 3 days ago. The solution for goimports ended up being https://github.com/golang/tools/blob/master/imports/fastwalk.go but that's not applicable to the standard library. This isn't fixable with the current API.

[alexkreidler]

@bradfitz Cool, thanks for catching me up!

[mainrs]

@bradfitz Sorry to ask here but is it possible to use the fastwalk API in one of my applications? I couldn't find any information on that.
Looks like no method is exported to the outside (all are lower-cased).

[bradfitz]

@sirwindfield, no, I did not expose its implementation publicly. You can copy/paste it into your own package if you'd like, but it's not something I want to support at this time.

[rasky]

For people looking for reusing the code into their own projecst, there is now this third-party library that is basically a clone of fastwalk: https://github.com/karrick/godirwalk

[s12chung]

forked the repo and made an update script to clean things up with tags: https://github.com/s12chung/fastwalk

[saracen]

@bradfitz Sorry for revisiting this old issue, but I have a few questions I was hoping you'd be able to answer.

Your fastwalk implementation only provides Filemode and states file stat calls must be done by the user.. However, included in the implementation is a fallback when Dirent.Type == DT_UNKNOWN (https://github.com/golang/tools/blob/master/internal/fastwalk/fastwalk_unix.go#L54), where an lstat is performed. Does this not mean we're guaranteed a complete FileInfo, or are there still edge cases?

[bradfitz]

The fastwalk callback gives you an os.FileMode, not an os.FileInfo.

[saracen]

@bradfitz I guess my question is, is there any reason it couldn't provide an os.FileInfo with no additional overhead? Unless I'm mistaken, it providing os.FileMode was intended to remove the overhead filepath.Walk has with using lstat on each call, guaranteeing a full os.FileInfo, but it looks like your implementation already achieves this but throws the information away and provides only os.FileMode.

I'm not suggesting that you change your implementation, but I guess I'm just confused as to why file.ReadDir and filepath.Walk both rely on additional lstat calls, rather than doing something similar to your implementation where a fallback is done if the full information isn't available in a single readdir call.

[bradfitz]

@saracen, Size. See #16399 (comment) above.

[saracen]

@bradfitz Thank you for the clarification, and sorry for adding to the noise there.

For people stumbling across this issue needing a fast version that returns a full os.FileInfo, I've just created this repository: https://github.com/saracen/walker - this performs the lstat call, and I'm hoping it's just as fast, or faster, than the implementations out there that don't.

There's a few people here that are really familiar with the issue, so I'd really appreciate if there's anybody willing to check my solution.

[karrick]

Years ago I started importing https://github.com/karrick/godirwalk into filepath.Walk, but stopped because it required creating another public data structure in the standard library. Rather than discuss it I just stopped working, and went back to my day job.

I am still open to a port of the godirwalk library as an extension to filepath if it's something folks would like to see.

(For the record, godirwalk was not a fork of FastWalk, but was started by me on 2017-08-21 while working on dep to account for dissimilarities when walking file system on Windows or UNIX.)

[benhoyt]

I think this issue is fixed by the new filepath.WalkDir function in Go 1.16. It uses the new os.DirEntry (fs.DirEntry) type to avoid a stat for every file. On my machine (with a large source code directory). Summary (and raw results below):

• find: 126ms
• Walk: 222ms (76% slower than find)
• WalkDir: 162ms (29% slower than find)

So WalkDir isn't quite as fast as find, but significantly closer now, and a lot faster than Walk.

# find
~/w$ time (find ./ | wc -l)
28466

real	0m0.126s
user	0m0.088s
sys	0m0.052s
~/w$ time (find ./ | wc -l)
28466

real	0m0.126s
user	0m0.045s
sys	0m0.095s
~/w$ 
~/w$ time (find ./ | wc -l)
28466

real	0m0.132s
user	0m0.066s
sys	0m0.078s


# walk.go - Brad's original using Walk
~/w$ time (./walk . | wc -l)
28468

real	0m0.239s
user	0m0.160s
sys	0m0.203s
~/w$ time (./walk . | wc -l)
28468

real	0m0.222s
user	0m0.106s
sys	0m0.236s
~/w$ time (./walk . | wc -l)
28468

real	0m0.232s
user	0m0.127s
sys	0m0.231s


# walk.go using WalkDir / DirEntry
~/w$ time (./walk . | wc -l)
28468

real	0m0.168s
user	0m0.120s
sys	0m0.129s
~/w$ time (./walk . | wc -l)
28468

real	0m0.162s
user	0m0.102s
sys	0m0.133s
~/w$ time (./walk . | wc -l)
28468

real	0m0.176s
user	0m0.102s
sys	0m0.151s

[seankhliao]

I think this can be closed now that we have the new WalkDir as mentioned above