Why Fast Search Starts Before You Type

microsoft/tgrep is a search tool for large codebases that builds a reusable index before it answers repeated queries. The central question here is simple: why would a grep-like command do work before anyone has typed a pattern, and what can that advance work safely buy? Understanding tgrep’s answer gives readers a practical way to judge its promise: when a persistent index can remove repeated scanning, when the full matcher must still take over, and why a slower fallback can be the correct behavior.

The cost hidden inside “search again”

A conventional repository search treats every query as a fresh inspection. It walks the tree, opens eligible files, reads their contents, and asks the matching engine whether each file contains the pattern. That is a reasonable design when the search happens once or the repository is small. It becomes a repeated tax in a large codebase. A developer may search for a symbol, change a call site, search for the symbol again, and then use a related pattern. An AI coding tool can create the same sequence at a much higher frequency.

The important cost is not just the number of characters in one pattern. It is the amount of repository data that must be touched again even when most files could never match. If a tree contains hundreds of thousands of files, a query for a distinctive function name still pays for the opportunity to find that name everywhere unless some earlier operation has recorded where it could occur.

That is the problem microsoft/tgrep is designed around. Its README describes ordinary grep and ripgrep scanning every file on every search—work proportional to the total bytes per query—while tgrep pre-builds a trigram index. The index records small fragments of text associated with files. A later query can use those fragments to avoid reading files that lack a necessary part of the pattern.

This is not the same as caching the answer to yesterday’s query. A query-result cache is useful only when the next request repeats the same question and the files have not changed. Tgrep stores a more general fact about the repository: which files contain particular three-byte fragments. Different literal searches can reuse that fact, and a regular expression can often contribute several literal fragments. The durable index is therefore a shared evidence layer between many questions, while the exact matcher remains specific to the current question.

That distinction also explains why an index cannot simply be trusted forever. The stored evidence describes a particular view of the files. If a file changes, a previously valid posting may no longer describe its contents. If the rules defining the searchable tree change, the index may contain too much or too little. Tgrep’s speed depends on reusing the evidence, but its correctness depends on knowing when the evidence no longer applies.

This changes the economics rather than abolishing cost. Index construction takes time, the index occupies storage, and the server that keeps it available consumes resources. The exchange is worthwhile only when later searches reuse the result. The more often a repository is searched, and the more selective the patterns are, the more opportunities there are to recover the initial investment.

tgrep’s four responsibilities

It helps to separate tgrep into responsibilities rather than think of it as “grep, but faster.” The index operation walks the repository and constructs the durable evidence used by later searches. The serve operation keeps that evidence available through a local client/server connection and can track changes. A search command turns the user’s pattern into requests against the index. Finally, the matching engine reads candidate files and decides whether the exact requested pattern really matches.

That last responsibility is the boundary that keeps the design honest. An index entry says that a file contains evidence compatible with a match; it does not say that the full regular expression matches there. The search path therefore has two distinct decisions:

  1. Candidate selection: Which files are possible matches according to cheap, reusable evidence?
  2. Verification: Which of those files satisfy the complete regex and the requested output rules?

The first decision is where tgrep tries to save work. The second remains authoritative. A candidate may survive because the index stores only a compact summary, because a summary can contain false positives, or because the regex includes structure that the index cannot represent exactly. A file that fails final verification is simply not a result.

The same separation governs what happens when indexed pruning is unavailable. A pattern may be too short to provide a useful three-byte fragment, or it may contain optional and wildcard behavior that imposes no fixed content. Some options change the set of files or the way bytes are decoded. In those cases, tgrep can inspect all eligible files directly instead of forcing an unsafe interpretation of an old index. “No index shortcut” means more work; it does not mean “no search.”

The server makes this arrangement reusable. The repository’s architecture describes a client sending a pattern over TCP to tgrep serve, which combines a memory-mapped on-disk reader with an in-memory overlay for files changed after the snapshot was built. Multiple clients can connect, so the cost of keeping the index warm is shared across requests rather than paid by every invocation.

The workflow also has a deliberately conservative readiness boundary. A cold or partial build is not treated as if it were a complete view of the repository. The server reports that complete hidden-file coverage is not ready, and the client can fall back to a local index or a filesystem scan. Returning a fast answer from only half the tree would make the result look precise while silently omitting files. In tgrep, completeness is part of the answer, not merely a startup detail.

A complete index is not automatically a current index either. Tgrep’s long-lived server needs a way to absorb ordinary edits and a way to recover when notifications are missed. That is why the architecture has a durable reader and a live layer rather than repeatedly rebuilding everything for each save. The details of those layers matter later, but the opening distinction is enough here: reusable state creates the opportunity for speed, and explicit state boundaries keep that speed from becoming silent omission.

flowchart LR A["Repository walk"] --> B["Build reusable trigram index"] B --> C["tgrep serve\n(durable reader + live changes)"] Q["Search query"] --> D["Plan necessary fragments"] C --> D D --> E["Candidate files"] E --> F["Read and verify\nfull regex"] F --> G["Results"] D --> H["No safe index shortcut\nor coverage unavailable"] H --> I["Filesystem scan"] I --> F

This flow explains why “instant search” is not the same as “the index already knows the answer.” The index narrows the work, the full matcher protects semantics, and the scan path protects coverage when the shortcut does not apply.

What the benchmark claim really says

The repository’s benchmark evidence supports a substantial but conditional claim. Its latest table reports 18 repository/platform cells from a 24 August 2026 sweep, with the index built before search timing began. tgrep wins 17 of the 18 cells. On the largest examples, it reports speedups of 17.6 times on Windows and 15.8 times on macOS for Chromium’s 504,351 files, and 38.6 times on Windows and 51.9 times on macOS for Gecko’s 387,841 files. These are measurements of a workload that repeatedly searches a large corpus after the indexing cost has been paid.

The initial cost is not trivial at the largest scale. The README reports an index build of about 248 seconds for Chromium on macOS, compared with about 3 seconds for Go on macOS; the benchmark document lists an index around 2,584 MB for Chromium and about 113 MB for Go. Those figures do not invalidate the design. They define the break-even question: a large repository searched often can amortize a substantial build, while a one-off query may not. A useful speedup ratio that excludes the build phase is informative for warm searches, but it cannot by itself describe total time for a single invocation.

The exception matters. On Kubernetes under Linux, the reported ratio is 0.93 times: tgrep takes about 101.8 milliseconds per query against ripgrep’s 94.4 milliseconds. The benchmark document attributes the near-loss to a warm page cache and the cost of delivering matches through the client/server path. Linux is also the weakest platform in the reported geometric mean, at 2.82 times, because a parallel brute-force scan can already be cheap when the data is warm.

The number of matches changes the equation too. A distinctive query benefits from eliminating files. A broad query that returns tens of thousands of lines may spend much of its time serializing, transmitting, deserializing, and printing those results. The index can select candidates efficiently while the result channel becomes the bottleneck. In that situation, tgrep’s central optimization is working, but it is no longer the dominant part of the query’s cost.

The benchmark tables are first-party measurements on shared GitHub-hosted runners, not a universal promise about every repository. Their strongest lesson is a decision rule: tgrep is most compelling when a large tree will be searched repeatedly with patterns selective enough to avoid most file reads. A one-shot search, a small or already-warm tree, a query with enormous output, or a request that changes the searchable corpus may favor direct scanning.

That rule also clarifies what must be learned next. Tgrep can only reuse evidence if the evidence is small, durable, and tied to a necessary property of the file. Its answer begins with the smallest useful unit of content: an overlapping three-byte fragment. Once that unit is understood, the index stops looking like magic and starts looking like a carefully limited statement about what a file must contain.

References