sdd 4.8.8

Scalable lock-free delayed memory reclaimer
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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145

use std::sync::{Arc, Barrier};
use std::time::Duration;
use std::{thread, time::Instant};

use criterion::{Criterion, criterion_group, criterion_main};
use sdd::{Guard, Owned, PrivateCollector, Shared};

fn guard_accelerate(c: &mut Criterion) {
    let _guard = Guard::new();
    c.bench_function("EBR: accelerate", |b| {
        b.iter(|| {
            let guard = Guard::new();
            guard.accelerate();
        })
    });
}

fn guard_single(c: &mut Criterion) {
    c.bench_function("EBR: guard", |b| {
        b.iter(|| {
            let _guard = Guard::new();
        })
    });
}

fn guard_superposed(c: &mut Criterion) {
    let _guard = Guard::new();
    c.bench_function("EBR: superposed guard", |b| {
        b.iter(|| {
            let _guard = Guard::new();
        })
    });
}

fn guard_traversal_8(c: &mut Criterion) {
    c.bench_function("EBR: traverse 16 collectors", |b| {
        b.iter_custom(|n| test_traverse(16, n))
    });
}

fn guard_traversal_64(c: &mut Criterion) {
    c.bench_function("EBR: traverse 256 collectors", |b| {
        b.iter_custom(|n| test_traverse(256, n))
    });
}

fn owned_allocate(c: &mut Criterion) {
    c.bench_function("Owned: allocate", |b| {
        b.iter(|| {
            let owned = Owned::new([0u64; 8]);
            drop(owned);
        })
    });

    for _ in 0..4 {
        Guard::new().accelerate();
    }
}

fn shared_allocate(c: &mut Criterion) {
    c.bench_function("Shared: allocate", |b| {
        b.iter(|| {
            let shared = Shared::new([0u64; 8]);
            drop(shared);
        })
    });

    for _ in 0..4 {
        Guard::new().accelerate();
    }
}

fn private_collector_push(c: &mut Criterion) {
    let private_collector = PrivateCollector::new();
    unsafe {
        private_collector.collect_owned(Owned::new(()), &Guard::new());
    }
    c.bench_function("PrivateCollector: push", |b| {
        b.iter_custom(|n| {
            let mut owned_vec = Vec::with_capacity(n as usize);
            for _ in 0..n {
                owned_vec.push(Owned::new(()));
            }
            let guard = Guard::new();
            let start = Instant::now();
            while let Some(owned) = owned_vec.pop() {
                unsafe {
                    private_collector.collect_owned(owned, &guard);
                }
            }
            let elapsed = start.elapsed();
            drop(owned_vec);
            guard.accelerate();
            elapsed
        })
    });
}

fn test_traverse(n: usize, iter: u64) -> Duration {
    let barrier = Arc::new(Barrier::new(n + 1));
    let mut threads = Vec::with_capacity(n);
    for _ in 0..n {
        let barrier = barrier.clone();
        threads.push(thread::spawn(move || {
            let guard = Guard::new();
            drop(guard);
            barrier.wait();
            barrier.wait();
        }));
    }
    let guard = Guard::new();
    drop(guard);
    barrier.wait();

    let start = Instant::now();
    for _ in 0..iter {
        let guard = Guard::new();
        guard.accelerate();
        drop(guard);
    }
    let elapsed = start.elapsed();

    barrier.wait();
    for t in threads {
        assert!(t.join().is_ok());
    }
    for _ in 0..4 {
        let guard = Guard::new();
        guard.accelerate();
    }
    elapsed
}

criterion_group!(
    ebr,
    guard_accelerate,
    guard_single,
    guard_superposed,
    guard_traversal_8,
    guard_traversal_64,
    owned_allocate,
    private_collector_push,
    shared_allocate,
);
criterion_main!(ebr);