Performance puzzle BtreeMap clone

[geebee22]

I have a test that clones a BTreeMap which looks like this:

const REP: usize = if cfg!(miri) { 2 } else { 100 };
const N: usize = if cfg!(miri) { 100 } else { 100000 };
#[test]
fn std_clone_test() {
    let mut m = std::collections::BTreeMap::<usize, usize>::new();
    let mut c = m.lower_bound_mut(Bound::Unbounded);
    let n = N;
    for i in 0..n {
        c.insert_before(i, i).unwrap();
    }
    assert!(m.len() == n);
    print_memory();

    for _rep in 0..REP {
        let cm = m.clone();
        assert!(cm.len() == n);
    }
}

This takes 0.24 seconds to run. However my implementation takes only 0.03 seconds, that is 8 times faster, which is a lot.

Now the node size can explain some of it, by default my implementation uses B=64 compared to the std implementation B=6, and when I change to B=6 my implementation takes 0.06 seconds to do the clone test, i.e. twice as long, but that still leaves a discrepancy of 4 times.

I have tried looking at the code for the std implementation, but wasn't able to understand it in detail yet. But anyway, can you figure out why it is so much slower?

[geebee22]

Trying to guess the answer, my guess is that instead of doing something simple, like making a copy of the leaf nodes in a fairly tight loop, the std implementation is doing something more complicated. But why?

My cloning inner loop looks like this:

    pub fn clone<A: Tuning>(&self, alloc: &A) -> Self
    where
        K: Clone,
        V: Clone,
    {
        let mut c = Self::new();
        c.set_alloc(self.alloc as usize, alloc);
        let mut n = self.len;
        if n > 0 {
            unsafe {
                let (mut sk, mut sv) = self.ixp(0);
                let (mut dk, mut dv) = c.ixmp(0);
                loop {
                    let k = (*sk).clone();
                    let v = (*sv).clone();
                    dk.write(k);
                    dv.write(v);
                    c.len += 1;
                    n -= 1;
                    if n == 0 {
                        break;
                    }
                    sk = sk.add(1);
                    sv = sv.add(1);
                    dk = dk.add(1);
                    dv = dv.add(1);
                }
            }
        }
        c
    }

from pstd 0.1.11 - Docs.rs