]>
Commit | Line | Data |
---|---|---|
3dfed10e XL |
1 | use std::collections::BTreeMap; |
2 | use std::iter::Iterator; | |
3 | use std::ops::RangeBounds; | |
4 | use std::vec::Vec; | |
5 | ||
6 | use rand::{seq::SliceRandom, thread_rng, Rng}; | |
7 | use test::{black_box, Bencher}; | |
8 | ||
9 | macro_rules! map_insert_rand_bench { | |
10 | ($name: ident, $n: expr, $map: ident) => { | |
11 | #[bench] | |
12 | pub fn $name(b: &mut Bencher) { | |
13 | let n: usize = $n; | |
14 | let mut map = $map::new(); | |
15 | // setup | |
16 | let mut rng = thread_rng(); | |
17 | ||
18 | for _ in 0..n { | |
19 | let i = rng.gen::<usize>() % n; | |
20 | map.insert(i, i); | |
21 | } | |
22 | ||
23 | // measure | |
24 | b.iter(|| { | |
25 | let k = rng.gen::<usize>() % n; | |
26 | map.insert(k, k); | |
27 | map.remove(&k); | |
28 | }); | |
29 | black_box(map); | |
30 | } | |
31 | }; | |
32 | } | |
33 | ||
34 | macro_rules! map_insert_seq_bench { | |
35 | ($name: ident, $n: expr, $map: ident) => { | |
36 | #[bench] | |
37 | pub fn $name(b: &mut Bencher) { | |
38 | let mut map = $map::new(); | |
39 | let n: usize = $n; | |
40 | // setup | |
41 | for i in 0..n { | |
42 | map.insert(i * 2, i * 2); | |
43 | } | |
44 | ||
45 | // measure | |
46 | let mut i = 1; | |
47 | b.iter(|| { | |
48 | map.insert(i, i); | |
49 | map.remove(&i); | |
50 | i = (i + 2) % n; | |
51 | }); | |
52 | black_box(map); | |
53 | } | |
54 | }; | |
55 | } | |
56 | ||
57 | macro_rules! map_find_rand_bench { | |
58 | ($name: ident, $n: expr, $map: ident) => { | |
59 | #[bench] | |
60 | pub fn $name(b: &mut Bencher) { | |
61 | let mut map = $map::new(); | |
62 | let n: usize = $n; | |
63 | ||
64 | // setup | |
65 | let mut rng = thread_rng(); | |
66 | let mut keys: Vec<_> = (0..n).map(|_| rng.gen::<usize>() % n).collect(); | |
67 | ||
68 | for &k in &keys { | |
69 | map.insert(k, k); | |
70 | } | |
71 | ||
72 | keys.shuffle(&mut rng); | |
73 | ||
74 | // measure | |
75 | let mut i = 0; | |
76 | b.iter(|| { | |
77 | let t = map.get(&keys[i]); | |
78 | i = (i + 1) % n; | |
79 | black_box(t); | |
80 | }) | |
81 | } | |
82 | }; | |
83 | } | |
84 | ||
85 | macro_rules! map_find_seq_bench { | |
86 | ($name: ident, $n: expr, $map: ident) => { | |
87 | #[bench] | |
88 | pub fn $name(b: &mut Bencher) { | |
89 | let mut map = $map::new(); | |
90 | let n: usize = $n; | |
91 | ||
92 | // setup | |
93 | for i in 0..n { | |
94 | map.insert(i, i); | |
95 | } | |
96 | ||
97 | // measure | |
98 | let mut i = 0; | |
99 | b.iter(|| { | |
100 | let x = map.get(&i); | |
101 | i = (i + 1) % n; | |
102 | black_box(x); | |
103 | }) | |
104 | } | |
105 | }; | |
106 | } | |
107 | ||
108 | map_insert_rand_bench! {insert_rand_100, 100, BTreeMap} | |
109 | map_insert_rand_bench! {insert_rand_10_000, 10_000, BTreeMap} | |
110 | ||
111 | map_insert_seq_bench! {insert_seq_100, 100, BTreeMap} | |
112 | map_insert_seq_bench! {insert_seq_10_000, 10_000, BTreeMap} | |
113 | ||
114 | map_find_rand_bench! {find_rand_100, 100, BTreeMap} | |
115 | map_find_rand_bench! {find_rand_10_000, 10_000, BTreeMap} | |
116 | ||
117 | map_find_seq_bench! {find_seq_100, 100, BTreeMap} | |
118 | map_find_seq_bench! {find_seq_10_000, 10_000, BTreeMap} | |
119 | ||
120 | fn bench_iteration(b: &mut Bencher, size: i32) { | |
121 | let mut map = BTreeMap::<i32, i32>::new(); | |
122 | let mut rng = thread_rng(); | |
123 | ||
124 | for _ in 0..size { | |
125 | map.insert(rng.gen(), rng.gen()); | |
126 | } | |
127 | ||
128 | b.iter(|| { | |
129 | for entry in &map { | |
130 | black_box(entry); | |
131 | } | |
132 | }); | |
133 | } | |
134 | ||
135 | #[bench] | |
136 | pub fn iteration_20(b: &mut Bencher) { | |
137 | bench_iteration(b, 20); | |
138 | } | |
139 | ||
140 | #[bench] | |
141 | pub fn iteration_1000(b: &mut Bencher) { | |
142 | bench_iteration(b, 1000); | |
143 | } | |
144 | ||
145 | #[bench] | |
146 | pub fn iteration_100000(b: &mut Bencher) { | |
147 | bench_iteration(b, 100000); | |
148 | } | |
149 | ||
150 | fn bench_iteration_mut(b: &mut Bencher, size: i32) { | |
151 | let mut map = BTreeMap::<i32, i32>::new(); | |
152 | let mut rng = thread_rng(); | |
153 | ||
154 | for _ in 0..size { | |
155 | map.insert(rng.gen(), rng.gen()); | |
156 | } | |
157 | ||
158 | b.iter(|| { | |
159 | for kv in map.iter_mut() { | |
160 | black_box(kv); | |
161 | } | |
162 | }); | |
163 | } | |
164 | ||
165 | #[bench] | |
166 | pub fn iteration_mut_20(b: &mut Bencher) { | |
167 | bench_iteration_mut(b, 20); | |
168 | } | |
169 | ||
170 | #[bench] | |
171 | pub fn iteration_mut_1000(b: &mut Bencher) { | |
172 | bench_iteration_mut(b, 1000); | |
173 | } | |
174 | ||
175 | #[bench] | |
176 | pub fn iteration_mut_100000(b: &mut Bencher) { | |
177 | bench_iteration_mut(b, 100000); | |
178 | } | |
179 | ||
136023e0 | 180 | fn bench_first_and_last_nightly(b: &mut Bencher, size: i32) { |
3dfed10e XL |
181 | let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect(); |
182 | b.iter(|| { | |
183 | for _ in 0..10 { | |
184 | black_box(map.first_key_value()); | |
185 | black_box(map.last_key_value()); | |
186 | } | |
187 | }); | |
188 | } | |
189 | ||
136023e0 XL |
190 | fn bench_first_and_last_stable(b: &mut Bencher, size: i32) { |
191 | let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect(); | |
192 | b.iter(|| { | |
193 | for _ in 0..10 { | |
194 | black_box(map.iter().next()); | |
195 | black_box(map.iter().next_back()); | |
196 | } | |
197 | }); | |
198 | } | |
199 | ||
200 | #[bench] | |
201 | pub fn first_and_last_0_nightly(b: &mut Bencher) { | |
202 | bench_first_and_last_nightly(b, 0); | |
203 | } | |
204 | ||
205 | #[bench] | |
206 | pub fn first_and_last_0_stable(b: &mut Bencher) { | |
207 | bench_first_and_last_stable(b, 0); | |
208 | } | |
209 | ||
210 | #[bench] | |
211 | pub fn first_and_last_100_nightly(b: &mut Bencher) { | |
212 | bench_first_and_last_nightly(b, 100); | |
213 | } | |
214 | ||
3dfed10e | 215 | #[bench] |
136023e0 XL |
216 | pub fn first_and_last_100_stable(b: &mut Bencher) { |
217 | bench_first_and_last_stable(b, 100); | |
3dfed10e XL |
218 | } |
219 | ||
220 | #[bench] | |
136023e0 XL |
221 | pub fn first_and_last_10k_nightly(b: &mut Bencher) { |
222 | bench_first_and_last_nightly(b, 10_000); | |
3dfed10e XL |
223 | } |
224 | ||
225 | #[bench] | |
136023e0 XL |
226 | pub fn first_and_last_10k_stable(b: &mut Bencher) { |
227 | bench_first_and_last_stable(b, 10_000); | |
3dfed10e XL |
228 | } |
229 | ||
230 | const BENCH_RANGE_SIZE: i32 = 145; | |
231 | const BENCH_RANGE_COUNT: i32 = BENCH_RANGE_SIZE * (BENCH_RANGE_SIZE - 1) / 2; | |
232 | ||
233 | fn bench_range<F, R>(b: &mut Bencher, f: F) | |
234 | where | |
235 | F: Fn(i32, i32) -> R, | |
236 | R: RangeBounds<i32>, | |
237 | { | |
238 | let map: BTreeMap<_, _> = (0..BENCH_RANGE_SIZE).map(|i| (i, i)).collect(); | |
239 | b.iter(|| { | |
240 | let mut c = 0; | |
241 | for i in 0..BENCH_RANGE_SIZE { | |
242 | for j in i + 1..BENCH_RANGE_SIZE { | |
243 | black_box(map.range(f(i, j))); | |
244 | c += 1; | |
245 | } | |
246 | } | |
247 | debug_assert_eq!(c, BENCH_RANGE_COUNT); | |
248 | }); | |
249 | } | |
250 | ||
251 | #[bench] | |
252 | pub fn range_included_excluded(b: &mut Bencher) { | |
253 | bench_range(b, |i, j| i..j); | |
254 | } | |
255 | ||
256 | #[bench] | |
257 | pub fn range_included_included(b: &mut Bencher) { | |
258 | bench_range(b, |i, j| i..=j); | |
259 | } | |
260 | ||
261 | #[bench] | |
262 | pub fn range_included_unbounded(b: &mut Bencher) { | |
263 | bench_range(b, |i, _| i..); | |
264 | } | |
265 | ||
266 | #[bench] | |
267 | pub fn range_unbounded_unbounded(b: &mut Bencher) { | |
268 | bench_range(b, |_, _| ..); | |
269 | } | |
270 | ||
271 | fn bench_iter(b: &mut Bencher, repeats: i32, size: i32) { | |
272 | let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect(); | |
273 | b.iter(|| { | |
274 | for _ in 0..repeats { | |
275 | black_box(map.iter()); | |
276 | } | |
277 | }); | |
278 | } | |
279 | ||
280 | /// Contrast range_unbounded_unbounded with `iter()`. | |
281 | #[bench] | |
282 | pub fn range_unbounded_vs_iter(b: &mut Bencher) { | |
283 | bench_iter(b, BENCH_RANGE_COUNT, BENCH_RANGE_SIZE); | |
284 | } | |
285 | ||
286 | #[bench] | |
287 | pub fn iter_0(b: &mut Bencher) { | |
288 | bench_iter(b, 1_000, 0); | |
289 | } | |
290 | ||
291 | #[bench] | |
292 | pub fn iter_1(b: &mut Bencher) { | |
293 | bench_iter(b, 1_000, 1); | |
294 | } | |
295 | ||
296 | #[bench] | |
297 | pub fn iter_100(b: &mut Bencher) { | |
298 | bench_iter(b, 1_000, 100); | |
299 | } | |
300 | ||
301 | #[bench] | |
302 | pub fn iter_10k(b: &mut Bencher) { | |
303 | bench_iter(b, 1_000, 10_000); | |
304 | } | |
305 | ||
306 | #[bench] | |
307 | pub fn iter_1m(b: &mut Bencher) { | |
308 | bench_iter(b, 1_000, 1_000_000); | |
309 | } | |
310 | ||
311 | const FAT: usize = 256; | |
312 | ||
313 | // The returned map has small keys and values. | |
314 | // Benchmarks on it have a counterpart in set.rs with the same keys and no values at all. | |
315 | fn slim_map(n: usize) -> BTreeMap<usize, usize> { | |
316 | (0..n).map(|i| (i, i)).collect::<BTreeMap<_, _>>() | |
317 | } | |
318 | ||
319 | // The returned map has small keys and large values. | |
320 | fn fat_val_map(n: usize) -> BTreeMap<usize, [usize; FAT]> { | |
321 | (0..n).map(|i| (i, [i; FAT])).collect::<BTreeMap<_, _>>() | |
322 | } | |
323 | ||
3dfed10e XL |
324 | #[bench] |
325 | pub fn clone_slim_100(b: &mut Bencher) { | |
326 | let src = slim_map(100); | |
327 | b.iter(|| src.clone()) | |
328 | } | |
329 | ||
330 | #[bench] | |
331 | pub fn clone_slim_100_and_clear(b: &mut Bencher) { | |
332 | let src = slim_map(100); | |
333 | b.iter(|| src.clone().clear()) | |
334 | } | |
335 | ||
336 | #[bench] | |
337 | pub fn clone_slim_100_and_drain_all(b: &mut Bencher) { | |
338 | let src = slim_map(100); | |
339 | b.iter(|| src.clone().drain_filter(|_, _| true).count()) | |
340 | } | |
341 | ||
342 | #[bench] | |
343 | pub fn clone_slim_100_and_drain_half(b: &mut Bencher) { | |
344 | let src = slim_map(100); | |
345 | b.iter(|| { | |
346 | let mut map = src.clone(); | |
347 | assert_eq!(map.drain_filter(|i, _| i % 2 == 0).count(), 100 / 2); | |
348 | assert_eq!(map.len(), 100 / 2); | |
349 | }) | |
350 | } | |
351 | ||
352 | #[bench] | |
353 | pub fn clone_slim_100_and_into_iter(b: &mut Bencher) { | |
354 | let src = slim_map(100); | |
355 | b.iter(|| src.clone().into_iter().count()) | |
356 | } | |
357 | ||
358 | #[bench] | |
359 | pub fn clone_slim_100_and_pop_all(b: &mut Bencher) { | |
360 | let src = slim_map(100); | |
361 | b.iter(|| { | |
362 | let mut map = src.clone(); | |
363 | while map.pop_first().is_some() {} | |
364 | map | |
365 | }); | |
366 | } | |
367 | ||
368 | #[bench] | |
369 | pub fn clone_slim_100_and_remove_all(b: &mut Bencher) { | |
370 | let src = slim_map(100); | |
371 | b.iter(|| { | |
372 | let mut map = src.clone(); | |
373 | while let Some(elt) = map.iter().map(|(&i, _)| i).next() { | |
374 | let v = map.remove(&elt); | |
375 | debug_assert!(v.is_some()); | |
376 | } | |
377 | map | |
378 | }); | |
379 | } | |
380 | ||
381 | #[bench] | |
382 | pub fn clone_slim_100_and_remove_half(b: &mut Bencher) { | |
383 | let src = slim_map(100); | |
384 | b.iter(|| { | |
385 | let mut map = src.clone(); | |
386 | for i in (0..100).step_by(2) { | |
387 | let v = map.remove(&i); | |
388 | debug_assert!(v.is_some()); | |
389 | } | |
390 | assert_eq!(map.len(), 100 / 2); | |
391 | map | |
392 | }) | |
393 | } | |
394 | ||
395 | #[bench] | |
396 | pub fn clone_slim_10k(b: &mut Bencher) { | |
397 | let src = slim_map(10_000); | |
398 | b.iter(|| src.clone()) | |
399 | } | |
400 | ||
401 | #[bench] | |
402 | pub fn clone_slim_10k_and_clear(b: &mut Bencher) { | |
403 | let src = slim_map(10_000); | |
404 | b.iter(|| src.clone().clear()) | |
405 | } | |
406 | ||
407 | #[bench] | |
408 | pub fn clone_slim_10k_and_drain_all(b: &mut Bencher) { | |
409 | let src = slim_map(10_000); | |
410 | b.iter(|| src.clone().drain_filter(|_, _| true).count()) | |
411 | } | |
412 | ||
413 | #[bench] | |
414 | pub fn clone_slim_10k_and_drain_half(b: &mut Bencher) { | |
415 | let src = slim_map(10_000); | |
416 | b.iter(|| { | |
417 | let mut map = src.clone(); | |
418 | assert_eq!(map.drain_filter(|i, _| i % 2 == 0).count(), 10_000 / 2); | |
419 | assert_eq!(map.len(), 10_000 / 2); | |
420 | }) | |
421 | } | |
422 | ||
423 | #[bench] | |
424 | pub fn clone_slim_10k_and_into_iter(b: &mut Bencher) { | |
425 | let src = slim_map(10_000); | |
426 | b.iter(|| src.clone().into_iter().count()) | |
427 | } | |
428 | ||
429 | #[bench] | |
430 | pub fn clone_slim_10k_and_pop_all(b: &mut Bencher) { | |
431 | let src = slim_map(10_000); | |
432 | b.iter(|| { | |
433 | let mut map = src.clone(); | |
434 | while map.pop_first().is_some() {} | |
435 | map | |
436 | }); | |
437 | } | |
438 | ||
439 | #[bench] | |
440 | pub fn clone_slim_10k_and_remove_all(b: &mut Bencher) { | |
441 | let src = slim_map(10_000); | |
442 | b.iter(|| { | |
443 | let mut map = src.clone(); | |
444 | while let Some(elt) = map.iter().map(|(&i, _)| i).next() { | |
445 | let v = map.remove(&elt); | |
446 | debug_assert!(v.is_some()); | |
447 | } | |
448 | map | |
449 | }); | |
450 | } | |
451 | ||
452 | #[bench] | |
453 | pub fn clone_slim_10k_and_remove_half(b: &mut Bencher) { | |
454 | let src = slim_map(10_000); | |
455 | b.iter(|| { | |
456 | let mut map = src.clone(); | |
457 | for i in (0..10_000).step_by(2) { | |
458 | let v = map.remove(&i); | |
459 | debug_assert!(v.is_some()); | |
460 | } | |
461 | assert_eq!(map.len(), 10_000 / 2); | |
462 | map | |
463 | }) | |
464 | } | |
465 | ||
466 | #[bench] | |
467 | pub fn clone_fat_val_100(b: &mut Bencher) { | |
468 | let src = fat_val_map(100); | |
469 | b.iter(|| src.clone()) | |
470 | } | |
471 | ||
472 | #[bench] | |
473 | pub fn clone_fat_val_100_and_clear(b: &mut Bencher) { | |
474 | let src = fat_val_map(100); | |
475 | b.iter(|| src.clone().clear()) | |
476 | } | |
477 | ||
478 | #[bench] | |
479 | pub fn clone_fat_val_100_and_drain_all(b: &mut Bencher) { | |
480 | let src = fat_val_map(100); | |
481 | b.iter(|| src.clone().drain_filter(|_, _| true).count()) | |
482 | } | |
483 | ||
484 | #[bench] | |
485 | pub fn clone_fat_val_100_and_drain_half(b: &mut Bencher) { | |
486 | let src = fat_val_map(100); | |
487 | b.iter(|| { | |
488 | let mut map = src.clone(); | |
489 | assert_eq!(map.drain_filter(|i, _| i % 2 == 0).count(), 100 / 2); | |
490 | assert_eq!(map.len(), 100 / 2); | |
491 | }) | |
492 | } | |
493 | ||
494 | #[bench] | |
495 | pub fn clone_fat_val_100_and_into_iter(b: &mut Bencher) { | |
496 | let src = fat_val_map(100); | |
497 | b.iter(|| src.clone().into_iter().count()) | |
498 | } | |
499 | ||
500 | #[bench] | |
501 | pub fn clone_fat_val_100_and_pop_all(b: &mut Bencher) { | |
502 | let src = fat_val_map(100); | |
503 | b.iter(|| { | |
504 | let mut map = src.clone(); | |
505 | while map.pop_first().is_some() {} | |
506 | map | |
507 | }); | |
508 | } | |
509 | ||
510 | #[bench] | |
511 | pub fn clone_fat_val_100_and_remove_all(b: &mut Bencher) { | |
512 | let src = fat_val_map(100); | |
513 | b.iter(|| { | |
514 | let mut map = src.clone(); | |
515 | while let Some(elt) = map.iter().map(|(&i, _)| i).next() { | |
516 | let v = map.remove(&elt); | |
517 | debug_assert!(v.is_some()); | |
518 | } | |
519 | map | |
520 | }); | |
521 | } | |
522 | ||
523 | #[bench] | |
524 | pub fn clone_fat_val_100_and_remove_half(b: &mut Bencher) { | |
525 | let src = fat_val_map(100); | |
526 | b.iter(|| { | |
527 | let mut map = src.clone(); | |
528 | for i in (0..100).step_by(2) { | |
529 | let v = map.remove(&i); | |
530 | debug_assert!(v.is_some()); | |
531 | } | |
532 | assert_eq!(map.len(), 100 / 2); | |
533 | map | |
534 | }) | |
535 | } |