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

**URL:** <https://internals.rust-lang.org/t/moving-arrayvec-has-complexity-o-capacity-instead-of-o-len/6749>\
**Category:** Uncategorized\
**Created:** [February 12, 2018, 11:37am UTC](https://internals.rust-lang.org/t/moving-arrayvec-has-complexity-o-capacity-instead-of-o-len/6749 "2018-02-12T11:37:48Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![gnzlbg](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/gnzlbg/32/3858_2.png) [@gnzlbg](https://internals.rust-lang.org/u/gnzlbg)\
**Post date:** [February 12, 2018, 11:37am UTC](https://internals.rust-lang.org/t/moving-arrayvec-has-complexity-o-capacity-instead-of-o-len/6749/1 "2018-02-12T11:37:48Z")

</div>

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

> <https://github.com/bluss/arrayvec/issues/94#issuecomment-363513858>
>
> The title says it all: moving an \`ArrayVec\` has complexity \`O(capacity())\` inste…ad of \`O(len())\`. This is pretty bad.
> 
> It is trivial to construct examples that show a massive slowdown (100x's slower) with respect to C++'s \`boost::container::static\_vector\`.
> 
> For example, moving an empty \`ArrayVec\<\[u64; 512\]\>\` involves \`memcpy\`ing 4104 bytes instead of just 8 bytes (the size of \`len\`). That's 513x more expensive than C++'s \`boost::container::static\_vector\`.

> 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.

---

<div class="post-metadata">

**Author:** ![scottmcm](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/scottmcm/32/2355_2.png) [@scottmcm](https://internals.rust-lang.org/u/scottmcm)\
**Post date:** [February 13, 2018, 7:27am UTC](https://internals.rust-lang.org/t/moving-arrayvec-has-complexity-o-capacity-instead-of-o-len/6749/2 "2018-02-13T07:27:48Z")

</div>

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:

```rust
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.)

---

<div class="post-metadata">

**Author:** ![newpavlov](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/newpavlov/32/3290_2.png) [@newpavlov](https://internals.rust-lang.org/u/newpavlov)\
**Post date:** [February 13, 2018, 9:55am UTC](https://internals.rust-lang.org/t/moving-arrayvec-has-complexity-o-capacity-instead-of-o-len/6749/3 "2018-02-13T09:55:47Z")

</div>

I guess it’s an additional use-case for move constructors in one form or another. One of the previous [discussions](https://internals.rust-lang.org/t/idea-on-movable-self-referential-structs/6694).

---

<div class="post-metadata">

**Author:** ![gnzlbg](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/gnzlbg/32/3858_2.png) [@gnzlbg](https://internals.rust-lang.org/u/gnzlbg)\
**Post date:** [February 13, 2018, 11:31am UTC](https://internals.rust-lang.org/t/moving-arrayvec-has-complexity-o-capacity-instead-of-o-len/6749/4 "2018-02-13T11:31:23Z")

</div>

@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" `memcpy`s 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.

---

<div class="post-metadata">

**Author:** ![hanna-kruppe](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/hanna-kruppe/32/6540_2.png) [@hanna-kruppe](https://internals.rust-lang.org/u/hanna-kruppe)\
**Post date:** [February 13, 2018, 12:02pm UTC](https://internals.rust-lang.org/t/moving-arrayvec-has-complexity-o-capacity-instead-of-o-len/6749/5 "2018-02-13T12:02:26Z")

</div>

> [@gnzlbg](#):
>
> 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 `memcpy`ing all the bytes remains valid, so it's slightly less of a backwards compatibility problem (but suddenly throwing from moves is also a problem).

---

<div class="post-metadata">

**Author:** ![cuviper](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/cuviper/32/1897_2.png) [@cuviper](https://internals.rust-lang.org/u/cuviper)\
**Post date:** [February 14, 2018, 5:31pm UTC](https://internals.rust-lang.org/t/moving-arrayvec-has-complexity-o-capacity-instead-of-o-len/6749/6 "2018-02-14T17:31:38Z")

</div>

Maybe special cases could be implemented using attributes?

```rust
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…)

---

<div class="post-metadata">

**Author:** ![gnzlbg](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/gnzlbg/32/3858_2.png) [@gnzlbg](https://internals.rust-lang.org/u/gnzlbg)\
**Post date:** [March 14, 2018, 8:22am UTC](https://internals.rust-lang.org/t/moving-arrayvec-has-complexity-o-capacity-instead-of-o-len/6749/7 "2018-03-14T08:22:19Z")

</div>

@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 @hanna-kruppe 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.

---

<div class="post-metadata">

**Author:** ![system](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/system/32/14092_2.png) [@system](https://internals.rust-lang.org/u/system)\
**Post date:** [March 25, 2019, 8:29am UTC](https://internals.rust-lang.org/t/moving-arrayvec-has-complexity-o-capacity-instead-of-o-len/6749/8 "2019-03-25T08:29:39Z")

</div>

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