1 #![feature(test)]
2 
3 extern crate test;
4 #[macro_use]
5 extern crate lazy_static;
6 
7 use fnv::FnvHasher;
8 use std::hash::BuildHasherDefault;
9 use std::hash::Hash;
10 type FnvBuilder = BuildHasherDefault<FnvHasher>;
11 
12 use test::black_box;
13 use test::Bencher;
14 
15 use indexmap::IndexMap;
16 
17 use std::collections::HashMap;
18 
19 use rand::rngs::SmallRng;
20 use rand::seq::SliceRandom;
21 use rand::SeedableRng;
22 
23 /// Use a consistently seeded Rng for benchmark stability
small_rng() -> SmallRng24 fn small_rng() -> SmallRng {
25     let seed = u64::from_le_bytes(*b"indexmap");
26     SmallRng::seed_from_u64(seed)
27 }
28 
29 #[bench]
new_hashmap(b: &mut Bencher)30 fn new_hashmap(b: &mut Bencher) {
31     b.iter(|| HashMap::<String, String>::new());
32 }
33 
34 #[bench]
new_indexmap(b: &mut Bencher)35 fn new_indexmap(b: &mut Bencher) {
36     b.iter(|| IndexMap::<String, String>::new());
37 }
38 
39 #[bench]
with_capacity_10e5_hashmap(b: &mut Bencher)40 fn with_capacity_10e5_hashmap(b: &mut Bencher) {
41     b.iter(|| HashMap::<String, String>::with_capacity(10_000));
42 }
43 
44 #[bench]
with_capacity_10e5_indexmap(b: &mut Bencher)45 fn with_capacity_10e5_indexmap(b: &mut Bencher) {
46     b.iter(|| IndexMap::<String, String>::with_capacity(10_000));
47 }
48 
49 #[bench]
insert_hashmap_10_000(b: &mut Bencher)50 fn insert_hashmap_10_000(b: &mut Bencher) {
51     let c = 10_000;
52     b.iter(|| {
53         let mut map = HashMap::with_capacity(c);
54         for x in 0..c {
55             map.insert(x, ());
56         }
57         map
58     });
59 }
60 
61 #[bench]
insert_indexmap_10_000(b: &mut Bencher)62 fn insert_indexmap_10_000(b: &mut Bencher) {
63     let c = 10_000;
64     b.iter(|| {
65         let mut map = IndexMap::with_capacity(c);
66         for x in 0..c {
67             map.insert(x, ());
68         }
69         map
70     });
71 }
72 
73 #[bench]
insert_hashmap_string_10_000(b: &mut Bencher)74 fn insert_hashmap_string_10_000(b: &mut Bencher) {
75     let c = 10_000;
76     b.iter(|| {
77         let mut map = HashMap::with_capacity(c);
78         for x in 0..c {
79             map.insert(x.to_string(), ());
80         }
81         map
82     });
83 }
84 
85 #[bench]
insert_indexmap_string_10_000(b: &mut Bencher)86 fn insert_indexmap_string_10_000(b: &mut Bencher) {
87     let c = 10_000;
88     b.iter(|| {
89         let mut map = IndexMap::with_capacity(c);
90         for x in 0..c {
91             map.insert(x.to_string(), ());
92         }
93         map
94     });
95 }
96 
97 #[bench]
insert_hashmap_str_10_000(b: &mut Bencher)98 fn insert_hashmap_str_10_000(b: &mut Bencher) {
99     let c = 10_000;
100     let ss = Vec::from_iter((0..c).map(|x| x.to_string()));
101     b.iter(|| {
102         let mut map = HashMap::with_capacity(c);
103         for key in &ss {
104             map.insert(&key[..], ());
105         }
106         map
107     });
108 }
109 
110 #[bench]
insert_indexmap_str_10_000(b: &mut Bencher)111 fn insert_indexmap_str_10_000(b: &mut Bencher) {
112     let c = 10_000;
113     let ss = Vec::from_iter((0..c).map(|x| x.to_string()));
114     b.iter(|| {
115         let mut map = IndexMap::with_capacity(c);
116         for key in &ss {
117             map.insert(&key[..], ());
118         }
119         map
120     });
121 }
122 
123 #[bench]
insert_hashmap_int_bigvalue_10_000(b: &mut Bencher)124 fn insert_hashmap_int_bigvalue_10_000(b: &mut Bencher) {
125     let c = 10_000;
126     let value = [0u64; 10];
127     b.iter(|| {
128         let mut map = HashMap::with_capacity(c);
129         for i in 0..c {
130             map.insert(i, value);
131         }
132         map
133     });
134 }
135 
136 #[bench]
insert_indexmap_int_bigvalue_10_000(b: &mut Bencher)137 fn insert_indexmap_int_bigvalue_10_000(b: &mut Bencher) {
138     let c = 10_000;
139     let value = [0u64; 10];
140     b.iter(|| {
141         let mut map = IndexMap::with_capacity(c);
142         for i in 0..c {
143             map.insert(i, value);
144         }
145         map
146     });
147 }
148 
149 #[bench]
insert_hashmap_100_000(b: &mut Bencher)150 fn insert_hashmap_100_000(b: &mut Bencher) {
151     let c = 100_000;
152     b.iter(|| {
153         let mut map = HashMap::with_capacity(c);
154         for x in 0..c {
155             map.insert(x, ());
156         }
157         map
158     });
159 }
160 
161 #[bench]
insert_indexmap_100_000(b: &mut Bencher)162 fn insert_indexmap_100_000(b: &mut Bencher) {
163     let c = 100_000;
164     b.iter(|| {
165         let mut map = IndexMap::with_capacity(c);
166         for x in 0..c {
167             map.insert(x, ());
168         }
169         map
170     });
171 }
172 
173 #[bench]
insert_hashmap_150(b: &mut Bencher)174 fn insert_hashmap_150(b: &mut Bencher) {
175     let c = 150;
176     b.iter(|| {
177         let mut map = HashMap::with_capacity(c);
178         for x in 0..c {
179             map.insert(x, ());
180         }
181         map
182     });
183 }
184 
185 #[bench]
insert_indexmap_150(b: &mut Bencher)186 fn insert_indexmap_150(b: &mut Bencher) {
187     let c = 150;
188     b.iter(|| {
189         let mut map = IndexMap::with_capacity(c);
190         for x in 0..c {
191             map.insert(x, ());
192         }
193         map
194     });
195 }
196 
197 #[bench]
entry_hashmap_150(b: &mut Bencher)198 fn entry_hashmap_150(b: &mut Bencher) {
199     let c = 150;
200     b.iter(|| {
201         let mut map = HashMap::with_capacity(c);
202         for x in 0..c {
203             map.entry(x).or_insert(());
204         }
205         map
206     });
207 }
208 
209 #[bench]
entry_indexmap_150(b: &mut Bencher)210 fn entry_indexmap_150(b: &mut Bencher) {
211     let c = 150;
212     b.iter(|| {
213         let mut map = IndexMap::with_capacity(c);
214         for x in 0..c {
215             map.entry(x).or_insert(());
216         }
217         map
218     });
219 }
220 
221 #[bench]
iter_sum_hashmap_10_000(b: &mut Bencher)222 fn iter_sum_hashmap_10_000(b: &mut Bencher) {
223     let c = 10_000;
224     let mut map = HashMap::with_capacity(c);
225     let len = c - c / 10;
226     for x in 0..len {
227         map.insert(x, ());
228     }
229     assert_eq!(map.len(), len);
230     b.iter(|| map.keys().sum::<usize>());
231 }
232 
233 #[bench]
iter_sum_indexmap_10_000(b: &mut Bencher)234 fn iter_sum_indexmap_10_000(b: &mut Bencher) {
235     let c = 10_000;
236     let mut map = IndexMap::with_capacity(c);
237     let len = c - c / 10;
238     for x in 0..len {
239         map.insert(x, ());
240     }
241     assert_eq!(map.len(), len);
242     b.iter(|| map.keys().sum::<usize>());
243 }
244 
245 #[bench]
iter_black_box_hashmap_10_000(b: &mut Bencher)246 fn iter_black_box_hashmap_10_000(b: &mut Bencher) {
247     let c = 10_000;
248     let mut map = HashMap::with_capacity(c);
249     let len = c - c / 10;
250     for x in 0..len {
251         map.insert(x, ());
252     }
253     assert_eq!(map.len(), len);
254     b.iter(|| {
255         for &key in map.keys() {
256             black_box(key);
257         }
258     });
259 }
260 
261 #[bench]
iter_black_box_indexmap_10_000(b: &mut Bencher)262 fn iter_black_box_indexmap_10_000(b: &mut Bencher) {
263     let c = 10_000;
264     let mut map = IndexMap::with_capacity(c);
265     let len = c - c / 10;
266     for x in 0..len {
267         map.insert(x, ());
268     }
269     assert_eq!(map.len(), len);
270     b.iter(|| {
271         for &key in map.keys() {
272             black_box(key);
273         }
274     });
275 }
276 
shuffled_keys<I>(iter: I) -> Vec<I::Item> where I: IntoIterator,277 fn shuffled_keys<I>(iter: I) -> Vec<I::Item>
278 where
279     I: IntoIterator,
280 {
281     let mut v = Vec::from_iter(iter);
282     let mut rng = small_rng();
283     v.shuffle(&mut rng);
284     v
285 }
286 
287 #[bench]
lookup_hashmap_10_000_exist(b: &mut Bencher)288 fn lookup_hashmap_10_000_exist(b: &mut Bencher) {
289     let c = 10_000;
290     let mut map = HashMap::with_capacity(c);
291     let keys = shuffled_keys(0..c);
292     for &key in &keys {
293         map.insert(key, 1);
294     }
295     b.iter(|| {
296         let mut found = 0;
297         for key in 5000..c {
298             found += map.get(&key).is_some() as i32;
299         }
300         found
301     });
302 }
303 
304 #[bench]
lookup_hashmap_10_000_noexist(b: &mut Bencher)305 fn lookup_hashmap_10_000_noexist(b: &mut Bencher) {
306     let c = 10_000;
307     let mut map = HashMap::with_capacity(c);
308     let keys = shuffled_keys(0..c);
309     for &key in &keys {
310         map.insert(key, 1);
311     }
312     b.iter(|| {
313         let mut found = 0;
314         for key in c..15000 {
315             found += map.get(&key).is_some() as i32;
316         }
317         found
318     });
319 }
320 
321 #[bench]
lookup_indexmap_10_000_exist(b: &mut Bencher)322 fn lookup_indexmap_10_000_exist(b: &mut Bencher) {
323     let c = 10_000;
324     let mut map = IndexMap::with_capacity(c);
325     let keys = shuffled_keys(0..c);
326     for &key in &keys {
327         map.insert(key, 1);
328     }
329     b.iter(|| {
330         let mut found = 0;
331         for key in 5000..c {
332             found += map.get(&key).is_some() as i32;
333         }
334         found
335     });
336 }
337 
338 #[bench]
lookup_indexmap_10_000_noexist(b: &mut Bencher)339 fn lookup_indexmap_10_000_noexist(b: &mut Bencher) {
340     let c = 10_000;
341     let mut map = IndexMap::with_capacity(c);
342     let keys = shuffled_keys(0..c);
343     for &key in &keys {
344         map.insert(key, 1);
345     }
346     b.iter(|| {
347         let mut found = 0;
348         for key in c..15000 {
349             found += map.get(&key).is_some() as i32;
350         }
351         found
352     });
353 }
354 
355 // number of items to look up
356 const LOOKUP_MAP_SIZE: u32 = 100_000_u32;
357 const LOOKUP_SAMPLE_SIZE: u32 = 5000;
358 const SORT_MAP_SIZE: usize = 10_000;
359 
360 // use lazy_static so that comparison benchmarks use the exact same inputs
361 lazy_static! {
362     static ref KEYS: Vec<u32> = shuffled_keys(0..LOOKUP_MAP_SIZE);
363 }
364 
365 lazy_static! {
366     static ref HMAP_100K: HashMap<u32, u32> = {
367         let c = LOOKUP_MAP_SIZE;
368         let mut map = HashMap::with_capacity(c as usize);
369         let keys = &*KEYS;
370         for &key in keys {
371             map.insert(key, key);
372         }
373         map
374     };
375 }
376 
377 lazy_static! {
378     static ref IMAP_100K: IndexMap<u32, u32> = {
379         let c = LOOKUP_MAP_SIZE;
380         let mut map = IndexMap::with_capacity(c as usize);
381         let keys = &*KEYS;
382         for &key in keys {
383             map.insert(key, key);
384         }
385         map
386     };
387 }
388 
389 lazy_static! {
390     static ref IMAP_SORT_U32: IndexMap<u32, u32> = {
391         let mut map = IndexMap::with_capacity(SORT_MAP_SIZE);
392         for &key in &KEYS[..SORT_MAP_SIZE] {
393             map.insert(key, key);
394         }
395         map
396     };
397 }
398 lazy_static! {
399     static ref IMAP_SORT_S: IndexMap<String, String> = {
400         let mut map = IndexMap::with_capacity(SORT_MAP_SIZE);
401         for &key in &KEYS[..SORT_MAP_SIZE] {
402             map.insert(format!("{:^16x}", &key), String::new());
403         }
404         map
405     };
406 }
407 
408 #[bench]
lookup_hashmap_100_000_multi(b: &mut Bencher)409 fn lookup_hashmap_100_000_multi(b: &mut Bencher) {
410     let map = &*HMAP_100K;
411     b.iter(|| {
412         let mut found = 0;
413         for key in 0..LOOKUP_SAMPLE_SIZE {
414             found += map.get(&key).is_some() as u32;
415         }
416         found
417     });
418 }
419 
420 #[bench]
lookup_indexmap_100_000_multi(b: &mut Bencher)421 fn lookup_indexmap_100_000_multi(b: &mut Bencher) {
422     let map = &*IMAP_100K;
423     b.iter(|| {
424         let mut found = 0;
425         for key in 0..LOOKUP_SAMPLE_SIZE {
426             found += map.get(&key).is_some() as u32;
427         }
428         found
429     });
430 }
431 
432 // inorder: Test looking up keys in the same order as they were inserted
433 #[bench]
lookup_hashmap_100_000_inorder_multi(b: &mut Bencher)434 fn lookup_hashmap_100_000_inorder_multi(b: &mut Bencher) {
435     let map = &*HMAP_100K;
436     let keys = &*KEYS;
437     b.iter(|| {
438         let mut found = 0;
439         for key in &keys[0..LOOKUP_SAMPLE_SIZE as usize] {
440             found += map.get(key).is_some() as u32;
441         }
442         found
443     });
444 }
445 
446 #[bench]
lookup_indexmap_100_000_inorder_multi(b: &mut Bencher)447 fn lookup_indexmap_100_000_inorder_multi(b: &mut Bencher) {
448     let map = &*IMAP_100K;
449     let keys = &*KEYS;
450     b.iter(|| {
451         let mut found = 0;
452         for key in &keys[0..LOOKUP_SAMPLE_SIZE as usize] {
453             found += map.get(key).is_some() as u32;
454         }
455         found
456     });
457 }
458 
459 #[bench]
lookup_hashmap_100_000_single(b: &mut Bencher)460 fn lookup_hashmap_100_000_single(b: &mut Bencher) {
461     let map = &*HMAP_100K;
462     let mut iter = (0..LOOKUP_MAP_SIZE + LOOKUP_SAMPLE_SIZE).cycle();
463     b.iter(|| {
464         let key = iter.next().unwrap();
465         map.get(&key).is_some()
466     });
467 }
468 
469 #[bench]
lookup_indexmap_100_000_single(b: &mut Bencher)470 fn lookup_indexmap_100_000_single(b: &mut Bencher) {
471     let map = &*IMAP_100K;
472     let mut iter = (0..LOOKUP_MAP_SIZE + LOOKUP_SAMPLE_SIZE).cycle();
473     b.iter(|| {
474         let key = iter.next().unwrap();
475         map.get(&key).is_some()
476     });
477 }
478 
479 const GROW_SIZE: usize = 100_000;
480 type GrowKey = u32;
481 
482 // Test grow/resize without preallocation
483 #[bench]
grow_fnv_hashmap_100_000(b: &mut Bencher)484 fn grow_fnv_hashmap_100_000(b: &mut Bencher) {
485     b.iter(|| {
486         let mut map: HashMap<_, _, FnvBuilder> = HashMap::default();
487         for x in 0..GROW_SIZE {
488             map.insert(x as GrowKey, x as GrowKey);
489         }
490         map
491     });
492 }
493 
494 #[bench]
grow_fnv_indexmap_100_000(b: &mut Bencher)495 fn grow_fnv_indexmap_100_000(b: &mut Bencher) {
496     b.iter(|| {
497         let mut map: IndexMap<_, _, FnvBuilder> = IndexMap::default();
498         for x in 0..GROW_SIZE {
499             map.insert(x as GrowKey, x as GrowKey);
500         }
501         map
502     });
503 }
504 
505 const MERGE: u64 = 10_000;
506 #[bench]
hashmap_merge_simple(b: &mut Bencher)507 fn hashmap_merge_simple(b: &mut Bencher) {
508     let first_map: HashMap<u64, _> = (0..MERGE).map(|i| (i, ())).collect();
509     let second_map: HashMap<u64, _> = (MERGE..MERGE * 2).map(|i| (i, ())).collect();
510     b.iter(|| {
511         let mut merged = first_map.clone();
512         merged.extend(second_map.iter().map(|(&k, &v)| (k, v)));
513         merged
514     });
515 }
516 
517 #[bench]
hashmap_merge_shuffle(b: &mut Bencher)518 fn hashmap_merge_shuffle(b: &mut Bencher) {
519     let first_map: HashMap<u64, _> = (0..MERGE).map(|i| (i, ())).collect();
520     let second_map: HashMap<u64, _> = (MERGE..MERGE * 2).map(|i| (i, ())).collect();
521     let mut v = Vec::new();
522     let mut rng = small_rng();
523     b.iter(|| {
524         let mut merged = first_map.clone();
525         v.extend(second_map.iter().map(|(&k, &v)| (k, v)));
526         v.shuffle(&mut rng);
527         merged.extend(v.drain(..));
528 
529         merged
530     });
531 }
532 
533 #[bench]
indexmap_merge_simple(b: &mut Bencher)534 fn indexmap_merge_simple(b: &mut Bencher) {
535     let first_map: IndexMap<u64, _> = (0..MERGE).map(|i| (i, ())).collect();
536     let second_map: IndexMap<u64, _> = (MERGE..MERGE * 2).map(|i| (i, ())).collect();
537     b.iter(|| {
538         let mut merged = first_map.clone();
539         merged.extend(second_map.iter().map(|(&k, &v)| (k, v)));
540         merged
541     });
542 }
543 
544 #[bench]
indexmap_merge_shuffle(b: &mut Bencher)545 fn indexmap_merge_shuffle(b: &mut Bencher) {
546     let first_map: IndexMap<u64, _> = (0..MERGE).map(|i| (i, ())).collect();
547     let second_map: IndexMap<u64, _> = (MERGE..MERGE * 2).map(|i| (i, ())).collect();
548     let mut v = Vec::new();
549     let mut rng = small_rng();
550     b.iter(|| {
551         let mut merged = first_map.clone();
552         v.extend(second_map.iter().map(|(&k, &v)| (k, v)));
553         v.shuffle(&mut rng);
554         merged.extend(v.drain(..));
555 
556         merged
557     });
558 }
559 
560 #[bench]
swap_remove_indexmap_100_000(b: &mut Bencher)561 fn swap_remove_indexmap_100_000(b: &mut Bencher) {
562     let map = IMAP_100K.clone();
563     let mut keys = Vec::from_iter(map.keys().copied());
564     let mut rng = small_rng();
565     keys.shuffle(&mut rng);
566 
567     b.iter(|| {
568         let mut map = map.clone();
569         for key in &keys {
570             map.swap_remove(key);
571         }
572         assert_eq!(map.len(), 0);
573         map
574     });
575 }
576 
577 #[bench]
shift_remove_indexmap_100_000_few(b: &mut Bencher)578 fn shift_remove_indexmap_100_000_few(b: &mut Bencher) {
579     let map = IMAP_100K.clone();
580     let mut keys = Vec::from_iter(map.keys().copied());
581     let mut rng = small_rng();
582     keys.shuffle(&mut rng);
583     keys.truncate(50);
584 
585     b.iter(|| {
586         let mut map = map.clone();
587         for key in &keys {
588             map.shift_remove(key);
589         }
590         assert_eq!(map.len(), IMAP_100K.len() - keys.len());
591         map
592     });
593 }
594 
595 #[bench]
shift_remove_indexmap_2_000_full(b: &mut Bencher)596 fn shift_remove_indexmap_2_000_full(b: &mut Bencher) {
597     let mut keys = KEYS[..2_000].to_vec();
598     let mut map = IndexMap::with_capacity(keys.len());
599     for &key in &keys {
600         map.insert(key, key);
601     }
602     let mut rng = small_rng();
603     keys.shuffle(&mut rng);
604 
605     b.iter(|| {
606         let mut map = map.clone();
607         for key in &keys {
608             map.shift_remove(key);
609         }
610         assert_eq!(map.len(), 0);
611         map
612     });
613 }
614 
615 #[bench]
pop_indexmap_100_000(b: &mut Bencher)616 fn pop_indexmap_100_000(b: &mut Bencher) {
617     let map = IMAP_100K.clone();
618 
619     b.iter(|| {
620         let mut map = map.clone();
621         while !map.is_empty() {
622             map.pop();
623         }
624         assert_eq!(map.len(), 0);
625         map
626     });
627 }
628 
629 #[bench]
few_retain_indexmap_100_000(b: &mut Bencher)630 fn few_retain_indexmap_100_000(b: &mut Bencher) {
631     let map = IMAP_100K.clone();
632 
633     b.iter(|| {
634         let mut map = map.clone();
635         map.retain(|k, _| *k % 7 == 0);
636         map
637     });
638 }
639 
640 #[bench]
few_retain_hashmap_100_000(b: &mut Bencher)641 fn few_retain_hashmap_100_000(b: &mut Bencher) {
642     let map = HMAP_100K.clone();
643 
644     b.iter(|| {
645         let mut map = map.clone();
646         map.retain(|k, _| *k % 7 == 0);
647         map
648     });
649 }
650 
651 #[bench]
half_retain_indexmap_100_000(b: &mut Bencher)652 fn half_retain_indexmap_100_000(b: &mut Bencher) {
653     let map = IMAP_100K.clone();
654 
655     b.iter(|| {
656         let mut map = map.clone();
657         map.retain(|k, _| *k % 2 == 0);
658         map
659     });
660 }
661 
662 #[bench]
half_retain_hashmap_100_000(b: &mut Bencher)663 fn half_retain_hashmap_100_000(b: &mut Bencher) {
664     let map = HMAP_100K.clone();
665 
666     b.iter(|| {
667         let mut map = map.clone();
668         map.retain(|k, _| *k % 2 == 0);
669         map
670     });
671 }
672 
673 #[bench]
many_retain_indexmap_100_000(b: &mut Bencher)674 fn many_retain_indexmap_100_000(b: &mut Bencher) {
675     let map = IMAP_100K.clone();
676 
677     b.iter(|| {
678         let mut map = map.clone();
679         map.retain(|k, _| *k % 100 != 0);
680         map
681     });
682 }
683 
684 #[bench]
many_retain_hashmap_100_000(b: &mut Bencher)685 fn many_retain_hashmap_100_000(b: &mut Bencher) {
686     let map = HMAP_100K.clone();
687 
688     b.iter(|| {
689         let mut map = map.clone();
690         map.retain(|k, _| *k % 100 != 0);
691         map
692     });
693 }
694 
695 // simple sort impl for comparison
simple_sort<K: Ord + Hash, V>(m: &mut IndexMap<K, V>)696 pub fn simple_sort<K: Ord + Hash, V>(m: &mut IndexMap<K, V>) {
697     let mut ordered: Vec<_> = m.drain(..).collect();
698     ordered.sort_by(|left, right| left.0.cmp(&right.0));
699     m.extend(ordered);
700 }
701 
702 #[bench]
indexmap_sort_s(b: &mut Bencher)703 fn indexmap_sort_s(b: &mut Bencher) {
704     let map = IMAP_SORT_S.clone();
705 
706     // there's a map clone there, but it's still useful to profile this
707     b.iter(|| {
708         let mut map = map.clone();
709         map.sort_keys();
710         map
711     });
712 }
713 
714 #[bench]
indexmap_simple_sort_s(b: &mut Bencher)715 fn indexmap_simple_sort_s(b: &mut Bencher) {
716     let map = IMAP_SORT_S.clone();
717 
718     // there's a map clone there, but it's still useful to profile this
719     b.iter(|| {
720         let mut map = map.clone();
721         simple_sort(&mut map);
722         map
723     });
724 }
725 
726 #[bench]
indexmap_sort_u32(b: &mut Bencher)727 fn indexmap_sort_u32(b: &mut Bencher) {
728     let map = IMAP_SORT_U32.clone();
729 
730     // there's a map clone there, but it's still useful to profile this
731     b.iter(|| {
732         let mut map = map.clone();
733         map.sort_keys();
734         map
735     });
736 }
737 
738 #[bench]
indexmap_simple_sort_u32(b: &mut Bencher)739 fn indexmap_simple_sort_u32(b: &mut Bencher) {
740     let map = IMAP_SORT_U32.clone();
741 
742     // there's a map clone there, but it's still useful to profile this
743     b.iter(|| {
744         let mut map = map.clone();
745         simple_sort(&mut map);
746         map
747     });
748 }
749 
750 // measure the fixed overhead of cloning in sort benchmarks
751 #[bench]
indexmap_clone_for_sort_s(b: &mut Bencher)752 fn indexmap_clone_for_sort_s(b: &mut Bencher) {
753     let map = IMAP_SORT_S.clone();
754 
755     b.iter(|| map.clone());
756 }
757 
758 #[bench]
indexmap_clone_for_sort_u32(b: &mut Bencher)759 fn indexmap_clone_for_sort_u32(b: &mut Bencher) {
760     let map = IMAP_SORT_U32.clone();
761 
762     b.iter(|| map.clone());
763 }
764