Vec::splice() has noticeable overhead for some use cases

[adrian17]

As far as I know, Vec::splice() is the only way to extend the Vec from a slice in an arbitrary location. However, being a fairly universal api makes it slower than a hypothetical dedicated insert_from_slice could be.

In fact, according to cargo bench, for small vectors (let's say under 10) and number of elements to insert, it can be faster to insert them in a loop:

    for i in 0..5 { data.insert(3, 77); }

than to call splice:

    let new = [77; 5];
    data.splice(3..3, new.iter().copied());

splice also seems to optimize badly in presence of constants. For example, looking at Godbolt, the optimizer can't seem to optimize

    let tab = [77; 1];
    vec.splice(5..6, tab.iter().cloned());

as good as

    vec[5] = 77;

Or

    let tab = [77; 1];
    vec.splice(5..5, tab.iter().cloned());

as good as

    vec.insert(5, 77);

It'd be nice if the function had lower overhead for small vectors/slices. Or maybe if another specialized method insert_from_slice(idx, slice) was added that avoids all overhead for this particular use case.

[the8472]

For example, looking at Godbolt, the optimizer can't seem to optimize

Maybe add links? That'll avoid redundant work of reproducing your findings.

[lolbinarycat]

are we looking at the same function? Vec::splice does not mutate the vec, it creates a lazy iterator.

it does seem like we could use an insert_slice, as the only stable way i can think of doing this efficiently involves reserve, spare_capacity_mut, set_len and some slightly sketchy memcpys (which should be safe, because memcpy cannot fail, but there would be some weird intermediate states where there's several copies of the same value, before they're overwritten)

I could write an ACP for this, if you want.

[kzdnk]

Some of those calls to Vec::splice are not inserting anything: 5..5 and 3..3 are empty ranges, only 5..6 contains a single 5.

Nevermind, it looks like splice will insert even if the range is empty.

[kzdnk]

are we looking at the same function? Vec::splice does not mutate the vec, it creates a lazy iterator.

It creates an iterator that on drop will replace the items in the vec.

it does seem like we could use an insert_slice, as the only stable way i can think of doing this efficiently involves reserve, spare_capacity_mut, set_len and some slightly sketchy memcpys (which should be safe, because memcpy cannot fail, but there would be some weird intermediate states where there's several copies of the same value, before they're overwritten)

Will it call drop on the elements in the Vec, though? I think your way would work only for T: Copy. If we had specialization we could do

impl<I: Iterator, A: Allocator> Drop for Splice<'_, I, A> 
    where I::Item: Copy 
{ ... } 
`