The Best Time to Go Deep

On Saturday I started porting a concurrent B-tree from Rust to C++ for DuckDB. By Monday, I had shoal: four header-only C++17 maps, with agents writing most of the code. I spent those three days reading design notes, steering the port, chasing performance gaps down to the instruction, reviewing diffs, and throwing away what was wrong. The iteration speed was new. The judgment it took drew on years of building search engines and, more recently, DuckDB extensions at Altertable.

The starting point was Xiangpeng Hao's bbtree, the Blessed B-tree, released that Saturday: a Rust B+ tree with design notes, a cost model and formal proofs. We wanted a map like that inside DuckDB, which is C++, and the Rust crate's own numbers gave us a bar to aim for. The next day, Shreya Shankar highlighted it as a case study in AI for systems development: experienced humans, good metrics and cost models, and agents writing code and tests. That was the loop I was already working in.

By Monday, shoal had a concurrent and a single-threaded tree map, two hash maps, zero dependencies, and SIMD node search on SSE2, AVX2, AVX-512 and NEON, with tests across Linux, macOS and Windows and sanitizer coverage. On the measured workloads, it was at parity or ahead of Rust on most single-threaded operations. In the 14-thread lookup race with half the keys missing below, its tree and hash maps each led the C++ maps we compared in their category.

This post is about why that is possible now, and why it still was not easy.

Low-level systems work has always been gated by the cost of one iteration. You suspect the program is doing unnecessary work, change the code, rebuild it, and measure the result. Then you inspect the machine instructions produced by the compiler to understand why it got faster, or why it did not. Much of the time goes into setting up the experiment and gathering enough evidence to decide what to try next. Supporting several processor types and compilers multiplies that work.

With agents, I could delegate the implementation and measurement work, and pursue independent investigations in parallel. Here are three examples; shoal's design notes have the low-level details:

• Doing less work for the same lookup. A function call can involve bookkeeping: saving the caller's working data, calling the function, then restoring that data. The C++ version was doing more of this than Rust. We adjusted the code so the compiler could combine small functions into their callers, an optimization called inlining. One lookup went from 372 machine instructions to 341, compared with Rust's 357.
• Spending less effort waiting. C++ inserts matched Rust when one thread worked alone, but fell 5–7% behind with several threads. When one thread held a lock, the others repeatedly checked whether it was free. Our waiting loop was checking too aggressively on Apple processors. Adopting the same processor instruction Rust used reduced that repeated checking, bringing the extra instruction count with several threads close to Rust's.
• Avoiding wasted guesses. Processors often guess which way an if will go and start work before they know the answer. In our lookup benchmark, half the keys were missing, so those guesses were frequently wrong and work had to be discarded. We rewrote the result selection so it did not depend on that guess, then checked that the compiler preserved the change. In a single-threaded test with all keys already in the processor's cache, throughput rose from 80 to 120 million lookups per second.

Each investigation started with an explanation of where we expected time to go. We then measured the work the processor actually did and traced it back to the source code. Agents handled much of the repetitive work: rebuilding, collecting measurements and comparing the C++ and Rust versions. I still had to review the changes and check that the measurements answered the right question.

This kind of systems work gives agents useful feedback. We compare results against C++'s standard map, check that the tree stays internally consistent, and measure the processor time each operation takes. Those checks make an idea easier to test. They still leave judgment calls about whether the tests reflect real usage, whether the measurements are reliable, and whether a speedup is worth the added complexity across the platforms we support.

Here is the part the hype leaves out. Several of the most consequential decisions in shoal drew on problems I had been burned by before.

• Benchmarks lie on a laptop. Back-to-back runs at 8 threads moved by up to 15%, more than the gaps we were chasing. An agent left alone will happily run a benchmark five times and report the median. We judged parity by instruction and cycle counts instead, and compared maps only within the same run.
• Keep related data together. A processor can spend more time waiting for data from memory than working on it. One possible fix is to ask it to fetch data before it is needed, a technique called prefetching. But if each lookup has to visit several scattered locations, our first priority is to store the information it needs together, reducing those trips to memory. We allow prefetching in a specific case: when processing several lookups together, we can request the next piece of data for one while working on another. The judgment is in deciding whether to reduce the waiting or reorganize the data so there is less to wait for.
• Measure what users will run. We could make the benchmark look faster by turning off a compiler-added check that detects certain memory errors. But shoal becomes part of DuckDB when DuckDB is compiled, so it inherits DuckDB's compiler settings, including those checks. Disabling them only in our benchmark would improve the score without making the version inside DuckDB any faster. We needed to optimize under the settings we would actually ship.
• Know when to change the design. Our first hash map was the slowest in the comparison. Finding a value required following a long chain of references through memory, with each step needed before the next could begin. We built another version that stored values directly in the table instead of behind several layers of references, removing much of that chain. It also let threads read without updating shared bookkeeping. The important decision was recognizing that the design itself needed to change before spending more time tuning individual operations.

Passing correctness tests would not have settled these decisions. Agents helped implement and investigate the alternatives; I had to decide which evidence mattered and which tradeoffs we could ship.

That judgment is not something you pick up from a prompt. I spent years building search engines at Exalead and Algolia, where the whole game is memory layout, posting lists, merge policies and tail latency on hardware you do not control. Those lessons keep coming back. And at Altertable we have spent the last year inside DuckDB's internals: rewriting NetQuack to be 4000x faster, building a MATCH_RECOGNIZE that scales, session windows and journeys, and upstreaming the fixes. shoal's single-threaded hash map follows DuckDB's own aggregate hash table, because we had already read that code closely.

If the judgment is the scarce part, the leverage is in making it reusable. Two things did most of the work.

Rules in the repository. Credit here belongs first to Xiangpeng's original AGENTS.md for bbtree. That was the starting point for how we guided agents on shoal. We carried the approach into shoal's own AGENTS.md and adapted it as the C++ work progressed: reason about the cost model, then measure; fix layout before reaching for prefetching, with a narrow exception for batch lanes; keep benchmark iterations under five minutes; investigate noisy measurements instead of repeatedly averaging them. Design decisions land in design/03-decisions.md with their rationale and measurements, and the code cites those notes. Those notes are the agent's memory between sessions and the reviewer's map. They also record what I asked for at each phase, and what I pushed back on in review.

Skills across repositories. The workflows I want every agent to follow (profiling with Instruments, systematic debugging, harsh reviews, writing plans) live in skillbrew, my curated collection of Agent Skills. It vendors skills from across GitHub as plain files, pins each to its upstream revision, and adapts them with a semantic patch, so updates keep my local changes and come back as a normal Git diff to review. It installs in Claude Code, Codex, Cursor and most other harnesses:

Copy
npx skills add redox/skillbrew

We raced shoal on the workload of bbtree's own README race: 10M random UUID keys, half the lookups missing, all 14 cores of a MacBook Pro M4 Pro, every map at its best API. The charts below use the updated runs from shoal PR #3, with one run per workload.

In the 50%-missing workload above, shoal's bulk tree lookups deliver roughly 18–20× the throughput of folly's skip list and oneTBB's ordered map. Its bulk hash lookups lead Boost's by 39% (551 versus 397 million lookups per second).

We also tested the same 10M keys and 14 threads with only 10% of lookups missing. Here are the results from that benchmark run, in millions of lookups per second:

With 10% missing, shoal's bulk hash lookups lead Boost's by 62% (510 versus 315 million lookups per second), while its tree map retains its lead over the ordered maps shown.

Finally, we reversed the mix: 90% of lookups missing, with the same 10M keys and 14 threads. This benchmark run shows where Boost still has the advantage:

Here, Boost's bulk hash lookups lead shoal's by 15% (927 versus 808 million lookups per second). shoal's tree map still leads the next-fastest ordered map by roughly 24×. The hash-map result is a useful reminder: which map is fastest depends on how it is used.

Against the Rust crate it ported, shoal is at parity or ahead on most single-threaded workloads.

All of it is open source, Apache-2.0 or MIT, at github.com/redox/shoal, with the benchmarks and their raw output, so you can check every number above. Next, we'll explore whether shoal can help DuckDB or DuckLake. We already see uses for it in the private DuckDB extensions we maintain at Altertable.

These three days changed my sense of what I can take on. Ideas that I would once have set aside because of the time needed to implement and test them now feel within reach. The years spent learning how systems behave still matter: they help me choose what to try, recognize a misleading result, and decide when to change direction. Cheaper iterations let me put more of that experience to work.

Pick the hard problem. Bring your cost model. Write your judgment down where the agents can read it. And then iterate faster than you ever could.

Thanks to Xiangpeng Hao for bbtree, the design notes and the cost model that made a faithful port possible.