Gold vs. Xudanu: Subsystem Complexity Comparison
Detailed side-by-side of every major subsystem, with estimated Big-O complexity and status alignment.
Methodology: Gold has almost no formal Big-O annotations (exactly one O(log) confession in the entire codebase). Complexity estimates below are derived from code structure analysis — tree heights, data structure choices, and algorithm patterns. Where Gold acknowledges inefficiency, it is noted.
1. Summary Matrix
| Subsystem |
Gold Approach |
Xudanu Approach |
Alignment |
Gold Complexity |
Xudanu Complexity |
Verdict |
| Core tree |
Enfilade (Split/Loaf/Dsp nodes) |
OrglRoot (Leaf/Split/Dsp nodes) |
Same shape |
O(log n) |
O(log n) |
Equivalent |
| Splay |
9-case rotation table |
SplayResult with split |
Same concept |
O(log n) |
O(log n) |
Equivalent |
| Region algebra |
XnRegion (sorted intervals) |
XnRegion (transition list) |
Same model |
O(n) contains* |
O(log n) contains |
Xudanu faster |
| Canopy filtering |
Balanced binary canopy + flags + cache |
Balanced binary canopy + flags (no cache) |
Partial |
O(1) flag check |
O(1) flag check |
Gold has cache |
| Backfollow query |
Persistent recorders + incremental |
On-demand index + DAG walk |
Diverged |
O(V+E) amortized |
O(V+E) per query |
Gold incremental |
| Transclusion model |
Structural (shared subtrees) |
Inline elements (references) |
Diverged |
O(1) share |
O(d) resolve |
Different trade-offs |
| Version DAG |
DagWood + TracePosition + cache |
DagWood + TracePosition + cache |
Direct port |
O(h) compare |
O(h) compare |
Equivalent |
| Diff / merge |
LCS (Miller-Myers O(ND)) |
Fingerprint alignment + 3-way |
Diverged |
O(ND) |
O(n) fingerprint |
Xudanu faster |
| Links |
FeHyperLink multi-ended |
HyperLink multi-ended |
Same model |
O(1) create |
O(1) create |
Equivalent |
| Identity merge |
makeIdentical + become |
make_range_identical |
Same concept |
O(n) redirect |
O(n) redirect |
Equivalent |
| Search |
Within-document scan |
Within-doc + global cross-work |
Xudanu superset |
O(n) scan |
O(n) scan |
Equivalent |
| Storage |
SnarfPacker + Urdi (versioned) |
Chunk store + WAL + manifest |
Diverged |
O(1) write |
O(1) write |
Different models |
| Protocol |
Custom binary (Recipe/Cookbook) |
Postcard + JSON over WS/HTTP |
Diverged |
O(n) serialize |
O(n) serialize |
Equivalent cost |
| Crypto |
Pluggable Encrypter/Scrambler |
Ed25519 + BLAKE3 + ChaCha20 + Argon2 |
Xudanu superset |
O(1) per op |
O(1) per op |
Xudanu stronger |
* Gold's IntegerRegion hasMember should be O(log n) binary search but is actually O(n) linear scan — the only explicit O() confession in the codebase: "Currently many of the methods which could be doing an O(log) binary search (such as hasMember) are instead doing a linear search. This will be fixed if it turns out to be a problem in practice."
2. Core Data Structure: Enfilade vs. O-Tree CRDT
| |
Gold: Enfilade (Loaf tree) |
Xudanu: OrglRoot (Loaf tree + CRDT) |
| Node types |
Leaf (sorted entries + default), Split (region partition: in/out children), Dsp (displacement/offset) |
Leaf (sorted entries + optional default), Split (region partition: in/out children), Dsp (displacement) |
| Max leaf size |
Configurable (recipe-driven) |
MAX_LEAF_SIZE = 16384 |
| Infinite editions |
Yes — default values on leaves |
Yes — with_default on leaves |
| Concurrency |
None — lock-based work grabbing |
CRDT — concurrent edits merge automatically via three-way diff |
| fetch(position) |
O(log n) — tree descent |
O(log n) — tree descent |
| with(position, element) |
O(log n) — insert + possible split |
O(log n) — insert + possible split |
| without(region) |
O(log n) amortized — splay + remove |
O(log n) amortized |
| combine(other) |
O(n) — merge all entries |
O(n) — merge all entries |
| copy(region) |
O(k log n) — splay + extract k entries |
O(k log n) |
| transformedBy(dsp) |
O(1) — wrap in Dsp node |
O(1) — wrap in Dsp node |
| all_entries() |
O(n) — full traversal |
O(n) — full traversal (cached after first call) |
| Memory sharing |
Subtree sharing via identity — two editions can point at the same enfilade nodes |
No sharing — each edition has its own tree |
Gold advantage: Subtree sharing means that if two versions differ by one character, only that character's nodes are duplicated — the rest is shared memory. Xudanu stores each revision as a full snapshot (chunk), so version-to-version diffing is O(n) to materialize rather than O(1) to share.
3. Splay Operations
Both systems use "splaying" — restructuring the tree so each child is fully inside or outside a query region, enabling O(log n) region-scoped operations.
| |
Gold |
Xudanu |
| Algorithm |
9-case transformation table for SplitLoaf rotations (swap, rotateLeft, rotateRight, interleave). Documented in loavesx.cxx lines 2627-2640. |
SplayResult struct with region split into in/out halves. Simpler case analysis — the Rust enum exhaustiveness check eliminates the invalid combinations that Gold's 9 cases handle. |
| splay(region) |
O(log n) expected |
O(log n) expected |
| Balancing |
Adaptive — tree shape depends on access patterns. Known inefficiency: "This should be splaying!" in fetchBottomAt and getBe; "This desperately needs to splay" in BeEdition. |
On-insert balancing via sorted leaf maintenance. No known splay gaps. |
| Known debt |
2 confirmed missing splay calls (efficiency bugs); OrglRoot::make builds unbalanced tree ("Hack!!! This should make a balanced tree directly") |
None identified |
4. Region Algebra (Position/Region/Dsp)
Both systems implement the same "space algebra" — positions, regions (sets of positions), and displacements (bijective transforms). This is the mathematical foundation for all addressing.
| |
Gold |
Xudanu |
| Representation |
IntegerRegion: sorted disjoint interval list |
XnRegion: sorted transition list with starts_inside flag (supports infinite regions natively) |
| contains(pos) |
O(n) — "linear search. This will be fixed" |
O(log n) — binary search on transition list |
| union / intersect |
O(n+m) — merge sorted intervals |
O(n+m) — merge transition lists |
| complement |
O(1) — flip starts_inside |
O(1) — flip starts_inside |
| shift(dsp) |
O(n) |
O(n) |
| Infinite regions |
Yes — via default flag on intervals |
Yes — via above(), below(), full() |
| Mapping (version comparison) |
Composite mappings with inverse — "can this be done more efficiently?" comment on inverse |
Mapping enum (Empty/Simple/Composite) with inverse — no known debt |
Xudanu advantage: Xudanu's XnRegion uses binary search for contains while Gold's IntegerRegion confesses to linear scan. For large documents (10K+ positions), this is a significant difference in hot paths like span lookup.
5. Canopy System (Endorsement/Permission Filtering)
The canopy is a balanced binary tree that aggregates endorsement/permission flags upward, enabling O(1) filter checks to prune subtrees during queries. Xudanu does use the canopy — it was directly ported from Gold and is live in the production backfollow path.
| |
Gold |
Xudanu |
| Tree type |
Accreting balanced binary tree (no rebalancing) |
Accreting balanced binary tree (no rebalancing) |
| Flag encoding |
32-bit flag word: public club bit, "other clubs" bit, up to 23 endorsement bits, sensor/not-partializable bits |
32-bit flag word: same encoding (BertProp, SensorProp, PropFinder) |
| Flag check |
O(1) — single bitwise OR + test |
O(1) — single bitwise OR + test (PropFinder::does_pass) |
| Flag propagation |
O(h) to root, early-exit on no-change |
O(h) to root, early-exit on no-change (propagate_flags) |
| computeJoin |
O(h) worst, O(h²) if isLE called twice |
O(h) worst, O(h²) if isLE called twice |
| Canopy cache |
CanopyCache — caches path lookups and root-finding for repeated queries |
No cache — CanopyCacheInner is defined but unused (scaffolding only) |
| walk_northward |
Live — the canopy's own traversal engine |
Defined but unused — query walk goes through HUpperCrumData::delayed_store_backfollow instead |
| Exhaustive fallback |
O(n) scan for criteria without dedicated flag bits |
O(n) scan for criteria without dedicated flag bits |
| Height maintenance |
Live (PropChanger, HeightChanger) |
Defined but unused (propagate_height, change_height) |
Gap: Canopy cache is unused. Gold's CanopyCache caches path lookups (pathFor, rootFor) so repeated queries on the same subtree are O(1) instead of O(h). Xudanu has the cache structure defined (CanopyCacheInner) but it's never called in production — only in unit tests. For workloads with many repeated transclusion queries, this could be a performance gap. Recommendation: wire up the canopy cache or add an LRU cache on path lookups.
Gold note from Ravi (12/2/92): "Any interesting Club or endorsement gets a bit, and there is a bit for 'any other Club' and 'any other endorsement'. Any criteria not given a bit of their own require an exhaustive search. When we start using more sophisticated hashing strategies, we will probably need to reanimate PropJoints." — Both systems share this limitation.
6. Backfollow / Transclusion Query Engine
This is the signature Xanadu algorithm: "find all documents that contain this content." Both systems implement it, but with very different approaches to persistence and incrementality.
| |
Gold |
Xudanu |
| Query model |
Persistent recorders — a query is planted in the sensor canopy and stays there, incrementally updating as new content is added. Survives server restart via RecorderFossil. |
On-demand index — TransclusionIndex (HashMap) is queried fresh each time. Results are computed by walking the DAG. |
| Algorithm |
Two-phase: (1) "future" — plant recorders + propagate filter props rootward; (2) "now" — southward O-tree walk then northward H-tree walk, both canopy-filtered |
Single-phase: look up content fingerprint in index, then walk hcrum DAG via delayed_store_backfollow with canopy flag pruning |
| find_transcluders(fingerprint) |
O(V+E) first query, O(1) incremental for subsequent updates |
O(V+E) every query (DAG walk with visited-set) |
| Incremental updates |
Yes — recorders fire automatically when new matching content is added |
No — must re-query |
| Persistence |
RecorderFossil survives restart — query state is on disk |
Index is rebuilt on restore — query state is ephemeral |
| Bounded cache |
HashSetCache(100) — deliberately bounded; "redundant work is still correct" |
HashSet<u32> visited-set per query (unbounded within a single query) |
| Async / chunked |
Yes — AgendaItem system chunks work across server loop iterations; "spawns unbounded work" |
Synchronous within request — no async query processing |
| Canopy pruning |
Yes — PropFinder::pass() prunes subtrees during walk |
Yes — same PropFinder::pass() pruning in delayed_store_backfollow |
Biggest architectural gap: persistent incremental queries. Gold's recorder system meant that a transclusion query was a living index — once planted, it updated automatically as new content arrived. Xudanu recomputes queries on demand. For a system with millions of documents and many transclusion relationships, Gold's approach scales better because it amortizes the query cost over time.
Recommendation: If Xudanu needs to scale transclusion queries, the RecorderFossil pattern from Gold is worth studying — plant persistent queries that fire incrementally rather than scanning on demand.
7. Transclusion Model
| |
Gold |
Xudanu |
| How content is shared |
Structural — BePlaceHolder.makeIdentical() merges element identity so two editions point at the same underlying content. Memory is shared at the tree level. |
Referential — RangeElement::Transclusion { source_work_id, char_start, char_end } stores a reference inline. Content is resolved on read. |
| Create transclusion |
O(1) — identity merge, no copy |
O(1) — insert reference element |
| Resolve (read content) |
O(1) — already points to shared content |
O(d) — recursive fetch up to 32 levels, with cycle detection |
| Memory efficiency |
Excellent — 100 copies of a paragraph cost O(1) memory |
Moderate — each reference stores (work_id, start, end); resolved content is cached separately |
| Span migration |
Automatic — shared subtree means edits propagate to all views |
O-tree positions survive edits; references store positions, not text. map_span_through_delta migrates. |
| Version awareness |
Inherent — the H-tree connects all versions; transclusion queries span versions automatically |
Revision-specific — each revision is a snapshot; cross-version transclusion requires explicit query |
| Cross-server |
Theoretical — all servers share the same protocol |
Functional — CrossServerRef with BLAKE3 hash verification + Ed25519 TOFU trust |
Different trade-offs, both valid. Gold's structural sharing is more memory-efficient and makes version-spanning queries natural, but requires a single-server memory model. Xudanu's referential model works better with CRDTs (you can't structurally share across concurrent edit sessions) and enables cross-server transclusion via hash verification.
8. Version Management & DAG
| |
Gold |
Xudanu |
| Version DAG |
DagWood with BranchDescription (Root/Tree/Dag for merges) |
DagWood with BranchStore (direct port) |
| Position comparison |
TracePosition::isLE with cached nav table |
TracePosition::isLE with cached nav table |
| isLE(a, b) |
O(h) first call, O(1) cached |
O(h) first call, O(1) cached |
| Revision storage |
Differential — only changed nodes stored; shared subtrees reused |
Snapshot — each revision serialized to its own chunk |
| fetch_revision(n) |
O(diff) — walk shared tree, apply delta |
O(n) — deserialize full snapshot from chunk store |
| Three-way merge |
Via combine on orgls (enfilade merge) |
three_way_merge — fingerprint alignment + LWW strategy |
| Intercomparison |
Yes — side-by-side visual document comparison with visible connections |
Has shared_region, jaccard_similarity, content_shared_region — algorithmic foundation exists but no visual side-by-side UI |
Gold advantage: differential revisions. Gold's enfilade means revision 100 only stores what changed from revision 99 — O(diff) to fetch. Xudanu stores full snapshots, so fetching revision 100 is O(document_size) regardless of how much changed. For documents with long revision histories, Gold is more storage-efficient.
Recommendation: Consider delta-compressed chunk storage for revisions: store revision 0 as a full snapshot, and subsequent revisions as deltas. This would bring Xudanu's storage efficiency closer to Gold's without changing the CRDT model.
9. Diff / Merge / Comparison
| |
Gold |
Xudanu |
| Diff algorithm |
Miller-Myers LCS (from "A File Comparison Program", Software Practice & Experience, 1985) |
Content-fingerprint seed matching + segment alignment |
| diff(a, b) |
O(ND) where N=total size, D=edit distance |
O(n) — hash-based fingerprint matching |
| Three-way merge |
Via enfilade combine with conflict detection |
O(n) fingerprint alignment, LWW conflict resolution, produces merged edition + mappings |
| shared_region(a, b) |
O(n) tree comparison |
O(n) entry list comparison |
| jaccard_similarity |
N/A |
O(n) word-set comparison (stop words filtered) |
| Visual comparison |
Transpointing windows — side-by-side with visible connections (Declaration of Independence demo) |
Revision timeline UI; comparison viewer for 2-3 versions |
10. Link Operations
| |
Gold |
Xudanu |
| Link model |
FeHyperLink with named ends ("LeftEnd", "RightEnd"), multi-ended |
HyperLink with named ends, multi-ended (same model) |
| Link types |
Unidirectional links |
6 built-in types (Comment, Reference, Disagreement, Quotation, See Also, Web Link) |
| create_link |
O(1) |
O(1) |
| list_links(work) |
O(k) where k = links for this work |
O(k) |
| find_backlinks(work) |
O(k) |
O(k) + cross-server backlinks via HTTP |
| Span migration |
Via enfilade positions |
O-tree positions + resolveMarkerPositions with excerpt fallback |
| Provenance chain |
again() recursive walk |
transclusion_again_chain — 32-level with cycle detection |
11. Identity Merging / Deduplication
| |
Gold |
Xudanu |
| Mechanism |
makeIdentical / tryAllBecome — merges a PlaceHolder's identity into another element. All pointers to the old element automatically see the new one. |
make_range_identical — rebinding labels to unify element identity |
| makeIdentical(a, b) |
O(n) — redirect all references to a→b |
O(n) — redirect labels |
| Content dedup index |
Via GrandMap ID→element mapping |
Via content_address.rs fingerprint→BeId index |
12. Search
| |
Gold |
Xudanu |
| Within-document |
O(n) scan |
O(n) scan (search_text) |
| Cross-document |
N/A |
O(W×L) global text search (W works × avg length), with context snippets |
| Source detection |
N/A |
O(L) MinHash similarity matching (source_matcher.rs) |
| Outline extraction |
N/A |
O(n) line scan for headings/sections |
13. Storage & Persistence
| |
Gold |
Xudanu |
| Storage engine |
Urdi — append-only versioned storage with crash recovery |
Chunk store (BLAKE3-addressed) + WAL (JSON append-only) + manifest (JSON) |
| Packing |
SnarfPacker — assigns objects to "snarfs" (disk blocks), forwarding, atomic commits |
packer.rs — similar snarf model (adapted from Gold) |
| Atomic commits |
BEGIN_CONSISTENT / END_CONSISTENT transactions with dirty-flock accounting |
WAL entries replayed on startup; checkpoint to chunks |
| Garbage collection |
Generation-scavenging GC for in-memory; disk GC for orphaned snarfs |
Chunk GC removes orphaned chunks on checkpoint |
| write |
O(1) amortized |
O(1) amortized |
| checkpoint |
O(n) all dirty objects |
O(n) all dirty works/clubs/editions |
| restore |
O(n) from Urdi view |
O(n) from manifest + chunks + WAL replay |
| Object stubbing |
Yes — objects "become" stubs when purged; reconstituted on demand |
No — full deserialization from chunks |
Gold advantage: object stubbing. Gold's persistence layer can "stub out" infrequently accessed objects — they become placeholders that are transparently reconstituted from disk when accessed. This acts as an automatic memory hierarchy: hot objects stay in RAM, cold objects are stubs. Xudanu deserializes full objects from chunks. For very large document sets, Gold's stubbing would reduce memory pressure.
Recommendation: If memory becomes an issue, consider lazy-loading edition content: store a stub (just the chunk hash + metadata) in memory, and deserialize entries on first fetch() call.
14. Protocol & Networking
| |
Gold |
Xudanu |
| Transport |
TCP with custom framing (Portal/Socket) |
HTTP + WebSocket (Axum) + TLS (rustls) |
| Serialization |
Recipe/Cookbook object graph encoding (binary or textual) |
Postcard (binary) + serde_json (human-facing) |
| Request dispatch |
2,596-line handler table in handlrsx.hxx |
4,338-line dispatch in dispatch.rs (~200+ ops) |
| Async I/O |
ServerChunk cooperative multitasking (run + yield) |
Tokio async runtime (true preemptive multitasking) |
| serialize(obj) |
O(n) in object graph size |
O(n) in object size |
| Cross-server |
Theoretical — required peer servers to speak full Xanadu protocol |
Functional — HTTP fetch + BLAKE3 + Ed25519 TOFU + SSRF protection |
| Session auth |
MatchLock (password), ChallengeLock (public-key), MultiLock (composite), BooLock (open), WallLock (closed) |
Same 5 lock types (lock.rs) + OAuth2 (GitHub, Google) + CSRF tokens |
15. Cryptography
| |
Gold |
Xudanu |
| Encryption |
Encrypter — pluggable public-key (RSA by name registration) |
ChaCha20-Poly1305 AEAD (aead.rs) |
| Hashing |
Scrambler — pluggable one-way hash (Snefru by name) |
BLAKE3 (content addressing, attribution signatures, KDF) |
| Signatures |
N/A |
Ed25519 per-author attribution + span-level signing |
| KDF |
N/A |
BLAKE3-based domain-separated KDF + Argon2 password hashing |
| Key exchange |
N/A |
X25519 ephemeral key exchange |
| Content verification |
None — trusted the server |
BLAKE3 hash on every cross-server fetch (forgery impossible) |
| Audit trail |
N/A |
Chained security log (tamper-evident, security.log.*) |
| Trust model |
Implicit server-to-server trust |
Ed25519 TOFU (Trust On First Use) — like SSH known_hosts |
16. What Gold Still Offers
After this detailed comparison, here is what Gold has that Xudanu could still learn from:
| Feature |
Status in Xudanu |
Gold's approach |
Recommendation |
| Persistent incremental backfollow |
On-demand only |
RecorderFossil + AgendaItem system plants persistent queries that fire incrementally as new content arrives |
Study for scaling transclusion queries to large docuverse |
| Canopy path cache |
Unused |
CanopyCache caches path/root lookups for O(1) repeated access |
Wire up the existing CanopyCacheInner or add LRU cache |
| Object stubbing |
Not implemented |
Objects become stubs when cold; reconstituted on access. Automatic memory hierarchy. |
Consider for large document sets (lazy-load edition entries) |
| Differential revisions |
Full snapshots |
Only changed enfilade nodes stored per revision; shared subtrees reused |
Consider delta-compressed chunk storage for revision history |
| Structural transclusion sharing |
Referential |
makeIdentical shares actual memory across editions |
Incompatible with CRDT model; not actionable without fundamental redesign |
| Intercomparison UI |
Algorithm exists, no visual UI |
Transpointing windows — side-by-side with visible connections |
Build a transpointing window view using existing shared_region + content_map_shared_to |
| AgendaItem async processing |
Synchronous |
Long-running queries chunked across iterations; survives crashes |
Consider for large backfollow queries (spawn task, return partial results) |
Priority ranking
- Canopy cache — already coded, just needs wiring. Low effort, immediate benefit for repeated queries.
- Differential revisions — moderate effort, big win for storage efficiency on long-lived documents.
- Intercomparison UI — algorithms exist (
shared_region, content_map_shared_to), just needs frontend work.
- Persistent incremental backfollow — high effort, but essential for docuverse-scale transclusion queries. Study Gold's
RecorderFossil pattern.
- Object stubbing — low priority until memory pressure becomes an issue.