mergex
A concurrent merge tree. Every thread writes to a node it owns; the aggregate is assembled only when someone asks for it.
use Mergex;
// data, identity, and the fold: father first, then son
let root = new;
let handles: =
.map
.collect;
for h in handles
assert_eq!; // folds every dirty node, deepest first
Nothing is shared on the write path. root.get() is what walks the tree, and when
nothing has changed it answers in a single atomic load. Workers that finish and drop
their handle deliver their last write and then disappear from the tree.
The contract
merge and identity must form a commutative monoid over T:
- folding
identityinto any value leaves it unchanged; - the fold is associative and commutative, because sons are folded in an order that depends on thread scheduling.
A node's data is the delta not yet folded into its father, not a local copy of
the aggregate. A fresh son starts at identity, and a node is reset to identity
the moment its data is folded upward — which is what stops one write from being
counted twice by two successive reads.
Is this the right tool?
Yes, if many threads write concurrently and something occasionally reads the
aggregate. That is the shape it is built for, and it holds up: at eight writers it
moves 671 million writes per second against 21.1 for a shared Mutex<i64>, a
factor of 32 — and it is not done climbing: at twelve, the machine's hardware thread
count, it reaches 795 while the Mutex is stuck at 18.4.
No, if many threads read concurrently. get() takes the root's lock, so
readers queue behind each other and behind any writer. Reads do not scale, and that
is a property of the design rather than a bug awaiting a fix:
| million reads/s | 1 reader | 2 | 4 | 8 |
|---|---|---|---|---|
| mergex, tree quiet | 91.2 | 18.6 | 16.6 | 13.7 |
| mergex, one writer alongside | 3.8 | 14.3 | 6.4 | 4.8 |
| left-right, one writer alongside | 7.7 | 17.3 | 45.9 | 119.1 |
AtomicI64, one writer alongside |
259.4 | 310.1 | 590.7 | 746.0 |
If your workload is read-heavy, left-right is the right structure and this one is not. The two are built for opposite problems — left-right is one writer and wait-free readers, mergex is many writers and an occasional reader — and each loses badly on the other's ground. left-right manages 10.2 million writes per second at eight writers, the slowest entry in the whole comparison.
Also no, if a flat one-level fold is all you need. One cache-line-padded
Mutex<i64> per thread, summed at the end, does 1018 million writes per second
against mergex's 671, in 128 bytes per producer against 240. Mergex earns its keep
with the tree — arbitrary depth, coalescing writes, self-cleaning membership, and an
O(1) answer to "has anything changed?" — not with raw speed.
How it works
┌─────────────┐
│ root │ get() folds here
└──────┬──────┘
subtree_dirty = true
┌──────────────┼──────────────┐
┌──────┴─────┐ ┌──────┴─────┐ ┌──────┴─────┐
│ son A │ │ son B │ │ son C │
│ dirty │ │ clean │ │ dirty │
└────────────┘ └────────────┘ └────────────┘
thread 1 thread 2 thread 3
A node holds its data behind its own Mutex, plus two flags:
dirty— this node owes its father something.subtree_dirty— some descendant may be dirty. Deliberately conservative: it may be true when nothing is, never false when something is. A false negative would lose data; a false positive only costs a wasted sweep.
get() folds every dirty descendant into the root, deepest first, because a node
that absorbs a grandchild is itself out of sync with its father. When the root's
subtree_dirty is clear the whole sweep collapses to one atomic load: 10.96 ns
whether the root has one son or a thousand.
Four decisions worth knowing about
There is no link back to the father. A dying node does not push its delta
upward — it leaves it exactly where it is, and the father, which owns it, folds it on
the next merge like any other son. That is what removes the two ways a hand-written
flush loses data: forgetting the pending delta, and folding it from outside a merge
walk, where merge_sons propagates a son only if its own bit is set or it changed
within that same walk — so a delta pushed in from the side stops there and never
reaches the root.
The price is that there is no get_father(). A worker that needs the root carries a
root.clone() into its thread, which is one line and is honest about the ownership:
the tree is owned from the root down.
No Weak::upgrade on the write path. Each node caches its ancestors'
subtree_dirty flags as Arc<AtomicBool>, built once in copy(). Upgrading a
Weak is a compare-exchange on a shared refcount, and under contention that is
brutal:
| ns per operation | 1 thread | 8 threads on the same target |
|---|---|---|
Weak::upgrade |
7.52 | 101.43 |
AtomicUsize::fetch_add |
3.43 | 23.32 |
AtomicBool::load |
0.89 | 0.17 |
A shared load gets cheaper per operation as threads are added, because the cache
line stays shared in every core. Every read-modify-write serialises. One upgrade
per write cost 30x the write throughput.
Raising an ancestor flag is always a read-modify-write. Never a load fast path,
even though the flag is usually already up and the RMW takes the line exclusively.
The swap is not there to change the flag — it is there to publish. merge_sons
reads a son's dirty bit without taking that son's data lock, so the only thing that
makes a raised bit visible to it is a release edge on the flag the merger clears. A
load that returns true and bails out releases nothing: the writer leaves having
published no edge, the merger may then read dirty stale, skip the son, and clear
the flags on its way out — and the write is gone for good, because nothing is left
flagged to bring anyone back.
This was a real bug in this crate, and an instructive one: on x86 it never fires,
because TSO hides it. Three hundred stress runs passed. loom finds it in a
two-level tree in hundredths of a second. tests/race.rs does not test ordering;
it tests x86. tests/loom.rs tests the protocol.
The cost is paid back elsewhere: update walks up only on the dirty false→true
transition, read under the data lock. A merge clears dirty under that same lock, so
a bit still raised means no merge has folded this node since the write that raised
it — and that write already flagged the ancestors. A burst of writes on one node
costs one walk, not one per write.
Node is cache-line aligned. Nodes are per-writer, so two landing on one 64-byte
line puts unrelated threads in a cache fight. Without #[repr(align(64))] the write
benchmark is bimodal, swinging 3x on allocator luck: worst case 207.7 million
writes per second against 634.2 with it, at the same median. It costs 64 bytes
per node and buys predictability.
Retiring a worker
Dropping the last handle to a node only plants a tombstone. It cannot unlink the node there: the node may still owe its father a delta, and only a merger — walking down from above, inside its own fold — is in a position to collect it.
The merge that folds a dead node's last delta is the one that unlinks it, and only
when it is spent: no handles, nothing pending, and nothing underneath it. That
last condition is not optional. A dead node with a live grandson still routes that
grandson's writes, and its descendants cache its subtree_dirty in their
ancestor_flags — so it can neither be unlinked nor re-parented, and it stays until
its own subtree drains.
Because a spent son is removed rather than tombstoned in place, the sibling list stays
the length of the live sons. This is the difference between working for a fixed
thread pool and working for spawn-per-task: without it, get() would cost O(nodes
ever created) rather than O(nodes alive), since a single dirty son puts the whole
sibling list into the sweep.
The bill is one dead load per son per merge — about 2 ns each, or 5% on a
thousand-son fold — plus the unlink itself when there is something to unlink.
API
| method | what it does |
|---|---|
new(data, identity, merge) |
root node; merge is Fn(&mut T, &T), father then son |
copy() |
register a son at identity and return its handle |
update(f) |
read-modify-write this node's data under one lock, mark it dirty |
set(value) |
update with a closure that overwrites |
get_threaded() |
this node's own delta, no merging |
get() |
fold every dirty descendant into this node, then return its value |
check_children() |
is any descendant dirty? O(1) when the subtree is clean |
Mergex<T> is a handle. Cloning it, or moving it into a thread, shares the node
rather than copying it. Dropping the last one retires the node.
Concurrency guarantees
- A write is never swallowed. The dirty flag is raised while the data lock is still held, so a concurrent merge cannot clear it in between. This was a real bug too: before the fix, 173 of 300 runs lost the last write of a racing writer.
- A dropped handle still delivers. A worker that writes and then goes away leaves its delta in place for the next merge to collect.
- Merging is idempotent. A folded node is reset to
identityunder its own lock, so the same delta is never counted twice. - Writes coalesce. Several writes to a node between merges arrive as one delta.
- A single
get()may return a stale value when several readers race: one wins the flag and merges, the others return immediately with whatever is there. Nothing is lost, since the winner completes the fold, butget()is not "the exact value right now" under concurrent readers. Once the tree is quiet it is exact. - No two locks are ever held at once. A son's delta is taken and its lock released
before the father's is acquired.
Mutexis not reentrant and there is no global acquisition order, so mixing this would deadlock — which is also why the unlink pass re-checks flags rather than a son's own son list.
Benchmarks
AMD Ryzen 5 PRO 5650U, 12 threads · rustc 1.95.0 · criterion 0.8.2 · Linux 7.1.4
Every entrant performs the same operation — += i on an i64, twenty thousand times
per thread. What differs is the topology: mergex, sharded and plain_local hit a
slot the thread owns, while Mutex, RwLock and AtomicI64 hit one cell shared by
every thread, which is the only way a single cell can hold a running total. That
difference is the subject of the benchmark.
Write throughput
Million writes per second, higher is better.
The machine has 12 hardware threads, so the sweep runs past it into oversubscription. Bold marks each structure's own peak.
| threads | 1 | 2 | 4 | 8 | 12 | 16 | 24 | 32 |
|---|---|---|---|---|---|---|---|---|
plain_local |
582.8 | 1242.6 | 2451.6 | 2546.2 | 2350.8 | 1575.2 | 1941.3 | 1784.9 |
sharded_padded |
142.1 | 274.3 | 547.8 | 1018.0 | 1010.2 | 775.9 | 908.5 | 866.0 |
| mergex | 132.7 | 271.2 | 535.3 | 671.3 | 795.0 | 649.8 | 761.8 | 725.4 |
AtomicI64 |
297.3 | 63.2 | 57.6 | 51.3 | 48.8 | 48.4 | 48.0 | 47.7 |
sharded |
142.3 | 21.4 | 29.3 | 40.1 | 58.9 | 79.9 | 69.6 | 74.4 |
Mutex |
140.7 | 41.8 | 29.3 | 21.1 | 18.4 | 18.4 | 18.4 | 17.8 |
RwLock |
151.5 | 39.7 | 29.0 | 15.0 | 11.1 | 11.6 | 11.6 | 12.0 |
left-right |
90.1 | 16.8 | 13.2 | 10.2 | 8.1 | 8.1 | 7.9 | 7.9 |
Every design that funnels writes through one cell peaks at one thread and falls
from there, the lock-free AtomicI64 included, because fetch_add still serialises
on one cache line. Only the per-writer designs climb.
Past the core count they do not collapse — they flatten. Mutex sits at 18.4 from
twelve threads onward, RwLock at about 11.5, left-right at 8. They were already
fully serialised at eight threads, so adding more changes nothing: the queue is the
queue. There is no lock convoy to see here.
Two things worth reading off the wide table:
mergex peaks at twelve, not eight. It is the only entrant still climbing at the
machine's physical limit — 671 to 795 — while sharded_padded had already topped out
at eight. Mergex uses the last four hardware threads that its rival cannot.
It degrades best when oversubscribed. As a share of its own peak at 32 threads:
mergex 91%, sharded_padded 85%, plain_local 70%. With no shared lock, a thread
descheduled mid-write blocks nobody, so the total work is conserved and merely spread
over more slices. And the advantage over a shared Mutex grows with thread count:
31x at eight, 43x at twelve, 41x at thirty-two.
Two oddities in that table are artefacts, not properties. Every row dips at 16 and
recovers at 24 — 16 does not divide 12 evenly while 24 is exactly two full passes, so
this is the scheduler, not the structures. And sharded improves with more threads
(21.4 at two, 79.9 at sixteen), alone in going the other way; the likely reason is that
oversubscription means fewer threads are genuinely simultaneous on the same cache line,
so its false sharing eases. That one is a hypothesis — it is not measured.
plain_local is one plain i64 per thread with no synchronisation at all, folded on
join. It is the ceiling, present so the rest can be read against something absolute —
but it is also the least reproducible entrant, because twenty thousand additions take
a few microseconds and scheduler skew dominates. Read it as an order of magnitude, not
a figure. sharded_padded is one cache-line-aligned Mutex<i64> per thread, summed at
the end — mergex by hand, one level deep, and the closest thing to a fair rival.
Compare sharded against sharded_padded: the same idea without the alignment is
27x slower at eight threads. Adjacent shards share a cache line, so the threads
fight over cache even though they never share a lock. It is the same effect
#[repr(align(64))] on Node exists to prevent.
Latency
| operation | cost |
|---|---|
set / update |
7.25 ns |
get_threaded |
7.10 ns |
get(), nothing dirty, 1 to 1000 sons |
10.96 ns |
check_children(), 1 to 1000 sons |
3.10 ns |
get() merging 10 dirty sons |
269 ns |
get() merging 1000 dirty sons |
38.1 µs |
get() folding and retiring 1 spent son |
140 ns |
get() folding and retiring 1000 spent sons |
145 µs |
copy() per node registered |
~150 ns |
The two flat rows are the point of the design: asking "is there anything to do?" costs the same with a thousand producers as with one.
Reading the aggregate when nothing has changed, single reader, 512 producers:
AtomicI64 |
0.89 ns |
Mutex |
7.10 ns |
| mergex | 10.87 ns |
left-right |
12.12 ns |
sharded |
3.65 µs |
Hand-rolled sharding has no shortcut and must sum every shard — 56.8 ns at 8 producers, 3.65 µs at 512. mergex and left-right are both flat. These are single-reader figures; see the reader-scaling table near the top for what happens with more than one, which is a different and less flattering story.
Memory
Live heap bytes, counted by a GlobalAlloc wrapper rather than estimated from
size_of.
| structure | bytes per producer |
|---|---|
| mergex | 240 |
sharded_padded |
128 |
sharded |
16 |
plain_local |
8 |
Mutex / RwLock / AtomicI64 |
0 |
A mergex node holds an Arc header, a Mutex<T>, a Mutex<Vec<Arc<Node>>> for its
sons, a handle count, two flags, Arcs to the merge function and the identity, and
the vector of ancestor flags — then rounds up to a cache line. This is the cost of a
live producer: retired ones are unlinked. The shared-cell designs are flat because
they have nothing per producer; they pay for concurrency in contention instead of
memory.
Method
- Thread spawn and join sit outside the timed region. A barrier holds every worker on the start line, the clock starts, a second barrier releases when the last worker is done.
- Every configuration is run 15 times, and the whole table repeatedly. A single run on this machine is not reproducible: min-to-max spread reaches 70% under background load. The medians are — they agreed within 1% across every pass — which is why medians are quoted here and min/max is not.
- This is a laptop with the
powersavegovernor, not a dedicated benchmarking box, and the bench suite is heavy enough to warm it up. Read the ratios, not the absolute figures. merge_dirtyandreapfigures include oneInstantpair (40.9 ns), because the harness has to start the clock after preparing the sons. It is subtracted in the latency table above; the raw criterion output does not subtract it.
Testing
RUSTFLAGS="--cfg loom"
tests/race.rs runs real threads and catches lost writes; tests/loom.rs model-checks
the flag protocol across every interleaving the memory model allows. The second is the
one that catches ordering bugs — see the third design decision above for why the first
cannot.
Credits
The tests (tests/, and the unit tests in src/lib.rs), the benchmark suite
(benches/), the measurement harnesses (examples/), the source comments and
documentation, and this README were written by Claude Code.
License
Dual-licensed under either MIT or Apache 2.0, at your option. Contributions are accepted under the same terms.