Vec::clone_from is slow

[apasel422]

In the process of implementing #28481 for BinaryHeap, I noticed that Vec::clone_from is often slower than Vec::clone:

#![cfg_attr(test, feature(test))]

#[cfg(test)]
extern crate test;

macro_rules! bench {
    ($name:ident, $src_len:expr, $dst_len:expr) => {
        mod $name {
            #[bench]
            fn clone_from(b: &mut ::test::Bencher) {
                let src: Vec<i32> = (0..$src_len).collect();
                let mut dst: Vec<i32> = (0..$dst_len).collect();

                b.iter(|| {
                    dst.clone_from(&src);
                    unsafe { dst.set_len($dst_len as usize); }
                    ::test::black_box(&mut dst);
                });
            }

            #[bench]
            fn clone(b: &mut ::test::Bencher) {
                let src: Vec<i32> = (0..$src_len).collect();
                let mut dst: Vec<i32> = (0..$dst_len).collect();

                b.iter(|| {
                    dst = src.clone();
                    unsafe { dst.set_len($dst_len as usize); }
                    ::test::black_box(&mut dst);
                });
            }
        }
    }
}

mod eq {
    bench! { src_100_dst_100, 100, 100 }
    bench! { src_1000_dst_1000, 1000, 1000 }
}

mod src_bigger {
    bench! { src_100_dst_10, 100, 10 }
    bench! { src_1000_dst_100, 1000, 100 }
}

mod dst_bigger {
    bench! { src_10_dst_100, 10, 100 }
    bench! { src_100_dst_1000, 100, 1000 }
}

Output with rustc 1.5.0-nightly (b2f379cdc 2015-09-23):

test dst_bigger::src_100_dst_1000::clone      ... bench:          34 ns/iter (+/- 1)
test dst_bigger::src_100_dst_1000::clone_from ... bench:          75 ns/iter (+/- 3)

test dst_bigger::src_10_dst_100::clone        ... bench:          25 ns/iter (+/- 0)
test dst_bigger::src_10_dst_100::clone_from   ... bench:           9 ns/iter (+/- 1)

test eq::src_1000_dst_1000::clone             ... bench:         105 ns/iter (+/- 2)
test eq::src_1000_dst_1000::clone_from        ... bench:         593 ns/iter (+/- 21)

test eq::src_100_dst_100::clone               ... bench:          34 ns/iter (+/- 1)
test eq::src_100_dst_100::clone_from          ... bench:          75 ns/iter (+/- 1)

test src_bigger::src_1000_dst_100::clone      ... bench:         103 ns/iter (+/- 5)
test src_bigger::src_1000_dst_100::clone_from ... bench:         148 ns/iter (+/- 5)

test src_bigger::src_100_dst_10::clone        ... bench:          34 ns/iter (+/- 1)
test src_bigger::src_100_dst_10::clone_from   ... bench:          20 ns/iter (+/- 0)

These benchmarks are probably naive (and different sizes may have a more meaningful effect), but it seems to warrant investigation.

[Veedrac]

Replacing the implementation of clone_from with just

self.truncate(0);
self.push_all(&other);

fixes this for me, and clone_from becomes faster. I assume it was the zip causing problems.

[bluss]

That makes clone_from shallow and not recursive. I can totally see zip causing problems. Maybe some zip optimizations can help?

[dotdash]

I guess we should keep the reuse of the current values, might be faster for types that need to be dropped because the length can be kept fixed instead of shrinking first and regrowing later. Just replace the zip with a faster loop.

[Veedrac]

The best non-shallow clone I've managed is

// Manually inlining this prevents LLVM turning it into a memcpy
unsafe fn clone_from_existing<T: Clone>(dst: &mut Vec<T>, src: &[T]) {
    for i in 0..dst.len() {
        dst.get_unchecked_mut(i).clone_from(src.get_unchecked(i));
    }
}

self.truncate(other.len());

unsafe { clone_from_existing(self, &other); }

let len = self.len();
if len != other.len() {
    self.push_all(&other[len..]);
}

Comparing it to self.truncate(0); self.push_all(&other);: For the given benchmarks, the above generally wins a tiny bit (<5%), except for the last two benchmarks where the simpler truncate-push version wins by 10-25%.

[apasel422]

Using iterate_slices_counted_2 from @bluss's zip optimizations link above, I have clone_from winning in each scenario. I will open a PR shortly.

[Veedrac]

@apasel422 My suggestion prior is giving me better times.

Yours:

test dst_bigger::src_100_dst_1000::clone_from ... bench:         112 ns/iter (+/- 1)
test dst_bigger::src_10_dst_100::clone_from   ... bench:          26 ns/iter (+/- 0)
test eq::src_1000_dst_1000::clone_from        ... bench:         921 ns/iter (+/- 15)
test eq::src_100_dst_100::clone_from          ... bench:         112 ns/iter (+/- 3)
test src_bigger::src_1000_dst_100::clone_from ... bench:         452 ns/iter (+/- 10)
test src_bigger::src_100_dst_10::clone_from   ... bench:          89 ns/iter (+/- 0)

Mine:

test dst_bigger::src_100_dst_1000::clone_from ... bench:          65 ns/iter (+/- 1)
test dst_bigger::src_10_dst_100::clone_from   ... bench:          23 ns/iter (+/- 0)
test eq::src_1000_dst_1000::clone_from        ... bench:         373 ns/iter (+/- 4)
test eq::src_100_dst_100::clone_from          ... bench:          66 ns/iter (+/- 1)
test src_bigger::src_1000_dst_100::clone_from ... bench:         424 ns/iter (+/- 7)
test src_bigger::src_100_dst_10::clone_from   ... bench:          91 ns/iter (+/- 14)

Clone:

test dst_bigger::src_100_dst_1000::clone      ... bench:         121 ns/iter (+/- 3)
test dst_bigger::src_10_dst_100::clone        ... bench:          79 ns/iter (+/- 3)
test eq::src_1000_dst_1000::clone             ... bench:         429 ns/iter (+/- 7)
test eq::src_100_dst_100::clone               ... bench:         121 ns/iter (+/- 2)
test src_bigger::src_1000_dst_100::clone      ... bench:         429 ns/iter (+/- 4)
test src_bigger::src_100_dst_10::clone        ... bench:         121 ns/iter (+/- 1)

And, for what it's worth, self.truncate(0); self.push_all(&other);

test dst_bigger::src_100_dst_1000::clone_from ... bench:          68 ns/iter (+/- 2)
test dst_bigger::src_10_dst_100::clone_from   ... bench:          26 ns/iter (+/- 0)
test eq::src_1000_dst_1000::clone_from        ... bench:         376 ns/iter (+/- 6)
test eq::src_100_dst_100::clone_from          ... bench:          68 ns/iter (+/- 4)
test src_bigger::src_1000_dst_100::clone_from ... bench:         377 ns/iter (+/- 7)
test src_bigger::src_100_dst_10::clone_from   ... bench:          68 ns/iter (+/- 1)

I'm not sure why the discrepancy, especially for src_1000_dst_1000.

[apasel422]

@Veedrac Hmm. The call to cmp::min in mine appears to be unnecessary. Let me investigate.