xstm 0.1.0

A Rust-implemented Software Transactional Memory (STM) library using TL2 (Transactional Locking II) algorithm
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

use std::sync::Arc;
use xstm::{Context, Stm, StmError, TVar, Transaction};

struct Fib {
    var_index: Arc<TVar<i32>>,
    var_a: Arc<TVar<u128>>,
    var_b: Arc<TVar<u128>>,
}

impl Transaction for Fib {
    type Output = (i32, u128);

    fn atomically<'this: 'var, 'context, 'var>(
        &'this self,
        context: &'context mut Context<'var>,
    ) -> Result<Self::Output, StmError> {
        let index = context.read(&self.var_index)?;
        context.write(&self.var_index, index + 1)?;

        let a = context.read(&self.var_a)?;
        let b = context.read(&self.var_b)?;
        let result = a + b;

        context.write(&self.var_a, b)?;
        context.write(&self.var_b, result)?;

        Ok((index, result))
    }
}

#[tokio::test]
async fn basic() {
    let stm = Arc::new(Stm::new());

    let var_index = Arc::new(TVar::new(1));
    let var_a = Arc::new(TVar::new(1));
    let var_b = Arc::new(TVar::new(1));

    let count = 10_000;

    let mut handles = Vec::new();
    for _ in 0..count {
        let _var_index = var_index.clone();
        let _var_a = var_a.clone();
        let _var_b = var_b.clone();
        let _stm = stm.clone();
        let handle = tokio::task::spawn_blocking(move || {
            let fib = Fib {
                var_index: _var_index,
                var_a: _var_a,
                var_b: _var_b,
            };

            let (index, result) = _stm.atomically(fib);

            // let tid = std::thread::current().id();
            // println!("ThreadID {tid:?} index = {index:?} : {result}");

            (index, result)
        });
        handles.push(handle);
    }
    let mut results = Vec::new();

    for handle in handles {
        results.push(handle.await.unwrap());
    }

    results.sort_by_key(|(index, _)| *index);

    let results = results
        .into_iter()
        .map(|(_, result)| result)
        .collect::<Vec<_>>();

    let fib = fib(count);

    let all = results
        .into_iter()
        .zip(fib.into_iter())
        .enumerate()
        .collect::<Vec<_>>();

    for window in all.windows(5) {
        let len = window.len();
        let half_index = len / 2;

        let middle = window[half_index];

        let (index, (result, fib)) = middle;

        if result != fib {
            let indices = window.iter().map(|(index, _)| index).collect::<Vec<_>>();

            let results = window
                .iter()
                .map(|(_, (result, _))| result)
                .collect::<Vec<_>>();

            let fibs = window.iter().map(|(_, (_, fibs))| fibs).collect::<Vec<_>>();

            assert_eq!(
                result, fib,
                "in {}: result({}) != fib({})\n{:?}\n{:?}\n{:?}",
                index, result, fib, &indices, &results, &fibs
            );
            return;
        }
    }
}

fn fib(count: i32) -> Vec<u128> {
    let mut a = 1;
    let mut b = 1;

    let mut v = Vec::new();
    for _ in 0..count {
        let result = a + b;

        a = b;
        b = result;

        v.push(result);
    }
    v
}