Is Vec::splice() efficient when the length doesn't change?

Question

When you use Vec::splice() to replace part of a Vec, is it smart enough to specially handle the case where the replacement is the same length as the chunk it is replacing, or should I handle that myself?

Is there any point doing this, or is array.splice() smart enough to do that anyway?

fn example(array: Vec<u64>, replacement: Vec<u64>, range: std::ops::Range<usize>) {
    if (replacement.len() == range.len()) {
        for i in range {
            array[i] = replacement[i];
        }
    } else {
        array.splice(range, replacement);
    }
}

Answer 1

I gave in and read the code. It is smart enough to handle that case. Here's how the code works:

1. You call .splice(), it creates a Splice object which includes a Drain iterator for the replacement range:

   pub fn splice<R, I>(&mut self, range: R, replace_with: I) -> Splice<'_, I::IntoIter>
   where
       R: RangeBounds<usize>,
       I: IntoIterator<Item = T>,
   {
       Splice { drain: self.drain(range), replace_with: replace_with.into_iter() }
   }
   

2. The Splice is dropped, which calls its drop() implementation.

   impl<I: Iterator> Drop for Splice<'_, I> {
       fn drop(&mut self) {
   

   The first thing it does is drop all of the elements that are being replaced.

           self.drain.by_ref().for_each(drop);
   

   Then it checks if the replacement is at the end of the Vec, if so just extend it and return.

           unsafe {
               if self.drain.tail_len == 0 {
                   self.drain.vec.as_mut().extend(self.replace_with.by_ref());
                   return;
               }
   

   Next it calls a helper fill() function, to replace the removed elements with as many as it can from the replacement iterator (replace_with). fill() returns false if it didn't fill the whole of the replacement range, in which case it returns (I'm not sure where the tail is moved in this case though?)

               // First fill the range left by drain().
               if !self.drain.fill(&mut self.replace_with) {
                   return;
               }
   

   Now replace_with may have 0 elements left (in which case we are done), or it may have more elements (in which case the tail needs to be moved back by that amount). This is what happens next.

               // There may be more elements. Use the lower bound as an estimate.
               // FIXME: Is the upper bound a better guess? Or something else?
               let (lower_bound, _upper_bound) = self.replace_with.size_hint();
               if lower_bound > 0 {
                   self.drain.move_tail(lower_bound);
                   if !self.drain.fill(&mut self.replace_with) {
                       return;
                   }
               }
   

   You might expect if lower_bound == 0 { return; }, but lower_bound is only an estimate so it tries with that first and if that fails it copies the replacement into a temporary vector, so it can know the full length.

               // Collect any remaining elements.
               // This is a zero-length vector which does not allocate if `lower_bound` was exact.
               let mut collected = self.replace_with.by_ref().collect::<Vec<I::Item>>().into_iter();
               // Now we have an exact count.
               if collected.len() > 0 {
                   self.drain.move_tail(collected.len());
                   let filled = self.drain.fill(&mut collected);
                   debug_assert!(filled);
                   debug_assert_eq!(collected.len(), 0);
               }
   

   The point is that if replace_with is empty, because the replacement size was the same as the range, then all of those operations are fairly simple nop-ish things.

   The final bit drops the Drain iterator itself, which will move the tail.. possibly again? I don't know I kind of lost track here. Anyway if the length is the same it definitely won't move it.

           }
           // Let `Drain::drop` move the tail back if necessary and restore `vec.len`.
       }
   }
   

Answer 2

Per the docs and another answer, splice is "smart" (optimal) in a few cases, including the case where "the lower bound of [replace_with]'s size_hint() is exact."

In your example function, the lower bound of size_hint() on replacement.iter() is exact, so one memory move should be performed.