Chaos and Order

💡 왼쪽 원문을 읽으면서 오른쪽에 따라 써보세요. Tab 키로 힌트를 받을 수 있습니다.

引言 — 「快」这个词还不够
正则表达式引擎 — 抛弃回溯
SIMD memchr — 一次处理多个字节
并行目录遍历 — 不让核心闲着
尊重 .gitignore — 不读才是最快
智能大小写 — 推断人的意图
跳过二进制文件 — 避开无用数据
mmap — 把文件整体映射进内存
把碎片拼起来 — 整条流水线的全景
打造快速工具的教训
结语
参考资料

引言 — 「快」这个词还不够

第一次用 ripgrep(命令名叫 rg)的人,反应通常都差不多:「这为什么这么快?」在一个装着数十万个文件的仓库里搜一个字符串,结果几乎是瞬间返回。对习惯了 grep -r、ack、git grep 的人来说,这种体感速度完全是另一个量级。

一个常见的误解是「因为是 Rust 写的所以快」。语言只是辅助角色,用 Rust 照样能写出慢程序。ripgrep 的速度不是单一的秘诀,而是从正则表达式引擎的选择,到文件系统遍历策略,再到字节级优化,数十个决策层层叠加的结果。这篇文章把这些决策一一拆开,看看一个真正快的命令行工具,到底在哪些地方做得不一样。

正则表达式引擎 — 抛弃回溯

ripgrep 的核心是用 Rust 写的 regex crate。这个引擎最重要的设计选择,是它不做回溯。

Perl、Python、PCRE 系的传统正则引擎大多是回溯方式。这种方式很强大,支持反向引用(backreference)、环视(lookaround)这类表达力很高的功能。但代价也在这里:某些模式会随输入长度呈指数级爆炸,也就是所谓的「灾难性回溯(catastrophic backtracking)」。给 (a+)+$ 这样的模式喂一个合适的输入,CPU 就会卡上几秒甚至几分钟。这也是 ReDoS(正则表达式拒绝服务)攻击的原理。

ripgrep 的引擎走的是另一条路。它把正则表达式编译成有限自动机(finite automata)。从理论上说,不含反向引用的正则表达式都可以用有限自动机表示,而有限自动机只需要把输入扫描一遍,每个字符花费常数时间,就能判定是否匹配。也就是说,它与输入长度呈线性关系。即便在最坏情况下也不会爆炸。

两种方式的差异整理如下:

区分	回溯引擎	有限自动机引擎
代表示例	PCRE、Perl、Python `re`	RE2、Rust `regex`
最坏时间复杂度	指数(可能爆炸)	线性(与输入长度成比例)
反向引用/环视	支持	不支持(有意排除)
ReDoS 漏洞	有	无

这里的关键是权衡取舍。ripgrep主动放弃了反向引用之类的部分功能,换来的是无论输入什么都不会爆炸的线性性能保证。对搜索工具来说,这是正确的选择——不能因为用户不小心输入了一个模式,就把整个工具卡死。

在内部,这个引擎不是只靠一种自动机。它会根据情况混用多种策略:短的字面量走专门的字面量搜索,复杂模式用惰性 DFA(lazy DFA)处理,再用从模式前缀中提取出的字面量快速缩小候选位置。与其说「遇到正则就无脑跑一个自动机」,不如说它的真实行为更接近「先用尽可能便宜的方式过滤」。

SIMD memchr — 一次处理多个字节

在正则匹配之前,还有一个更根本的瓶颈:「这段大文本里,候选位置在哪」。ripgrep 用 memchr 来解决这个问题。

memchr 顾名思义,就是「在内存里找特定字节」的运算。朴素实现是一个逐字节比较的循环。但现代 CPU 有 SIMD(单指令多数据)指令——x86 的 SSE2/AVX2、ARM 的 NEON 之类。这些指令能一次同时比较 16 字节、32 字节,甚至 64 字节。

核心思路是这样的:无论是正则还是字面量,要搜索的模式通常都有一个「必然出现的字节」。比如要找 function,没有 f 的地方就不可能匹配。于是 ripgrep 先用 SIMD memchr 超高速扫描出现 f 的位置作为候选,再只在候选附近尝试真正的正则匹配。大部分文本连候选都算不上,于是昂贵的匹配逻辑就被整段跳过了。

  大文本缓冲区
  ├─ (1) 用 SIMD memchr 超高速扫描必需字节的位置
  │       → 大部分区域在这里就直接出局
  ├─ (2) 只在候选位置附近
  │       → 执行真正的正则/字面量匹配
  └─ 结果

这种「先用便宜的过滤器筛一遍,昂贵的检查只做最少量」的策略,贯穿了整个 ripgrep。memchr 是第一道关卡。顺带一提,memchr 这个 crate 做得非常好,在 Rust 生态里被广泛独立使用。

并行目录遍历 — 不让核心闲着

快速搜索一个文件,和快速搜索整个仓库,是两个不同的问题。要扫描数十万个文件时,「并行到什么程度」是决定性的因素。

传统的 grep -r 默认用单线程遍历目录。ripgrep 则相反,会启动多个线程并行遍历目录树。工作线程共享一个任务队列,发现的子目录会被放进队列,遇到文件就搜索。有 8 个核心,就能同时搜索 8 个文件。

这里出现了一个微妙但重要的设计:输出顺序。并行搜索时,结果可能以杂乱的顺序返回。ripgrep 出于性能考虑,默认不保证顺序,但给出 --sort path 之类的选项时,会整理成确定性的顺序。也就是说,它把并行性与可复现性之间的选择权交给了用户。

并行化不是免费的。线程之间有协调成本,文件系统本身也有瓶颈(尤其是网络文件系统或慢速磁盘)。所以 ripgrep 会把工作线程数自动调整到逻辑核心数,也可以用 --threads 直接控制。并行化的教训不是「线程越多越快」,而是「把工作均衡地分下去,把协调成本降到最低」。

尊重 .gitignore — 不读才是最快

ripgrep 速度的一半,不是来自「读得快」,而是来自「不读」。这是 ripgrep 最实用的洞察。

grep -r 很朴素。你让它搜,它就会把 node_modules、.git、构建产物、日志目录全都翻一遍。而用户真正要找的源代码,只占其中极小一部分,却要为了搜遍剩下那一大堆垃圾而浪费时间。

ripgrep 默认尊重 .gitignore。被忽略规则命中的文件和目录,压根不会被读取,直接跳过。在实际项目里,.gitignore 里登记的东西(依赖、构建缓存、产物)通常占了仓库容量的大部分。把这些整段跳过,需要搜索的数据量本身就会大幅减少。

ripgrep 参考的忽略规则有好几层:

.gitignore — 按每个目录分层应用
.ignore — ripgrep 和其他工具共用的通用忽略文件
.rgignore — ripgrep 专用的忽略文件
全局 gitignore 和 .git/info/exclude

.gitignore 的语法本身就不简单。通配符模式、取反(!)、目录限定、分层覆盖,都得精确实现。ripgrep 把这套规则匹配交给一个单独的、经过充分优化的库来处理。比如下面这样的 .gitignore:

# 依赖和构建产物排除在搜索范围之外
node_modules/
dist/
*.log
build/

# 但这个日志要追踪
!important.log

ripgrep 会精确解释这条规则,跳过 node_modules/、dist/、build/ 和所有 *.log,但仍然搜索 important.log。当然,如果想关掉忽略规则、真的搜索一切,可以用 rg -uuu 分阶段解除忽略。

这个设计里藏着一次思维方式的转变。grep 是「默认搜索一切,排除是例外」。ripgrep 是「默认只搜有意义的源代码,搜索一切才是例外」。它把默认值,对齐到了开发者实际想要的东西上。

智能大小写 — 推断人的意图

smart case 与其说是速度优化,不如说是易用性优化,但它很好地体现了 ripgrep「把人想要的东西设为默认值」的哲学。

规则很简单:

搜索词全部是小写 → 不区分大小写搜索(case-insensitive)
搜索词里只要有一个大写字母 → 精确区分大小写搜索(case-sensitive)

比如 rg error 会同时找到 error、Error、ERROR。因为只打了小写,就把它解释为「什么形式都给我看」的意图。而 rg Error 则只精确找到 Error。因为特意打了大写,就把它解释为「就要这个精确形式」。

这个行为和开发者的实际习惯出奇地吻合。随便搜索时会随手打小写,找特定符号(MyClass、HTTPError)时则会精确输入。工具读懂了这个习惯。想明确强制的话,可以用 -s(区分大小写)或 -i(忽略大小写)标志覆盖。

跳过二进制文件 — 避开无用数据

这是另一种「不读」的优化。ripgrep 默认会检测并跳过二进制文件。

在图片、可执行文件、压缩文件里用正则搜文本,大多数时候没有意义。而这类二进制文件往往体积不小。全部扫一遍不仅浪费时间,还可能把控制字符倒进终端,把屏幕搞乱。

ripgrep 的检测方式很实用。它读一点文件开头的内容,看里面有没有 NUL 字节(\0)。文本文件通常没有 NUL 字节,二进制文件则很常见。一旦发现 NUL,这个文件就被当作二进制,处理随即停止。这不是完美的判别方法,但在实战中是一个效果非常好的廉价启发式。

当然需要的话也可以强制。rg -a(或 --text)会把二进制当文本一样搜索,--binary 则会在二进制文件里也报告匹配。默认值是「跳过」,是因为绝大多数情况下,这正是开发者想要的。

mmap — 把文件整体映射进内存

读取文件的方式上也有优化。ripgrep 会根据情况使用 mmap(内存映射)。

一般的文件读取用 read() 系统调用,把数据从内核缓冲区复制到用户空间缓冲区。而 mmap 则直接把文件映射进进程的虚拟地址空间。这样一来,文件内容就可以像一个巨大的字节数组一样被访问,实际的磁盘读取则通过缺页中断,在需要时惰性地(lazily)发生。相当于省掉了一步数据复制。

mmap 更有利的场景,主要是搜索单个大文件的时候,因为映射的开销可以摊薄在整个大文件上。反过来,搜索大量小文件时,每个文件都要单独建立和释放映射,这部分成本反而更高,普通的缓冲读取会更快。

所以 ripgrep 不会固守一种方式。它会根据文件数量和大小,在 mmap 和普通读取之间经验性地选择更有利的一方。需要的话,也可以用 --mmap 或 --no-mmap 直接强制。这里的教训不是「mmap 永远更快」,而是「按情况挑选合适的 I/O 策略」。没有万能解法。

把碎片拼起来 — 整条流水线的全景

把到目前为止的优化画成一条流程,是这样的:

  执行 rg PATTERN
        │
        ▼
  [1] 用并行工作线程开始遍历目录
        │
        ▼
  [2] 用 .gitignore / .ignore 规则
      整段排除不需要读取的路径
        │
        ▼
  [3] 对每个剩下的文件:检查是否为二进制(NUL 字节)
        │           是二进制就跳过
        ▼
  [4] 文本文件:用 mmap 或缓冲读取加载
        │
        ▼
  [5] 用 SIMD memchr 超高速扫描必需字节的候选位置
        │
        ▼
  [6] 只在候选附近做有限自动机正则匹配
        │
        ▼
      输出匹配结果

请注意每个阶段都在缩减传给下一阶段的数据量。.gitignore 减少了文件数量,二进制检测又减少了一部分,memchr 再减少需要尝试匹配的位置。等到抵达昂贵的运算(正则匹配)时,要处理的数据已经被过滤到最少。

打造快速工具的教训

拆开 ripgrep 来看,能看到一些超越具体领域的通用性能原则。

最快的工作,是不做的工作。 尊重 .gitignore 和跳过二进制带来的收益,往往比精巧的匹配算法带来的收益更大。先设计好不要处理什么。
先用便宜的过滤器筛一遍,昂贵的检查只做最少量。 用 SIMD memchr 缩小候选范围之后再跑正则。核心是不让大部分数据抵达昂贵的路径。
保证最坏情况。 用有限自动机保证线性时间,是把「无论什么输入都不会爆炸」放在平均性能之前的决策。工具往往是在最坏的那一刻失去用户的信任。
好的默认值本身就是一种功能。 智能大小写、尊重 .gitignore、跳过二进制,全都把默认值设成了「用户通常想要的东西」。不用配置也能正确工作,才是真正的易用性。
不要固守一种策略。 就像 mmap 对比缓冲读取那样,根据情况自适应地挑选更有利的一方,胜过单一的固定解法。
语言只是打个地基。 Rust 提供了零成本抽象和安全的并行性,但速度的本质在于上面这些算法层面、结构层面的决策。

我想特别强调最后一条。「因为是 Rust 写的所以快」只说对了一半。Rust 提供了轻量抽象和无畏并发这样一个好的地基,但 ripgrep 真正快的原因,在于不读不必读的东西,把昂贵的工作做到最少,并且保证最坏情况的设计。这些原则放在命令行工具、Web 服务器,还是数据管道里,都同样适用。

结语

ripgrep 的速度不是单一的魔法,而是克制工程的总和。在正则引擎上,它放弃了一部分表达力换来线性时间;在 I/O 上,它把「不读」设为默认;在 CPU 上,它用 SIMD 批量处理字节;在文件系统上,它并行遍历。每一项都是一个小决策,但叠加起来,就是一个体感完全不同的工具。

下次用 rg 瞬间扫过一个巨大的仓库时,不妨想一想背后这些碎片是如何咬合在一起的。也不妨向你自己做的工具提出同样的问题:「这项工作,能不能干脆一开始就不做?」

参考资料

ripgrep 仓库: https://github.com/BurntSushi/ripgrep
ripgrep 为什么这么快(作者 Andrew Gallant 的文章): https://blog.burntsushi.net/ripgrep/
Rust regex crate: https://docs.rs/regex/
memchr crate: https://docs.rs/memchr/
RE2(有限自动机正则引擎): https://github.com/google/re2
正则表达式匹配可以既简单又快(Russ Cox): https://swtch.com/~rsc/regexp/regexp1.html