golang对遍历目次操作的优化

一转眼go1.23都快发布了，时间过得真快。
不外本日我们把时间倒流回三年半之前，来关注一个在go1.16引入的关于处理目次时的优化。
对于go1.16的新变化，各人印象最深的大概是io包的大规模重构，但这个重构现实上还引进了一个优化，这篇文章要说的就是这个优化。
本文默认Linux环境，不外这个优化在BSD系统上也是通用的。
遍历目次时的优化

遍历目次是个很常见的需求，尤其是对于有大量文件的目次来说，遍历的性能直接关系到了整体程序的性能。
go1.16对于遍历目次增加了几个新接口：os.ReadDir，(*os.File).ReadDir，filepath.WalkDir。
这几个接口最大的特征是对目次项使用fs.DirEntry表示而不是os.FileInfo。fs.DirEntry是一个接口，它提供了类似os.FileInfo的方法：

1. type DirEntry interface {
2.         Name() string
3.         IsDir() bool
4.         Type() FileMode
5.         Info() (FileInfo, error)
6. }

复制代码

它还提供了一个叫Info的方法以便获得os.FileInfo。
这个接口有什么神奇的呢？我们看下性能测试：

1. func IterateDir(path string) int {
2.     // go1.16 的 os.ReadDir 就是这么实现的，为了测试我们把它展开成对(*os.File).ReadDir的调用
3.         f, err := os.Open(path)
4.         if err != nil {
5.                 panic(err)
6.         }
7.         defer f.Close()
9.         files, err := f.ReadDir(-1)
10.         if err != nil {
11.                 panic(err)
12.         }
13.         length := 0
14.         for _, finfo := range files {
15.                 length = max(length, len(finfo.Name()))
16.         }
17.         return length
18. }
20. func IterateDir2(path string) int {
21.     // 1.16之前遍历目录的常用方法之一
22.         f, err := os.Open(path)
23.         if err != nil {
24.                 panic(err)
25.         }
26.         defer f.Close()
28.         files, err := f.Readdir(-1)
29.         if err != nil {
30.                 panic(err)
31.         }
32.         length := 0
33.         for _, finfo := range files {
34.                 length = max(length, len(finfo.Name()))
35.         }
36.         return length
37. }
39. func BenchmarkIter1(b *testing.B) {
40.         for range b.N {
41.                 IterateDir("../test")
42.         }
43. }
45. func BenchmarkIter2(b *testing.B) {
46.         for range b.N {
47.                 IterateDir2("../test")
48.         }
49. }

复制代码

test目次是一个有5000个文件的位于Btrfs文件系统上的目次，我们的测试用例会遍历目次并找出名字最长的文件的文件名长度。
这是测试结果：

可以看到优化后的遍历比原先的快了480%。换了个函数为什么就会有这么大的提拔？想知道答案的话就继续看吧。
优化的原理

继续深入前我们先看看老的接口是怎么获取到目次里的文件信息的。答案是遍历目次拿到路径，然后调用os.Lstat获取完整的文件信息：

1. func (f *File) Readdir(n int) ([]FileInfo, error) {
2.         if f == nil {
3.                 return nil, ErrInvalid
4.         }
5.         _, _, infos, err := f.readdir(n, readdirFileInfo)
6.         if infos == nil {
7.                 // Readdir has historically always returned a non-nil empty slice, never nil,
8.                 // even on error (except misuse with nil receiver above).
9.                 // Keep it that way to avoid breaking overly sensitive callers.
10.                 infos = []FileInfo{}
11.         }
12.         return infos, err
13. }

复制代码

这个f.readdir会根据第二个参数的值来改变自己的活动，根据值不同它会遵循1.16前老代码的活动大概采用新的优化方法。这个函数不同系统上的实现也不同，我们选则*nix系统上的实现看看：

1. func (f *File) readdir(n int, mode readdirMode) (names []string, dirents []DirEntry, infos []FileInfo, err error) {
2.         ...
4.         for n != 0 {
5.                 // 使用系统调用获得目录项的数据
6.         // 目录项的元信息一般是存储在目录本身的数据里的，所以读这些信息和读普通文件很类似
7.                 if d.bufp >= d.nbuf {
8.                         d.bufp = 0
9.                         var errno error
10.                         d.nbuf, errno = f.pfd.ReadDirent(*d.buf)
11.                         runtime.KeepAlive(f)
12.                         if errno != nil {
13.                                 return names, dirents, infos, &PathError{Op: "readdirent", Path: f.name, Err: errno}
14.                         }
15.                         if d.nbuf <= 0 {
16.                                 break // EOF
17.                         }
18.                 }
20.                 buf := (*d.buf)[d.bufp:d.nbuf]
21.                 reclen, ok := direntReclen(buf)
22.                 if !ok || reclen > uint64(len(buf)) {
23.                         break
24.                 }
25.         // 注意这行
26.                 rec := buf[:reclen]
28.                 if mode == readdirName {
29.                         names = append(names, string(name))
30.                 } else if mode == readdirDirEntry {
31.                         // 这里的代码后面再看
32.                 } else {
33.                         info, err := lstat(f.name + "/" + string(name))
34.                         if IsNotExist(err) {
35.                                 // File disappeared between readdir + stat.
36.                                 // Treat as if it didn't exist.
37.                                 continue
38.                         }
39.                         if err != nil {
40.                                 return nil, nil, infos, err
41.                         }
42.                         infos = append(infos, info)
43.                 }
44.         }
46.         if n > 0 && len(names)+len(dirents)+len(infos) == 0 {
47.                 return nil, nil, nil, io.EOF
48.         }
49.         return names, dirents, infos, nil
50. }

复制代码

ReadDirent对应的是Linux上的系统调用getdents，这个系统调用会把目次的目次项信息读取到一块内存里，之后程序可以解析这块内存里的数据来获得目次项的一些信息，这些信息一样平常包括了文件名，文件的类型，文件是否是目次等信息。
老代码在读取完这些信息后会利用文件名再次调用lstat，这个也是系统调用，可以获取更完整的文件信息，包括了文件的拥有者，文件的大小，文件的修改日期等。
老的代码有啥问题呢？大的问题不存在，接口也算易用，但有些小瑕疵：

• 大多数时间遍历目次主要是要获得目次中文件的名字大概类型等属性，显然os.FileInfo返回的信息过多了。这些用不着的信息会浪费不少内存，获取这些信息也需要额外花时间——lstat需要去举行磁盘io才气得到这些信息，而目次里的文件不像目次项信息那样紧密的存储在一起，它们是分散的，以是逐一读取它们的元信息带来的负担会很大。
  
• 使用的系统调用太多了。由于我们测试目次的文件许多，但getdents大概要调用多次，这里假设为两次好了。对于每一个目次项，都需要用lstat去获取文件的详细信息，这样又有5000次系统调用，加起来是5002次。系统调用的开销是很大的，积累到5000多次则会带来肉眼可见的性能下降。现实上linux自己对lstat有优化，不会真的出现要反复进入系统调用5000次的情况，但几十到上百次还是需要的。
  

优化的代码其实只改了一行，是f.readdir(n, readdirDirEntry)，第二个参数变了。新代码会走上面解释掉的那段逻辑：

1. // rec := buf[:reclen] 防止你忘了rec是哪来的
2. de, err := newUnixDirent(f.name, string(name), direntType(rec))
3. if IsNotExist(err) {
4.         // File disappeared between readdir and stat.
5.         // Treat as if it didn't exist.
6.         continue
7. }
8. if err != nil {
9.         return nil, dirents, nil, err
10. }
11. dirents = append(dirents, de)

复制代码

取代lstat的是函数newUnixDirent，这个函数可以不依赖额外的系统调用获取文件的一部分元数据：

1. type unixDirent struct {
2.         parent string
3.         name   string
4.         typ    FileMode
5.         info   FileInfo
6. }
8. func newUnixDirent(parent, name string, typ FileMode) (DirEntry, error) {
9.         ude := &unixDirent{
10.                 parent: parent,
11.                 name:   name,
12.                 typ:    typ,
13.         }
14.     // 检测文件类型信息是否有效
15.         if typ != ^FileMode(0) && !testingForceReadDirLstat {
16.                 return ude, nil
17.         }
19.         info, err := lstat(parent + "/" + name)
20.         if err != nil {
21.                 return nil, err
22.         }
24.         ude.typ = info.Mode().Type()
25.         ude.info = info
26.         return ude, nil
27. }

复制代码

文件名和类型都是在解析目次项时就得到的，因此直接设置就行。不外不是每个文件系统都支持在目次项数据里存储文件类型，以是代码里做了回退，一旦发现文件类型是无效数据就会使用lstat重新获取信息。
如果只使用文件名和文件的类型这两个信息，那么整个遍历的逻辑流程到这就结束了，文件系统提供支持的情况下不需要调用lstat。以是整个遍历只需要两次系统调用。这就是为什么优化方案会快接近五倍的原因。
对于要使用其他信息好比文件大小的用户，优化方案现实上也有好处，因为如今lstat是延迟且按需调用的：

1. func (d *unixDirent) Info() (FileInfo, error) {
2.         if d.info != nil {
3.                 return d.info, nil
4.         }
5.     // 只会调用一次
6.         return lstat(d.parent + "/" + d.name)
7. }

复制代码

这样也能只管减少不须要的系统调用。
以是整体优化的原理是：只管充分利用文件系统自己提供的信息+减少系统调用。要遍历的目次越大优化的效果也越明显。
优化的支持情况

上面也说了，能做到优化需要文件系统把文件类型信息存储在目次的目次项数据里。这个需要文件系统的支持。
如果文件系统不支持的话最后还是需要依赖lstat去读取详细文件的元数据。
不同文件系统的信息着实太分散，另有不少过时的，以是我花了几天看代码+查文档做了下整理：

• btrfs，ext2，ext4：这个几个文件系统支持优化，man pages加文件系统代码都能证明这一点
  
• OpenZFS：这个文件系统不在Linux内核里，以是man pages里没提到，但也支持优化
  
• xfs：支持优化，但得在创建文件系统时使用类似mkfs.xfs -f -n ftype=1的选项才行
  
• F2FS，EROFS：文档没提过，但看内核的代码里是支持的，代码的位置在xxx_readdir这个函数附近。
  
• fat32，exfat：文档没提过，但看内核代码发现是支持的，不外fat家属的文件类型没有那么多格式，只有目次和普通文件这两种，以是代码里很粗暴的判定目次项是否设置了dir标志，有就是目次没有统统算普通文件。这么做倒是正常的，因为fat本来就不支持别的文件类型，毕竟这个文件系统连软链接都不支持，更不用指望Unix Domain Socket和命名管道了。
  
• ntfs：支持，然而如解释所说，因为ntfs和其他文件系统处理type的方式不一样，导致固然文件系统自己支持大部分文件类型，但type信息里只能获得文件是不是目次。以是它后面对于不是目次的文件会去磁盘上读取文件的inode然后再从inode里获取文件类型——现实上相当于执行了一次lstat，相比lstat减少了进入系统调用时的一次上下文切换，以是ntfs上优化效果会不如其他文件系统。
  

这么一看的话根本上主流的常见的文件系统都支持这种优化。
这也是为什么go1.16会引入这个优化，不仅支持广泛而且提拔很大，免费的加快谁不爱呢。
别的语言里怎么利用这个优化

看到这里，你应该发现这个优化其实是系统层面的，golang只不外是适配了一下而已。
确实是这样的，以是这个优化不光golang能吃到，c/c++/python都行。
先说说c里怎么利用：直接用系统提供的readdir函数就行，这个函数会调用getdents，然后就能天然吃到优化了。注意事项和go的一样，需要检测文件系统是否支持设置d_type。
c++：和c一样，另外libstdc++的filesystem就是拿readdir实现的，以是用filesystem标准库也能获得优化：

1. // https://github.com/gcc-mirror/gcc/blob/master/libstdc++-v3/src/filesystem/dir-common.h#L270
2. inline file_type
3. get_file_type(const std::filesystem::__gnu_posix::dirent& d [[gnu::unused]])
4. {
5. #ifdef _GLIBCXX_HAVE_STRUCT_DIRENT_D_TYPE
6.   switch (d.d_type)
7.   {
8.   case DT_BLK:
9.     return file_type::block;
10.   case DT_CHR:
11.     return file_type::character;
12.   case DT_DIR:
13.     return file_type::directory;
14.   case DT_FIFO:
15.     return file_type::fifo;
16.   case DT_LNK:
17.     return file_type::symlink;
18.   case DT_REG:
19.     return file_type::regular;
20.   case DT_SOCK:
21.     return file_type::socket;
22.   case DT_UNKNOWN:
23.     return file_type::unknown;
24.   default:
25.     return file_type::none;
26.   }
27. #else
28.   return file_type::none;
29. #endif
30. }
32. // 如果操作系统以及文件系统不支持，则回退到lstat
33. // https://github.com/gcc-mirror/gcc/blob/master/libstdc++-v3/include/bits/fs_dir.h#L342
34. file_type
35. _M_file_type() const
36. {
37.     if (_M_type != file_type::none && _M_type != file_type::symlink)
38.             return _M_type;
39.     return status().type();
40. }

复制代码

唯一的区别在于如果目标文件是软连接，也会调用stat。
python：使用os.scandir可以获得优化，底层和c一样使用readdir：https://github.com/python/cpython/blob/main/Modules/posixmodule.c#L16211，实现方法甚至类名都和golang很像，代码就不贴了。
总结

go固然性能上一直被诟病，但在系统编程上倒是不含糊，根本常见的优化都有做，可以经常关注下新版本的release notes去看看go在这方面做的积极。
看着简单的优化，背后的可行性验证确实很复杂的，尤其是不同文件系统在怎么存储额外的元数据上很不相同，光是看代码就花了不少时间。
前面提到的ntfs在优化效果上会办理扣头，以是我特意拿Windows设备测试了下，测试条件稳定：

可以看到几乎没什么区别。如果不是看了linux的ntfs驱动，我是不知道会产生这样的结果的。以是这个优化Windows上效果不理想，但在Linux和MacOS上是适用的。
大胆假设，小心求证，系统编程和性能优化的乐趣也正在于此。
参考

exfat的fuse驱动填充d_type的逻辑：https://github.com/relan/exfat/blob/master/libexfat/utils.c#L28
Linux的ntfs驱动需要获取文件的inode才气得到正确的file type：https://github.com/torvalds/linux/blob/master/fs/ntfs3/dir.c#L337

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。