fastwalk

Fast parallel directory traversal for Golang.

Package fastwalk provides a fast parallel version of filepath.WalkDir that is ~2x faster on macOS, ~4x faster on Linux, ~6x faster on Windows, allocates 50% less memory, and requires 25% fewer memory allocations. Additionally, it is ~4-5x faster than godirwalk across OSes.

Inspired by and based off of golang.org/x/tools/internal/fastwalk.

Features

• Fast: multiple goroutines stat the filesystem and call the filepath.WalkDirFunc callback concurrently
• Safe symbolic link traversal (Config.Follow)
• Same behavior and callback signature as filepath.WalkDir
• Wrapper functions are provided to ignore duplicate files and directories: IgnoreDuplicateFiles() and IgnoreDuplicateDirs()
• Extensively tested on macOS, Linux, and Windows

Usage

Usage is the same as filepath.WalkDir, but the walkFn argument to fastwalk.Walk must be safe for concurrent use.

Examples can be found in the examples directory.

The below example is a very simple version of the POSIX find utility:

// fwfind is a an example program that is similar to POSIX find,
// but faster and worse (it's an example).
package main

import (
	"flag"
	"fmt"
	"io/fs"
	"os"
	"path/filepath"

	"github.com/charlievieth/fastwalk"
)

const usageMsg = `Usage: %[1]s [-L] [-name] [PATH...]:

%[1]s is a poor replacement for the POSIX find utility

`

func main() {
	flag.Usage = func() {
		fmt.Fprintf(os.Stdout, usageMsg, filepath.Base(os.Args[0]))
		flag.PrintDefaults()
	}
	pattern := flag.String("name", "", "Pattern to match file names against.")
	followLinks := flag.Bool("L", false, "Follow symbolic links")
	flag.Parse()

	// If no paths are provided default to the current directory: "."
	args := flag.Args()
	if len(args) == 0 {
		args = append(args, ".")
	}

	// Follow links if the "-L" flag is provided
	conf := fastwalk.Config{
		Follow: *followLinks,
	}

	walkFn := func(path string, d fs.DirEntry, err error) error {
		if err != nil {
			fmt.Fprintf(os.Stderr, "%s: %v\n", path, err)
			return nil // returning the error stops iteration
		}
		if *pattern != "" {
			if ok, err := filepath.Match(*pattern, d.Name()); !ok {
				// invalid pattern (err != nil) or name does not match
				return err
			}
		}
		_, err = fmt.Println(path)
		return err
	}
	for _, root := range args {
		if err := fastwalk.Walk(&conf, root, walkFn); err != nil {
			fmt.Fprintf(os.Stderr, "%s: %v\n", root, err)
			os.Exit(1)
		}
	}
}

Benchmarks

Benchmarks were created using go1.17.6 and can be generated with the bench_comp make target:

$ make bench_comp

Darwin

Hardware:

goos: darwin
goarch: arm64
cpu: Apple M1 Max

filepath.WalkDir vs. fastwalk.Walk():

              filepath       fastwalk       delta
time/op       27.9ms ± 1%    13.0ms ± 1%    -53.33%
alloc/op      4.33MB ± 0%    2.14MB ± 0%    -50.55%
allocs/op     50.9k ± 0%     37.7k ± 0%     -26.01%

godirwalk.Walk() vs. fastwalk.Walk():

              godirwalk      fastwalk       delta
time/op       58.5ms ± 3%    18.0ms ± 2%    -69.30%
alloc/op      25.3MB ± 0%    2.1MB ± 0%     -91.55%
allocs/op     57.6k ± 0%     37.7k ± 0%     -34.59%

Linux

Hardware:

goos: linux
goarch: amd64
cpu: Intel(R) Core(TM) i9-9900K CPU @ 3.60GHz
drive: Samsung SSD 970 PRO 1TB

filepath.WalkDir vs. fastwalk.Walk():

              filepath       fastwalk       delta
time/op       10.1ms ± 2%    2.8ms ± 2%     -72.83%
alloc/op      2.44MB ± 0%    1.70MB ± 0%    -30.46%
allocs/op     47.2k ± 0%     36.9k ± 0%     -21.80%

godirwalk.Walk() vs. fastwalk.Walk():

              filepath       fastwalk       delta
time/op       13.7ms ±16%    2.8ms ± 2%     -79.88%
alloc/op      7.48MB ± 0%    1.70MB ± 0%    -77.34%
allocs/op     53.8k ± 0%     36.9k ± 0%     -31.38%

Windows

Hardware:

goos: windows
goarch: amd64
pkg: github.com/charlievieth/fastwalk
cpu: Intel(R) Core(TM) i9-9900K CPU @ 3.60GHz

filepath.WalkDir vs. fastwalk.Walk():

              filepath       fastwalk       delta
time/op       88.0ms ± 1%    14.6ms ± 1%    -83.47%
alloc/op      5.68MB ± 0%    6.76MB ± 0%    +19.01%
allocs/op     69.6k ± 0%     90.4k ± 0%     +29.87%

godirwalk.Walk() vs. fastwalk.Walk():

              filepath       fastwalk       delta
time/op       87.4ms ± 1%    14.6ms ± 1%    -83.34%
alloc/op      6.14MB ± 0%    6.76MB ± 0%    +10.24%
allocs/op     100k ± 0%      90k ± 0%       -9.59%

Darwin: getdirentries64

The nogetdirentries build tag can be used to prevent fastwalk from using and linking to the non-public __getdirentries64 syscall. This is required if an app using fastwalk is to be distributed via Apple's App Store (see golang/go#30933 for more details). When using __getdirentries64 is disabled, fastwalk will use readdir_r instead, which is what the Go standard library uses for os.ReadDir and is about ~10% slower than __getdirentries64 (benchmarks).

Example of how to build and test that your program is not linked to __getdirentries64:

# NOTE: the following only applies to darwin (aka macOS)

# Build binary that imports fastwalk without linking to __getdirentries64.
$ go build -tags nogetdirentries -o YOUR_BINARY
# Test that __getdirentries64 is not linked (this should print no output).
$ ! otool -dyld_info YOUR_BINARY | grep -F getdirentries64

There is a also a script scripts/links2getdirentries.bash that can be used to check if a program binary links to getdirentries.