Add Vec::insert_slice_at to insert the content of a slice at an arbitrary index

#1

Relatively often you need to insert a slice of data (usually bytes) into a vec at some arbitrary index. Sadly std doesn't have any optimized and short method to do exactly that. Currently you will have to write:

vec.reserve(slice.len()); // optional, but increases the performance
let mut v = vec.split_off(index);
vec.extend_from_slice(&slice);
vec.append(&mut v);

This solution isn't slow, but not too nice to use and could be faster. I'd propose adding a method which can insert a slice of Copyable elements into a vec. I have come up with this code to do exactly that.

According to my benchmarks the custom (unsafe) solution is about 50% faster. Take my benchmarks with a grain of salt though, they aren't perfect.

What do you think about that? Are there better solutions or names?

#2

I think Vec::splice is the method for this, but it still uses a temporary allocation for the tail. Maybe it could internally use the iterator's size_hint to move the tail out an appropriate amount? (With appropriate fallbacks, unless this is only for TrustedLen.)

There might also be room for a method that inserts slices instead of iterators, but I think the splice could be improved to get closer to what you want already.

#3

Vec::splice will do it without extra allocations, as long as the replacement has a good size hint already, and that's no problem when it's the slice iterator.

That said, a solution with rotate is also fun:

fn main() {
    let mut vec = vec![1; 24];
    let slice = [0; 8];
    let index = 3;
    
    // 1
    vec.reserve(slice.len()); // optional, but increases the performance
    let mut v = vec.split_off(index);
    vec.extend_from_slice(&slice);
    vec.append(&mut v);
    
    // 2
    let tail = vec.len() - index;
    vec.extend(&slice);
    vec[index..].rotate_left(tail);
    
    // 3
    vec.splice(index..index, slice.iter().copied());
    
    println!("{:?}", vec);
}
1 Like
#4

I considered those solutions, but they sadly are slower than 'split_off + extend + append' and 'the unsafe one'. 'splice' takes almost 10x as much time as 'the unsafe one'. 'extend and rotate' is elegant, but sadly takes 2x as long as 'the unsafe one'

1 Like
#5

That's interesting. 10x slower in release compile? We need to profile that, then.

2 Likes
#6

Feels like we ought to be able to do something smarter here, like create a size_hint.0 hole, fill that, and then put the rest on the end that we rotate into the correct place on drop, or something.

2 Likes