ORDB benchmark workloads

What the benchmark workloads do, how their random input is built, how the result checksum is computed and what the JSON output looks like — written out in enough detail that a second implementation can run the same thing and get comparable numbers. The Python code in benchmarks/ is what actually runs; this page exists so the Zig ORDB (see the zig branch) can match it and emit the same JSON, which python -m benchmarks.report merges. The zigbridge FFI is left out on purpose: each side benchmarks its own data structures.

Storage backends

A backend stores one subgraph: a mapping nodes: nid -> node (nid: unsigned integer; node: immutable tuple of attribute values with a type tag), a combined index index: key -> bucket, and an allocation cursor nid_alloc_start.

What a backend does:

  • txn begin / commit / abort — all mutation happens inside a transaction. While one is open, the subgraph itself still shows the pre-transaction state; only the transaction’s view sees uncommitted changes. Aborting leaves the subgraph untouched.

  • node set / node remove — insert, overwrite or delete one node.

  • bucket add / remove — index maintenance. Bucket kinds:

    • NID: set of nids, iterated in ascending order;

    • SORTED: nids ordered by an externally supplied sort value (ties: later-inserted first, i.e. leftmost-insertion/bisect_left order);

    • SET: unordered set of values.

    index[key] returns an immutable snapshot of the bucket, so callers can iterate it while mutating the subgraph; the same holds for every other public read path that exposes buckets. An empty bucket looks the same as an absent key. The node and index mappings themselves must reject in-place mutation through their public API (all mutation goes through a transaction) – snapshots may share state objects, so a stray write would corrupt every subgraph in the sharing group.

  • freeze — produce an immutable snapshot; the mutable subgraph stays usable afterwards.

  • thaw — produce a new mutable subgraph from a snapshot.

  • fork — produce an independent mutable copy of a mutable subgraph.

  • compact (optional) — produce a content-identical snapshot with flattened internal structure (delta chains); identity for flat backends.

Python backend names: pyrsistent-patricia, pyrsistent-pvector (persistent HAMT maps; Patricia-trie vs sorted-vector NID buckets), fullcopy (plain dicts, full copies at every boundary incl. txn begin), cow (plain dicts, O(1) share-on-snapshot, copy-on-first-write), delta / delta-compactN (delta chains ported from the Zig design; N = auto-compact chain-depth threshold at freeze). Zig backend names should describe their structure analogously (e.g. zig:delta).

PRNG

64-bit LCG, Knuth MMIX constants. State update and output (all in unsigned 64-bit arithmetic, modulo 2^64):

state' = state * 6364136223846793005 + 1442695040888963407
output = state' >> 33          (31-bit value)

Lcg(seed): state = seed. randint(n) = next() % n (modulo bias is accepted). Every random choice in a workload draws from one Lcg instance seeded with the run’s seed parameter (default 1), in the exact order given by the workload definitions below. The same seed has to give the same workload everywhere, otherwise the numbers are not comparable.

Schema

Node types used by the workloads; all attributes are int or str. LocalRef stores a nid of the same subgraph, ExternalRef a nid of another subgraph resolved through a SubgraphRef (a reference to a frozen subgraph). Index(attr) = NID bucket per attr value; Index(attr, sortkey=order) = SORTED bucket; CombinedIndex([a, b], unique=True) = NID bucket keyed by the value pair, enforcing uniqueness at commit. NonLeaf types can own named children (paths); named insertion creates one extra path node (NPath) per name, itself indexed by (parent, name) and by referenced nid. Every subgraph has a root node at nid 0; nids allocate sequentially from nid_alloc_start.

  • Symbol-like: SymRoot (root); SymPin(num:int); SymPoly(layer:int); SymVertex(ref:LocalRef(SymPoly), order:int, x:int, y:int; Index(ref, sortkey=order)).

  • Schematic-like: SchRoot (root); SchNet(w:int); SchInst(sym:SubgraphRef(SymRoot), x:int, y:int); SchConn(ref:LocalRef(SchInst), pin:ExternalRef(SymPin via ref.sym), net:LocalRef(SchNet); Index(ref); CombinedIndex([ref, pin], unique)).

  • Layout-like: LayRoot(kind:int) (root); LRect(layer, lx, ly, ux, uy:int); LPoly(layer:int); LVertex (as SymVertex, ref to LPoly); LLabel(layer, x, y:int, text:str); LInst(sub:SubgraphRef(LayRoot), dx, dy:int).

  • Sim-like: SimRoot (root); SimGroup(depth:int) (NonLeaf); SimItem(group:LocalRef(SimGroup), key:str; CombinedIndex([group, key], unique)); SimAnnot(target:LocalRef(SimItem), value:int).

  • Chain: ChainRoot (root); CNode(tag:int, val:int; Index(tag)).

  • Micro: MicroRoot (root); Box(val:int); MPoly(val:int); UNode(val:int; Index(val, unique)).

What actually runs is the code in benchmarks/workloads/; the summaries below describe it. A port needs the same PRNG draws in the same order, the same insertion order and the same transaction boundaries — otherwise the checksums diverge and there is nothing left to compare.

Workloads

Phases are timed separately (wall clock). “own txn” = the operation opens and commits its own transaction, as ORDeC generator code does for every statement.

symbol_build — phases: build

Mirrors small view-generator builds. M times: create a SymRoot; K pins inserted under names p0..p{K-1} (own txn each, one NPath each); P polys (own txn), each with V vertices SymVertex(order=o, x=rand(1000), y=rand(1000)) (own txn each); poly layer = rand(8); freeze. All M frozen subgraphs are retained. Draw order per poly: layer, then per vertex x, y.

Params (default): M=200, K=8, P=6, V=5. small: M=100. large: M=5000. tiny: M=5, K=4, P=2, V=3.

layout_flatten — phases: copy, flatten, expand, freeze, scan

Mirrors the layout flatten/expand webdata pipeline. Untimed setup: C frozen cells of S shapes (per shape: layer=rand(8), x=rand(10000), y=rand(10000); even shapes an LRect with ux=x+1+rand(500), uy=y+1+rand(500), odd shapes an LPoly with 4 vertices x+rand(500), y+rand(500) each; every 8th shape adds an LLabel), built in one txn each; a frozen top with I instances named i0.. referencing cell rand(C) at dx,dy = rand(100000). Timed: copy = mutable copy of the top; flatten = for each LInst: re-insert every cell shape translated by (dx, dy) (own txn per insert), then remove the instance; expand = replace every LRect (iterating the bucket snapshot) by an LPoly plus 4 corner vertices, reusing the rect’s nid; freeze; scan = 3 passes over all LPoly, LVertex, LLabel reading attributes.

Params (default): C=5, S=40, I=50. small: 5/20/20. large: 10/200/2000. tiny: 2/8/4.

render_scan — phases: build, scan

Mirrors read-only schematic rendering. build (reported, but the scan is the point): Y frozen symbols (pins P, polys Q with V vertices as in symbol_build); a SchRoot with N nets (named n0.., w=rand(4)), then I instances: pick symbol rand(Y), insert SchInst (x, y = rand(100000)) named i{i}, and one SchConn per symbol pin to net rand(N) (own txn each); freeze. scan, R repetitions, zero mutation: for every SchInst read x, y, resolve its symbol; for every conn of the instance (Index(ref) query) resolve the external pin’s num; for every symbol poly iterate its vertices via the sorted index with coordinate arithmetic; build the instance’s full path string; then read w of every net.

Params (default): Y=8, P=4, Q=6, V=5, I=200, N=100, R=5. small: I=100, N=50, R=3. large: I=8000, N=4000, R=20.

sim_hierarchy — phases: build, annotate

Mirrors SimHierarchy construction plus result back-annotation. build: recurse from the root, depth D, fanout F: insert SimGroup named g{f} (depth=level), then E items SimItem(group, key='k{e}') (own txn each; unique (group, key) check at each commit); recurse into each group. annotate: for every group in creation order, for e in 0..E-1: look up the item by the unique (group, ‘k{e}’) index query, insert SimAnnot(target=item, value=rand(2^20)) (own txn).

Params (default): D=3, F=4, E=6. small: D=3, F=3, E=4. large: D=5, F=6, E=8.

snapshot_chain — phases: build, chain, read

The generation-chain stress. build: N CNodes (tag=rand(64), val=rand(2^20)) in one txn; freeze (generation 0). A mirror list live of inserted nids is maintained for reproducible picks. chain: K times: thaw the newest snapshot; one txn with max(1, N*p/1000) patch ops, each drawing r=rand(100): r<60 → update val=rand(2^20) of nid live[rand(len)]; r<85 → insert new CNode (draws tag, val; append nid); else remove nid at live index rand(len) (drop from live); freeze. If compact_every > 0 and the generation number is a multiple, compact the new snapshot before continuing. ALL K+1 snapshots are retained (memory measurement). read on the newest snapshot: iterate all CNodes summing val; for tag 0..63 iterate the tag index query; N random point lookups nodes[live[rand(len)]].

Draw order per patch op: r, then the op’s own draws in the order named. Params (default): N=10000, K=32, p=20 (permille), compact_every=0 (set e.g. --param snapshot_chain.compact_every=8 to exercise explicit compaction). small: N=1000, K=8. large: N=50000, K=64. Chain depth K is what this workload exists to measure – copy-on-write backends only reveal their cost at depth – so the default keeps K high rather than trimming it for runtime.

micro_remove_all / micro_insert_descending / micro_replace / micro_abort

Single phase each. NType-bucket micros:

  • remove (n Box prebuilt, untimed): one txn removing all n nids one-by-one in ascending order.

  • insert: one txn inserting Box(val=nid) at explicit nids n..1 (descending), forcing head insertion into the NID bucket.

  • replace (n Box prebuilt): for each Box cursor (bucket snapshot), replace it by MPoly(val) reusing the nid (own txn each).

  • abort (n UNode(val=i) prebuilt): rounds times, one txn inserting batch fresh UNodes then one duplicate val → unique violation at commit → rollback; the state is unchanged after each round.

Params (default): n=3000; abort: batch=300, rounds=10. small: n=1000; abort: batch=100, rounds=5. large: n=50000; abort: batch=2000, rounds=20.

Checksum

FNV-1a 64-bit (offset 0xcbf29ce484222325, prime 0x100000001b3) over the canonical serialization of the final subgraph; all integers little-endian:

for each nid ascending:
    u64(nid)
    u32(len(typename)) ++ typename utf-8    (canonical node type name)
    per attribute in declaration order, tagged:
        0x00                     None
        0x01 ++ i64(value)       int
        0x02 ++ u32(len) ++ utf8 str
        0x03 ++ u64(nid)         LocalRef
        0x04 ++ u64(nid)         ExternalRef
        0x05 ++ u64(checksum)    SubgraphRef (recursive checksum)
finally u64(nid_alloc_start)

NPath nodes participate like any other node (typename “NPath”, attributes parent: LocalRef, name: int-or-str tagged by value, ref: LocalRef). For a workload retaining a list of subgraphs, the result checksum is FNV-1a over the concatenated u64 per-subgraph checksums. Reported as "fnv1a64:0x<16 hex digits>". Backends and worlds that disagree here are not comparing the same thing; the report tool flags mismatches.

Measurement protocol

  • Per (workload, backend): warmup untimed runs, then repeats timed runs. Report every repeat’s per-phase wall time in ns (statistics are computed by the report tool; use min for noise-resistant comparison).

  • Scale tiers: tiny is for CI, default is sized so the whole matrix runs in a few minutes, and large is the tier for drawing real conclusions (asymptotic differences need it; see --param for one-off sizes). A second implementation only needs to match the tier it reports.

  • --time-limit (Python runner: 30 s per workload/backend, 0 disables) stops starting further repeats once the budget is spent, so a run is only ever cut between repeats, never inside one; at least one timed repeat always survives. repeats in the output is how many actually ran, which is why it may be below repeats_requested.

  • Garbage collection: collect before each run, leave enabled during runs (allocator/GC behavior is part of what is measured).

  • Memory (optional, Python): one extra instrumented pass, separate from timing: allocation peak via tracemalloc plus retained_bytes = deduped deep size of the objects the workload retains (e.g. all generations of snapshot_chain) — the structure-sharing comparison number. Caveats: the walker cannot see C-level internals (record pyrsistent_c_ext), and interned/shared small objects are attributed to the graph. Other worlds report the closest equivalents (e.g. arena bytes) and document them.

JSON result format

{
  "spec_version": 1,
  "world": "python",
  "impl": {"python": "3.13.5", "ordec_git": "abc1234", "cpu": "...",
           "hostname": "...", "pyrsistent_c_ext": false},
  "timestamp": "2026-07-07T12:00:00Z",
  "results": [
    {
      "workload": "snapshot_chain",
      "backend": "delta",
      "params": {"n": 10000, "k": 32, "patch_permille": 20,
                 "compact_every": 0, "scale": "default", "seed": 1},
      "warmup": 1,
      "repeats": 5,
      "repeats_requested": 5,
      "phases": {"build": {"wall_ns": [1, 2, 3, 4, 5]},
                 "chain": {"wall_ns": [1, 2, 3, 4, 5]},
                 "read":  {"wall_ns": [1, 2, 3, 4, 5]}},
      "mem": {"tracemalloc_peak_bytes": 0, "retained_bytes": 0},
      "checksum": "fnv1a64:0x0123456789abcdef"
    }
  ]
}

world distinguishes implementations (“python”, “zig”). impl is free-form host/implementation metadata. mem and checksum may be null when not measured. Records are keyed by (world, backend, workload, params) when merging; the same key from a later file wins.

Checks

  1. ORDEC_ORDB_BACKEND=<b> pytest green for every backend.

  2. python -m benchmarks.equivalence: identical checksums for every workload under every backend, plus a differential fuzz (seeded random insert/update/remove/freeze/thaw/fork/abort sequence applied lockstep under candidate and reference backends, full state compared after every op, including transaction isolation and abort checks).

  3. tests/test_benchmarks.py runs both in CI at the tiny scale.