Extend_from_slice efficiency

1

I have some piece of code which needs to add part of a vector to another vector.

I use extend_from_slice for that, which works fine technically, see example code at the end.

The question is: Is the code performant?

To me it looks like internally this is resolved to an iterator which does a memcpy for each element.

I was hoping it would do a memcpy for all elements at once, so instead of
self.reserve(lower.saturating_add(1)); for each element
self.reserve(lower.saturating_add(10000));
Besides doing it in multiple steps this could also result in multiple re-allocations of the memory for the vector. To me it looks I better to a capacity extension before calling extend. I was hoping the calles subroute does this for me.

I believe the elements of the vector (or array) are always stored consecutively in heap(or stack), so it would be possible to copy in one step, or not? (Clone could be different)

Best,
Gunnar

    // mod.rs: Rust code which does the work
    impl<T, A: Allocator> Vec<T, A> {
    // leaf method to which various SpecFrom/SpecExtend implementations delegate when
    // they have no further optimizations to apply
    #[cfg(not(no_global_oom_handling))]
    fn extend_desugared<I: Iterator<Item = T>>(&mut self, mut iterator: I) {
        // This is the case for a general iterator.
        //
        // This function should be the moral equivalent of:
        //
        //      for item in iterator {
        //          self.push(item);
        //      }
        while let Some(element) = iterator.next() {
            let len = self.len();
            if len == self.capacity() {
                let (lower, _) = iterator.size_hint();
                self.reserve(lower.saturating_add(1));
            }
            unsafe {
                ptr::write(self.as_mut_ptr().add(len), element);
                // Since next() executes user code which can panic we have to bump the length
                // after each step.
                // NB can't overflow since we would have had to alloc the address space
                self.set_len(len + 1);
            }
        }
    }

// Sample code
#[derive(Debug, Clone, Copy, PartialEq)]
struct Data {
    id: usize,
    x: u16,
    y: u16,
    color: (u8, u8, u8),
}

impl Data    {
    fn new(id: usize) -> Self {
        Self {
            id,
            x: id as u16,
            y: id as u16,
            color: (0,0,0),
        }
    }
}


fn main() {
    let size = 10_000;
    let master: Vec<Data> = (0..size).into_iter().map(|it| Data::new(it)).collect::<Vec<_>>();
    let master_check = master.clone();
    let mut target: Vec<Data> = Vec::new();

    let start = size / 2;
    target.extend_from_slice(&master[start..]);

    assert_eq!(master, master_check);
    assert_eq!(target, master_check[start..]);
}
2

I believe Vec::extend() (and extend_from_slice()) is implemented using the experimental specialization feature:

when extend from a slice of Copy type, it uses the specialized implementation, which just forwards to the non-public method append_elements():

and append_elements() is implemented just like that:

6 Likes
3

It's typical for Rust to expand to code that looks naive, but is designed to optimize well later to remove the overhead.

You can check the optimized result:

2 Likes
4

Also, honorable mention to https://godbolt.org/ which is great to explore if such stuff actually gets optimized correctly

5

@nerditation's mention of the specialization for slices is your specific answer here.

But note also that for anything which is TrustedIter, it ends up here;

Which reserves exactly the correct amount up-front because the iterator made an unsafe promise that it's accurate.

(Vec needs to be sound even if you write, in safe code, an Iterator that lies about how many elements it'll have, so the most general case does need multiple reserves.)

1 Like
6

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.