The Benchmark

The following benchmark has been run against Linux 6.12: 86,501 files, 1,011 MiB of source, and I was comparing my solution (built for Gitmoap) with the standard Zoekt:

Gitmoap Zoekt
Index size 1,405 MiB (1.39× source) 2,760 MiB (2.73×)
p50, all queries 2.35 ms 1.75 ms
p95 58 ms 3,586 ms
p99 276 ms 6,003 ms
Building the Linux index 12.8 s 117.6 s

1. How trigram code search works

First off, a trigram is any 3 consecutive bytes. Hence, for the following word:

config

There will be four trigrams:

config con onf nfi fig 

The idea

At index time, we keep, for each trigram, a so-called posting list. This is nothing but a list of all the files that contain that specific trigram.

Now, at query time, what's done is the following:

  • Split the query into its trigrams;
  • Intersect their posting lists and take those files as candidates;
  • Open and search these files to find actual matches.

Toy example

Now, let me briefly expand a little bit more on the second step. Let's consider that we want to search for the config word above, hence our set of trigrams is: ["con", "onf", "nfi", "fig"]. Now, suppose our index is a hashmap like:

{ "gdf": ["file1", "file23", "file43"], "con": ["file2", "file53"], "ker": ["file2"], "onf": ["file53", "file423", "file9345"], "reg": ["file21"], "nfi": ["file2", "file53", "file21"], "rwe": ["file1", "file7"], "fig": ["file2", "file32", "file53"], ... } 

Of course we will then access the posting lists of only the trigrams of our word:

{ "con": ["file2", "file53"], "onf": ["file53", "file423", "file9345"], "nfi": ["file2", "file53", "file21"], "fig": ["file2", "file32", "file53"] } 

At this point, we just intersect these lists, namely, we find the files that are common to ALL of these lists. In this case that would be just one file: ["file53"].

The third step, then, opens that file and does a search for the config word.

2. Where the time goes

Steps 1 and 2 are of course incredibly quick, while the slow part of the algorithm is opening the candidate files and doing the actual search.

Some specific examples on the Linux codebase:

Query Every trigram (plain index) Opened by Gitmoap Actually match p50 (ms)
cfvei_transmit 1 5 1 0.08
omap2xxx_dss_dispc_hwmod 3 37 3 0.16
drm_bridge 286 529 220 1.91
unwrap() 30 262 15 0.24
ramp_delay 1,878 1,331 79 1.81
become 5,752 2,357 2,252 2.77
/fn\s+\w+_test/ 11,209 7,797 3 2.03
/\d{4}-\d{2}-\d{2}/ (scan) 86,078 86,078 351 59.65

3. Why three bytes?

Three seems like a sweet spot for this problem... how come?

  • Two bytes: There are only 65,536 possible pairs, hence, in source code the common ones would appear in almost every file, meaning that the filter would basically amount to nothing.
  • Four bytes: The lists filter better; however, there are many more distinct keys in the index. Moreover, three-letter queries cannot use the index, hence they would need a full scan.
  • Three bytes: Sweet spot that was used by Google Code Search, as described by Russ Cox in 2012.

4. Speeding up the algorithm

If we were just saving the trigrams with the posting lists containing only the files where the trigram occurs, the search would be slower, as we would need to open all those files and search through them.

Hence, in the postings we are also saving some more data that can allow us to discard files that for sure do not contain the word we are searching for.

I am going to explore two different kinds of data that we can save in the postings, as they have different trade-offs: positions or masks.

Positional (what Zoekt does): Each entry contains every offset where the trigram occurs in each file. How does this help? For our config you will need nfi to be at some position p and fig to be at p+1, which can then easily be checked from these lists without opening the file. The cost is bytes for each occurrence of the trigram in each file.
--> For the Linux codebase, when I built my engine this way, the postings came to 1,924 MiB.

Masks (from GitHub's Project Blackbird): This idea was developed at GitHub for their code search, and Cursor's post on fast regex search explains it really well. Each entry stores the file plus two single-byte summaries:

  • Position mask: bit p mod 8 is set for every position p where the trigram occurs (OR-ed together);
  • Next-byte mask: bit (next byte lowercased) mod 8 is set for each byte that follows each occurrence.

--> For the Linux codebase, the postings came to 361 MiB.

Let's see with a concrete example how these masks work.

Suppose we want to find the word become in the following content:

because the economy is common at home ^^^ ^^^ ^^^ ^^^ bec eco com ome <- all four present, no "become" 

On Linux, for example, a plain index would make the algorithm open 5,752 files while Gitmoap only opens 2,357.

Now, in that example what would be the values of those bytes?

bec at offset 0 0 0 0 0 0 0 0 1 rotate left by 1 0 0 0 0 0 0 1 0 eco at offset 12 0 0 0 1 0 0 0 0 AND 0 0 0 0 0 0 0 0 -> zero, skip the file 

If the result is zero, it means that the file, with certainty, does not contain the word become, meaning that it will never get opened. Conversely, if the result is not zero, it means that the file might contain become.

Of course, with this method we are losing some information to have a kind of heuristic that would at least allow us to remove some files from the possible candidates.

We are trading a smaller index size for a few false positives.

Currently, this is the trade-off that I've decided for Gitmoap: since all these indexes need to be stored in memory, postings more than 5 times smaller (and a whole index half the size) for about a millisecond of slowness in the p50 is a very acceptable trade (this delay is not really perceivable by humans anyway, and the network is what actually bounds a code search request's full round trip).

5. Should we compress the content?

LZ4 in 64 KiB blocks would halve the size of the index; however, in my testing, the p50 over all queries got a massive overhead, with a staggering 10-20x increase in time.

Conclusions

With the masks indexing implementation of Gitmoap compared to the positional one of Zoekt, the latter is faster at the median (p50), while Gitmoap is 20 to 60 times faster at p95 and p99. However, the Rust implementation, when indexing using the positional way, gave results that were a bit faster than Zoekt at the median too.

At the end of the day, that was a well-thought-out and accepted trade-off.

The correctness of the Gitmoap algorithm was tested against brute force, giving perfect results on a test suite of 10,000 cases.

Test your assumptions against the dumbest implementation you can write.

In Gitmoap, the code search feature is enabled on every tier (even the free plan), with a cap (limit) on how many bytes we are indexing... But still a very nice feature to have, that some other providers include only in their paid tiers.

Let me know if you would be interested in having a crate published with this implementation! I am probably going to do that soon enough, though it would be interesting for me to gauge the interest!

I hope you found this post interesting!

Till next time,
Kevin