binarytrees/
binarytrees.rs

1use std::sync::Arc;
2
3use rsgc::{
4    heap::{region::HeapArguments, thread::Thread},
5    system::object::{Allocation, Handle},
6    system::traits::Object,
7};
8
9#[allow(dead_code)]
10pub struct TreeNode {
11    item: i64,
12    left: Option<Handle<Self>>,
13    right: Option<Handle<Self>>,
14}
15
16unsafe impl Object for TreeNode {
17    fn trace(&self, visitor: &mut dyn rsgc::system::traits::Visitor) {
18        if let Some(ref left) = self.left {
19            left.trace(visitor);
20        }
21
22        if let Some(ref right) = self.right {
23            right.trace(visitor);
24        }
25    }
26}
27
28unsafe impl Allocation for TreeNode {}
29
30impl TreeNode {
31    fn check_tree(&self) -> usize {
32        if self.left.is_none() {
33            return 1;
34        }
35
36        1 + self.left.unwrap().check_tree() + self.right.unwrap().check_tree()
37    }
38}
39
40fn create_tree(thread: &mut Thread, depth: i64) -> Handle<TreeNode> {
41    thread.safepoint();
42    let node = if 0 < depth {
43        let mut node = thread.allocate(TreeNode {
44            item: 0,
45            left: None,
46            right: None,
47        });
48
49        thread.write_barrier(node);
50        node.left = Some(create_tree(thread, depth - 1));
51        thread.write_barrier(node);
52        node.right = Some(create_tree(thread, depth - 1));
53
54        node 
55    } else {
56        let node = TreeNode {
57            item: 0,
58            left: None,
59            right: None,
60        };
61
62        thread.allocate(node)
63    };
64    
65    node
66}
67
68fn bench_parallel() {
69
70    let mut n = 0;
71    if let Some(arg) = std::env::args().skip(1).next() {
72        if let Ok(x) = arg.parse::<usize>() {
73            n = x;
74        }
75    }
76
77    let min_depth = 4;
78    let max_depth = if n < (min_depth + 2) {
79        min_depth + 2
80    } else {
81        n 
82    };
83
84    let start = std::time::Instant::now();
85    let stretch_depth = max_depth + 1;
86
87    {
88        println!(
89            "stretch tree of depth {}\t check: {}",
90            stretch_depth,
91            create_tree(Thread::current(), stretch_depth as _)
92                .as_ref()
93                .check_tree()
94        );
95    }
96
97    let long_lasting_tree = create_tree(Thread::current(), max_depth as _);
98    use parking_lot::Mutex;
99    let results = Arc::new(
100        (0..(max_depth - min_depth) / 2 + 1)
101            .map(|_| Mutex::new(String::new()))
102            .collect::<Vec<_>>(),
103    );
104    rsgc::thread::scoped::scoped(|scope| {
105        let mut d = min_depth;
106
107        while d <= max_depth {
108            let depth = d;
109            let cloned = results.clone();
110            scope.spawn(move || {
111                let thread = Thread::current();
112                let iterations = 1 << (max_depth - depth + min_depth);
113                let mut check = 0;
114                for _ in 1..=iterations {
115                    let tree_node = create_tree(thread, depth as _);
116                    check += tree_node.as_ref().check_tree();
117                }
118
119                *cloned[(depth - min_depth) / 2].lock() = format!(
120                    "{}\t trees of depth {}\t check: {}",
121                    iterations, depth, check
122                );
123            });
124
125            d += 2;
126        }
127    });
128    for result in results.iter() {
129        println!("{}", *result.lock());
130    }
131    println!(
132        "long lived tree of depth {}\t check: {}",
133        max_depth,
134        long_lasting_tree.as_ref().check_tree()
135    );
136
137    println!(
138        "time: {}ms",
139        start.elapsed().as_millis()
140    );
141}
142
143fn main() {
144    env_logger::init();
145    let args = HeapArguments::from_env();
146
147    let _ = rsgc::thread::main_thread(args, |heap| {
148        heap.add_core_root_set();
149
150        bench_parallel();
151
152        Ok(())
153    });
154}
binarytrees/binarytrees.rs

binarytrees/
binarytrees.rs
