ORDB storage backends and benchmarks

ORDB’s subgraph storage is pluggable: every subgraph carries a reference to a storage backend (ordec.core.ordb.backend) that owns the representation of its node store and combined index, the transaction mechanics, the freeze/thaw/copy lifecycle and frozen-subgraph value equality. The rest of ORDB (nodes, cursors, indices, queries, the updater) is backend-independent.

Available backends

Name	Storage model
`pyrsistent-patricia`	Persistent HAMT maps (pyrsistent), Patricia-trie integer-set buckets. The default.
`pyrsistent-pvector`	Same maps, sorted persistent-vector buckets (the pre-Patricia behavior; kept as a baseline).
`fullcopy`	Plain dicts, full copies at every boundary including transaction begin. Strawman baseline.
`cow`	Plain dicts, O(1) snapshot sharing, transactions copy only what they touch (top-level dict once after a snapshot, buckets on first write).
`delta` /	Delta chains ported from the Zig ORDB
`delta-compactN`	reimplementation (`zig` branch): each frozen generation stores only its delta; reads walk the chain. `compactN` flattens chains deeper than N at freeze.

Backend selection: the ORDEC_ORDB_BACKEND environment variable, or programmatically ordb.use_backend(name) (context manager) / MutableSubgraph(backend=...). Derived subgraphs (freeze/thaw/copy) inherit their origin’s backend. The whole test suite is expected to pass under every backend:

ORDEC_ORDB_BACKEND=delta pytest -m "not web"

Benchmark suite

The top-level benchmarks/ package (not shipped in the wheel) compares the backends on synthetic workloads shaped like real ORDeC usage: many small view builds, layout flatten/expand, read-only render scans, simulation-hierarchy construction, freeze/thaw generation chains, and index-bucket micros. ORDB benchmark workloads writes out what they do, along with the PRNG, the checksum and the JSON output, so that a pure-Zig ORDB can run the same workloads and be compared against (the zigbridge FFI is deliberately not benchmarked).

Typical usage:

# list workloads and backends
python -m benchmarks.runner --list

# quick sanity run
python -m benchmarks.runner --tiny --workloads all --backends all

# full run with memory measurement and checksums (a few minutes)
python -m benchmarks.runner --workloads all --backends all \
    --repeats 5 --warmup 1 --mem --checksum --out results/py.json

# the tier to actually draw conclusions from -- slow, run it deliberately
python -m benchmarks.runner --workloads all --backends all --scale large \
    --repeats 5 --warmup 1 --checksum --time-limit 0 --out results/py.json

# compare (also merges results from other worlds/machines)
python -m benchmarks.report results/*.json --baseline pyrsistent-pvector

# HTML report
python -m benchmarks.report results/*.json --baseline pyrsistent-pvector \
    --html results/report.html --no-tables

The default scale is sized so the full matrix stays in the minutes range; --scale large is where asymptotic differences between backends actually show up. Every workload/backend pair is capped by --time-limit (30 s by default, 0 disables): once the budget is spent the runner stops starting new repeats and says so, rather than silently reporting a truncated run as a full one.

--html writes one self-contained page built around a workload x backend matrix, which is the shape of the question the suite exists to answer. It needs no dependencies and contains no JavaScript, so it is a ~25 KB file that opens anywhere and prints to PDF from the browser.

The page is: a headline (which backend won, and on how many workloads), the total-time matrix, the same matrix for peak and retained memory when the run used --mem, and each multi-phase workload’s phases behind a <details> so the page opens on the summary rather than on every number at once.

Cells are shaded on a diverging scale around the baseline – blue better, red worse, neutral at parity – log-spaced, because the ratios span roughly 0.02× to 90×. Every cell also carries its ratio and absolute value as text: colour is a redundant channel, so the page survives printing, greyscale and colour-vision deficiency. Change what everything is measured against with --baseline.

total (a total row in the tables, the total-time matrix in the HTML report) is the workload’s phases summed. It is derived by the report tool, not stored in the JSON, and only appears for multi-phase workloads – for a single-phase one the phase already is the total. It sums the phases within each run and only then applies --stat: summing per-phase minima would take each phase from whichever run suited it best and understate every backend by a different margin. Untimed setup belongs to no phase, so total is the measured work, not the wall time of the whole run.

Two checks keep a comparison honest:

python -m benchmarks.equivalence checks that every workload produces an identical canonical checksum under every backend and runs a differential fuzz (random op sequence applied lockstep under candidate and reference backends, state compared after every operation, including transaction-isolation and abort checks).
tests/test_benchmarks.py runs the whole suite at the smallest scale in CI.

Transactions, index snapshots and immutability

While a SubgraphUpdater transaction is open, the subgraph’s own nodes/index keep showing the pre-transaction state; only the updater’s views expose uncommitted changes. Real code (e.g. resolve_instances in ordec/schematic/helpers.py) queries the subgraph mid-transaction and depends on this. Additionally, index[key] returns an immutable snapshot of the bucket, so callers may iterate a query result while removing exactly those nodes (the expand_rects pattern). Backends have to get both right (ordec.core.ordb.backend); the differential fuzz checks them.

The state mappings a subgraph hands out via .nodes/.index must also reject in-place mutation through their public API: frozen subgraphs cache their content hash, and backends share state objects across freeze/thaw/fork, so a stray write would silently corrupt every subgraph in the sharing group. pyrsistent gets this from pmap; the dict-based backends use guarded dict subclasses whose public mutators raise TypeError and whose index read paths ([], get, items, values, copy) return bucket snapshots (ordec/core/ordb/backend_fullcopy.py). Reads stay at native dict speed, but note for cross-version comparisons that turning fullcopy’s node store from an exact dict into a subclass costs roughly a third on raw node reads (CPython specializes exact dicts only); cow’s node store was a subclass all along. tests/test_ordb.py asserts the contract under every backend.

Going forward

Patricia buckets removed the quadratic index maintenance, but the layout webdata path is still slow, and its profile no longer points at a single hotspot: what is left is the sheer volume of transactional work. Roughly in order of payoff:

webdata() mutates the graph in order to serialize it. expand_geom opens a transaction per replaced rect — around 29k of them — and inserts ~147k nodes, paying index updates and constraint checks for a result that is discarded once rendered. A read-only traversal prototype (walk instances recursively with accumulated transforms, expand shapes inline, never touch the graph) produced identical shape counts in 0.42 s where the current pipeline takes roughly 100 s. That is the fix for the web path, and it also removes the flatten() and mutable_copy() costs. ordec.layout.helpers.compare() can check geometric equivalence against the old pipeline.

pyrsistent runs as pure Python on 3.13 — its C extension does not build there, and pmap.set dominates what remains. That costs roughly 2–3× across all ORDB operations, not only this path. Worth pursuing upstream or vendoring the patch; a startup warning when the extension is missing would at least make the degradation visible rather than silent.

webdata() is not memoized. Views are frozen and hashable, so caching the conversion per frozen view in the server would make reopening a panel free.

Further out, the schema itself amplifies: every polygon vertex is its own node, so geometry-heavy subgraphs carry several times the node count and every bulk operation pays for it. Running bulk transforms in a single transaction rather than one per node is the cheap mitigation; storing vertex arrays as an attribute (as SimArray does for simulation data) would change the constraint-based layout workflow and is a separate discussion.

On the benchmark side, a default-backend decision wants large-scale runs, and runs with a working pyrsistent C extension, before it is made. The delta backend’s weakness on micro_replace points at its index-delta merge at commit. Candidates worth measuring: a cow backend with Patricia buckets, and an unsorted-NID-bucket variant — ascending iteration is the only ordering the API promises, so a hash set with sort-on-read is admissible.