Эффективна ли Vec::splice(), когда длина не меняется?

Question

Когда вы используете Vec::splice() заменить часть Vec, достаточно ли он умен, чтобы специально обрабатывать случай, когда длина заменяемого фрагмента равна длине заменяемого фрагмента, или я должен справиться с этим самостоятельно?

Есть ли смысл это делать, или array.splice() в любом случае достаточно умен, чтобы это сделать?

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

Я сдался и прочитал код. Это является достаточно умен, чтобы справиться с этим делом. Вот как работает код:

1. Ты звонишь .splice(), это создает Splice объект, который включает Drain итератор для диапазона замены:

   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. В Splice отбрасывается, что вызывает drop() реализация.

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

   Первое, что он делает - это отбрасывает все заменяемые элементы.

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

   Затем он проверяет, находится ли замена в конце Vec, в таком случае просто продлите его и верните.

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

   Затем он вызывает помощника fill() функция, чтобы заменить удаленные элементы как можно большим количеством из замещающего итератора (replace_with). fill() возвращается false если он не заполнил весь диапазон замены, и в этом случае он вернется (хотя я не уверен, куда перемещается хвост в этом случае?)

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

   Сейчас же replace_withможет остаться 0 элементов (в этом случае мы закончили) или может быть больше элементов (в этом случае хвост нужно отодвинуть назад на это количество). Вот что происходит дальше.

               // 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;
                   }
               }
   

   Вы могли ожидать if lower_bound == 0 { return; }, но lower_bound это только оценка, поэтому он пытается сначала использовать это, и если это не удается, он копирует замену во временный вектор, чтобы он мог знать полную длину.

               // 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);
               }
   

   Дело в том, что если replace_with является пустым, так как размер замены был таким же, как диапазон, то все эти операции довольно простым NOP-ишем вещь.

   Последний бит отбрасывает Drainсам итератор, который сдвинет хвост.. возможно опять? Я не знаю, что я потерялся здесь. В любом случае, если длина такая же, он точно не сдвинется.

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

Answer 2

Согласно документам и другому ответу,splice является "умным" (оптимальным) в нескольких случаях, включая случай, когда "нижняя граница [replace_with] size_hint() точно."

В вашем примере функции нижняя граница size_hint() на replacement.iter() точно, поэтому нужно выполнить один ход памяти.

Answer 3

Насколько я могу судить, Splice::drop это то, что делает большую часть работы, и это требует fill, который, в случае совпадения длин, будет проходить через replace_with, и вернуться true но оставь replace_with пустой, так что lower_bound равно 0 и collected.len() равно 0.

Drain::drop потом бежит. Цикл не должен делать ничего, так какSplice::drop уже повторил его, а затем DropGuard::drop, при котором может потребоваться смещение элементов, не нужно перемещать / копировать элементы, поскольку в результате совпадения длин tail должен равняться start.