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

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

About this issue

Original URL
State: closed
Created 8 years ago
Reactions: 6
Comments: 50 (34 by maintainers)

Commits related to this issue

cmd/goimports, imports: optimize directory scanning and other things This brings goimports from 160ms to 100ms on my laptop, and under 50ms on my Linux machine. Using cmd/trace, I noticed that filep... — committed to golang/tools by bradfitz 8 years ago
strings: add special cases for Join of 2 and 3 strings We already had special cases for 0 and 1. Add 2 and 3 for now too. To be removed if the compiler is improved later (#6714). This halves the num... — committed to golang/go by bradfitz 8 years ago
imports: wait for fastWalk workers to finish before returning In some cases walkFn is being called after the fastWalk function has returned. This often happens when an error was encountered early on ... — committed to golang/tools by jstemmer 7 years ago
Revert "imports: wait for fastWalk workers to finish before returning" This reverts commit 4436e5475416d77a9352558d118d0b585b962ef1. Reason for revert: Breaks goimports. See: https://github.com/gola... — committed to golang/tools by bradfitz 7 years ago
imports: wait for fastWalk workers to finish before returning (take 2) This is Joël Stemmer's https://golang.org/cl/40092 again, but with a fix to prevent workers from deadlocking on send if the call... — committed to golang/tools by bradfitz 7 years ago
Added aggregation logic for decoders duplicating metrics; speeded up cgroup decoder. Signed-off-by: Bartlomiej Plotka <bwplotka@gmail.com> — committed to bwplotka/ebpf_exporter by bwplotka 3 years ago

Most upvoted comments

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

rasky on Jan 5, 2018

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

benhoyt on Feb 9, 2021

@Tim15, there can’t be any update on this due to the fundamental API design. See comment https://github.com/golang/go/issues/16399#issuecomment-233190667 above.

I’ll label this bug Go 2. Maybe we can change the walk interface to be more efficient later.

bradfitz on Nov 1, 2017

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

bradfitz on Jul 17, 2016

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.

bradfitz on Jul 17, 2016

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

seankhliao on Nov 17, 2021

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

dgryski on Jul 17, 2016

@saracen, Size. See https://github.com/golang/go/issues/16399#issuecomment-236624924 above.

bradfitz on Oct 11, 2019

@johansglock, thanks, and sorry. I’ve reverted the change in https://go-review.googlesource.com/c/40296/

bradfitz on Apr 11, 2017

That’s interesting, I hadn’t considered that. It think this happens when a worker received more input but then gets stuck on sending the result to w.resc here.

Another possible way of dealing with this that doesn’t involve draining could be:

func (w *walker) doWork(wg *sync.WaitGroup) {
	defer wg.Done()
	for {
		select {
		case <-w.donec:
			return
		case it := <-w.workc:
			err := w.walk(it.dir, !it.callbackDone)
			select {
			case <-w.donec:
				return
			case w.resc <- err:
			}
		}
	}
}

I wonder if there’s a better way of dealing with this.

jstemmer on Apr 11, 2017

In my observations there were 2 problems:

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)
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)

YuriyNasretdinov on Jul 18, 2016