becca.monster
forked from
tangled.org/core
Monorepo for Tangled
7.1 kB
231 lines
1use std::cell::Cell;
2use std::cmp::Ordering;
3use std::collections::BTreeSet;
4use std::ops::Bound;
5
6type Key = (u64, u32);
7
8fn splitmix64(state: &mut u64) -> u64 {
9 *state = state.wrapping_add(0x9E37_79B9_7F4A_7C15);
10 let mut z = *state;
11 z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
12 z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
13 z ^ (z >> 31)
14}
15
16fn adversarial_keys(n: u32) -> Vec<Key> {
17 (0..n)
18 .scan(0xD1CE_5EED_u64, |state, i| Some((splitmix64(state), i)))
19 .collect()
20}
21
22fn vec_shift_work(keys: &[Key]) -> u128 {
23 let mut sorted: Vec<Key> = Vec::with_capacity(keys.len());
24 keys.iter().fold(0u128, |moves, &key| {
25 match sorted.binary_search(&key) {
26 Ok(_) => moves,
27 Err(pos) => {
28 let displaced = (sorted.len() - pos) as u128;
29 sorted.insert(pos, key);
30 moves + displaced
31 }
32 }
33 })
34}
35
36thread_local! {
37 static COMPARES: Cell<u128> = Cell::new(0);
38}
39
40#[derive(PartialEq, Eq)]
41struct CountedKey(Key);
42
43impl PartialOrd for CountedKey {
44 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
45 Some(self.cmp(other))
46 }
47}
48
49impl Ord for CountedKey {
50 fn cmp(&self, other: &Self) -> Ordering {
51 COMPARES.with(|c| c.set(c.get() + 1));
52 self.0.cmp(&other.0)
53 }
54}
55
56fn btree_compare_work(keys: &[Key]) -> u128 {
57 COMPARES.with(|c| c.set(0));
58 let mut tree: BTreeSet<CountedKey> = BTreeSet::new();
59 keys.iter().for_each(|&key| {
60 tree.insert(CountedKey(key));
61 });
62 COMPARES.with(Cell::get)
63}
64
65fn doubling_ratios(work: &[u128]) -> Vec<f64> {
66 work.windows(2)
67 .map(|w| w[1] as f64 / w[0] as f64)
68 .collect()
69}
70
71#[test]
72fn sorted_vec_build_is_quadratic_while_btree_is_quasilinear() {
73 let sizes = [2_048u32, 4_096, 8_192, 16_384];
74 let measured: Vec<(u128, u128)> = sizes
75 .iter()
76 .map(|&n| {
77 let keys = adversarial_keys(n);
78 (vec_shift_work(&keys), btree_compare_work(&keys))
79 })
80 .collect();
81
82 let vec_work: Vec<u128> = measured.iter().map(|m| m.0).collect();
83 let btree_work: Vec<u128> = measured.iter().map(|m| m.1).collect();
84
85 eprintln!("{:<8} {:>16} {:>16}", "N", "vec_shifts", "btree_compares");
86 sizes.iter().enumerate().for_each(|(i, n)| {
87 eprintln!("{:<8} {:>16} {:>16}", n, vec_work[i], btree_work[i]);
88 });
89
90 let vec_ratios = doubling_ratios(&vec_work);
91 let btree_ratios = doubling_ratios(&btree_work);
92 eprintln!("vec doubling ratios: {vec_ratios:?}");
93 eprintln!("btree doubling ratios: {btree_ratios:?}");
94
95 vec_ratios.iter().for_each(|&ratio| {
96 assert!(
97 (3.5..=4.5).contains(&ratio),
98 "sorted-vec build must quadruple per doubling of N, proving O(n^2), got {ratio:.2}x"
99 );
100 });
101
102 btree_ratios.iter().for_each(|&ratio| {
103 assert!(
104 ratio < 3.0,
105 "btree build must stay near a doubling per doubling of N, proving sub-quadratic, got {ratio:.2}x"
106 );
107 });
108
109 let advantage: Vec<f64> = (0..sizes.len())
110 .map(|i| vec_work[i] as f64 / btree_work[i] as f64)
111 .collect();
112 advantage.windows(2).for_each(|w| {
113 assert!(
114 w[1] > w[0],
115 "btree's advantage over the sorted vec must widen as N grows, got {advantage:?}"
116 );
117 });
118}
119
120fn vec_remove_work(keys: &[Key]) -> u128 {
121 let mut sorted: Vec<Key> = keys.to_vec();
122 sorted.sort_unstable();
123 keys.iter().fold(0u128, |moves, key| {
124 match sorted.binary_search(key) {
125 Ok(pos) => {
126 let displaced = (sorted.len() - pos - 1) as u128;
127 sorted.remove(pos);
128 moves + displaced
129 }
130 Err(_) => moves,
131 }
132 })
133}
134
135fn btree_remove_work(keys: &[Key]) -> u128 {
136 let mut tree: BTreeSet<CountedKey> = keys.iter().map(|&k| CountedKey(k)).collect();
137 COMPARES.with(|c| c.set(0));
138 keys.iter().for_each(|&k| {
139 tree.remove(&CountedKey(k));
140 });
141 COMPARES.with(Cell::get)
142}
143
144fn sample_cursors(keys: &[Key]) -> Vec<Key> {
145 let mut sorted = keys.to_vec();
146 sorted.sort_unstable();
147 let step = (sorted.len() / 256).max(1);
148 sorted.iter().step_by(step).copied().collect()
149}
150
151fn vec_seek_work(keys: &[Key], cursors: &[Key]) -> u128 {
152 let mut sorted: Vec<CountedKey> = keys.iter().map(|&k| CountedKey(k)).collect();
153 sorted.sort_unstable();
154 COMPARES.with(|c| c.set(0));
155 cursors.iter().for_each(|&cur| {
156 let _ = sorted.partition_point(|k| *k <= CountedKey(cur));
157 });
158 COMPARES.with(Cell::get)
159}
160
161fn btree_seek_work(keys: &[Key], cursors: &[Key]) -> u128 {
162 let tree: BTreeSet<CountedKey> = keys.iter().map(|&k| CountedKey(k)).collect();
163 COMPARES.with(|c| c.set(0));
164 cursors.iter().for_each(|&cur| {
165 let _ = tree
166 .range((Bound::Excluded(CountedKey(cur)), Bound::Unbounded))
167 .next();
168 });
169 COMPARES.with(Cell::get)
170}
171
172#[test]
173fn sorted_vec_teardown_is_quadratic_while_btree_is_quasilinear() {
174 let sizes = [2_048u32, 4_096, 8_192, 16_384];
175 let measured: Vec<(u128, u128)> = sizes
176 .iter()
177 .map(|&n| {
178 let keys = adversarial_keys(n);
179 (vec_remove_work(&keys), btree_remove_work(&keys))
180 })
181 .collect();
182
183 let vec_ratios = doubling_ratios(&measured.iter().map(|m| m.0).collect::<Vec<_>>());
184 let btree_ratios = doubling_ratios(&measured.iter().map(|m| m.1).collect::<Vec<_>>());
185 eprintln!("teardown vec doubling ratios: {vec_ratios:?}");
186 eprintln!("teardown btree doubling ratios: {btree_ratios:?}");
187
188 vec_ratios.iter().for_each(|&ratio| {
189 assert!(
190 (3.5..=4.5).contains(&ratio),
191 "sorted-vec teardown must quadruple per doubling, proving O(n^2), got {ratio:.2}x"
192 );
193 });
194 btree_ratios.iter().for_each(|&ratio| {
195 assert!(
196 ratio < 3.0,
197 "btree teardown must stay sub-quadratic, got {ratio:.2}x"
198 );
199 });
200}
201
202#[test]
203fn cursor_seek_is_sublinear_for_both_representations() {
204 let sizes = [2_048u32, 4_096, 8_192, 16_384];
205 let measured: Vec<(u128, u128)> = sizes
206 .iter()
207 .map(|&n| {
208 let keys = adversarial_keys(n);
209 let cursors = sample_cursors(&keys);
210 (
211 vec_seek_work(&keys, &cursors),
212 btree_seek_work(&keys, &cursors),
213 )
214 })
215 .collect();
216
217 let vec_ratios = doubling_ratios(&measured.iter().map(|m| m.0).collect::<Vec<_>>());
218 let btree_ratios = doubling_ratios(&measured.iter().map(|m| m.1).collect::<Vec<_>>());
219 eprintln!("seek vec doubling ratios: {vec_ratios:?}");
220 eprintln!("seek btree doubling ratios: {btree_ratios:?}");
221
222 vec_ratios
223 .iter()
224 .chain(btree_ratios.iter())
225 .for_each(|&ratio| {
226 assert!(
227 ratio < 1.8,
228 "a fixed cursor sample must seek in logarithmic work as N grows, got {ratio:.2}x"
229 );
230 });
231}