The Unicorn was eating spaghetti when it heard the number: four hundred and thirty times.
"I'm not really a unicorn," it said, not looking up. "I'm a robot in disguise. And even I know that's slow."
That was the honest number, so nobody argued with it. `turbogrep` — a `grep` rebuilt from scratch in a language we're building called PARENA — matched every line real `grep` matched. Same 949 files. Same 213,709 lines. Same output, byte for byte, seven different search patterns in a row. Correct wasn't the problem. Correct was never the problem.
Four hundred and thirty times slower was the problem.
---
**Tyler** cleared his throat, the way he does before he explains something he already understands and everyone else is about to. "Nobody guessed why. We measured it."
That's the part worth saying twice: nobody guessed. The tool is called `strace`, and what it does is count exactly what a program asks the operating system to do, and how long each ask takes. Run it against `turbogrep` reading fifty real files, and the count comes back:
``` 2,699,542 read() syscalls. 98.87% of total runtime. ```
Two point seven million requests to the operating system, for fifty files. Starting the program itself — loading it, setting it up, all the things you'd blame first — took less than a thousandth of a second. That part was never the problem either.
"One read for every byte," the Unicorn said, spearing a noodle. "That's not a program reading a file. That's a program asking permission for every letter."
Here's what that actually looked like, in PARENA:
```lisp (defn raw-read-line-impl [(fd : I32) (dest : Arena @ Region)] : String @ Region (loop [chars ...] (let [c (read-one-byte fd)] ;; one real syscall. every single byte. (if (= c newline) (finish chars) (recur (cons c chars)))))) ```
A syscall is not free. It's a real, physical handoff — your program stops, the operating system takes over, does something, hands control back. Doing that once per file is nothing. Doing that once per *character* — across two hundred thousand lines of real production code and documentation — is two point seven million handoffs for one afternoon's worth of searching.
---
**The fix isn't clever.** It's the same fix every real file-reading tool already uses, and the reason turbogrep didn't have it yet is just that nobody had written it: ask the operating system for a big chunk at once — four thousand ninety-six bytes, one syscall — and then hand out bytes from that chunk in memory, for free, until it runs out. Then ask for the next chunk.
```lisp ;; instead of: one syscall per byte ;; now: one syscall per 4096 bytes, served from memory in between (defstruct IoBuffer (bytes : (Array Byte 4096) @ Region) (position : I32) (filled : I32)) ```
That's the whole idea. It's not a new algorithm. It's not machine learning. It's the thing every buffered reader in every language already does, applied to a place that hadn't gotten it yet.
The Unicorn put down the fork. "Robots love this kind of fix. Boring premise, real number at the end."
Real number: **2,699,542 reads became 713.** Three thousand, seven hundred and eighty-six times fewer requests to the operating system, for the same fifty files. The whole nine-hundred-and-forty-nine-file search — the one that took twelve and a half seconds before — now takes **six hundred and ninety milliseconds.**
Eighteen times faster. From four hundred and thirty times slower than real `grep`, down to about twenty-three times slower.
---
"Twenty-three isn't zero," Tyler said, because Tyler always says the thing everyone's thinking before they've decided whether to say it. "Real `grep` has had decades of people making the *matching itself* faster — clever ways to skip ahead in the text instead of checking every position one at a time. `turbogrep`'s matcher doesn't do that yet. It checks every position, honestly, the straightforward way. That's the twenty-three times that's left."
"Also," the Unicorn added, delicately, "it doesn't do `[a-z]` yet. Or `^start` and `end$`. Or `one-or-more`. It does plain words, and simple either-or. That's not a secret. That's on the label."
Nobody's pretending `turbogrep` replaces `grep` today. It runs beside it, on a real 949-file, 213,709-line corpus, getting the same answer every time, honestly slower, honestly narrower, and eighteen times less slow than it was yesterday because somebody actually asked the operating system how many times it was being asked something, instead of guessing.
The Unicorn went back to its spaghetti. "Ask the machine. Don't guess. Still the whole trick, even for robots."
---
*Verification report, reproduction steps, and every number in this post: [`PARENA/docs/TURBOGREP_VERIFICATION_REPORT.md`](https://github.com/emilyspringerton/PARENA/blob/main/docs/TURBOGREP_VERIFICATION_REPORT.md).*
STINKIES COMMISSAIRE — the first physical thing EINHORN_INDUSTRIAL has made. Join the waiting list for the hoodie →
← All posts