More benchmarks of BTreeMap mutation

2 files changed, 332 insertions, 22 deletions

diff --git a/library/alloc/benches/btree/map.rs b/library/alloc/benches/btree/map.rs
index 38d19c59ad1..7c2e5694a62 100644
--- a/library/alloc/benches/btree/map.rs
+++ b/library/alloc/benches/btree/map.rs
@@ -282,3 +282,305 @@ pub fn iter_10k(b: &mut Bencher) {
 pub fn iter_1m(b: &mut Bencher) {
     bench_iter(b, 1_000, 1_000_000);
 }
+
+const FAT: usize = 256;
+
+// The returned map has small keys and values.
+// Benchmarks on it have a counterpart in set.rs with the same keys and no values at all.
+fn slim_map(n: usize) -> BTreeMap<usize, usize> {
+    (0..n).map(|i| (i, i)).collect::<BTreeMap<_, _>>()
+}
+
+// The returned map has small keys and large values.
+fn fat_val_map(n: usize) -> BTreeMap<usize, [usize; FAT]> {
+    (0..n).map(|i| (i, [i; FAT])).collect::<BTreeMap<_, _>>()
+}
+
+// The returned map has large keys and values.
+fn fat_map(n: usize) -> BTreeMap<[usize; FAT], [usize; FAT]> {
+    (0..n).map(|i| ([i; FAT], [i; FAT])).collect::<BTreeMap<_, _>>()
+}
+
+#[bench]
+pub fn clone_slim_100(b: &mut Bencher) {
+    let src = slim_map(100);
+    b.iter(|| src.clone())
+}
+
+#[bench]
+pub fn clone_slim_100_and_clear(b: &mut Bencher) {
+    let src = slim_map(100);
+    b.iter(|| src.clone().clear())
+}
+
+#[bench]
+pub fn clone_slim_100_and_drain_all(b: &mut Bencher) {
+    let src = slim_map(100);
+    b.iter(|| src.clone().drain_filter(|_, _| true).count())
+}
+
+#[bench]
+pub fn clone_slim_100_and_drain_half(b: &mut Bencher) {
+    let src = slim_map(100);
+    b.iter(|| {
+        let mut map = src.clone();
+        assert_eq!(map.drain_filter(|i, _| i % 2 == 0).count(), 100 / 2);
+        assert_eq!(map.len(), 100 / 2);
+    })
+}
+
+#[bench]
+pub fn clone_slim_100_and_into_iter(b: &mut Bencher) {
+    let src = slim_map(100);
+    b.iter(|| src.clone().into_iter().count())
+}
+
+#[bench]
+pub fn clone_slim_100_and_pop_all(b: &mut Bencher) {
+    let src = slim_map(100);
+    b.iter(|| {
+        let mut map = src.clone();
+        while map.pop_first().is_some() {}
+        map
+    });
+}
+
+#[bench]
+pub fn clone_slim_100_and_remove_all(b: &mut Bencher) {
+    let src = slim_map(100);
+    b.iter(|| {
+        let mut map = src.clone();
+        while let Some(elt) = map.iter().map(|(&i, _)| i).next() {
+            let v = map.remove(&elt);
+            debug_assert!(v.is_some());
+        }
+        map
+    });
+}
+
+#[bench]
+pub fn clone_slim_100_and_remove_half(b: &mut Bencher) {
+    let src = slim_map(100);
+    b.iter(|| {
+        let mut map = src.clone();
+        for i in (0..100).step_by(2) {
+            let v = map.remove(&i);
+            debug_assert!(v.is_some());
+        }
+        assert_eq!(map.len(), 100 / 2);
+        map
+    })
+}
+
+#[bench]
+pub fn clone_slim_10k(b: &mut Bencher) {
+    let src = slim_map(10_000);
+    b.iter(|| src.clone())
+}
+
+#[bench]
+pub fn clone_slim_10k_and_clear(b: &mut Bencher) {
+    let src = slim_map(10_000);
+    b.iter(|| src.clone().clear())
+}
+
+#[bench]
+pub fn clone_slim_10k_and_drain_all(b: &mut Bencher) {
+    let src = slim_map(10_000);
+    b.iter(|| src.clone().drain_filter(|_, _| true).count())
+}
+
+#[bench]
+pub fn clone_slim_10k_and_drain_half(b: &mut Bencher) {
+    let src = slim_map(10_000);
+    b.iter(|| {
+        let mut map = src.clone();
+        assert_eq!(map.drain_filter(|i, _| i % 2 == 0).count(), 10_000 / 2);
+        assert_eq!(map.len(), 10_000 / 2);
+    })
+}
+
+#[bench]
+pub fn clone_slim_10k_and_into_iter(b: &mut Bencher) {
+    let src = slim_map(10_000);
+    b.iter(|| src.clone().into_iter().count())
+}
+
+#[bench]
+pub fn clone_slim_10k_and_pop_all(b: &mut Bencher) {
+    let src = slim_map(10_000);
+    b.iter(|| {
+        let mut map = src.clone();
+        while map.pop_first().is_some() {}
+        map
+    });
+}
+
+#[bench]
+pub fn clone_slim_10k_and_remove_all(b: &mut Bencher) {
+    let src = slim_map(10_000);
+    b.iter(|| {
+        let mut map = src.clone();
+        while let Some(elt) = map.iter().map(|(&i, _)| i).next() {
+            let v = map.remove(&elt);
+            debug_assert!(v.is_some());
+        }
+        map
+    });
+}
+
+#[bench]
+pub fn clone_slim_10k_and_remove_half(b: &mut Bencher) {
+    let src = slim_map(10_000);
+    b.iter(|| {
+        let mut map = src.clone();
+        for i in (0..10_000).step_by(2) {
+            let v = map.remove(&i);
+            debug_assert!(v.is_some());
+        }
+        assert_eq!(map.len(), 10_000 / 2);
+        map
+    })
+}
+
+#[bench]
+pub fn clone_fat_val_100(b: &mut Bencher) {
+    let src = fat_val_map(100);
+    b.iter(|| src.clone())
+}
+
+#[bench]
+pub fn clone_fat_val_100_and_clear(b: &mut Bencher) {
+    let src = fat_val_map(100);
+    b.iter(|| src.clone().clear())
+}
+
+#[bench]
+pub fn clone_fat_val_100_and_drain_all(b: &mut Bencher) {
+    let src = fat_val_map(100);
+    b.iter(|| src.clone().drain_filter(|_, _| true).count())
+}
+
+#[bench]
+pub fn clone_fat_val_100_and_drain_half(b: &mut Bencher) {
+    let src = fat_val_map(100);
+    b.iter(|| {
+        let mut map = src.clone();
+        assert_eq!(map.drain_filter(|i, _| i % 2 == 0).count(), 100 / 2);
+        assert_eq!(map.len(), 100 / 2);
+    })
+}
+
+#[bench]
+pub fn clone_fat_val_100_and_into_iter(b: &mut Bencher) {
+    let src = fat_val_map(100);
+    b.iter(|| src.clone().into_iter().count())
+}
+
+#[bench]
+pub fn clone_fat_val_100_and_pop_all(b: &mut Bencher) {
+    let src = fat_val_map(100);
+    b.iter(|| {
+        let mut map = src.clone();
+        while map.pop_first().is_some() {}
+        map
+    });
+}
+
+#[bench]
+pub fn clone_fat_val_100_and_remove_all(b: &mut Bencher) {
+    let src = fat_val_map(100);
+    b.iter(|| {
+        let mut map = src.clone();
+        while let Some(elt) = map.iter().map(|(&i, _)| i).next() {
+            let v = map.remove(&elt);
+            debug_assert!(v.is_some());
+        }
+        map
+    });
+}
+
+#[bench]
+pub fn clone_fat_val_100_and_remove_half(b: &mut Bencher) {
+    let src = fat_val_map(100);
+    b.iter(|| {
+        let mut map = src.clone();
+        for i in (0..100).step_by(2) {
+            let v = map.remove(&i);
+            debug_assert!(v.is_some());
+        }
+        assert_eq!(map.len(), 100 / 2);
+        map
+    })
+}
+
+#[bench]
+pub fn clone_fat_100(b: &mut Bencher) {
+    let src = fat_map(100);
+    b.iter(|| src.clone())
+}
+
+#[bench]
+pub fn clone_fat_100_and_clear(b: &mut Bencher) {
+    let src = fat_map(100);
+    b.iter(|| src.clone().clear())
+}
+
+#[bench]
+pub fn clone_fat_100_and_drain_all(b: &mut Bencher) {
+    let src = fat_map(100);
+    b.iter(|| src.clone().drain_filter(|_, _| true).count())
+}
+
+#[bench]
+pub fn clone_fat_100_and_drain_half(b: &mut Bencher) {
+    let src = fat_map(100);
+    b.iter(|| {
+        let mut map = src.clone();
+        assert_eq!(map.drain_filter(|i, _| i[0] % 2 == 0).count(), 100 / 2);
+        assert_eq!(map.len(), 100 / 2);
+    })
+}
+
+#[bench]
+pub fn clone_fat_100_and_into_iter(b: &mut Bencher) {
+    let src = fat_map(100);
+    b.iter(|| src.clone().into_iter().count())
+}
+
+#[bench]
+pub fn clone_fat_100_and_pop_all(b: &mut Bencher) {
+    let src = fat_map(100);
+    b.iter(|| {
+        let mut map = src.clone();
+        while map.pop_first().is_some() {}
+        map
+    });
+}
+
+#[bench]
+pub fn clone_fat_100_and_remove_all(b: &mut Bencher) {
+    let src = fat_map(100);
+    b.iter(|| {
+        let mut map = src.clone();
+        while let Some(elt) = map.iter().map(|(&i, _)| i).next() {
+            let v = map.remove(&elt);
+            debug_assert!(v.is_some());
+        }
+        map
+    });
+}
+
+#[bench]
+pub fn clone_fat_100_and_remove_half(b: &mut Bencher) {
+    let src = fat_map(100);
+    b.iter(|| {
+        let mut map = src.clone();
+        for i in (0..100).step_by(2) {
+            let v = map.remove(&[i; FAT]);
+            debug_assert!(v.is_some());
+        }
+        assert_eq!(map.len(), 100 / 2);
+        map
+    })
+}
diff --git a/library/alloc/benches/btree/set.rs b/library/alloc/benches/btree/set.rs
index 2518506b9b5..07bf5093727 100644
--- a/library/alloc/benches/btree/set.rs
+++ b/library/alloc/benches/btree/set.rs
@@ -50,27 +50,31 @@ macro_rules! set_bench {
     };
 }
 
+fn slim_set(n: usize) -> BTreeSet<usize> {
+    (0..n).collect::<BTreeSet<_>>()
+}
+
 #[bench]
 pub fn clone_100(b: &mut Bencher) {
-    let src = pos(100);
+    let src = slim_set(100);
     b.iter(|| src.clone())
 }
 
 #[bench]
 pub fn clone_100_and_clear(b: &mut Bencher) {
-    let src = pos(100);
+    let src = slim_set(100);
     b.iter(|| src.clone().clear())
 }
 
 #[bench]
 pub fn clone_100_and_drain_all(b: &mut Bencher) {
-    let src = pos(100);
+    let src = slim_set(100);
     b.iter(|| src.clone().drain_filter(|_| true).count())
 }
 
 #[bench]
 pub fn clone_100_and_drain_half(b: &mut Bencher) {
-    let src = pos(100);
+    let src = slim_set(100);
     b.iter(|| {
         let mut set = src.clone();
         assert_eq!(set.drain_filter(|i| i % 2 == 0).count(), 100 / 2);
@@ -80,13 +84,13 @@ pub fn clone_100_and_drain_half(b: &mut Bencher) {
 
 #[bench]
 pub fn clone_100_and_into_iter(b: &mut Bencher) {
-    let src = pos(100);
+    let src = slim_set(100);
     b.iter(|| src.clone().into_iter().count())
 }
 
 #[bench]
 pub fn clone_100_and_pop_all(b: &mut Bencher) {
-    let src = pos(100);
+    let src = slim_set(100);
     b.iter(|| {
         let mut set = src.clone();
         while set.pop_first().is_some() {}
@@ -96,11 +100,12 @@ pub fn clone_100_and_pop_all(b: &mut Bencher) {
 
 #[bench]
 pub fn clone_100_and_remove_all(b: &mut Bencher) {
-    let src = pos(100);
+    let src = slim_set(100);
     b.iter(|| {
         let mut set = src.clone();
         while let Some(elt) = set.iter().copied().next() {
-            set.remove(&elt);
+            let ok = set.remove(&elt);
+            debug_assert!(ok);
         }
         set
     });
@@ -108,11 +113,12 @@ pub fn clone_100_and_remove_all(b: &mut Bencher) {
 
 #[bench]
 pub fn clone_100_and_remove_half(b: &mut Bencher) {
-    let src = pos(100);
+    let src = slim_set(100);
     b.iter(|| {
         let mut set = src.clone();
-        for i in (2..=100 as i32).step_by(2) {
-            set.remove(&i);
+        for i in (0..100).step_by(2) {
+            let ok = set.remove(&i);
+            debug_assert!(ok);
         }
         assert_eq!(set.len(), 100 / 2);
         set
@@ -121,25 +127,25 @@ pub fn clone_100_and_remove_half(b: &mut Bencher) {
 
 #[bench]
 pub fn clone_10k(b: &mut Bencher) {
-    let src = pos(10_000);
+    let src = slim_set(10_000);
     b.iter(|| src.clone())
 }
 
 #[bench]
 pub fn clone_10k_and_clear(b: &mut Bencher) {
-    let src = pos(10_000);
+    let src = slim_set(10_000);
     b.iter(|| src.clone().clear())
 }
 
 #[bench]
 pub fn clone_10k_and_drain_all(b: &mut Bencher) {
-    let src = pos(10_000);
+    let src = slim_set(10_000);
     b.iter(|| src.clone().drain_filter(|_| true).count())
 }
 
 #[bench]
 pub fn clone_10k_and_drain_half(b: &mut Bencher) {
-    let src = pos(10_000);
+    let src = slim_set(10_000);
     b.iter(|| {
         let mut set = src.clone();
         assert_eq!(set.drain_filter(|i| i % 2 == 0).count(), 10_000 / 2);
@@ -149,13 +155,13 @@ pub fn clone_10k_and_drain_half(b: &mut Bencher) {
 
 #[bench]
 pub fn clone_10k_and_into_iter(b: &mut Bencher) {
-    let src = pos(10_000);
+    let src = slim_set(10_000);
     b.iter(|| src.clone().into_iter().count())
 }
 
 #[bench]
 pub fn clone_10k_and_pop_all(b: &mut Bencher) {
-    let src = pos(10_000);
+    let src = slim_set(10_000);
     b.iter(|| {
         let mut set = src.clone();
         while set.pop_first().is_some() {}
@@ -165,11 +171,12 @@ pub fn clone_10k_and_pop_all(b: &mut Bencher) {
 
 #[bench]
 pub fn clone_10k_and_remove_all(b: &mut Bencher) {
-    let src = pos(10_000);
+    let src = slim_set(10_000);
     b.iter(|| {
         let mut set = src.clone();
         while let Some(elt) = set.iter().copied().next() {
-            set.remove(&elt);
+            let ok = set.remove(&elt);
+            debug_assert!(ok);
         }
         set
     });
@@ -177,11 +184,12 @@ pub fn clone_10k_and_remove_all(b: &mut Bencher) {
 
 #[bench]
 pub fn clone_10k_and_remove_half(b: &mut Bencher) {
-    let src = pos(10_000);
+    let src = slim_set(10_000);
     b.iter(|| {
         let mut set = src.clone();
-        for i in (2..=10_000 as i32).step_by(2) {
-            set.remove(&i);
+        for i in (0..10_000).step_by(2) {
+            let ok = set.remove(&i);
+            debug_assert!(ok);
         }
         assert_eq!(set.len(), 10_000 / 2);
         set