mergex

A concurrent merge tree. Every thread writes to a node it owns; the aggregate is assembled only when someone asks for it.

This is an educational project. It works and it is tested — the memory ordering is model-checked with loom, and every number below was measured rather than estimated — but it was built to learn how one of these behaves under contention, not because the ecosystem was missing it. The comparison section says plainly what beats it and by how much. Read that before depending on it.

use mergex::Mergex;

// data, identity, and the fold: father first, then son
let root = Mergex::new(0i64, 0, |father: &mut i64, son: &i64| *father += *son);

let handles: Vec<_> = (0..8)
    .map(|_| {
        let node = root.copy();           // register a son, get its handle
        std::thread::spawn(move || {
            for i in 1..=1000 {
                node.update(|slot| *slot += i);   // writes only to this node
            }
        })
    })
    .collect();

for h in handles {
    h.join().unwrap();
}

assert_eq!(root.get(), 4_004_000);        // 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.

This is not the fastest way to add up numbers from several threads, and the next section says what is. It is a way to aggregate a tree of them, and to ask whether anything has changed without looking.

The contract

merge and identity must form a commutative monoid over T:

• folding identity into 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?

Probably not, and the honest way to start is with what beats it.

If you need a flat per-thread accumulator, use thread_local. It is faster than this crate at every thread count, on cheap and expensive T alike, and it needs no handle threaded through your code — it finds the slot from the thread id.

million updates/s, T = HashMap	1	2	4	8
ThreadLocal, padded slots	70.7	140.1	273.4	304.8
mergex	33.5	85.3	188.9	212.0
one Mutex<HashMap> per thread	55.6	26.8	27.4	60.5
one shared Mutex<HashMap>	55.8	8.7	6.5	5.2

If your workload is read-heavy, use left-right. Its readers are wait-free and scale; get() here takes the root's lock and does not. At eight concurrent readers with a writer alongside, left-right does 119.1 million reads per second against 4.8.

What is left, and it is narrower than it looks:

• An O(1) answer to "has anything changed?" check_children() is one atomic load — 3.10 ns whether there is one producer or a thousand. Every flat design has to sweep every slot to find out: summing 512 shards costs 3.65 µs. For an observer that polls, that is the difference between polling being free and polling being the workload.
• A tree, not a row. Aggregation at arbitrary depth, folding bottom-up, with each interior node holding a real partial result. Per-thread → per-core → per-socket, or a scope tree where sub-scopes roll into parents.
• Membership by handle, not by thread id. One thread can own several nodes; a node outlives the thread that made it and delivers its last write; nodes retire and are unlinked when their handle drops. ThreadLocal gives you exactly one slot per live thread and reuses it when a thread id is recycled.

If none of those three is what you came for, the alternatives above are faster and simpler. That is the whole recommendation.

A note on cache lines, which is most of what these numbers measure

ThreadLocal packs its slots contiguously, so with a small T two threads land on one 64-byte line and fight over it. Padding the slot is the difference between a collapse and a win:

million writes/s, T = i64	1	2	4	8
ThreadLocal<PaddedCell>	719.6	1226.9	2517.3	3430.7
ThreadLocal<Cell<i64>>	736.1	1241.0	546.0	218.9

Identical up to two threads, then 15x apart. The same effect governs a hand-rolled shard array — one Mutex<i64> per thread in a Vec is 27x slower than the padded version at eight threads — and it is why Node here carries #[repr(align(64))]. Without it this crate's own write benchmark is bimodal, swinging 3x on allocator luck.

If you take one thing from this comparison, take that: for per-thread accumulation, the padding decides more than the data structure does.

Prior art

None of this is new, and the parts that are borrowed are worth naming, because a reader who recognises them will recognise them in about ten seconds anyway.

LongAdder and LongAccumulator (Doug Lea, JDK 8) are the direct ancestors. LongAdder stripes a counter across padded cells, a thread hashes to one, and sum() walks them all — contention-free writes paid for with an O(cells) read, which is the same bargain this crate makes. LongAccumulator is the same machinery with a caller-supplied binary operator and an identity, and its documentation draws exactly the line the contract above draws — "the order of accumulation within or across threads is not guaranteed and cannot be depended upon, so this class is only applicable to functions for which the order of accumulation does not matter". Its own worked example is Long::max with Long.MIN_VALUE as the identity. So "a LongAdder generalised to a user-supplied monoid" is not the difference here. That already exists, and it has been in the JDK since 2014.

Combining trees (software combining, Yew/Tzeng/Lawrie 1987 and Goodman/Vernon/Woest 1989; textbook treatment in Herlihy and Shavit, The Art of Multiprocessor Programming, ch. 12) are where the tree shape comes from. The mechanism is different, though, and the name is a little misleading here. A combining tree combines operations in flight: threads rendezvous at interior nodes, one of them carries the combined operation onward, and results are distributed back down. It is synchronous, and it exists to relieve contention on one hot location. Nothing rendezvouses in this crate. Nodes are durable per-writer slots, nobody waits for anybody, and the folding is deferred entirely to whoever reads. It is closer to a reduction tree that happens to be persistent than to a combining tree.

Delta-state CRDTs are the closest match for the contract. A state-based CRDT (CvRDT; Shapiro, Preguiça, Baquero, Zawirski, 2011) needs a join-semilattice — merge associative, commutative, and idempotent. This crate needs the first two and not the third, because a fold takes the son's delta and leaves the identity behind, so each delta is folded exactly once. That is the delta-state variant (Almeida, Shoker, Baquero, 2015): ship what changed, not the whole state.

Worth being clear that this is a downgrade in robustness, not an upgrade. A CvRDT can merge the same state twice and nothing happens. Here, folding the same delta twice is a wrong answer, and it was a real bug in this crate: the fold used to clone the son's value out and leave it in place, so update(|x| *x += 1) twice with a get() in between landed as +1 and then +2. The identity exists to close that hole, and the "reset to identity on fold" rule in the contract above is the fix, not a flourish.

In Rust, thread_local is the flat version of this idea and is what tracing-subscriber and the metrics crates already do: a slot per thread, swept on read. left-right sits at the opposite corner — one writer, wait-free readers. Folly's ThreadCachedInt is the same family in C++.

So what is actually different

Two things, and neither is a new primitive:

• T is arbitrary, not a machine word. LongAccumulator folds longs. This folds whatever forms a commutative monoid — a HashMap, a sketch, a set.
• It is a tree, not a row. Interior nodes hold real partial results, so an aggregate can be read at any depth: per-core, per-socket, per-scope. LongAdder, LongAccumulator and thread_local give you the total or nothing.

The O(1) "has anything changed?" check falls out of the tree rather than being a third idea. If neither of those two matters to you, the section above already named the faster things to use instead.

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.

impl<T> Drop for Mergex<T> {
    fn drop(&mut self) {
        if self.node.handles.fetch_sub(1, Ordering::AcqRel) == 1 {
            self.node.dead.store(true, Ordering::Release);
        }
    }
}

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 identity under 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, but get() 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. Mutex is 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, ThreadLocal, 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.

plain_local is one plain i64 per thread with no synchronisation at all, folded on join — the ceiling, present so the rest can be read against something absolute. It is also the least reproducible entrant, since twenty thousand additions take a few microseconds and scheduler skew dominates; read it as an order of magnitude.

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
ThreadLocal, padded	719.6	1226.9	2517.3	3430.7	2737.0	1830.1	2155.9	—
plain_local	582.8	1242.6	2451.6	2546.2	2350.8	1575.2	1941.3	1784.9
ThreadLocal, unpadded	736.1	1241.0	546.0	218.9	287.6	292.2	258.3	—
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 — 671 to 795 — where sharded_padded had already topped out at eight. That is a point in its favour against the shard array and nothing more: a padded ThreadLocal is above it at every column.

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.

sharded_padded is one cache-line-aligned Mutex<i64> per thread, summed at the end — mergex by hand, one level deep.

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 powersave governor, not a dedicated benchmarking box, and the bench suite is heavy enough to warm it up. Read the ratios, not the absolute figures.
• merge_dirty and reap figures include one Instant pair (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

cargo test                                                # unit + concurrency regressions
RUSTFLAGS="--cfg loom" cargo test --release --test loom    # the memory-ordering protocol

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.