]>
Commit | Line | Data |
---|---|---|
8bb4bdeb XL |
1 | use std::iter::Iterator; |
2 | use std::vec::Vec; | |
3 | use std::collections::BTreeMap; | |
9fa01778 | 4 | |
0731742a | 5 | use rand::{Rng, seq::SliceRandom, thread_rng}; |
8bb4bdeb XL |
6 | use test::{Bencher, black_box}; |
7 | ||
85aaf69f SL |
8 | macro_rules! map_insert_rand_bench { |
9 | ($name: ident, $n: expr, $map: ident) => ( | |
10 | #[bench] | |
8bb4bdeb | 11 | pub fn $name(b: &mut Bencher) { |
85aaf69f SL |
12 | let n: usize = $n; |
13 | let mut map = $map::new(); | |
14 | // setup | |
9346a6ac | 15 | let mut rng = thread_rng(); |
85aaf69f SL |
16 | |
17 | for _ in 0..n { | |
c34b1796 | 18 | let i = rng.gen::<usize>() % n; |
85aaf69f SL |
19 | map.insert(i, i); |
20 | } | |
21 | ||
22 | // measure | |
23 | b.iter(|| { | |
c34b1796 | 24 | let k = rng.gen::<usize>() % n; |
85aaf69f SL |
25 | map.insert(k, k); |
26 | map.remove(&k); | |
27 | }); | |
28 | black_box(map); | |
29 | } | |
30 | ) | |
1a4d82fc JJ |
31 | } |
32 | ||
85aaf69f SL |
33 | macro_rules! map_insert_seq_bench { |
34 | ($name: ident, $n: expr, $map: ident) => ( | |
35 | #[bench] | |
8bb4bdeb | 36 | pub fn $name(b: &mut Bencher) { |
85aaf69f SL |
37 | let mut map = $map::new(); |
38 | let n: usize = $n; | |
39 | // setup | |
40 | for i in 0..n { | |
41 | map.insert(i * 2, i * 2); | |
42 | } | |
43 | ||
44 | // measure | |
45 | let mut i = 1; | |
46 | b.iter(|| { | |
47 | map.insert(i, i); | |
48 | map.remove(&i); | |
49 | i = (i + 2) % n; | |
50 | }); | |
51 | black_box(map); | |
52 | } | |
53 | ) | |
1a4d82fc JJ |
54 | } |
55 | ||
85aaf69f SL |
56 | macro_rules! map_find_rand_bench { |
57 | ($name: ident, $n: expr, $map: ident) => ( | |
58 | #[bench] | |
8bb4bdeb | 59 | pub fn $name(b: &mut Bencher) { |
85aaf69f SL |
60 | let mut map = $map::new(); |
61 | let n: usize = $n; | |
62 | ||
63 | // setup | |
9346a6ac | 64 | let mut rng = thread_rng(); |
c34b1796 | 65 | let mut keys: Vec<_> = (0..n).map(|_| rng.gen::<usize>() % n).collect(); |
85aaf69f SL |
66 | |
67 | for &k in &keys { | |
68 | map.insert(k, k); | |
69 | } | |
70 | ||
0731742a | 71 | keys.shuffle(&mut rng); |
85aaf69f SL |
72 | |
73 | // measure | |
74 | let mut i = 0; | |
75 | b.iter(|| { | |
76 | let t = map.get(&keys[i]); | |
77 | i = (i + 1) % n; | |
78 | black_box(t); | |
79 | }) | |
80 | } | |
81 | ) | |
1a4d82fc JJ |
82 | } |
83 | ||
85aaf69f SL |
84 | macro_rules! map_find_seq_bench { |
85 | ($name: ident, $n: expr, $map: ident) => ( | |
86 | #[bench] | |
8bb4bdeb | 87 | pub fn $name(b: &mut Bencher) { |
85aaf69f SL |
88 | let mut map = $map::new(); |
89 | let n: usize = $n; | |
90 | ||
91 | // setup | |
92 | for i in 0..n { | |
93 | map.insert(i, i); | |
94 | } | |
95 | ||
96 | // measure | |
97 | let mut i = 0; | |
98 | b.iter(|| { | |
99 | let x = map.get(&i); | |
100 | i = (i + 1) % n; | |
101 | black_box(x); | |
102 | }) | |
103 | } | |
104 | ) | |
1a4d82fc | 105 | } |
8bb4bdeb XL |
106 | |
107 | map_insert_rand_bench!{insert_rand_100, 100, BTreeMap} | |
108 | map_insert_rand_bench!{insert_rand_10_000, 10_000, BTreeMap} | |
109 | ||
110 | map_insert_seq_bench!{insert_seq_100, 100, BTreeMap} | |
111 | map_insert_seq_bench!{insert_seq_10_000, 10_000, BTreeMap} | |
112 | ||
113 | map_find_rand_bench!{find_rand_100, 100, BTreeMap} | |
114 | map_find_rand_bench!{find_rand_10_000, 10_000, BTreeMap} | |
115 | ||
116 | map_find_seq_bench!{find_seq_100, 100, BTreeMap} | |
117 | map_find_seq_bench!{find_seq_10_000, 10_000, BTreeMap} | |
118 | ||
119 | fn bench_iter(b: &mut Bencher, size: i32) { | |
120 | let mut map = BTreeMap::<i32, i32>::new(); | |
121 | let mut rng = thread_rng(); | |
122 | ||
123 | for _ in 0..size { | |
124 | map.insert(rng.gen(), rng.gen()); | |
125 | } | |
126 | ||
127 | b.iter(|| { | |
128 | for entry in &map { | |
129 | black_box(entry); | |
130 | } | |
131 | }); | |
132 | } | |
133 | ||
134 | #[bench] | |
135 | pub fn iter_20(b: &mut Bencher) { | |
136 | bench_iter(b, 20); | |
137 | } | |
138 | ||
139 | #[bench] | |
140 | pub fn iter_1000(b: &mut Bencher) { | |
141 | bench_iter(b, 1000); | |
142 | } | |
143 | ||
144 | #[bench] | |
145 | pub fn iter_100000(b: &mut Bencher) { | |
146 | bench_iter(b, 100000); | |
147 | } |