A Secret Too Long to Look For
I had budgeted about fourteen seconds for the scan of the laptop. It ran for 366. The same walk, once I found the cause, takes 18.8 seconds, and nothing on the laptop changed in between.
The laptop was fine. What had changed was the list of things I had asked it to be searched for.
What the search is
I keep a small defensive tool that reads my own machines the way an attacker would. One of its checks starts from the credentials a machine declares in its configuration, takes each value as a literal run of bytes, and looks for those exact bytes everywhere the value is not supposed to be: the transcripts the coding agents leave behind, the shell histories, temporary directories, browser stores, caches. A secret that some session once printed to its own terminal is still sitting in that session’s transcript, and nothing but a byte search will say so.
It ran on the box at home first. The laptop is a different machine, and in the way that matters here it is a poorer one: no GNU grep, no ripgrep, no node. There is the system’s BSD grep, and there is the system’s perl.
Choosing by measurement
I timed both on one directory of agent transcripts, 158 MB, with the 56 patterns the box’s stores declare.
BSD grep, fixed strings, patterns read from a file: 32 seconds, which is 4.5 MB per second, and the time grows linearly with the number of patterns.
Perl, handed the same 56 strings as one alternation of quoted literals: 0.7 seconds. Its regex compiler notices an alternation of plain literals and builds a trie out of them, so every position in the input is checked against all 56 needles at once. Forty-five times faster on the same bytes.
That was the decision, and the measurement behind it was correct.
366 seconds
The full walk covers 154,928 files, 19.3 GiB, in four workers. When it came back at 366 seconds I went looking in the usual places. The disk. The file count. A root I had not meant to include. A worker starved by the other three.
Per byte, the walk had run at 3 MB per second. That is slower than the grep I had rejected.
The roots were the same roots. The script was the same script. What was not the same was the needle set, because on the laptop the tool searches for the union of what both machines declare, and the laptop declares things the box does not. One of them is the sign-in token for one of the coding tools I use. It is a JWT, and it is 1,940 bytes long.
Take that one needle out: 144 MB per second. Put it back: 3. The box’s perl is 5.42 and the laptop’s is 5.34, and both do exactly the same thing.
Two hundred and fifty-five
Perl’s regex compiler stores a literal string in a node whose length field is one byte. A literal longer than 255 bytes is split into a chain of nodes. The trie is built over an alternation whose branches are single literal nodes, and one branch that is a chain is enough for the compiler to decline the trie. What runs instead is the plain thing: at every byte of the input, try alternative one, then alternative two, then the remaining fifty-four.
There is a tunable for the trie, a ceiling on how large it may grow. Raising it does nothing here, because the trie is not too big; it was never built.
Nothing reported that. The regex compiled. Every match it found was correct. The fast path had not failed; it had a condition, the condition was on the length of a string a vendor decides, and one input had crossed it. The only instrument that registered anything was the clock, and it registered 26x.
A prefix and a comparison
Each needle’s first 255 bytes go into the alternation. At a match, the whole needle is compared against the input byte for byte, and a match that fails the comparison is not a hit. The reader carries the tail of each 16 MiB chunk into the next so a needle straddling the boundary stays whole, and two needles that share their first 255 bytes are told apart at the comparison.
The walk now takes 18.8 seconds for the same 154,928 files.
What I had actually measured
The 45x was real, and it was a fact about my 56 needles on the day I measured them. Keys, tokens, passwords: all short. I read that number as a property of the tool, and the tool has no such property. It has a fast path with an entry condition I did not write, could not see, and had never tested against a value I was not yet searching for.
A benchmark on a fixed input is a claim about that input. Every fast path I have ever leaned on, a query planner choosing an index, a JIT staying on its compiled tier, a regex engine building its trie, is a conditional, and the condition is usually on a property of the data rather than the code. There is no error in this failure mode. There is the slow path, producing correct answers, for as long as nobody times it.
The token is still 1,940 bytes. The regex looks for the first 255 of them, and only asks about the rest when it has to.