mst hot paths: make the tree shape boring

written against zig 0.16.

Notes from making the AT Protocol Merkle Search Tree in Zat (atproto building blocks for zig) line up with Atmos (a Go AT Protocol implementation used as the performance reference) and then benching both.

the shape that won

The fastest useful representation was also the least clever one:

• loaded child edges are ?*Node
• missing child edges are null
• an unloaded lazy child is a real Node whose cid is set but whose entries/children are empty
• ensureLoaded mutates that stub node in place
• clean nodes keep their cached CID; mutation marks the changed path dirty

This is semantically enough for lazy/blockstore-backed MSTs, partial CAR trees, and normal repo authoring. The important part is that the inner loop sees pointer chasing, not a tagged edge union.

The earlier Zat representation used a ChildRef union with none/node/stub. That made partial-tree semantics explicit, but it also put an extra state machine on every child traversal. Atmos gets the same practical behavior by making "unloaded" a property of the node, not a property of the edge.

key comparison matters more than it looks

ATProto record keys have long shared prefixes:

app.bsky.feed.post/...
app.bsky.feed.like/...
app.bsky.graph.follow/...

A generic byte comparator is correct, but it is a hot tax. In this workload, std.mem.order(u8, a, b) spent too much time walking equal bytes one at a time.

A chunked comparator can preserve lexicographic byte order by loading big-endian machine words, comparing those words, and falling back to byte-level logic only around the first differing chunk. Big-endian chunk interpretation is the trick: numeric order of the word matches lexicographic order of the bytes.

Rule of thumb: when sorted keys share long prefixes and comparison is inside a tree walk, treat comparison as part of the data structure, not as a library afterthought.

small nodes do not want binary search

Another easy trap: using binary search for MST lookup because entries are sorted. That is the correct textbook move for large arrays, but ATProto MST nodes are small. In the 50k-record bench the largest node had 32 entries and lookup depth averaged about 7.7 nodes.

Binary lower-bound on those tiny slices meant unpredictable midpoint branches and less friendly memory access. A linear scan, Atmos-style, was faster despite doing more comparisons in the abstract. In the diagnostic bench, Zat getWithHeight dropped from roughly 213-235 ns/op to 135.78 ns/op after switching lookup to linear scan.

Keep binary search for mutation positioning if it helps there. For hot successful lookup through small sorted nodes, contiguous linear scan wins.

cached content addressing is part of the data structure

For an MST, rootCid() is not a cheap metadata call if every invocation reserializes and rehashes the whole tree. Dirty-node tracking changes the cost model:

• insertion dirties only the changed path
• clean subtrees return their cached CIDs
• serialization and hashing are paid for changed nodes

This matches the content-addressed semantics better than treating root computation as a full-tree fold every time.

direct serialization beats generic value construction

The MST node schema is fixed and small. Building generic CBOR values, allocating per entry, then serializing those values is a lot of machinery for bytes whose shape is known up front.

Direct DAG-CBOR serialization into a sized buffer was both simpler to reason about in the benchmark and faster. The caution is that this should stay covered by root-byte parity tests against a reference implementation, because hand serialization moves correctness responsibility into local code.

one representation beats fast/semantic forks

It was tempting to keep a rich semantic MST path for partial sync verification and add a separate fast path for authoring/lookup. Avoid that until the evidence forces it.

The better move was to ask whether the semantic states could be represented in a hot-path-friendly way. They could:

• "absent" is null
• "loaded" is a node pointer
• "known but not loaded" is a node pointer to a CID-only node

The result keeps one code path for lookup, mutation, lazy loading, partial trees, root calculation, and benchmark parity. That is easier to test and easier to keep Atmos-compatible.

One late example: tracking key ownership with a boolean on every entry fixed a theoretical borrowed-key/delete hazard, but it also widened the hot entry layout. The better fit was to make the MST lifetime-shaped: copied keys live with the tree, borrowed keys must outlive the tree, and delete removes the logical entry without reclaiming key storage. That matches the arena-style allocation already used by the rest of the structure.

zig-specific lesson

Zig gives you very explicit data layout and allocation control, but it does not automatically make an abstractly cleaner representation faster. If the workload is pointer-heavy and branch-heavy, the shape of the state machine is the performance story.

Useful questions before optimizing:

1. Can this tagged union become a pointer plus sentinel state?
2. Can caller-known facts, like MST key height, be threaded into the hot path?
3. Are we allocating typed intermediate values where the wire shape is already fixed?
4. Is a generic stdlib helper scalar where the competing runtime has a tuned primitive?
5. Can tests keep the rich semantics while the representation gets boring?

The representation, not the language, was the performance story: giving Zig the same boring problem that Atmos gives Go is what closed the gap.