1 files changed, 86 insertions, 15 deletions

diff --git a/benches/bench.rs b/benches/bench.rs
index 771e716..568c513 100644
--- a/benches/bench.rs
+++ b/benches/bench.rs
@@ -9,8 +9,11 @@ extern crate test;
 use test::{black_box, Bencher};
 
 use hashbrown::hash_map::DefaultHashBuilder;
-use hashbrown::HashMap;
-use std::collections::hash_map::RandomState;
+use hashbrown::{HashMap, HashSet};
+use std::{
+    collections::hash_map::RandomState,
+    sync::atomic::{self, AtomicUsize},
+};
 
 const SIZE: usize = 1000;
 
@@ -40,6 +43,20 @@ impl Iterator for RandomKeys {
     }
 }
 
+// Just an arbitrary side effect to make the maps not shortcircuit to the non-dropping path
+// when dropping maps/entries (most real world usages likely have drop in the key or value)
+lazy_static::lazy_static! {
+    static ref SIDE_EFFECT: AtomicUsize = AtomicUsize::new(0);
+}
+
+#[derive(Clone)]
+struct DropType(usize);
+impl Drop for DropType {
+    fn drop(&mut self) {
+        SIDE_EFFECT.fetch_add(self.0, atomic::Ordering::SeqCst);
+    }
+}
+
 macro_rules! bench_suite {
     ($bench_macro:ident, $bench_ahash_serial:ident, $bench_std_serial:ident,
      $bench_ahash_highbits:ident, $bench_std_highbits:ident,
@@ -69,10 +86,11 @@ macro_rules! bench_insert {
             b.iter(|| {
                 m.clear();
                 for i in ($keydist).take(SIZE) {
-                    m.insert(i, i);
+                    m.insert(i, (DropType(i), [i; 20]));
                 }
                 black_box(&mut m);
-            })
+            });
+            eprintln!("{}", SIDE_EFFECT.load(atomic::Ordering::SeqCst));
         }
     };
 }
@@ -87,13 +105,38 @@ bench_suite!(
     insert_std_random
 );
 
+macro_rules! bench_grow_insert {
+    ($name:ident, $maptype:ident, $keydist:expr) => {
+        #[bench]
+        fn $name(b: &mut Bencher) {
+            b.iter(|| {
+                let mut m = $maptype::default();
+                for i in ($keydist).take(SIZE) {
+                    m.insert(i, DropType(i));
+                }
+                black_box(&mut m);
+            })
+        }
+    };
+}
+
+bench_suite!(
+    bench_grow_insert,
+    grow_insert_ahash_serial,
+    grow_insert_std_serial,
+    grow_insert_ahash_highbits,
+    grow_insert_std_highbits,
+    grow_insert_ahash_random,
+    grow_insert_std_random
+);
+
 macro_rules! bench_insert_erase {
     ($name:ident, $maptype:ident, $keydist:expr) => {
         #[bench]
         fn $name(b: &mut Bencher) {
             let mut base = $maptype::default();
             for i in ($keydist).take(SIZE) {
-                base.insert(i, i);
+                base.insert(i, DropType(i));
             }
             let skip = $keydist.skip(SIZE);
             b.iter(|| {
@@ -103,11 +146,12 @@ macro_rules! bench_insert_erase {
                 // While keeping the size constant,
                 // replace the first keydist with the second.
                 for (add, remove) in (&mut add_iter).zip(&mut remove_iter).take(SIZE) {
-                    m.insert(add, add);
+                    m.insert(add, DropType(add));
                     black_box(m.remove(&remove));
                 }
                 black_box(m);
-            })
+            });
+            eprintln!("{}", SIDE_EFFECT.load(atomic::Ordering::SeqCst));
         }
     };
 }
@@ -128,14 +172,15 @@ macro_rules! bench_lookup {
         fn $name(b: &mut Bencher) {
             let mut m = $maptype::default();
             for i in $keydist.take(SIZE) {
-                m.insert(i, i);
+                m.insert(i, DropType(i));
             }
 
             b.iter(|| {
                 for i in $keydist.take(SIZE) {
                     black_box(m.get(&i));
                 }
-            })
+            });
+            eprintln!("{}", SIDE_EFFECT.load(atomic::Ordering::SeqCst));
         }
     };
 }
@@ -157,7 +202,7 @@ macro_rules! bench_lookup_fail {
             let mut m = $maptype::default();
             let mut iter = $keydist;
             for i in (&mut iter).take(SIZE) {
-                m.insert(i, i);
+                m.insert(i, DropType(i));
             }
 
             b.iter(|| {
@@ -185,7 +230,7 @@ macro_rules! bench_iter {
         fn $name(b: &mut Bencher) {
             let mut m = $maptype::default();
             for i in ($keydist).take(SIZE) {
-                m.insert(i, i);
+                m.insert(i, DropType(i));
             }
 
             b.iter(|| {
@@ -211,7 +256,7 @@ bench_suite!(
 fn clone_small(b: &mut Bencher) {
     let mut m = HashMap::new();
     for i in 0..10 {
-        m.insert(i, i);
+        m.insert(i, DropType(i));
     }
 
     b.iter(|| {
@@ -224,7 +269,7 @@ fn clone_from_small(b: &mut Bencher) {
     let mut m = HashMap::new();
     let mut m2 = HashMap::new();
     for i in 0..10 {
-        m.insert(i, i);
+        m.insert(i, DropType(i));
     }
 
     b.iter(|| {
@@ -237,7 +282,7 @@ fn clone_from_small(b: &mut Bencher) {
 fn clone_large(b: &mut Bencher) {
     let mut m = HashMap::new();
     for i in 0..1000 {
-        m.insert(i, i);
+        m.insert(i, DropType(i));
     }
 
     b.iter(|| {
@@ -250,7 +295,7 @@ fn clone_from_large(b: &mut Bencher) {
     let mut m = HashMap::new();
     let mut m2 = HashMap::new();
     for i in 0..1000 {
-        m.insert(i, i);
+        m.insert(i, DropType(i));
     }
 
     b.iter(|| {
@@ -258,3 +303,29 @@ fn clone_from_large(b: &mut Bencher) {
         black_box(&mut m2);
     })
 }
+
+#[bench]
+fn rehash_in_place(b: &mut Bencher) {
+    b.iter(|| {
+        let mut set = HashSet::new();
+
+        // Each loop triggers one rehash
+        for _ in 0..10 {
+            for i in 0..224 {
+                set.insert(i);
+            }
+
+            assert_eq!(
+                set.capacity(),
+                224,
+                "The set must be at or close to capacity to trigger a re hashing"
+            );
+
+            for i in 100..1400 {
+                set.remove(&(i - 100));
+                set.insert(i);
+            }
+            set.clear();
+        }
+    });
+}