首页
/ Powerlevel10k 之 gitstatusd 极速目录遍历:ListDir() 五轮性能优化全记录(得分 100 到 143.3)

Powerlevel10k 之 gitstatusd 极速目录遍历:ListDir() 五轮性能优化全记录(得分 100 到 143.3)

2026-09-05 21:52:58作者:邵娇湘

本文以 gitstatus/docs/listdir.md 这份官方技术文档为主线,完整还原 gitstatusd 中 ListDir() 目录遍历函数从朴素实现到最终形态的五轮性能优化:arena 内存复用、openat() 替代 opendir()、直接调用 getdents64() 系统调用、以及手工重写的字符串比较。读完后,你将理解每一轮优化的动机、具体实现与实测得分(100.0 → 112.7 → 116.2 → 137.8 → 143.3),并能在 gitstatus/src/dir.cc 中看到这些优化最终落地的真实代码,从而掌握一套可直接移植到其他文件系统遍历场景的底层优化方法。

为什么 gitstatusd 必须把目录遍历做到极致

Powerlevel10k 主题依赖同仓库内嵌的 gitstatus 组件——其核心是一个用 C++ 编写的常驻进程 gitstatusd,用于以远高于 git status 的速度计算仓库状态(见 gitstatus/README.md)。

gitstatusd 判定"未跟踪文件"(untracked files)的方式是:把目录中的实际文件列表与 Git index 中的条目做比对。因此它必须列出仓库内每一个目录的内容。而这份列表还有一个硬性要求:必须按字典序排序,这样才能与同样有序排序的 Git index 做快速的双指针归并比较,而不是对每个文件做一次 O(N·M) 的查找。

这就是 ListDir() 的职责定义:给定一个目录,产出其中所有文件的有序名称列表。由于目录遍历是文件系统操作中最常见的动作之一,文档在开头即指出:这些优化不止对 gitstatusd 有价值,任何需要遍历文件系统的其他项目同样可以受益。

v1:朴素基线实现(得分 100.0)

文档给出的起点是任何 C++ 开发者都会写出的标准实现:opendir() + readdir() 循环,过滤掉 ".""..",最后 sort()。出错时返回空列表。

vector<string> ListDir(const char* dirname) {
  vector<string> entries;
  if (DIR* dir = opendir(dirname)) {
    while (struct dirent* ent = (errno = 0, readdir(dir))) {
      if (!Dots(ent->d_name)) entries.push_back(ent->d_name);
    }
    if (errno) entries.clear();
    sort(entries.begin(), entries.end());
    closedir(dir);
  }
  return entries;
}

其中 Dots() 是一个用于过滤 "."".." 的辅助函数:

bool Dots(const char* s) { return s[0] == '.' && (!s[1] || (s[1] == '.' && !s[2])); }

性能基线的测量方式是对一个含 32 个文件、文件名长度为 16 字符的典型目录跑 100 万次,耗时 12.7 秒。这个基准目录并非随意挑选——文档结论部分说明,它是采样自 gitstatusd 在 chromium 仓库上运行时的实际目录,以保证结果对真实负载有代表性。

v2:用 Arena 消除堆分配(得分 112.7)

有经验的 C++ 工程师会立刻指出 v1 的致命伤:返回 vector<string> 意味着每个文件名都要做一次独立的堆分配。而 ListDir() 会被调用成千上万次,内存是可以复用的。v2 引入一个 arena(内存池),在多次调用之间复用同一块内存,条目改为指向 arena 内偏移的裸指针,排序改用 strcmp()

void ListDir(const char* dirname, string& arena, vector<char*>& entries) {  // +
  entries.clear();                                                          // +
  if (DIR* dir = opendir(dirname)) {
    arena.clear();                                                          // +
    while (struct dirent* ent = (errno = 0, readdir(dir))) {
      if (!Dots(ent->d_name)) {
        entries.push_back(reinterpret_cast<char*>(arena.size()));           // +
        arena.append(ent->d_name, strlen(ent->d_name) + 1);                 // +
      }
    }
    if (errno) entries.clear();
    for (char*& p : entries) p = &arena[reinterpret_cast<size_t>(p)];      // +
    sort(entries.begin(), entries.end(),                                   // +
         [](const char* a, const char* b) { return strcmp(a, b) < 0; });   // +
    closedir(dir);
  }
}

为了便于对比,文档将得分以 v1 归一化为 100:

version 优化点 得分
v1 基线 100.0
v2 避免堆分配(arena) 112.7

消除堆分配带来 12.7% 的提速。(文档还顺手调侃:那几处 reinterpret_cast 至少能吓退误入代码库的前端开发者。)

v3:用 openat() 替代 opendir()(得分 116.2)

opendir() 是一个昂贵的调用:它的路径解析开销与目录路径中的子目录层数成正比,因为每一层都要做一次查找(lookup)。v3 改用 openat()——它接收父目录的文件描述符加子目录名,只需一次查找,CPU 时间更少。

这个优化的前提假设是:调用方已经持有父目录的描述符。文档说明,对 gitstatusd 而言确实如此(它自顶向下遍历仓库),许多其他文件系统遍历程序也满足这一条件。

void ListDir(int parent_fd, const char* dirname, string& arena, vector<char*>& entries) {   // +
  entries.clear();
  int dir_fd = openat(parent_fd, dirname, O_NOATIME | O_RDONLY | O_DIRECTORY | O_CLOEXEC);  // +
  if (dir_fd < 0) return;                                                                   // +
  if (DIR* dir = fdopendir(dir_fd)) {
    arena.clear();
    while (struct dirent* ent = (errno = 0, readdir(dir))) {
      if (!Dots(ent->d_name)) {
        entries.push_back(reinterpret_cast<char*>(arena.size()));
        arena.append(ent->d_name, strlen(ent->d_name) + 1);
      }
    }
    if (errno) entries.clear();
    for (char*& p : entries) p = &arena[reinterpret_cast<size_t>(p)];
    sort(entries.begin(), entries.end(),
         [](const char* a, const char* b) { return strcmp(a, b) < 0; });
    closedir(dir);
  } else {                                                                                  // +
    close(dir_fd);                                                                          // +
  }                                                                                         // +
}
version 优化点 得分
v1 基线 100.0
v2 避免堆分配 112.7
v3 openat() 打开目录 116.2

约 3.5% 的提速。

v4:直接调用 getdents64()(得分 137.8)

把文件名拷贝进 arena 并非免费,但看起来似乎无法避免。深挖之下发现:POSIX 的 readdir 在 Linux 上底层就是 getdents64 系统调用。虽然该调用没有 glibc 封装(其 man 页原话是"这不是你感兴趣的接口"),但文档选择直接用它,从而绕开整个 libc 目录读取栈。

需要两样前置设施。第一个是一个能按 8KB 块分配内存的简单 Arena 类:

class Arena {
 public:
  enum { kBlockSize = 8 << 10 };

  char* Alloc() {
    if (cur_ == blocks_.size()) blocks_.emplace_back(kBlockSize, 0);
    return blocks_[cur_++].data();
  }

  void Clear() { cur_ = 0; }

 private:
  size_t cur_ = 0;
  vector<string> blocks_;
};

第二个是自己定义的 dirent64_t 结构,因为该系统调用没有现成的 C 结构体可用:

struct dirent64_t {
  ino64_t d_ino;
  off64_t d_off;
  unsigned short d_reclen;
  unsigned char d_type;
  char d_name[];
};

随后是 v4 的 ListDir() 主体:循环调用 getdents64(),按 d_reclen 在变长记录数组中逐条推进,直接采集 d_name 指针(指向 arena 缓冲区内,无需拷贝):

void ListDir(int parent_fd, Arena& arena, vector<char*>& entries) {                       // +
  entries.clear();
  int dir_fd = openat(parent_fd, dirname, O_NOATIME | O_RDONLY | O_DIRECTORY | O_CLOEXEC);
  if (dir_fd < 0) return;
  arena.Clear();                                                                          // +
  while (true) {                                                                          // +
    char* buf = arena.Alloc();                                                            // +
    int n = syscall(SYS_getdents64, dir_fd, buf, Arena::kBlockSize);                      // +
    if (n <= 0) {                                                                         // +
      if (n) entries.clear();                                                             // +
      break;                                                                              // +
    }                                                                                     // +
    for (int pos = 0; pos < n;) {                                                         // +
      auto* ent = reinterpret_cast<dirent64_t*>(buf + pos);                               // +
      if (!Dots(ent->d_name)) entries.push_back(ent->d_name);                             // +
      pos += ent->d_reclen;                                                               // +
    }                                                                                     // +
  }                                                                                       // +
  sort(entries.begin(), entries.end(),
       [](const char* a, const char* b) { return strcmp(a, b) < 0; });
  close(dir_fd);
}
version 优化点 得分
v1 基线 100.0
v2 避免堆分配 112.7
v3 openat() 打开目录 116.2
v4 直接调用 getdents64() 137.8

结结实实的 20% 提速。还有一个"免费赠品":entries 中每个元素在偏移 -1 处恰好是 d_type(来自 dirent64_t 的内存布局),调用方可以零成本地区分普通文件与目录——gitstatusd 恰好需要这个信息。

v5:手工优化字符串比较(得分 143.3)

CPU profile 显示,v4 的 ListDir() 几乎把所有用户态 CPU 时间都花在了 strcmp() 上。原因在排序算法里:std::sort() 对短序列退化为 Insertion Sort,32 个元素正好落在阈值之下,而插入排序是 O(N²) 次比较。换 qsort() 或 Timsort 都没用——所有主流排序在小规模数据上最终都会落到插入排序。

既然减少不了比较次数,就加快每一次比较。strcmp() 逐字节比较,无法越过第一个 null 字节继续读,因为它不知道读后面的内存是否合法。但我们自己拥有缓冲区:缓冲区是 8KB 的 arena 块,而 Linux 上文件名最长 255 字节,所以把 getdents64() 的缓冲上限设为 kBlockSize - 256,就能保证读越界最后一个条目也是安全的:

int n = syscall(SYS_getdents64, dir_fd, buf, Arena::kBlockSize - 256);

于是比较函数可以换成固定长度的 memcmp()

[](const char* a, const char* b) { return memcmp(a, b, 255) < 0; }

这一版本身没有带来额外提速,但它暴露了下一个问题:d_namedirent64_t 中偏移 19 字节,导致 memcmp() 拿到的指针数值形如 N * 8 + 3,是 8 字节非对齐的。memcmp() 遇到这样的指针会先逐字节比较前 5 字节,之后才切换到 8 字节(乃至向量化)的大块比较,白白浪费了对齐优势。

v5 的解法堪称"又快又深奥":读取每个文件名时,先用 __builtin_bswap64 把它的前 8 个字节做字节序反转写回缓冲区。这样在比较时,一次小端 uint64_t 读取得到的整数值,其大小关系恰好等价于原始字节序列的字典序(第一个原始字节落在最高位上)。前 8 字节用一次 64 位整数比较搞定,相等时用 memcmp(a + 5, b + 5, 256) 兜底比较剩余部分(从偏移 5 开始,确保第 5~7 字节被覆盖)。排序结束后再把字节序换回来,调用方看到的就是正常的文件名。

uint64_t Read64(const void* p) {                                                          // +
  uint64_t x;                                                                             // +
  memcpy(&x, p, sizeof(x));                                                                // +
  return x;                                                                               // +
}                                                                                         // +

void ByteSwap64(void* p) {                                                                // +
  uint64_t x = __builtin_bswap64(Read64(p));                                              // +
  memcpy(p, &x, sizeof(x));                                                               // +
}                                                                                         // +

void ListDir(int parent_fd, Arena& arena, vector<char*>& entries) {
  entries.clear();
  int dir_fd = openat(parent_fd, dirname, O_NOATIME | O_RDONLY | O_DIRECTORY | O_CLOEXEC);
  if (dir_fd < 0) return;
  arena.Clear();
  while (true) {
    char* buf = arena.Alloc();
    int n = syscall(SYS_getdents64, dir_fd, buf, Arena::kBlockSize - 256);                // +
    if (n <= 0) {
      if (n) entries.clear();
      break;
    }
    for (int pos = 0; pos < n;) {
      auto* ent = reinterpret_cast<dirent64_t*>(buf + pos);
      if (!Dots(ent->d_name)) {
        ByteSwap64(ent->d_name);                                                          // +
        entries.push_back(ent->d_name);
      }
      pos += ent->d_reclen;
    }
  }
  sort(entries.begin(), entries.end(), [](const char* a, const char* b) {
    uint64_t x = Read64(a);                                                               // +
    uint64_t y = Read64(b);                                                               // +
    return x < y || (x == y && a != b && memcmp(a + 5, b + 5, 256) < 0);                  // +
  });
  for (char* p : entries) ByteSwap64(p);                                                  // +
  close(dir_fd);
}

文档注明:以上是 Little Endian 架构的实现;Big Endian 架构不需要 ByteSwap64(),反而还会快一点。

version 优化点 得分
v1 基线 100.0
v2 避免堆分配 112.7
v3 openat() 打开目录 116.2
v4 直接调用 getdents64() 137.8
v5 手工优化 strcmp() 143.3

结论:内核是最后的性能边界

文档的结论是:一系列渐进式改进让目录遍历相比朴素实现(v1)提速 43.3%,相比一位资深 C/C++ 工程师会写出的"合理实现"(v2)提速 27.2%。

但作者特别强调了证据边界:这些数字来自人工基准测试,真正的裁判是真实代码。幸运的是,各版本 ListDir() 在 gitstatusd 内部的相对表现与基准测试一致。最终版本 ListDir()97% 的 CPU 时间花在内核里;如果假设系统调用数量已是最小且调用本身最优,那么未来还能挤出的性能上限只有约 3%——ListDir() 里几乎没有可以优化的东西了。原文附带的 CPU profile(用 gperftools 采集、pprof 渲染)直观地展示了这一点:用户态火焰几乎不存在。

从文档到代码库:gitstatusd 中的真实 ListDir()

文档中的 v1–v5 是教学化的演化过程,而 gitstatus/src/dir.hgitstatus/src/dir.cc 才是最终落地形态。对照阅读能验证每一轮优化如何被工程化。

接口契约:dir.h 里的 API 说明

真实签名比文档版本多了两个能力参数(dir.h):

bool ListDir(int dir_fd, Arena& arena, std::vector<char*>& entries, bool precompose_unicode,
             bool case_sensitive);

头文件注释(dir.h)完整继承了文档里的关键约定,并补充了两点工程事实:

  • 每个追加条目都是 null 结尾字符串,偏移 -1 处是它的 d_type——正是 v4 中"免费赠品"的制度化;
  • 存在 Linux 与 POSIX 两套实现,Linux 版快约 20%(dir.cc 的注释同样写明 "about 20% faster");
  • 排序被有意并入目录遍历:在 Linux 上,getdents64 的 API 允许比普通的 vector<char*> 更快地完成排序;而 POSIX 版本则用通用的 StrSort() 在末尾统一排序;
  • "为获得最佳效果,请对多次调用复用同一个 arena 和 vector 以避免堆分配"——v2 思想的接口化。

Linux 路径:dir.cc 中的最终形态

Linux 实现(dir.cc)与文档 v5 一一对应,同时做了两处更严谨的落地:

constexpr size_t kBufSize = 8 << 10;
...
char* buf = static_cast<char*>(arena.Allocate(kBufSize, alignof(linux_dirent64)));
// Save 256 bytes for the rainy day.
int n = syscall(SYS_getdents64, dir_fd, buf, kBufSize - 256);
  • kBufSize - 256 的"雨天备份"注释直接对应 v5 中"为 256 字节的越界读留空间"的推导;
  • 分配改为带对齐参数的 arena.Allocate(kBufSize, alignof(linux_dirent64))
  • 一个值得注意的细节:dir.cc 里留有一段被注释掉的优化——"假设 getdents64 总是尽量填满缓冲区"。注释坦承这一行为不受规范保证,且对 gitstatus 实际性能无可测量的影响,因此被主动关闭。这是文档中没有、但真实工程取舍的补充证据。

手工排序比较(dir.cc)按大小写敏感与否做了模板特化:

template <bool kCaseSensitive>
void SortEntries(char** begin, char** end) {
  static_assert(kCaseSensitive, "");
  SwapBytes(begin, end);
  std::sort(begin, end, [](const char* a, const char* b) {
    uint64_t x = Read64(a);
    uint64_t y = Read64(b);
    // Add 5 for good luck.
    return x < y || (x == y && std::memcmp(a + 5, b + 5, 256) < 0);
  });
  SwapBytes(begin, end);
}

template <>
void SortEntries<false>(char** begin, char** end) {
  std::sort(begin, end, StrLt<false>());
}

可以看到 64 位字节交换技巧只用在大小写敏感路径上(大小写不敏感比较无法转成整数比较,直接走 string_cmp.h 中基于 tolowerStrLt<false>)。SwapBytes__builtin_bswap64 + memcpy 实现(dir.cc),并对非小端非大端架构直接 #error 拒绝编译——比文档版本更严格。

POSIX 路径:d_type 偏移 -1 的跨平台保证

非 Linux 平台(dir.cc)走 fdopendir + readdir,但它通过 DirentDup() 在 arena 中给每个名字显式前置一个 d_type 字节dir.cc):

char* DirentDup(Arena& arena, const struct dirent& ent, size_t len) {
  char* p = arena.Allocate<char>(len + 2);
  *p++ = ent.d_type;
  std::memcpy(p, ent.d_name, len + 1);
  return p;
}

这样"偏移 -1 处是 d_type"的契约在所有平台上都成立。此外还有 Apple 专属路径:macOS 上 HFS+ 目录名以 decomposed UTF-8(UTF-8-MAC)存储,dir.cc 通过 iconv 将其转成 precomposed UTF-8——这正是接口中 precompose_unicode 参数的用途;转换前先用一个字节扫描跳过纯 ASCII 名字,避免无谓开销。

调用方:index.cc 中排序列表的真正用途

ListDir() 的核心调用方在 index.cc。每次进入一个新目录时:

entries.clear();
arena.Reuse();
if (!ListDir(*dir_fd, arena, entries, caps.precompose_unicode, caps.case_sensitive)) {

随后(index.cc)就是文档开头说的那种归并:ListDir() 产出的有序条目与来自 Git index 的有序文件列表、有序子目录列表各走一个指针,逐次 str.Cmp() 比较,比较结果 <0 报 deleted、==0fstatat 判断 modified、>0 落空则成为 untracked 候选。排序列表在这里是线性扫描正确性的前提。

还有一个文档没有展开、但从源码结构可以确认的协同优化:untracked 结果缓存(index.cc)会先 fstat 目录,若目录 stat 与上次相同就直接复用上一轮缓存的未匹配条目,跳过整个 ListDir() 调用。也就是说,目录遍历的极致优化与目录 mtime 缓存是互补的两层防线。

ListDir() 的其他调用方还包括清理陈旧 .gitstatus.* 标记目录的 check_dir_mtime.cc,以及枚举松散 Git tag 的 tag_db.cc——说明这套底层设施已被抽象为 gitstatusd 内部通用的文件系统遍历原语。

Arena:从文档的 8KB 块到真实实现

文档 v4 中的玩具 Arena 在真实代码中演进为 arena.h 的完整类:默认 min_block_size = 64max_block_size = 8 << 10(8KB,与文档一致),快路径 Allocate() 只做一次对齐计算和边界判断,越界才走 AllocateSlow()Reuse() 则对应 index.cc 中每次 ListDir() 前的 arena.Reuse()——保留已有内存块、仅重置分配指针,这正是 v2"跨调用复用内存"思想的生产级实现。

要点回顾

  1. 需求驱动排序:目录列表必须有序,才能与 Git index 做 O(N+M) 的双指针归并(见 index.cc),排序因此被并入遍历函数内部;
  2. 内存复用(v2,+12.7%):arena 跨调用复用,消除每文件一次堆分配,落地为 arena.hReuse() 协议;
  3. 减少路径查找(v3,+3.5%):openat(parent_fd, name) 单次 lookup 替代 opendir() 的逐层查找;
  4. 绕过 libc 目录栈(v4,+20%):直接 syscall(SYS_getdents64, ...),自解析 dirent64 变长记录,名字指针原地指向 arena,并免费获得 d_type
  5. 让比较吃到向量化路径(v5,+4%):为 255 字节文件名上限预留 256 字节越界读空间,用"字节交换 + 64 位整数比较 + memcmp(a+5, b+5, 256)"替换 strcmp()
  6. 承认边界:最终实现 97% 的 CPU 时间在内核,用户态可优化空间仅剩约 3%——这组优化已经把"列出目录"这件事推到了系统调用本身的天花板之下。

这套"基准归一化 → 逐版本 A/B → profile 定位热点 → 对照真实代码验证"的方法,以及 arena 复用、openat 遍历、变长记录自解析这三个可直接移植的组件,使其对任何需要高频目录遍历的 C/C++ 项目都有参考价值。

登录后查看全文
热门项目推荐
相关项目推荐

项目优选

收起
kernelkernel
deepin linux kernel
C
33
18
ops-transformerops-transformer
本项目是CANN提供的transformer类大模型算子库,实现网络在NPU上加速计算。
C++
1.12 K
2.72 K
kernelkernel
openEuler内核是openEuler操作系统的核心,既是系统性能与稳定性的基石,也是连接处理器、设备与服务的桥梁。
C
528
588
ops-nnops-nn
本项目是CANN提供的神经网络类计算算子库,实现网络在NPU上加速计算。
C++
906
1.83 K
pytorchpytorch
作为 Ascend for PyTorch 社区的核心组件,TorchNPU 是昇腾专为 PyTorch 打造的深度学习适配插件,使 PyTorch 框架能够直接调用昇腾 NPU,为开发者提供昇腾 AI 处理器的超强算力。
Python
854
1.34 K
docsdocs
暂无描述
Markdown
891
5.79 K
jiuwenswarmjiuwenswarm
JiuwenSwarm 是一款基于openJiuwen开发的智能AI Agent,它能够将大语言模型的强大能力,通过你日常使用的各类通讯应用,直接延伸至你的指尖。
Python
3.53 K
1.01 K
ops-mathops-math
本项目是CANN提供的数学类基础计算算子库,实现网络在NPU上加速计算。
C++
1.34 K
1.45 K
cann-learning-hubcann-learning-hub
CANN 学习中心仓,支持在线互动运行、边学边练,提供教程、示例与优化方案,一站式助力昇腾开发者快速上手。
Jupyter Notebook
988
506
AscendNPU-IRAscendNPU-IR
AscendNPU-IR是基于MLIR(Multi-Level Intermediate Representation)构建的,面向昇腾亲和算子编译时使用的中间表示,提供昇腾完备表达能力,通过编译优化提升昇腾AI处理器计算效率,支持通过生态框架使能昇腾AI处理器与深度调优
C++
540
384