Ch.13: Algorithms: Why grep Is Fast

0:00 Search a huge log for error. The obvious loop tries every starting position. But grep can sometimes reject several positions after inspecting just one character. Which sounds suspiciously like the optimization that makes a slow test run faster because it stopped checking the answer. The tests are green, the assertions are gone, everyone's delighted. But we can actually prove which positions are impossible and skip those checks safely. Okay, a speedup with the answer still attached. Let's hear it. Imagine a five-letter window sliding over text, looking for error.

0:32 Its last slot contains an X. There is no X anywhere in the word we're searching for. So that placement fails. But how much of a jump does one wrong character really buy us? Enough to move the entire window past that X. GNU grep's original author, Mike Haertel, described avoiding inspections as a source of speed. Then let's walk through that jump ourselves. I want to know exactly which possible matches we're ruling out. First, take that five-slot window with X at its right edge. We're using plain uppercase English.

1:04 Move the window one place right. The X is still inside, just one slot closer to the left. So the window still can't contain error. Exactly. Keep moving and that X stays disqualifying until the window has passed it entirely. Sure. Let me do the rest. Slide until X leaves through the left side. Now the window starts just after it, five positions beyond where we began. That's it. In this strip, the next five letters spell error. We check them and find our answer. Oh, nice. The other placements never needed their own comparisons.

1:37 As long as they contained X, the remaining letters couldn't save them. Now consider a separate strip of text. The 5th character is E, and error begins at that E. Would you jump five places again? No. E could be the beginning of error. I'd align the start with that E, four places along, and check from there. Yes. A full five-place jump would miss that match. So the allowed distance depends on which character we found and where it appears in our pattern. And we can prepare those distances once. The inner loop gets a lookup table instead of reasoning through the whole window every time. Right. That's the kind of skipping Boyer-Moore uses.

2:18 According to GNU's performance manual, it uses that algorithm for a single fixed pattern when feasible. Got it. Fixed pattern means those exact characters. Two searches can look similar at the command line and take different matching paths underneath. But I still want to separate two costs. The matcher skipped comparisons inside the text. Did it also avoid reading that text from the disk? We haven't shown that. The operating system can still deliver buffers containing those characters. What we've proved is enough to skip candidate starts safely.

2:50 But the candidate idea could help with a harder request. Suppose we need error, then a space, then one or more digits. A regex, or regular expression, describes that extra rule. Error 5:03 qualifies. Error banana doesn't, even if that's how the incident feels. A fruit-related outage would at least have a memorable name. But both lines contain error. Could literal searching still help? Yeah. Literal means exact text. Every real match needs that word, so search for it cheaply first. Then verify the complete rule on surviving candidates.

3:26 Ah, okay. The banana line reaches verification and gets rejected there. A candidate can be wrong; the filter cannot throw away a valid answer. That's how ripgrep's author describes it: find candidates using useful literal text, then bring in the full regex matcher when needed. For example, if error appears on nearly every line, the filter won't save much. Most of the file still reaches verification. Whereas a rare required word can, you know, cut out a lot of checks. Same technique, very different payoff depending on the input.

3:59 Take a different request: error or warn. Searching only for error would lose every warn-only match. Yep. You need to cover both alternatives. Just because a word shows up in the pattern doesn't mean every match has to contain it. That gives us a filter we can trust. So what happens inside the full check when several alternatives are still possible? Now let's give the verifier an actual branching case. Imagine a pattern with two optional A slots, followed by B. Each A may be present or absent. And the input is just A, then B.

4:33 One A to assign to either optional slot. Right. One route puts the input's A in the first slot and skips the second. The other leaves the first empty and fills the second. So both routes can reach the same point, waiting for B, with that final B still unread. Exactly. If we're only asking whether the pattern matches, keeping two copies of that waiting point buys nothing. Their remaining job is identical. Oh, I see. Read B, and either history succeeds. We need one marker at that point, not separate work for both ways of arriving.

5:08 That point is a state. The matcher tracks a set of possible states as characters arrive. Duplicate arrivals at a state get merged. Instead of exploring one route, failing, and returning to try another. That's backtracking, and branching can give it an enormous number of routes to revisit. Russ Cox's implementation walkthrough shows exactly that saving. Keep track of where the routes can end up, without carrying every history along. So if I point this at a log that keeps growing, what does that do to the cost?

5:39 For the basic method, the bound depends on pattern size times input length. Fix the pattern, double the text, and that bound doubles. Okay. I think we still need to watch pattern size. A bigger pattern can mean more states to process. It can. Every active state still needs attention. Our two routes, though, are waiting for the same B. One marker is enough for that shared wait. And features matter too. Rust's regex library leaves out backreferences, which ask for the exact text captured earlier. That guarantee doesn't cover everything called a regex.

6:13 So leave those extra features aside. Search for exact text again, but several patterns together: spin, pin, and pine. The last two share their first three letters. Build that shared beginning once. Then let's scan spine. Just before its final E, we've found two answers: spin itself, and pin at the end. Right. Now the E arrives. Nothing in our list extends spin any further. But its ending, pin, can still grow into pine. So keep pin as useful progress, then take that E. We find pine without going back and reading its beginning again.

6:49 Exactly. That shared structure has a link from spin to its useful ending. The input keeps moving forward even when the current path can't continue. Finishing spin doesn't wipe the slate clean. We've already read the beginning of pine. All three answers fit inside that one word, spine. That's Aho-Corasick's shared-scan idea. GNU documents using it for multiple fixed patterns when feasible, instead of requiring a separate file scan for each. Well, imagine a reviewer saying, give it a million patterns, then the file only needs one pass.

7:22 Where's the bill hiding? In building and storing the machine, for a start. The pattern set isn't free. Reporting a huge number of matches also costs time. And we've asked for every match, including overlaps. That gives three here. Ask instead for whole lines containing a match, and this line appears once. Sure. So which result are we buying with that scan? Whatever the caller requested. Which means a fair speed comparison has to agree on the answer, not just hand two programs the same text. Next, that same text has to reach the matcher.

7:58 Ripgrep's author, Andrew Gallant, describes changing how his early implementation did that. He initially used memory maps: access file contents through memory addresses and let the operating system bring the data in. My first thought is that mapping ought to win. Why copy chunks into a buffer when the file could look like memory? Well, take his workload of opening and searching many small files. Creating and dismantling those mappings had a cost of its own. So he tried buffered reading, copying a chunk into working memory, searching it, then getting the next one.

8:30 Yep, and the prototype was faster in those experiments. His large-file test went the other way; mapping helped there. Huh. It's tempting to blame the visible copy. The bookkeeping inside the operating system is, I mean, easier to leave out of the mental model. It really is. One setup for a large file and repeated setup for many little files aren't the same workload. Current ripgrep supports both input strategies. Those historical results explain an engineering decision, not a ratio for today's laptop.

9:01 A faster search loop can disappear inside the cost of opening the files. But even inside a buffer, we might do work too soon. Haertel's 2010 account has another detail: postpone finding the lines themselves. Hold on. Grep prints matching lines. Wouldn't finding the line breaks come first? You'd think so. His account describes searching the raw buffer first, then finding the surrounding newlines after locating a match. So a rare match lets you defer that boundary search for lots of irrelevant text.

9:34 You don't split everything into lines before searching it. Exactly. Some options, including requesting line numbers, disabled that shortcut in his account. The output request could force extra work even with the same pattern. And for existence alone, GNU's current manual describes quiet mode stopping after success. That can leave the rest unread, beyond saving comparisons in a buffer. So whether a shortcut is legitimate depends on what you asked for. Otherwise we could be celebrating a program that simply left something out.

10:05 Imagine a teammate's benchmark: same repo, new tool, finished instantly. But debugging the missing result reveals that ignore rules excluded the file containing the error. A fast empty result is, honestly, quite a convincing demo until you need the answer. Very efficient at searching the wrong files. Ripgrep respects ignore rules by default, so check the actual file set before attributing the difference to its matcher. Then preserve the matching rules too. GNU documents performance differences between locales, the settings for character and language rules.

10:38 Changing those for speed can change results. That leaves us with a useful comparison: same files, same matching semantics, same requested output. Now investigate what work each implementation avoided. Sources are linked in the description. So speed comes from knowing what you can leave undone. Sometimes that's a candidate start; sometimes it's repeated matching history or work on irrelevant lines. The skipped work still needs a reason. Our X rules out whole placements. In the separate E case, we jump less far because the answer might start there.

11:11 Right. I want that reasoning in a code review before I celebrate the benchmark. Otherwise we're back to the green tests with the assertions missing. Yeah. Keep the assertions. Next we'll look at Bloom filters, another way systems avoid unnecessary lookups. We'll pin down what their answers promise, and what still needs checking. Thanks for listening to Learning Podcasts.