系统与基础设施lists.freebsd.org
为什么 GNU grep 这么快
Why GNU grep is Fast
2010 — 2022，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
这是 FreeBSD 邮件列表上一篇广为流传的帖子，解释 GNU grep 为什么快：核心在于 Boyer-Moore 字符串搜索算法配合精心优化的内部循环和 I/O，让程序在搜索时“几乎什么都不做”。作者用一句名言点题——让程序变快的秘诀是让它少做事。
为什么经久不衰：它用极短的篇幅讲透了算法选择与工程优化如何相辅相成，多年来反复登上首页，至今仍是理解性能优化的经典入门材料。
HN 评论精选
算法选择是工程权衡：小文本暴力法够用，grep 面对的海量输入才让 Boyer-Moore 物有所值
我几年前测试过各种字符串搜索算法，暴力搜索的性能出奇地好，以至于选算法成了工程上的权衡。在《白鲸》末尾找一句话暴力法只用 8ms，比 Boyer-Moore 慢 7 倍。但我们多数人搜的不是《白鲸》，而是 HTTP 头、用户输入或文档段落，所以大多数语言和库都用暴力法——初始化 Boyer-Moore 可能反而更慢。但 Boyer-Moore 对 grep 是完美选择：Unix 上的典型输入都是日志文件、目录树、程序输出等海量文本，小小的跳转表初始化成本会被 I/O 和文本量淹没。
jakevoytko查看英文原文
I tested string searching algorithms a few years ago[0][1], and Brute Force was surprisingly performant, enough that picking a string searching algorithm becomes an engineering tradeoff. It found a sentence fragment at the end of Moby Dick within 8ms, 7 times slower than Boyer-Moore. But most of us aren't searching Moby Dick, but rather a HTTP header, some user input, or a paragraph of a document. Even long-winded users won't write Moby Dick into your <textarea>. Most languages and libraries use brute force for this reason - initializing and using Boyer-Moore may be slower than brute-forcing the text. Sometimes "practically nothing" is just a brute-force search. But Boyer-Moore is the perfect choice for Grep! The likely inputs on Unix are all huge: log files, entire directory trees, output pipes from loud programs, etc. The cost of initializing a small skip table is overwhelmed by the cost of I/O and the potential volume of text. It's not surprising that they've gone to some lengths to optimize the core inner loops and the I/O in that context. [0] http://www.jakevoytko.com/blog/2007/12/11/fun-with-string-searching/ I've declared bankruptcy on broken TeX and code examples... WordPress mangles them every few updates. [1] http://www.lysium.de/blog/index.php?/archives/201-Fun-With-String-Searching.html A few improvements to the code in my post
Boyer-Moore 的反直觉设计（匹配串越长反而越快）体现了顶尖的算法思维
Boyer-Moore 是让我清醒认识到自己在程序员能力谱系中并不出众的例子之一。有些算法的巧思会让你震撼。最有趣的是，此前大多数模式匹配算法在匹配串变长时会变慢，而 Boyer-Moore 反而变快了！
jacquesm查看英文原文
Boyer-Moore is one of the examples that made me realize clearly that on the larger scale of programmer competence I'm nobody special. Some algorithms show such out-of-the-box thinking that it blows your mind. The most interesting thing is that most pattern matching algorithms up to then got slower with longer match strings, but Boyer-Moore actually got faster! To quote Majikthise: "Bloody hell, now that is what I call thinking."...
性能优化的核心原则是减少工作量，而非提高单步效率
“让程序变快的关键是让它几乎什么都不做”——这是我很久以前在这里发过的一句话的改写：“你无法让程序跑得更快，只能让它做更少的事。”虽然不完全正确（有博士论文专门研究例外情况），但当你需要优化程序时，这是极好的起点。
RiderOfGiraffes查看英文原文
This: > The key to making programs fast is > to make them do practically nothing. > ;-) is a paraphrase of something I posted here a long time ago: > You can't make programs run faster, > you can only make them do less. While not entirely true (and Ph.D. theses have been written about the corners where it's wrong) it's an excellent start when you have to make a program run faster.
实测数据印证 GNU grep 的优化远胜 BSD grep，差距可达数十倍
值得指出的是 OS X 用的是 BSD grep。通过 Homebrew 安装 GNU grep 后差异惊人：同一个 1.5GB 的日志文件，GNU grep 搜 "foobarbaz" 用时 1.3 秒，而系统自带的 BSD grep 用了 37 秒；即使是对 BSD 有利的行首正则 ^INFO，也是 0.6 秒对 3.6 秒。
Twirrim查看英文原文
It's probably worth pointing out that OS X is using BSD grep. You will see a phenomenal difference if you install the gnu grep via homebrew: $ homebrew info grep GNU grep, egrep and fgrep https://www.gnu.org/software/grep/ /usr/local/Cellar/grep/3.3 (21 files, 885.3KB) * Poured from bottle on 2019-01-03 at 12:23:37 From: https://github.com/Homebrew/homebrew-core/blob/master/Formula/grep.rb ... This is a very arbitrary example, but I've got 1.5Gb application log sitting on my machine right now that'll suffice. I'll even do this in a way that might give a slight performance advantage to BSD, by using gnu grep first: $ time /usr/local/bin/ggrep "foobarbaz" application.log real 0m1.319s user 0m0.948s sys 0m0.345s vs OSX's grep: $ time /usr/bin/grep "foobarbaz" application.log real 0m37.225s user 0m31.036s sys 0m1.286s 1s vs 37s. Same file. There's nothing odd about the file, straight boring application logs, and the line starts with the logging level in capital letters. So I can use a regex that is pinned to the start of the line, about as optimal as you can get: first gnugrep: $ time /usr/local/bin/ggrep -c "^INFO" application.log 1527786 real 0m0.622s user 0m0.323s sys 0m0.292s then OS X's native bsd grep: $ time /usr/bin/grep -c "^INFO" application.log 1527786 real 0m3.588s user 0m3.206s sys 0m0.349s BSD grep was significantly better than the prior search, but it is still notably slower than the gnu grep. In my experience, this isn't the most pathological example, but it's close. Note that this also applies to other tools that leverage grep under the surface, like zgrep etc. I've specifically aliased grep over to ggrep in my shell so that I'm avoiding bsd grep whenever I can: $ alias grep alias grep='/usr/local/bin/ggrep'
Unix 经典工具的优化深度超出新手想象，不要轻易以为能手写更快的版本
职业生涯早期，和多数新手一样，我以为针对特定目的精心手写的 C 程序会比 Unix 工具快得多。但我一次也没能超过 grep、cut、cat 这些工具的速度。那时我才意识到这些工具写得有多好、做了多少优化。
abhinai查看英文原文
Early on in my career, like most novice programmers, I thought that custom written C programs could be much faster than unix tools if written well and for a specific purpose. However, I could not beat the speed of unix tools like grep, cut or cat even once. That is when I realized just how well written these tools are and just how much optimization work has been done.
历次讨论
同类还值得读
TTY 揭秘（2008）
The TTY demystified (2008)
经典文章深入剖析了 Unix/Linux 中 TTY 子系统的工作原理，包括线路规程、终端驱动、信号与控制字符等机制。
系统与基础设施上首页 11 次 · 2009–2025linusakesson.net编辑精选Xplain：为普通人讲解 X11
Xplain – Explaining X11 for the rest of us
《Xplain》是作者（HN 用户 Jasper_）写的一系列 X11 长文，用他在浏览器中重建的 X11 绘图模型做交互演示，讲解 X11 的绘图模型与窗口系统设计。
系统与基础设施上首页 6 次 · 2013–2020magcius.github.io编辑精选旋风教程：为 Linux 创建极小 ELF 可执行文件（1999）
A Whirlwind Tutorial on Creating Really Teensy ELF Executables for Linux (1999)
breadbox 写于 1999 年的经典教程，主题是如何为 Linux 手工构造并裁剪出体积极小的 ELF 可执行文件。
系统与基础设施上首页 6 次 · 2007–2025muppetlabs.comPostgreSQL 内部原理
The internals of PostgreSQL
《The Internals of PostgreSQL》是一本免费在线书籍，系统讲解 PostgreSQL 的内部实现，包括查询处理、并发控制、WAL、缓冲区管理等核心机制。
系统与基础设施上首页 5 次 · 2017–2025interdb.jp编辑精选给分布式系统新人的笔记（2013）
Notes on Distributed Systems for Young Bloods (2013)
一篇面向分布式系统新手的经验笔记，作者以格言式的短条总结了多年实战中踩过的坑，涵盖一致性、延迟、背压、监控、CAP 定理等主题。
系统与基础设施上首页 5 次 · 2013–2024somethingsimilar.com编辑精选