Skip to main content

mergex/
lib.rs

1//! A tree of per-thread slots that are folded lazily into their father.
2//!
3//! Writers only ever touch the node they own, so they never share a cache line;
4//! the aggregate is rebuilt on demand, when someone reads the root.
5//!
6//! # Contract
7//!
8//! `merge` and `identity` must form a commutative monoid over `T`:
9//!
10//!  * **identity**: `merge(&mut x, &identity)` leaves `x` unchanged.
11//!  * **associative** and **commutative**: sons are folded in an order that
12//!    depends on thread scheduling, so any order must give the same answer.
13//!
14//! A node's data is the **delta not yet folded into its father**, not a local
15//! copy of the aggregate. A fresh son starts at `identity`, and a node is reset
16//! to `identity` as soon as its data has been folded upward.
17
18#![warn(missing_docs)]
19
20use std::mem;
21
22// The README's example is compiled and run as a doctest. It is the public API's
23// only prose description of itself, and it has drifted out of date before -- a
24// signature changed and the snippet kept claiming the old one.
25#[cfg(all(doctest, not(loom)))]
26#[doc = include_str!("../README.md")]
27struct ReadmeExamples;
28
29// Under `--cfg loom` the locks and the flags are rebuilt on loom's instrumented
30// primitives, so the model checker can drive every interleaving the memory
31// model allows. See tests/loom.rs.
32//
33// `Arc`/`Weak` stay on std: loom 0.7 has no `Weak` and its `Arc` cannot hold an
34// unsized `dyn Fn`, which is what `MergeFn` is. No loss for what is under test
35// here -- the protocol lives in the AtomicBools and the Mutexes, not in the
36// refcounts -- but it does mean loom is not watching the `Arc` graph, so it
37// will not catch a leaked cycle.
38#[cfg(loom)]
39use loom::sync::Mutex;
40#[cfg(loom)]
41use loom::sync::atomic::{AtomicBool, AtomicUsize, Ordering};
42#[cfg(not(loom))]
43use std::sync::Mutex;
44#[cfg(not(loom))]
45use std::sync::atomic::{AtomicBool, AtomicUsize, Ordering};
46use std::sync::Arc;
47
48/// Merge function: folds a son's data into its father's data.
49/// Must be associative and commutative; see the crate docs.
50pub type MergeFn<T> = Arc<dyn Fn(&mut T, &T) + Send + Sync>;
51
52/// The shared node. Never handed out directly: users get a `Mergex` handle.
53///
54/// Aligned to two cache lines: nodes are per-writer, so two of them landing on
55/// one line puts unrelated threads in a cache fight. Without this the write
56/// benchmark is bimodal, swinging 3x on allocator luck alone.
57#[repr(align(64))]
58struct Node<T> {
59    // There is deliberately no link back to the father. A dying node does not
60    // push its delta upward -- it leaves it where it is, and the father, which
61    // owns it, folds it on the next merge like any other son. That removes the
62    // two ways a hand-written flush loses data: forgetting the pending delta,
63    // and folding it from outside a merge walk, where `merge_sons` would not
64    // propagate it any further.
65    sons: Mutex<Vec<Arc<Node<T>>>>,
66    // live `Mergex` handles pointing here. `Arc::strong_count` cannot stand in:
67    // the father holds one, and `snapshot_sons` clones more for the duration of
68    // a merge, so it never settles.
69    handles: AtomicUsize,
70    // set once the last handle is gone. The node keeps its place, and whatever
71    // it still owes, until a merger folds it and reaps it.
72    dead: AtomicBool,
73    data: Mutex<T>,
74    dirty: AtomicBool, // if true means that it is not sync with father node
75    // conservative hint: true when some strict descendant may be dirty. Lets a
76    // clean subtree be skipped in O(1) instead of being walked son by son.
77    // Never a false negative, which is the only direction that would lose data.
78    subtree_dirty: Arc<AtomicBool>,
79    // the subtree_dirty flags of every ancestor, father first. Built once at
80    // copy() time so a write never has to upgrade a Weak: doing that per set
81    // is a CAS on the root's shared refcount from every writer at once.
82    ancestor_flags: Vec<Arc<AtomicBool>>,
83    // what a node holds when it has nothing pending for its father. Shared down
84    // from the root like `merge`, so every node of a tree agrees on it.
85    identity: Arc<T>,
86    merge: MergeFn<T>,
87}
88
89/// Handle to a node in the tree. Cloning (or moving one into a thread) shares
90/// the node, it does not copy it.
91///
92/// Except at the root, the data a node holds is the delta still owed to its
93/// father, not the aggregate: it goes back to `identity` every time it is
94/// folded upward.
95pub struct Mergex<T> {
96    node: Arc<Node<T>>,
97}
98
99impl<T> Clone for Mergex<T> {
100    fn clone(&self) -> Self {
101        self.node.handles.fetch_add(1, Ordering::Relaxed);
102        Mergex {
103            node: Arc::clone(&self.node),
104        }
105    }
106}
107
108impl<T> Drop for Mergex<T> {
109    /// Dropping the last handle only plants a tombstone. It cannot unlink the
110    /// node here: the node may still owe its father a delta, and only a merger
111    /// -- walking down from above, inside its own fold -- is in a position to
112    /// collect it. See `Node::reap`.
113    fn drop(&mut self) {
114        if self.node.handles.fetch_sub(1, Ordering::AcqRel) == 1 {
115            self.node.dead.store(true, Ordering::Release);
116        }
117    }
118}
119
120impl<T: std::fmt::Debug> std::fmt::Debug for Mergex<T> {
121    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
122        let sons: Vec<Mergex<T>> = self
123            .node
124            .sons
125            .lock()
126            .unwrap()
127            .iter()
128            .map(|n| Mergex { node: Arc::clone(n) })
129            .collect();
130        f.debug_struct("Mergex")
131            .field("data", &*self.node.data.lock().unwrap())
132            .field("dirty", &self.node.dirty.load(Ordering::Acquire))
133            .field("sons", &sons)
134            .finish()
135    }
136}
137
138impl<T: Clone> Mergex<T> {
139    /// Builds a root holding `data`.
140    ///
141    /// `identity` is the neutral element of `merge`: folding it into any value
142    /// must leave that value unchanged. Every node is reset to it once its data
143    /// has been folded into its father, which is what stops the same delta from
144    /// being counted twice by two successive reads.
145    pub fn new(data: T, identity: T, merge: impl Fn(&mut T, &T) + Send + Sync + 'static) -> Self {
146        Mergex {
147            node: Arc::new(Node {
148                sons: Mutex::new(vec![]),
149                handles: AtomicUsize::new(1),
150                dead: AtomicBool::new(false),
151                data: Mutex::new(data),
152                dirty: AtomicBool::new(false),
153                subtree_dirty: Arc::new(AtomicBool::new(false)),
154                ancestor_flags: vec![],
155                identity: Arc::new(identity),
156                merge: Arc::new(merge),
157            }),
158        }
159    }
160
161    /// Registers a new son and returns its handle. Move it into a thread.
162    ///
163    /// The son starts at `identity`: it owes its father nothing yet. Seeding it
164    /// with a value instead would be a write nobody ever asked for, and would
165    /// land in the aggregate the first time any of its own sons was folded.
166    pub fn copy(&self) -> Self {
167        let son = Arc::new(Node {
168            sons: Mutex::new(vec![]),
169            handles: AtomicUsize::new(1),
170            dead: AtomicBool::new(false),
171            data: Mutex::new((*self.node.identity).clone()),
172            dirty: AtomicBool::new(false),
173            subtree_dirty: Arc::new(AtomicBool::new(false)),
174            ancestor_flags: {
175                let mut f = Vec::with_capacity(self.node.ancestor_flags.len() + 1);
176                f.push(Arc::clone(&self.node.subtree_dirty));
177                f.extend(self.node.ancestor_flags.iter().cloned());
178                f
179            },
180            identity: Arc::clone(&self.node.identity),
181            merge: Arc::clone(&self.node.merge),
182        });
183        self.node.sons.lock().unwrap().push(Arc::clone(&son));
184        Mergex { node: son }
185    }
186
187    /// Overwrites this node's data and marks it out of sync with its father.
188    pub fn set(&self, data: T) {
189        self.update(|slot| *slot = data);
190    }
191
192    /// Read-modify-writes this node's data under a single lock and marks it out
193    /// of sync with its father. `set` is this with a closure that overwrites.
194    pub fn update(&self, f: impl FnOnce(&mut T)) {
195        // the dirty flag is raised while still holding the data lock, so a
196        // concurrent merge can never clear it in between and swallow the write
197        let mut guard = self.node.data.lock().unwrap();
198        f(&mut guard);
199        // A plain load and store, not a read-modify-write: `dirty` is only ever
200        // *written* under this data lock -- by `update` here, and by the merge
201        // that clears it -- so holding the lock already makes the pair atomic
202        // against everyone who could change it. The one unlocked reader,
203        // `merge_sons`' fast path, only loads. The old value says whether this
204        // node already owed its father something.
205        let was_dirty = self.node.dirty.load(Ordering::Relaxed);
206        self.node.dirty.store(true, Ordering::Release);
207        drop(guard);
208
209        // Walking up is what costs: `mark_ancestors` takes a line shared by
210        // every writer in the subtree, exclusively. Skipping it when the bit was
211        // already up turns a burst of writes on one node into a single walk,
212        // which is the difference between a per-write shared RMW and a
213        // per-fold one -- roughly a factor of ten under eight writers.
214        //
215        // Sound because a merge clears `dirty` under this same data lock. So
216        // `was_dirty` true means no merge has folded this node since the write
217        // that raised the bit, and that write is the one that flagged the
218        // ancestors: either it has finished doing so, or it is still on its way
219        // up, and its RMWs land in the same modification order the merger's
220        // clearing swap reads from. Nothing is left unflagged that a merge has
221        // already walked past.
222        if !was_dirty {
223            self.node.mark_ancestors();
224        }
225    }
226
227    /// This node's own data, with no merging. Away from the root that is the
228    /// delta still owed to the father, so it reads back as `identity` right
229    /// after a fold, not as everything this node has ever written.
230    pub fn get_threaded(&self) -> T {
231        self.node.data.lock().unwrap().clone()
232    }
233
234    /// Folds every dirty descendant into this node, deepest first, and returns
235    /// the result. Called on the root, that is the aggregate.
236    ///
237    /// When nothing below has changed this is a single atomic load, whatever
238    /// the size of the subtree. When several threads call it at once, one wins
239    /// the sweep and the others return what is currently there rather than
240    /// waiting -- so an individual call can be stale under concurrent readers,
241    /// though nothing is lost and a call on a quiet tree is exact.
242    ///
243    /// ```
244    /// # use mergex::Mergex;
245    /// let root = Mergex::new(10i64, 0, |f: &mut i64, s: &i64| *f += *s);
246    /// let son = root.copy();
247    /// son.set(5);
248    /// assert_eq!(root.get(), 15);
249    /// assert_eq!(root.get(), 15); // the delta is not folded twice
250    /// ```
251    pub fn get(&self) -> T {
252        self.node.merge_sons();
253        self.get_threaded()
254    }
255
256    /// Whether any descendant has something pending. `false` does not promise
257    /// that a `get` is free, only that no write is waiting to be folded.
258    ///
259    /// Costs one atomic load on a clean subtree, whatever its size.
260    pub fn check_children(&self) -> bool {
261        self.node.check_children()
262    }
263
264    /// Whether this node itself owes its father a delta.
265    pub fn check_dirty_bit(&self) -> bool {
266        self.node.dirty.load(Ordering::Acquire)
267    }
268}
269
270impl<T: Clone> Node<T> {
271    /// Flags every ancestor as having a dirty descendant. Stops at the first
272    /// one that was already flagged, so a burst of sets on the same node costs
273    /// one RMW, not one walk per set.
274    fn mark_ancestors(&self) {
275        for flag in &self.ancestor_flags {
276            // Always a read-modify-write, never a `load` fast path, even though
277            // the flag is usually already up and the RMW takes the line
278            // exclusive. The swap is not here to change the flag -- it is here
279            // to *publish*.
280            //
281            // `merge_sons` reads a son's `dirty` bit without taking that son's
282            // data lock, so the only thing that makes the raised bit visible to
283            // it is a release edge on the flag it clears. A `load` that returns
284            // true and bails out releases nothing: the writer leaves having
285            // published no edge at all, the merger may then read `dirty` stale,
286            // skip the son, and clear the flags on its way out -- and the write
287            // is gone for good, because nothing is left flagged to bring anyone
288            // back. loom finds it in a two-level tree; see tests/loom.rs.
289            //
290            // A plain load is also unsound for a second reason, one the lock
291            // would not fix either: it can read a stale `true` for an ancestor a
292            // merge has just cleared, and then the walk stops short of the root
293            // and no later read ever comes down. An RMW cannot -- it always
294            // reads the latest value in the flag's modification order.
295            //
296            // The RMW is what closes it: it lands in the flag's modification
297            // order, so the merger's own `swap(false)` either reads it -- and
298            // then acquires everything this writer did, `dirty` included -- or
299            // precedes it, in which case the flag is left up and the next read
300            // comes back down.
301            if flag.swap(true, Ordering::AcqRel) {
302                return;
303            }
304        }
305    }
306
307    /// Folds every dirty descendant into this node, deepest first.
308    /// Returns whether `self.data` changed.
309    fn merge_sons(&self) -> bool {
310        // cleared before the walk, not after: a set landing mid-walk re-flags
311        // this node and is picked up by the next merge instead of being lost
312        if !self.subtree_dirty.swap(false, Ordering::AcqRel) {
313            return false;
314        }
315
316        let mut changed = false;
317        let mut spent: Vec<Arc<Node<T>>> = Vec::new();
318        // one clone of the handle list per level: the sons lock must not be held
319        // across the recursion or copy() would block for the whole subtree merge.
320        // The subtree_dirty check above means a clean tree never gets here.
321        for son in self.snapshot_sons() {
322            // grandsons first: a son that absorbs a grandson is itself out of sync
323            let son_changed = son.merge_sons();
324            // cheap check first, to skip the lock on a clean son
325            if !son.dirty.load(Ordering::Acquire) && !son_changed {
326                // Nothing to fold. Reaping rides along on this same walk rather
327                // than a second pass: a second `snapshot_sons` would allocate a
328                // vector and touch every refcount again on every merge, spent
329                // sons or not, and that showed up as +47% on a 1000-son fold.
330                if son.is_spent() {
331                    spent.push(son);
332                }
333                continue;
334            }
335            // read and clear under the son's lock: this pairs with set(), so the
336            // two can never interleave. copy the value out before taking our own
337            // lock, we must never hold two at once.
338            let son_data = {
339                let mut guard = son.data.lock().unwrap();
340                son.dirty.store(false, Ordering::Release);
341                // take the delta and leave the identity behind. Cloning it out
342                // and leaving it in place would fold the same delta again on
343                // the next read: `update(|x| *x += 1)` twice, with a get() in
344                // between, would land as +1 then +2.
345                mem::replace(&mut *guard, (*son.identity).clone())
346            };
347            (self.merge)(&mut self.data.lock().unwrap(), &son_data);
348            changed = true;
349            // folded and empty-handed: this is the moment it becomes reapable
350            if son.is_spent() {
351                spent.push(son);
352            }
353        }
354        if !spent.is_empty() {
355            self.reap(&spent);
356        }
357        changed
358    }
359
360    /// A node with no handles left, nothing pending, and nothing underneath it.
361    /// Anything less and unlinking it would lose data or orphan a live writer.
362    fn is_spent(&self) -> bool {
363        self.dead.load(Ordering::Acquire)
364            && self.handles.load(Ordering::Acquire) == 0
365            && !self.dirty.load(Ordering::Acquire)
366            && self.sons.lock().unwrap().is_empty()
367    }
368
369    /// Unlinks spent sons. `swap_remove` semantics via `retain`: nothing caches
370    /// a position, so there are no indices to patch. Because a dead son is
371    /// removed rather than tombstoned in place, the list stays the length of the
372    /// *live* sons, which is what keeps `snapshot_sons` from growing with the
373    /// number of nodes the process has ever created.
374    fn reap(&self, spent: &[Arc<Node<T>>]) {
375        // Two regimes. A pool recycling one worker at a time retires a single
376        // son per merge, and there a linear scan beats allocating and sorting.
377        // A whole generation retiring at once makes `spent` as long as `sons`,
378        // and then `any(ptr_eq)` inside `retain` is quadratic -- 362us to reap a
379        // thousand sons, against 154us by address.
380        const LINEAR: usize = 8;
381        let marks: Vec<*const Node<T>> = if spent.len() > LINEAR {
382            let mut m: Vec<*const Node<T>> = spent.iter().map(Arc::as_ptr).collect();
383            m.sort_unstable();
384            m
385        } else {
386            Vec::new()
387        };
388        let is_marked = |s: &Arc<Node<T>>| {
389            if spent.len() > LINEAR {
390                marks.binary_search(&Arc::as_ptr(s)).is_ok()
391            } else {
392                spent.iter().any(|d| Arc::ptr_eq(s, d))
393            }
394        };
395
396        let mut sons = self.sons.lock().unwrap();
397        sons.retain(|s| {
398            if !is_marked(s) {
399                return true;
400            }
401            // Re-check the flags, but never the son's own `sons` list: taking
402            // that lock here would mean holding two at once, which this crate
403            // does not do anywhere else. It is not needed. A new son can only
404            // appear through `copy()`, which needs a handle, and this node has
405            // none and can never be handed one again -- `dead` is permanent
406            // because nothing hands out a handle to an existing node.
407            s.handles.load(Ordering::Acquire) != 0 || s.dirty.load(Ordering::Acquire)
408        });
409    }
410
411    fn check_children(&self) -> bool {
412        if !self.subtree_dirty.load(Ordering::Acquire) {
413            return false;
414        }
415        self.snapshot_sons()
416            .iter()
417            .any(|s| s.dirty.load(Ordering::Acquire) || s.check_children())
418    }
419
420    /// Clones the son handles out so the `sons` lock is not held while
421    /// recursing: another thread calling copy() on us would block on it.
422    fn snapshot_sons(&self) -> Vec<Arc<Node<T>>> {
423        self.sons.lock().unwrap().to_vec()
424    }
425}
426
427#[cfg(all(test, not(loom)))]
428mod tests {
429    use super::*;
430    use std::thread;
431
432    fn sum() -> Mergex<i32> {
433        Mergex::new(7, 0, |father: &mut i32, son: &i32| *father += *son)
434    }
435
436    #[test]
437    fn thread_updates_reach_the_root() {
438        let root = sum();
439        let t1 = root.copy();
440        let t2 = root.copy();
441
442        let a = thread::spawn(move || t1.set(10));
443        let b = thread::spawn(move || t2.set(20));
444        a.join().unwrap();
445        b.join().unwrap();
446
447        assert!(root.check_children());
448        assert_eq!(root.get(), 37); // 7 + 10 + 20
449        assert!(!root.check_children()); // dirty bits cleared
450    }
451
452    #[test]
453    fn grandsons_merge_bottom_up() {
454        let root = sum();
455        let son = root.copy();
456        let grandson = son.copy();
457        grandson.set(5);
458
459        assert!(root.check_children()); // seen through the son
460        assert_eq!(root.get(), 12); // 7 + (0 + 5)
461    }
462
463    #[test]
464    fn sons_created_inside_a_thread_register() {
465        let root = sum();
466        let t1 = root.copy();
467
468        thread::spawn(move || {
469            let grandson = t1.copy();
470            grandson.set(1000);
471        })
472        .join()
473        .unwrap();
474
475        assert_eq!(root.get(), 1007); // 7 + (0 + 1000)
476    }
477
478    #[test]
479    fn dropping_the_root_strands_the_son() {
480        let son = {
481            let root = sum();
482            let son = root.copy();
483            son.set(3); // never folded: the root is about to go away
484            son
485        }; // root handle dropped here, nothing else holds it
486
487        // the tree is owned from the root down, so the son survives on its own
488        // handle but has nowhere left to fold into
489        assert_eq!(son.get_threaded(), 3);
490    }
491
492    #[test]
493    fn a_dropped_handle_still_delivers_its_write() {
494        let root = sum();
495        {
496            let worker = root.copy();
497            worker.set(5);
498        } // the worker is gone before anyone reads
499
500        assert_eq!(root.get(), 12); // 7 + 5, collected by the merge
501    }
502
503    #[test]
504    fn a_spent_son_is_unlinked_by_the_next_merge() {
505        let root = sum();
506        {
507            let worker = root.copy();
508            worker.set(5);
509        }
510        assert_eq!(root.node.sons.lock().unwrap().len(), 1); // still linked
511
512        assert_eq!(root.get(), 12); // folds, then reaps
513        assert_eq!(root.node.sons.lock().unwrap().len(), 0);
514    }
515
516    #[test]
517    fn a_live_son_is_never_unlinked() {
518        let root = sum();
519        let worker = root.copy();
520        worker.set(5);
521
522        assert_eq!(root.get(), 12);
523        assert_eq!(root.node.sons.lock().unwrap().len(), 1); // handle still held
524
525        worker.set(2);
526        assert_eq!(root.get(), 14); // and still usable
527    }
528
529    #[test]
530    fn a_dead_son_holding_a_live_grandson_stays() {
531        let root = sum();
532        let grandson = {
533            let son = root.copy();
534            son.copy()
535        }; // the intermediate handle is gone, but its son is not
536        grandson.set(9);
537
538        assert_eq!(root.get(), 16); // 7 + (0 + 9), through the dead intermediate
539        assert_eq!(root.node.sons.lock().unwrap().len(), 1); // not reaped: not empty
540    }
541
542    #[test]
543    fn a_pool_of_short_lived_workers_does_not_grow_the_son_list() {
544        let root = Mergex::new(0i64, 0, |f: &mut i64, s: &i64| *f += *s);
545        for i in 1..=100 {
546            let w = root.copy();
547            w.set(i);
548            drop(w);
549            root.get(); // a pool reads between tasks
550        }
551
552        assert_eq!(root.get(), (1..=100).sum::<i64>());
553        assert_eq!(root.node.sons.lock().unwrap().len(), 0);
554    }
555
556    #[test]
557    fn many_threads_registering_and_setting_at_once() {
558        let root = Mergex::new(0i64, 0, |father: &mut i64, son: &i64| *father += *son);
559
560        let handles: Vec<_> = (1..=50)
561            .map(|i| {
562                let r = root.clone(); // concurrent copy(): stresses the sons lock
563                thread::spawn(move || r.copy().set(i))
564            })
565            .collect();
566        for h in handles {
567            h.join().unwrap();
568        }
569
570        assert_eq!(root.get(), (1..=50).sum::<i64>()); // 1275, nothing lost
571    }
572
573    #[test]
574    fn merging_is_idempotent() {
575        let root = sum();
576        root.copy().set(10);
577
578        assert_eq!(root.get(), 17);
579        assert_eq!(root.get(), 17); // dirty bit cleared, no double counting
580    }
581
582    #[test]
583    fn a_read_does_not_replay_an_earlier_delta() {
584        let root = sum();
585        let son = root.copy();
586
587        // the son accumulates in place, so its data still holds the previous
588        // increments. Each read must fold only what is new since the last one.
589        son.update(|x| *x += 1);
590        assert_eq!(root.get(), 8);
591        son.update(|x| *x += 1);
592        assert_eq!(root.get(), 9); // not 10: the first +1 is not folded twice
593        son.update(|x| *x += 1);
594        assert_eq!(root.get(), 10);
595    }
596
597    #[test]
598    fn folding_resets_the_son_to_the_identity() {
599        let root = sum();
600        let son = root.copy();
601
602        assert_eq!(son.get_threaded(), 0); // a fresh son owes its father nothing
603        son.set(5);
604        assert_eq!(root.get(), 12);
605        assert_eq!(son.get_threaded(), 0); // and owes nothing again once folded
606    }
607
608    #[test]
609    fn an_intermediate_node_is_reset_too() {
610        let root = sum();
611        let son = root.copy();
612        let grandson = son.copy();
613
614        grandson.set(4);
615        assert_eq!(root.get(), 11);
616        assert_eq!(son.get_threaded(), 0); // the son passed the delta on
617        assert_eq!(grandson.get_threaded(), 0);
618
619        grandson.set(4);
620        assert_eq!(root.get(), 15); // 11 + 4, not 11 + 8
621    }
622}