mrdt: implement the library; harden and profile it
TDD from the committed spec suite, tests untouched. Counter, pair,
set, queue and map implement the OOPSLA 2019 relational merges; the
replica layer keeps a version store keyed by (replica, seq) with
version vectors, so ancestry, LCA and the acknowledged frontier are
vector comparisons. Criss-cross heads merge their incomparable LCAs
recursively, Git style. Compaction collapses history below a version
acknowledged by all replicas, with the extra soundness condition the
criss-cross test exposed: the snapshot point must also be comparable
to every retained version, or recursive LCA queries between
incomparable survivors can reach below the frontier.
pull now rejects peers that are not replicas of the same object
(group size, initial state, or disagreeing shared versions), and the
suite gains hostile cases: non-ancestor merges (queue order cycles
broken by arbitration), overflow, self pulls, single-replica groups
and deep criss-cross schedules. Fuzz adds queue- and map-typed
replica convergence with compaction over random schedules; a 60 s
AFL campaign (dune build @fuzz --profile afl, now invoking the
binary via ./fuzz.exe as afl requires) found no crashes.
bench/bench.ml reports throughput and words/op; three
memtrace_hotspots iterations cut total bench allocation 31x
(15.7 GB -> 0.5 GB): the queue merge evaluates the membership and
occurs-before relations over position arrays instead of materialized
pair sets (x256 merge: 22 -> 2138 ops/s, 144x fewer words), set and
map merges regroup the diamond per side so unchanged subtrees keep
their sharing (set: 13715 -> 105 words/op; map: 22x fewer words,
2.5x faster), and the replica layer's vector comparisons no longer
allocate closures.
gazagnaire.org