1 #![feature(test)]
2
3 extern crate test;
4
5 use test::Bencher;
6
7 use indexmap::IndexMap;
8
9 use std::collections::HashMap;
10
11 use rand::rngs::SmallRng;
12 use rand::seq::SliceRandom;
13 use rand::SeedableRng;
14
15 use std::hash::{Hash, Hasher};
16
17 use std::borrow::Borrow;
18 use std::ops::Deref;
19
20 /// Use a consistently seeded Rng for benchmark stability
small_rng() -> SmallRng21 fn small_rng() -> SmallRng {
22 let seed = u64::from_le_bytes(*b"indexmap");
23 SmallRng::seed_from_u64(seed)
24 }
25
26 #[derive(PartialEq, Eq, Copy, Clone)]
27 #[repr(transparent)]
28 pub struct OneShot<T: ?Sized>(pub T);
29
30 impl Hash for OneShot<str> {
hash<H: Hasher>(&self, h: &mut H)31 fn hash<H: Hasher>(&self, h: &mut H) {
32 h.write(self.0.as_bytes())
33 }
34 }
35
36 impl<'a, S> From<&'a S> for &'a OneShot<str>
37 where
38 S: AsRef<str>,
39 {
from(s: &'a S) -> Self40 fn from(s: &'a S) -> Self {
41 let s: &str = s.as_ref();
42 unsafe { &*(s as *const str as *const OneShot<str>) }
43 }
44 }
45
46 impl Hash for OneShot<String> {
hash<H: Hasher>(&self, h: &mut H)47 fn hash<H: Hasher>(&self, h: &mut H) {
48 h.write(self.0.as_bytes())
49 }
50 }
51
52 impl Borrow<OneShot<str>> for OneShot<String> {
borrow(&self) -> &OneShot<str>53 fn borrow(&self) -> &OneShot<str> {
54 <&OneShot<str>>::from(&self.0)
55 }
56 }
57
58 impl<T> Deref for OneShot<T> {
59 type Target = T;
deref(&self) -> &T60 fn deref(&self) -> &T {
61 &self.0
62 }
63 }
64
shuffled_keys<I>(iter: I) -> Vec<I::Item> where I: IntoIterator,65 fn shuffled_keys<I>(iter: I) -> Vec<I::Item>
66 where
67 I: IntoIterator,
68 {
69 let mut v = Vec::from_iter(iter);
70 let mut rng = small_rng();
71 v.shuffle(&mut rng);
72 v
73 }
74
75 #[bench]
insert_hashmap_string_10_000(b: &mut Bencher)76 fn insert_hashmap_string_10_000(b: &mut Bencher) {
77 let c = 10_000;
78 b.iter(|| {
79 let mut map = HashMap::with_capacity(c);
80 for x in 0..c {
81 map.insert(x.to_string(), ());
82 }
83 map
84 });
85 }
86
87 #[bench]
insert_hashmap_string_oneshot_10_000(b: &mut Bencher)88 fn insert_hashmap_string_oneshot_10_000(b: &mut Bencher) {
89 let c = 10_000;
90 b.iter(|| {
91 let mut map = HashMap::with_capacity(c);
92 for x in 0..c {
93 map.insert(OneShot(x.to_string()), ());
94 }
95 map
96 });
97 }
98
99 #[bench]
insert_indexmap_string_10_000(b: &mut Bencher)100 fn insert_indexmap_string_10_000(b: &mut Bencher) {
101 let c = 10_000;
102 b.iter(|| {
103 let mut map = IndexMap::with_capacity(c);
104 for x in 0..c {
105 map.insert(x.to_string(), ());
106 }
107 map
108 });
109 }
110
111 #[bench]
lookup_hashmap_10_000_exist_string(b: &mut Bencher)112 fn lookup_hashmap_10_000_exist_string(b: &mut Bencher) {
113 let c = 10_000;
114 let mut map = HashMap::with_capacity(c);
115 let keys = shuffled_keys(0..c);
116 for &key in &keys {
117 map.insert(key.to_string(), 1);
118 }
119 let lookups = (5000..c).map(|x| x.to_string()).collect::<Vec<_>>();
120 b.iter(|| {
121 let mut found = 0;
122 for key in &lookups {
123 found += map.get(key).is_some() as i32;
124 }
125 found
126 });
127 }
128
129 #[bench]
lookup_hashmap_10_000_exist_string_oneshot(b: &mut Bencher)130 fn lookup_hashmap_10_000_exist_string_oneshot(b: &mut Bencher) {
131 let c = 10_000;
132 let mut map = HashMap::with_capacity(c);
133 let keys = shuffled_keys(0..c);
134 for &key in &keys {
135 map.insert(OneShot(key.to_string()), 1);
136 }
137 let lookups = (5000..c)
138 .map(|x| OneShot(x.to_string()))
139 .collect::<Vec<_>>();
140 b.iter(|| {
141 let mut found = 0;
142 for key in &lookups {
143 found += map.get(key).is_some() as i32;
144 }
145 found
146 });
147 }
148
149 #[bench]
lookup_indexmap_10_000_exist_string(b: &mut Bencher)150 fn lookup_indexmap_10_000_exist_string(b: &mut Bencher) {
151 let c = 10_000;
152 let mut map = IndexMap::with_capacity(c);
153 let keys = shuffled_keys(0..c);
154 for &key in &keys {
155 map.insert(key.to_string(), 1);
156 }
157 let lookups = (5000..c).map(|x| x.to_string()).collect::<Vec<_>>();
158 b.iter(|| {
159 let mut found = 0;
160 for key in &lookups {
161 found += map.get(key).is_some() as i32;
162 }
163 found
164 });
165 }
166
167 #[bench]
lookup_indexmap_10_000_exist_string_oneshot(b: &mut Bencher)168 fn lookup_indexmap_10_000_exist_string_oneshot(b: &mut Bencher) {
169 let c = 10_000;
170 let mut map = IndexMap::with_capacity(c);
171 let keys = shuffled_keys(0..c);
172 for &key in &keys {
173 map.insert(OneShot(key.to_string()), 1);
174 }
175 let lookups = (5000..c)
176 .map(|x| OneShot(x.to_string()))
177 .collect::<Vec<_>>();
178 b.iter(|| {
179 let mut found = 0;
180 for key in &lookups {
181 found += map.get(key).is_some() as i32;
182 }
183 found
184 });
185 }
186