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