Vec::resize_left API

libs
#1

Currently there's not really any safe way to resize a Vec from the left, and we'd rather not roll our own unsafe for it.

So what are the use-cases for this? well:

  1. Left-pad.
  2. Emulation.

The left-pad case is an interesting one, but personally the emulation case is way more useful. And if the allocator could be adjusted to natively support it, that'd mean even more performance where it matters. But even without allocator support, at least the compiler/stdlib would be able to do optimized unsafe code to handle it, while providing a safe API.

#2

For reference, I think the most efficient way to do this currently is:

vec.splice(..0, repeat(x).take(n));
5 Likes
#3

I don't think any allocator supports this - and since even in C/C++ nobody asked for it I doubt they would add support for it. Even a realloc which intends to extend to the right might often be a completely new allocation and copying things.

Therefore I guess having such an API would be mainly a convenience addition.

I actually think can get the best performance by just allocating a new vector of the final size, and moving elements over. Along:

let mut new = Vec::with_capacity(old.len() + 1);
new.push(left); // Or multiple elements
new.add(old);

I haven't looked at the implementation of the splice method that @mbrubeck mentioned - but I would doubt it's more efficient: It takes an iterator as an argument - so it won't know upfront how big the final collection would be and therefore might trigger additional reallocations.

#4

As usual there's an obvious "can you just use VecDeque instead?" question here.

mbrubeck's suggestion of splice is probably best here. Of course there are also manual versions of that with the same Big-O, like just append the extra stuff to the end of the Vec and rotate them to the front:

fn prepend<T: Clone>(v: &mut Vec<T>, x: T, n: usize) {
    v.resize(v.len() + n, x);
    v.rotate_right(n);
}

fn main() {
    let mut v = vec![1, 2, 3];
    prepend(&mut v, 0, 2);
    assert_eq!(v, [0, 0, 1, 2, 3])
}

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=acdb11f18e3e2c9dba0343182ea9b424

That's not a problem for something like repeat(x).take(n), since that will have an exact size_hint, which will be used to preallocate the appropriate space.

Not that there aren't things to worry about, though. The two that jump to mind:

  • it needs to be panic-safe, since Iterator::next might panic.
  • it can't just ptr::copy_nonoverlapping (though it could with specialization, which Vec uses fairly heavily)
2 Likes
#5

This would fail endianness. No good way to use it.

#6

Do we still not have an allocator that allocates like it's an ext4 filesystem and removes process and thread stack size limits while at it?

#7

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.