Three Ways to Make HyperCrux Faster: A C Search Loop, New Storage Under Go or a New Engine in C

HyperCrux 0.1 is a Go library and command on top of SQLite, and it’s quick at the sizes it was built for. In the recorded benchmarks on a two-core cloud machine, a get by key takes 18 microseconds and a walk one link out 43 microseconds. A search among 100,000 vectors of 384 values takes 0.41 seconds. The question that comes up next is how much faster it could get, and what each step would cost.

There are three paths, from a small one that keeps everything to a large one that builds a new database. None of them is built yet. This post sets them side by side, and the largest one now has a written plan.

Three paths compared. A C search loop inside SQLite speeds up vector search with one C extension and keeps the SQLite file. New storage under Go speeds up key reads, and the SQLite file goes. A new engine in C changes everything for the most work, and the SQLite file goes.

Where the Time Goes Today

The benchmarks already say a lot about this. A search among 10,000 vectors of 384 values takes 42 milliseconds, about 4.2 microseconds a vector. A search among 100,000 vectors where only a tenth pass the filter takes 0.13 seconds. It compares as many vectors as the 42-millisecond search, so the extra 86 milliseconds go on the 90,000 rows that fail, about a microsecond each. That’s SQLite reading a row and testing it. By that measure, roughly three quarters of each comparison happens after SQLite hands the row over: the driver copies the vector into Go, and a Go loop decodes the floats one at a time.

Longer vectors cost more per value. Among 10,000 vectors of 1,536 values a search takes 0.12 seconds, so each extra value adds about 7 nanoseconds. The loop is only part of that: rows this long spill onto a second SQLite page, and each vector is copied into Go before the loop reads it.

One more figure matters for what follows. A committed write takes 0.35 milliseconds, and most of that, by our reading, is the disk confirming the data is safe. No rewrite removes that without weakening the guarantee. Gets and walks are fast already. A get is one indexed SQL query run through Go’s database/sql, a walk is a recursive SQL query, and neither has been timed in parts.

Path One: A C Search Loop Inside SQLite

The smallest step moves only the hot loop. A short C extension would run inside SQLite and compare each vector there, using SIMD instructions that work on several values at once. It would still add in float64, as today, so distances stay within rounding of today’s. The copy into Go would go away for every row, and the loop would get cheaper. The same code would speed up SQL’s distance(), since today every call crosses from SQLite into Go and back.

Everything else stays: the SQLite file, the rules stored in it as triggers, the Go API, the command and every test. HyperCrux already builds SQLite from C, so no new tools are needed. The cost is some C in a codebase that’s meant to need little attention, which is why this step waits until search speed holds someone back.

Path Two: New Storage Under Go

The middle step keeps HyperCrux’s Go layer and swaps SQLite for a storage engine written in C for HyperCrux, with a direct path to each record that never goes through SQL. Gets would speed up and the HyperCrux code would get leaner, since the triggers and the schema bookkeeping around them would go. Files could shrink as well, because each key is stored three times today: in its row, in the row’s primary-key index and in the key registry.

It would also cost HyperCrux what makes it worth having. The file would stop being an SQLite file, so a Python script that writes a HyperCrux file today by FORMAT.md’s rules couldn’t open it at all. SQL would have to be rebuilt on top, or shrink. And someone would have to build and prove a storage engine first, the hardest part of any database, while the Go layer still crossed into C for every row it read. On its own this path gives up too much for too little. Its one good idea, storage made for HyperCrux, is what path three takes all the way.

Path Three: A New Engine in C

The largest step, and the one aimed at the most speed, is a new database engine written in C with all four handles built in. It starts from what each handle needs. A key wants a hash lookup, and SQL wants to check fields record by record. Links want each record’s references in a list, and similarity wants a table’s vectors in one block. All of that is quickest in memory, and at HyperCrux’s sizes every record fits there, so the engine keeps the data in memory where a general database would use a B-tree on disk.

A link is a field holding other records’ keys, and a vector is a field holding numbers, so there’s only one thing to store: records with fields. Everything in memory can be rebuilt from the records, which means only the records have to survive a crash. They live in one append-only file, where a crash can only cut off the end. Every process that opens the database reads the file into its own copy in memory and keeps it up to date as other processes add to the file. One writer at a time appends to the file and syncs once per commit. The four handles can’t disagree, because they’re all views of one point in one file. Commits only add to the end of it, and when dead data is cleared out, a finished new file takes its place in one step, so a plain copy is a backup.

The price is real. Every process holds the whole database in memory, and opening reads the whole file. SQL would start as a defined subset, one table at a time plus walks, and walks cover what 0.1 used recursive queries for. The file format is new, which leaves SQLite’s tools behind for good. The engine would run on Linux only at first, on x86 and ARM, with macOS after. Even after the weeks of building and crash testing, it would take years of use before anyone should trust it with data.

The Beta plan sets out the design handle by handle, targets set against 0.1’s recorded numbers, phases that each end at a gate, and the decisions to make before any code is written. How long it would take has a post of its own.

What Happens Next

Nothing changes for 0.1. It stays on SQLite and keeps getting fixes. Path one is the natural next step whenever search speed becomes the limit, and its SIMD code could carry into path three if that ever starts. Whatever gets built, the numbers on this site will keep coming from recorded test runs, and the download page has 0.1 in the meantime.