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