rawgrep

Benchmarks

Mean wall time. 75 warm runs after 5 warmup runs, and 10 cold runs, with OS cache dropped before each.

Tool cache is each tool's own persistent cache. For rawgrep it is the Fragment Cache, for fff it is its bigram inverted index. ripgrep has no persistent cache, so its two rows per cache state are just repeat runs.

For rawgrep, Tool cache off (--no-cache) disables only the Fragment Cache. The Directory Snapshot and Binary Verdicts caches stay on, since they are part of how rawgrep stands in for the general-purpose caches of the kernel.

Wall time, in milliseconds

Peak Resident Set Size (RSS), in MiB

rawgrep won 12 of the 16 scenarios. With warm OS cache and Tool cache on, it is 2.5× to 3.5× faster than fff and 4.0× to 6.4× faster than ripgrep. With cold OS cache and Tool cache off, rawgrep’s lead over fff shrinks to 1.06× to 1.25×.

Of the four losses, three are to fff (cold OS cache, Tool cache on), by 1.08× to 2.37×. That is to be expected, since fff relies on much heavier caching (see Design). The fourth one is on the Linux regex pattern (warm OS cache, Fragment Cache off), where rawgrep trails ripgrep by about 7 ms and fff by about 4 ms. rawgrep will likely win this one too in a future patch...

On memory, rawgrep uses 6% to 28% less than ripgrep on the Chromium tree, but 172% to 224% more on the Linux tree, though its peak never exceeds 40 MiB. fff’s peak RSS is not in the table, since nearly all of it lives in the long-running fff[d] process, not the benchmarked fff[q] client. On the Chromium corpus, fff[d] sits at about 250 MB after indexing and climbs to 2.43 GB during search, where it stays, even when idle. Although, I should add that fff-grep configures fff-search with an unlimited memory budget, so that it runs as fast as it possibly can.

Also, even with --no-cache, fff[d]’s SharedFilePicker still indexes the existing files, and from what I've seen, that indexing cannot really be turned off. This likely explains why fff is faster than ripgrep in six of the eight runs with the Tool cache off.

System information

Design

Tools like fff, Zoekt, ugrep, Google’s codesearch and others keep their own persistent caches, and those caches are large: often tens of times the size of rawgrep’s, and tens to hundreds of times as slow to prepare. That space is paid for on disk, and paid for again in RAM, because their pages usually tend to stay resident. Some of them, for instance fff, also demand a background file watcher, that also keeps the persistent cache always in RAM. By design, rawgrep has no file watcher. By design, rawgrep is a one-shot program. By design, Rawgrep’s caches are kept as light as they can be kept, while still providing the most performance benefit. Here is everything rawgrep stores inside ~/.cache/rawgrep/ after the benchmarks above, not counting a few empty lock files:

rawgrep has no subcommand for preparing its caches, and by design it never will. It is fast enough to build them in passing, as a side effect of searching. Every run updates the caches automatically, but only when an update is actually necessary. The very first write, starting from no caches at all, happens after all the searching is done and all the matches are printed, and with warm OS cache it stays well under 100 ms of wall time, even on the Chromium corpus.

Each of these caches, and the rest of rawgrep’s machinery, is explained below.

Features

Fragment Cache

The Fragment Cache is a rather small and heavily tuned cache, and it exists to answer one question as cheaply as possible: given this pattern, can a file be skipped without being read at all? It is inspired by the fragment-based filtering of nowgrep and works much like a Bloom filter with explicit tracking.

A fragment is a small sliding window of 3 or 4 bytes taken from the pattern and hashed. Searching for ERROR: produces three of them:

ERRO
 RROR
  ROR:

For every file, rawgrep keeps a compact bitset of the fragments it has seen, that is trusted only while the file's ctime is unchanged. A later search can then rule a file out the moment one of the fragments it needs is known to be absent. Because the cache is built from fragments rather than whole patterns, even a different pattern profits from earlier searches whenever the two share fragments.

Literal Extractor

Real patterns are rarely plain strings. The Literal Extractor digs the literal text out of more sophisticated kinds of patterns, such as regular expressions and alternations, and works in conjunction with the Fragment Cache, so that even a pattern that looks hopelessly dynamic can be filtered by the literals hiding inside it.

Binary Verdicts cache

Binary files rarely deserve a search. Between runs, rawgrep accumulates what it learns about each file, from probing its contents to looking at its name and extension, and collects it into the Binary Verdicts cache. On the next run it already knows which files to skip, unless you pass --binary, which would force rawgrep to skip this cache. Binary Verdicts are likewise keyed on ctime.

Directory Snapshot cache

The Directory Snapshot Cache follows naturally from rawgrep being a raw partition scanner. Bypassing the VFS also means bypassing the kernel’s directory cache, so every directory would otherwise be decoded from its on-disk structures on every run. Internally, in rawgrep, a directory entry is packed down to just 12 bytes, so for directories that have not changed, rawgrep skips that decoding: it packs their entries into the Directory Cache. A snapshot is trusted only while the directory’s mtime and ctime still match and, following the racy-git rule, only if both are older than the moment the snapshot was written.

Disk Warmness Checker

A cold run and a warm run are different problems. The Disk Warmness Checker inspects which virtual memory pages are resident and adapts the hinting algorithms accordingly.

Stale Pages Detector

This isn’t really a feature, but it’s quite an interesting detail.

Reading the block device directly brings a problem that conventional greps never meet: the device has a page cache of its own, separate from the per-file one. When a file is edited, writeback goes around that cache, so blocks cached before the edit stay stale until they are dropped. Calling sync() does not help, and dropping the whole device cache on every run would make every run cold.

So rawgrep drops only what can actually be stale: the pages of files whose ctime shows they changed since the last boot. A tiny memo file records which of those files’ pages it has already dropped and re-read, so it does not drop them again on every run, and files that have not been written to stay warm.

Download

You can download the binaries from the v0.3.1 release page:

• rawgrep-x86_64, with runtime SIMD dispatch
• rawgrep-x86_64-v3, built for the v3 subset, with AVX2 baked in

Usage

$ rawgrep TODO
$ rawgrep '[A-Z]+_SUSPEND' ../linux

Permissions

rawgrep reads raw block devices such as /dev/sda1, which the OS protects. Instead of running it under sudo every time, you grant the binary a single Linux capability, CAP_DAC_READ_SEARCH, which does exactly one thing: it bypasses file read permission checks, so any user who can run the binary can read any file on the partition.

$ sudo setcap cap_dac_read_search=eip ./rawgrep

To check what the binary has, or to revoke it and go back to sudo:

$ getcap ./rawgrep
./rawgrep = cap_dac_read_search+eip

$ sudo setcap -r ./rawgrep

Capabilities are tied to the binary file itself, so run setcap again whenever you replace it with a new download. rawgrep deliberately ships no script that runs sudo for you: the command is a single line, and you should see exactly what it does.

Going further ...

You can skip this step. rawgrep keeps its on-disk Fragment Cache mlocked in memory once it is mapped, so a large scan under memory pressure cannot evict it. Locking memory is possible without any permissions, but only a small amount, which is not enough for the caches, even on the Linux corpus. Locking all of it requires root or the cap_ipc_lock capability. Without that, rawgrep still works fine and falls back to a best-effort strategy that is usually just as fast, but can occasionally be slower on a cold cache under heavy concurrent memory pressure. To grant both capabilities in one command, use this instead of the one above:

$ sudo setcap 'cap_dac_read_search,cap_ipc_lock=eip' ./rawgrep

Links

• Issues: github.com/rakivo/rawgrep/issues
• Updates: x.com/marktyrkba
• Email: marktyrkba456@gmail.com