We write the replacement find (1) on golang under Linux

For one internal utility, I needed to write a scan of changes in the directory, similar to the find utility, and I ran into an unexpected thing: the standard Open () + Readdir () + Close () in go is very slow compared to how linux ' new find utility. In the picture you can see the strace of this utility. You can see that it makes some very strange system calls, and in these system calls we will try to figure out and write an analogue of find on go, which will only work under Linux, but at a comparable speed.

Naive implementation

Let's first write the “naive” implementation of find, which will, for simplicity, recursively list the files in a directory.

package main import (...) func readdir(dir string) { dh, err := os.Open(dir) defer dh.Close() for { fis, err := dh.Readdir(10) if err == io.EOF { break } for _, fi := range fis { fmt.Printf("%s/%s\n", dir, fi.Name()) if fi.IsDir() { readdir(dir + "/" + fi.Name()) } } } } func main() { readdir(os.Args[1]) } 

( full code, with import and error handling )
')
If we run this code, it will certainly work, but the wall time and rusage will be about 3 times larger than that of find (the difference in one file is due to the fact that we do not print the requested directory itself, unlike find) :

 $ time find /path/to/dir | wc -l 169561 real 0m0.333s user 0m0.104s sys 0m0.272s $ time GOGC=300 ./find-simple /path/to/dir | wc -l 169560 real 0m1.160s user 0m0.540s sys 0m0.944s 

Note that the system time is very large, and add output buffering:

 @@ -7,5 +7,7 @@ import ( +var bufout = bufio.NewWriter(os.Stdout) func readdir(dir string) { @@ -28,3 +30,7 @@ func readdir(dir string) { for _, fi := range fis { - fmt.Printf("%s/%s\n", dir, fi.Name()) + bufout.WriteString(dir) + bufout.WriteByte('/') + bufout.WriteString(fi.Name()) + bufout.WriteByte('\n') if fi.IsDir() { @@ -44,2 +50,3 @@ func main() { readdir(dir) + bufout.Flush() } 

( full version )

The results will be much better, but still far from ideal:

 $ time GOGC=300 ./find-simple-bufio /path/to/dir | wc -l 169560 real 0m0.796s user 0m0.352s sys 0m0.616s 

For example, here is the result for the same PHP program :

 $ php ~/find-ob.php /path/to/dir | wc -l 169560 real 0m0.777s user 0m0.276s sys 0m0.500s 

The PHP program is even a little faster and consumes measurable fewer resources! This is clearly not what I would like to get from the compiled language ...

Learning Linux system calls

If you look at strace from find, you will notice that it does getdents64 and almost does not do stat! But at the same time, the utility somehow knows which names correspond to directories. Let's see what this call to getdents64 is:

 SYNOPSIS int getdents(unsigned int fd, struct linux_dirent *dirp, unsigned int count); DESCRIPTION This is not the function you are interested in. Look at readdir(3) for the POSIX conforming C library interface. This page documents the bare kernel system call interface. The system call getdents() reads several linux_dirent structures from the directory referred to by the open file descriptor fd into the buffer pointed to by dirp. The argument count is specifies the size of that buffer. The linux_dirent structure is declared as follows: struct linux_dirent { ... char d_name[]; char pad; // Zero padding byte */ char d_type; // File type (only since Linux 2.6.4 } 

This is exactly what we need! Interestingly, on BSD-systems, when reading a directory, a field with a file type (d_type) is also available for some file systems. We are strongly discouraged from using this system call, but the same find utility doesn’t bother it.

As it turned out, under the hood, the standard go library also calls getdents (2), so we just have to “tear out” the code that does it and clean it of everything superfluous:

 package main import (...) var bufout = bufio.NewWriter(os.Stdout) func readdir(dir string, file string, dirfd int, pathbuf []byte) { origbuf := make([]byte, 4096) // ,    getdents dh, err := syscall.Openat(dirfd, file, syscall.O_RDONLY, 0777) //       origpathbuf := pathbuf[0:0] //       ,   for { n, errno := syscall.ReadDirent(dh, origbuf) //  getdents if n <= 0 { break // EOF } buf := origbuf[0:n] //     ,    :) for len(buf) > 0 { //      ParseDirent: dirent := (*syscall.Dirent)(unsafe.Pointer(&buf[0])) buf = buf[dirent.Reclen:] if dirent.Ino == 0 { // File absent in directory. continue } bytes := (*[10000]byte)(unsafe.Pointer(&dirent.Name[0])) name := bytes[0:clen(bytes[:])] //  clen()     if len(name) == 1 && name[0] == '.' || len(name) == 2 && name[0] == '.' && name[1] == '.' { continue } //         , //        pathbuf = append(pathbuf, dir...) pathbuf = append(pathbuf, '/') pathbuf = append(pathbuf, file...) dirlen := len(pathbuf) pathbuf = append(pathbuf, '/') pathbuf = append(pathbuf, name...) pathbuf = append(pathbuf, '\n') bufout.Write(pathbuf) //   ,   ,  string if dirent.Type == syscall.DT_DIR { readdir(string(pathbuf[0:dirlen]), string(name), dh, origpathbuf) } pathbuf = origpathbuf[0:0] } buf = origbuf[0:0] } syscall.Close(dh) } func main() { dir := os.Args[1] parentDir := filepath.Dir(dir) dh, err := os.Open(parentDir) pathbuf := make([]byte, 16 * 1024) readdir(parentDir, filepath.Base(dir), int(dh.Fd()), pathbuf) bufout.Flush() } 

( complete program source code, error handling and clen function )

results

With all the optimizations and the use of the system call, getdents managed to reduce resource consumption to such an extent that it works faster than find:

 $ time GOGC=300 ./find-simple /path/to/dir | wc -l 169560 real 0m1.160s user 0m0.540s sys 0m0.944s $ time GOGC=300 ./find-optimized /path/to/dir | wc -l 169560 real 0m0.200s user 0m0.060s sys 0m0.160s $ time find /path/to/dir | wc -l 169561 real 0m0.333s user 0m0.104s sys 0m0.272s 

Resource consumption and total running time is less than half as much as find. The main reasons for this are that find gives a sorted list of files and also accept the conditions for filtering the list.

Obviously, simply getting the list of files and displaying it on the screen does not represent much value, but this method allows many go programs to be accelerated, which, for example, provide an alternative to grep by reducing the overhead of reading the file list from the directory.

References:

• naive implementation
• use output buffering
• PHP equivalent
• Final version