Add selected single-file persistent tree store

store-tree.c keeps every document in one append-only file as a persistent
B-tree of byte extents, with the key catalog in the same structure. A splice
writes only the changed leaf and path; unchanged extents are shared between
versions, readers take no lock, and two alternating head slots publish a
commit after its nodes are durable. Compaction rewrites reachable nodes.

On the recorded ext4 host a durable 1-byte middle insert into a 1 MiB
document took 8.58 ms against 78.51 ms for the default store, and the real
TUI's Ctrl+S after typing took 16.60 ms against 84.59 ms. check-tree runs the
store's crash/oracle tests and the unchanged runtime, splice, async and
real-PTY editor checks on it. It stays opt-in: linked code is 12.7 KB larger
and contiguous multi-leaf reads copy.

1 files changed, 49 insertions, 0 deletions

diff --git a/research/experiments/008-tree-store-edit-cost/run.py b/research/experiments/008-tree-store-edit-cost/run.py
new file mode 100755
index 0000000..1b9dfa8
--- /dev/null
+++ b/research/experiments/008-tree-store-edit-cost/run.py
@@ -0,0 +1,49 @@
+#!/usr/bin/env python3
+"""Build bench.c against each selected store and time durable edits on disk."""
+import argparse
+import json
+import platform
+import shutil
+import subprocess
+from pathlib import Path
+
+HERE = Path(__file__).resolve().parent
+CONNECTIONS = HERE.parents[2] / 'prototypes' / 'connections'
+STORES = {'flat': 'store.c', 'paged': 'store-paged.c', 'tree': 'store-tree.c'}
+OPS = ['insert-middle', 'delete-middle', 'replace-end', 'append-end']
+
+
+def main():
+    parser = argparse.ArgumentParser()
+    parser.add_argument('--work', type=Path, default=CONNECTIONS / 'build' / 'bench-tree-cost')
+    parser.add_argument('--count', type=int, default=32)
+    parser.add_argument('--sizes', default='256,1048576')
+    parser.add_argument('--output', type=Path)
+    args = parser.parse_args()
+    shutil.rmtree(args.work, ignore_errors=True)
+    args.work.mkdir(parents=True)
+    source = subprocess.check_output(['findmnt', '-n', '-T', str(args.work), '-o', 'SOURCE,FSTYPE'], text=True).split()
+    assert source[1] != 'tmpfs', 'fsync is free on tmpfs; choose a real device'
+    results = []
+    for name, store in STORES.items():
+        binary = args.work / f'bench-{name}'
+        subprocess.run(['cc', '-std=c17', '-O2', '-Wall', '-Wextra', '-Werror', f'-I{CONNECTIONS}',
+                        str(HERE / 'bench.c'), str(CONNECTIONS / store), '-o', str(binary)], check=True)
+    for size in map(int, args.sizes.split(',')):
+        for op in OPS:
+            for name in STORES:  # interleave stores within each scenario
+                directory = args.work / f'{name}-{op}-{size}'
+                line = subprocess.check_output([str(args.work / f'bench-{name}'), name, str(directory),
+                                                str(size), op, str(args.count)], text=True)
+                results.append(json.loads(line))
+                print(line.strip(), flush=True)
+                shutil.rmtree(directory)
+    report = {'device': source[0], 'filesystem': source[1], 'machine': platform.machine(),
+              'kernel': platform.release(), 'compiler': subprocess.check_output(['cc', '--version'], text=True).splitlines()[0],
+              'edits_per_scenario': args.count, 'results': results}
+    if args.output:
+        args.output.write_text(json.dumps(report, indent=2) + '\n')
+
+
+if __name__ == '__main__':
+    main()