Moving `ArrayVec` has complexity O(capacity()) instead of O(len())

[gnzlbg]

Maybe something can be done at the language level to improve on this.

Issue: Moving `ArrayVec`s has complexity O(capacity()) instead of O(len())

For example, moving an empty ArrayVec<[u64; 512]> involves memcpying 4104 bytes instead of just 8 bytes (the size of len).

OTOH C++'s boost::container::static_vector has O(len()) complexity.

[scottmcm]

Hmm, this seems more plausible than most similar discussions since it’s an optimization over moving, not a requirement that something other than memcpy be done. (So a Vec<ArrayVec<>> could still just realloc its buffer, for example.)

Strawman with terrible idents:

unsafe trait OnlyNeedToMoveUpTo {
    fn only_need_to_move_up_to(&self) -> *const ();
}
default unsafe impl<T> OnlyNeedToMoveUpTo for T {
    fn only_need_to_move_up_to(&self) -> *const () {
        unsafe { (self as *const Self).offset(1) as *const () }
    }
}
unsafe impl<T> OnlyNeedToMoveUpTo for ArrayVec<T> {
    fn only_need_to_move_up_to(&self) -> *const () {
        // assuming len is before the storage
        unsafe { self.as_ptr().add(self.len()) as _ }
    }
}

Then the compiler could emit the memcpy for that length instead of the type’s full size, and in the normal case it would still be a const, so the same codegen would happen.

(Other options and variations include returning ranges instead of just prefixes, using lengths instead of pointers, deciding this is a terrible idea, making it not take self so people can’t import this on everything, having it required to be a const fn, and a whole bunch of other things I’m sure I’ve forgotten.)

[newpavlov]

I guess it’s an additional use-case for move constructors in one form or another. One of the previous discussions.

[gnzlbg]

@scottmcm

Hmm, this seems more plausible than most similar discussions since it’s an optimization over moving, not a requirement that something other than memcpy be done.

I thought about this for a while but ended up concluding that even if only “some” memcpys must be done, the logic required for this might still be pretty close to full move constructors.

Example: A data-structure similar to ArrayVec, but with holes for O(1) erase

Suppose I have a similar data-structure to ArrayVec but with holes to achieve O(1) erase. That is, it stores a bitset with one bit per element, where if the bit is true the element is alive, and when the bit is false the element is dead.

On move, it just wants to move the elements that are alive. Any kind of “range”-based approach will fail here. We need to be able to explicitly choose which elements to move. So at least it would need to return a range-of-ranges to select which parts of its representation need to be moved. Returning this range-of-ranges shall not allocate memory, and this range-of-ranges can be constructed using arbitrary logic. At this point, move constructors start looking like an easier solution than “scoped” moves.

An alternative could be to be able to pass the compiler a closure that returns whether a byte must be moved or not, but this still can do pretty much arbitrary code execution while moving.

[rkruppe]

I thought about this for a while but ended up concluding that even if only “some” memcpys must be done, the logic required for this might still be pretty close to full move constructors.

Yeah. Any solution that performs any computations at run time shares the problem that moving can suddently throw – unless specific and rather drastic precautions are taken (such as terminating on panics). And since those counter measures are not really specific to this approach and could just as well be applied to “full” move constructors…

The one advantage of restricting the logic to picking out a subset of bytes to memcpy, and do nothing else, is that simply memcpying all the bytes remains valid, so it’s slightly less of a backwards compatibility problem (but suddenly throwing from moves is also a problem).

[cuviper]

Maybe special cases could be implemented using attributes?

pub struct ArrayVec<A: Array> {
    #[partial_move(size_of = "A::Item", count = "len")]
    xs: NoDrop<A>,
    len: A::Index,
}

That would have to be an unsafe attribute somehow, and decide what to do with overlong calculations – just saturate? But at least the compiler would still control the entire move.

(This is so ugly and niche that I doubt it would ever happen…)

[gnzlbg]

@cuviper That helps for ArrayVec, but not for ArrayVecWithHoles where the array can have holes indicated bit a bit set/unset and you only want to move the elements that are actually alive.

I agree with @rkruppe here, the general solution to this problem is move constructors.

A different approach could be to implement !Move for ArrayVec and provide a function that moves the elements of the ArrayVec out of it into a new ArrayVec. At the end of the day this is just a poor’s man move constructor, but just worse.

[system]

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