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

use std::sync::Arc;

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

type BigArray = TVar<[u32; 10086]>;

struct Update {
    array: Arc<BigArray>,
}

impl Transaction for Update {
    type Output = u32;

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

        for (_ , window) in array.windows(2).enumerate() {
            let first = window[0];
            let second = window[1];

            if second != first + 1 {
                let tid = std::thread::current().id();
                panic!("{:?} Bad Input: {:?}", tid,window);
            }
        }

        for i in &mut array {
            *i += 1
        }

        context.write(&self.array, array)?;

        Ok(array[0])
    }
}

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

    let mut array = [0; 10086];

    let mut gen = 1..;
    array.fill_with(|| gen.next().unwrap());

    let array = Arc::new(TVar::new(array));

    let count = 100_00;

    let mut handles = Vec::new();
    for _ in 0..count {
        let update_transaction = Update {
            array: array.clone(),
        };
        let _stm = stm.clone();
        let handle = tokio::task::spawn_blocking(move || {
            let first = _stm.atomically(update_transaction);

            let tid = std::thread::current().id();
            println!("ThreadID {tid:?} committed array[0] = {first}");
        });
        handles.push(handle);
    }

    for handle in handles {
        handle.await.unwrap()
    }

    let result_array = stm.atomically(array.read());

    let correct_array = generate_correct_array(result_array.len(), count);

    let all = result_array
        .iter()
        .zip(correct_array.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, expected)) = middle;

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

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

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

            assert_eq!(
                result, expected,
                "in {}: result({}) != expected({})\nindices: {:?}\nresults: {:?}\nexpects: {:?}",
                index, result, expected, &indices, &results, &expects
            );
            return;
        }
    }
}

fn generate_correct_array(array_len: usize, count: u32) -> Vec<u32> {
    (1_u32..array_len as u32).map(|x| x + count).collect()
}